散列表也叫哈希表，是根据键值对 (key，value) 进行访问的一种数据结构。他把一对 (key，value) 通过 key 的哈希值来映射到数组中，也就是说，它通过把关键值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
举个例子，为了查找某个好友的微信号，你可以按照好友首字母顺序查找，在首字母为 W 的表中查找 王 姓的好友，显然比直接查找要快得多。这里使用人名作为关键字， 取首字母 是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
冲突处理
由于关键字的函数映射关系，散列表难免会出现 Hash 值冲突，也就是不同的 key 值通过散列函数可以映射到数组中的同一个位置，这就是哈希冲突。哈希冲突不一定是哈希值冲突，也有可能是函数映射的结果出现冲突。比如一个哈希值是 654321 ，另一个哈希值是 978321 ，而哈希函数是取他们的后 3 位，所以他们通过哈希函数计算结果都是 321 。
HashMap
散列表大家最熟悉的可能就是 HashMap 了， HashMap 实际上是数组加链表的一种数据结构，当出现哈希冲突的时候，他会以链表的形式存在，如下图所示。
HashMap 的哈希映射函数非常简单，就是用数组的长度减 1 然后和哈希值进行 与运算， (n - 1) & hash ，这里 n 是数组的长度，也是 2 的幂次方。这个运算非常巧妙，我们来介绍一下他是怎么把一个数变成不小于他的 2 的幂次方的。比如传入 17 会返回 32 ，传入 32 也会返回 32 ，传入 33 会返回 64 ，他返回的都是 2 的幂次方，并且不能小于传入的值。第一种方式，通过 while 循环，这个比较简单。
public static int tableSizeFor(int initialCapacity) {
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
return capacity;
}
第二种方式，这个相当于把一个数的二进制中最左边的 1 往右铺开，最后在加上 1 就变成不小于它的 2 的幂次方，如下图所示。这里最开始的时候减 1 ，是为了防止本来就是 2 的幂次方，通过运算会放大一倍，比如 32 ，在开始运算的时候如果不减 1 ，最后就会变成 64 。
int tableSizeFor(int i) {
i--;
i |= i >>> 1;
i |= i >>> 2;
i |= i >>> 4;
i |= i >>> 8;
i |= i >>> 16;
return i + 1;
}
第三种方式，首先判断如果就是 2 的幂次方，直接返回， 2 的幂次方在二进制中只有一个 1 ，其他位都是 0 。否则也是把最左边的 1 往右边铺开，然后只保留最左边的 1 ，其他的都减掉，最后在往左移一位就行了。
int tableSizeFor(int i) {
if ((i & (i - 1)) == 0)
return i;
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return (i - (i >>> 1)) << 1;
}
ArrayMap
除了 HashMap 以外，还有一个类是 ArrayMap ，他是纯数组的一种数据结构，有两个数组，一个存放哈希值，一个存放 key 和 value ，其中存放 key 和 value 的数组长度是存放哈希值数组长度的 2 倍，并且存放哈希值的数组是有序的，查找的时候是通过二分法进行查找。当出现哈希冲突的时候，说明哈希映射是一样的，他们在哈希数组中是挨着的，查找的时候如果有相同的哈希映射但 key 值不一样，还需要往两边进行查找，如下图所示。
SparseArray
还有一个和 ArrayMap 非常相似的数据结构 SparseArray ， SparseArray 也是有两个数组，和 ArrayMap 不同的是这两个数组长度都是一样的，一个数组存放的是 key 值，一个数组存放的是 value 值，大家可能会有疑惑，有没有存放哈希值的，其实这里的 key 值可以把它看做是哈希值，因为这里的 key 值必须是 int 类型，并且存放 key 值的数组也是有序的，查找的时候也是通过二分法进行查找，如下图所示。
ThreadLocalMap
这个就更简单了，首先根据哈希值找到需要存放的位置，如果该位置为空就把数据存进去，如果该位置不为空，就往该位置后面查找空闲的位置，如果有空闲的就存进去，如果没空闲的就一直往后找。
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
参考：
HashMap.java
ArrayMap.java
SparseArray.java
SparseIntArray.java
ThreadLocal.java
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
