Hash 表原理
通过 哈希函数 ，将键值对进行映射，从而根据键获得值对应的位置，检索出对应值。理论上时间复杂度为 。
hash = hashfunc(key)
index = hash % array_sizeHash 冲突
两个不同的键根据哈希函数映射到相同的 index 下标。
处理 Hash 冲突的方法
开放地址法（线性探测、平方探测、双散列函数探测）、链地址法、再哈希法、建立公共溢出区。
- 开放地址法：从冲突的单元开始，按照一定的次序去寻找下一个空闲的单元。
- 线性探测法：正向 - 单元 +1、+2… 依次判断是否有空闲单元；双向 - 单元 +1、-1、+2… 依次判断是否有空闲单元。
- 平方探测法：单元 +1、+4、+9… 依次判断是否有空闲单元。
- 双散列函数探测：d=h (key)，(d+h1 (key))%m，(d+2h1 (key))%m，…等
- 链地址法：在单元后面增加链表，将数据补充到链表尾部 or 头部。
- 再哈希法：构造多个哈希函数，依次使用不同的哈希函数获得 index，h1 (key)，h2 (key)…
Java 具体应用
JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的；JDK1.8 以后 HashMap 为了减少链表过长的时候搜索时间过长引入了红黑树。