Hash表
如Java中的HashMap等，一种(K,V)的数据存储结构。HashMap底层使用的是数组+链表，主要是数组，并非所有的hash表都这样。
当在Hash表中增加一个元素时，将元素的键通过特定的散列函数得到一个hash值并计算出存储在当前数组的存储位置。
散列函数
将元素的键通过特定函数计算出对应hash值的函数。也叫哈希函数。
Hash冲突
相同的元素的键经过hash计算后，会得出相同的哈希值。
不同的键经过hash计算理论应当得出不同的hash值，但是真实中并没使用过这么“完美的”hash函数，所以不同的键可能计算出相同的hash值；另外存储的数组不大，元素过多时，多个元素也可能都计算到数组的同一个位置，这就是hash冲突，也叫散列冲突。
解决方法
下面只介绍其中的几个方法，现实中有很多的解决办法，具体需查阅相关资料。
开放寻址法
底层存储是一个数组：
（p.s. 以前一直没看弄明白，这个解决方法，其实就几句话的事）
- 经过hash计算找到在数组的位置
- 如果这个位置已存在元素，继续找一个空闲位置
位置已经存在元素就是散列冲突了，继续探测下一个空闲位置有如下方法：
- 线性探测
- 二次探测
- 双重散列
- ...
以线性探测来说明，增加、查询、删除的过程，如下：
黑色数字的位置表示已存在元素，蓝色表示为空闲位置。
增加
增加一个元素的时候，出现冲突，按序往后面找，直到找到一个空间的位置，如上图，如果新加元素位置在元素1，已经存在，继续往后找，2也存在，再往后，找到3了。
如果新加元素在10，往后依次找10->11->1->2->3，3是空闲位置找到了。
查询
hash后，位置在1，比对后发现不是，继续往下找，2是，就是找到了，如果2还不是，往后找，3是空闲位置，说明该元素不存在，见空就是结束了。
删除
删除元素的时候，不能直接删除，因为会影响查询，查询结束的判断条件可能就是遇到空了。所以删除的时候只是将元素标记为删除（查询的时候如果标记删除的肯定不是了）。
其它几种探测方法的区别就是继续探测的步长不一样，比如上面的线性探测每次是一步，二次探测是当前步数的平方，双重散列就是使用多个Hash函数，出现冲突更换下一个Hash函数。
示例
在java中的ThreadLocalMap采用的就是线性探测，如果hash冲突的时候，往下再找，直到找到一个合适的位置。
这个是set时候的部分代码：
for (Entry e = tab[i];
e != null;
// nextIndex就是i+1或0： ((i + 1 < len) ? i + 1 : 0
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
if (k == key) {
// 存在就替换
e.value = value;
return;
}
// 不存在就写入
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}链表法
底层存储还是个数组，但是每个位置实际存储的是一个链表，当新增一个元素的时候，就是这个位置的链表上新增的一个结点。
新增
对键hash后计算在数组的位置，经过比对后，如果当前链接上没有该元素，就新增该元素作为链表的一个结点，如果存在就是替换了。
查询
键hash后计算在数组的位置，一一比较该链表上结点直到找到或者为空。
删除
如果找到该结点，就是常规的链表删除一个结点，找不到不用处理的。
示例
Java中的HashMap基本就是这种方法的实现，区别是，它不一定是一个纯粹的链表，在jdk8中的实现里（其它版本没具体注意），当该链上的节点达到8个之后，就变成红黑树了。
为了直观的看到实现，把部分源码copy过来了：
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}