构造哈希表的基本方法
1、除留余数法
例如 Hash(Key) = Key%P
值得注意的是， P 必须为质数。若 P 中含有质因子，则所有含同一个质因子的 Key 均会被映射到该地址。
冲突处理
当两个 Key 的 Hash() 值相同时，即视作冲突。遇到冲突时通常有以下几种应对方法。
1、开放定址法
若令 Hashᵢ = (Hash(Key)+dᵢ)%M，i = (1,2,3,…,M-1) ，其中 Hash(Key) 为哈希函数，M为哈希表长，dᵢ为增量序列。
- 若取 dᵢ = (1,2,3,…,m-1)，则称为线性探测再散列；
- 若取 dᵢ = (1²,-1²,2²,-2²,…,±k²)，则称为二次探测再散列。二次探测再散列在内存中左右探测，更加灵活。
- 若取 dᵢ 为伪随机数序列，则称为伪随机探测再散列。
在读取哈希表时，若遇到读取的地址存储的Key和欲读取的Key不同，则按照相应的探测方法寻找下一个地址。
2、链地址法
将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中，且使链表按关键字有序。
由链地址法存储的哈希表可以视为一个数组+多个链表的结构。
在读取哈希表时，如果定位到的数组位置不含链表，那么仅需一次寻址。否则遍历链表逐一查找。
3、公共溢出区法
将所有发生冲突的项放入公共溢出区中。
若查找时 Key 不相等，则遍历公共溢出区。
链地址法中，JDK1.8在链表过长时改为用红黑树存储（可以避免在极端情况下退化成链表）
Java的链表实现里有个Entry类，当Entry的Netx==Null的时候即代表读取到的位置莫得冲突，否则就可以根据Key遍历
static class Entry implements Map.Entry { next;
final K key;
V value;
Entry
int hash;
/** n) {
* Creates new entry.
*/
Entry(int h, K k, V v, Entry
value = v;
next = n;
key = k;
hash = h;
}
呃……Tab全乱了