共计 1286 个字符，预计需要花费 4 分钟才能阅读完成。
什么是哈希表？
哈希表（Hash table, 也叫散列表），是根据键（Key）来直接访问在内存存储位置的数据结构。它通过一个哈希函数将所需要查询的数据映射到一张哈希表中，来提升查询效率。哈希函数的实现方法：1. 除留余数法取关键字被某个不大于哈希表表长的数除后所得的余数为散列地址。2. 折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。3. 平方取中法取关键字平方后的中间几位为哈希地址。4. 直接定址法取关键字或关键字的某个线性函数值为哈希地址。
哈希冲突
不管用什么哈希函数去计算哈希地址，都是会产生哈希冲突的，因此我们需要想办法解决哈希冲突，并且在设计哈希函数时，尽可能减少哈希冲突。1. 单独的链表法在哈希表的后面单独链上一个单链表来存储冲突的元素，JDK 1.8 里的 HashMap 就是选择的这种方式解决冲突的，不过它对链表做了一层优化。当元素个数大于等于 8 时，会把链表转换成红黑树，提升查询效率。2. 线性探测法当发生哈希冲突时，逐个探测存放地址的表，直到查找到一个空单元。这个方式不便于查找，不建议使用。3. 建立一个公共溢出区当发生哈希冲突时，就把元素存入到公用的溢出区，查询时遍历溢出区。从上面这几种处理方法来说，还是链表法效率比较高，推荐使用。不过都有现成的工具类使用，因此只需要知道实现原理，最好自己可以去写代码实现它。
哈希表有什么用？
哈希表在日常开发中还是比较常用的，因为它最优的查询时间复杂度是 O(1)，当哈希冲突比较严重的时候，查询效率就相当于线性的，因此哈希算法直接影响到查询的效率。
哈希表怎么实现的？
哈希表的结构
public class HashMap<K,V> {
// 用节点数组当作哈希表
Node<K,V>[] table;
int size;
// 节点
static class Node<K,V> {
// 哈希值
final int hash;
// 键
final K key;
// 值
V value;
// 哈希值冲突时存储
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}
总结
哈希表是一个键值对的存储结构，并且根据键进行哈希算法找到对应的存储位置。哈希算法会直接影响到哈希表的查询效率，一般选择哈希冲突小的实现方式，以便提升查询效率。当哈希冲突时，一般选择链表来存储冲突的元素，当冲突的元素增多时，可以采用红黑树来存储，以提升查询效率。JDK 1.8 版本的 HashMap，当链表个数大于等于 8 时，就是采用红黑树来存储的。在知道元素个数时，初始化哈希表时直接指定哈希表大小，因为当元素达到哈希表大小时，会做 resize 操作。当元素越来越多时，resize 是很耗时的，相当于重建哈希表。因此直接指定哈希表大小，减少 resize 次数以便提升插入性能。
PS: 清山绿水始于尘，博学多识贵于勤。我有酒，你有故事吗？微信公众号：「清尘闲聊」。欢迎一起谈天说地，聊代码。
