散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
上文解释了散列表的含义。通过哈希函数f(key)找到在表中的位置。aKey和bKey不相等时，f(aKey) 可能等于 f(bKey)。这种现象称为碰撞。 目前解决该问题有两种办法
- 开放寻址法
- 拉链法（又称分离链表法）
开放寻址法 开放寻址法 Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列
从而有三种取法：
- di=1,2,3，…，m-1，称线性探测再散列
- di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列
- di=伪随机数序列，称伪随机探测再散列
Android 源码的 ThreadLocal 就是用的该方法解决冲突。 ThreadLocal使用的第一种线性探测方法，
f(key) = key & (len-1))
key += 0x61c88647
复制代码int temp = 0;
for (int i = 0; i < 16; i++) {
int k = temp & 15;
Log.d("tag", " " + k);
temp += HASH_INCREMENT;
}
D/tag: 0
D/tag: 7
D/tag: 14
D/tag: 5
D/tag: 12
D/tag: 3
D/tag: 10
D/tag: 1
D/tag: 8
D/tag: 15
D/tag: 6
D/tag: 13
D/tag: 4
D/tag: 11
D/tag: 2
D/tag: 9
复制代码可以看到很分散。
当冲突时，i+1向后继续寻找位置，直到不为空的位置或无效位置。 同时当表即将满员后，会进行resize表大小。
图片来自 http://alexyyek.github.io/2014/12/14/hashCollapse/
拉链法
图片来自 http://faculty.cs.niu.edu/~freedman/340/340notes/340hash.htm
可以看到拉链法会找到key所对应的链表，通过链表链接f(key)相同的元素。