[] - 2022-06-25 HashMap夺命14问，你能坚持到第几问？.pdf

HashMap是Java编程中常用的数据结构之一，用于存储键值对，具有高效的查找和插入性能。在JDK的不同版本中，HashMap的实现有所不同。在JDK 1.7中，HashMap基于"数组+链表"的数据结构，每个桶（bucket）通过链表链接哈希冲突的元素。而在JDK 1.8中，为了进一步优化性能，引入了红黑树（Red-Black Tree）数据结构。当链表长度超过8且数组长度超过64时，链表会转换为红黑树，以减少查找时间，因为红黑树的搜索时间复杂度为O(logn)，而链表为O(n)。 HashMap的特点包括： 1. 存取无序：HashMap中元素的插入顺序与实际获取顺序无关。 2. 允许键和值为null：但键只能唯一，且只能有一个null键。 3. 数据结构：在JDK 1.8前是数组+链表，1.8后增加红黑树。 4. 阈值转换：当桶中的元素数量超过8且整个数组大小超过64时，链表转为红黑树。 5. 加载因子：默认为0.75，用于控制何时扩容，平衡空间利用率和查询效率。 解决哈希冲突的方法有多种，HashMap采用的是链地址法，即将哈希值相同的元素链接在一起形成链表。其他方法包括： 1. 开放定址法：再次哈希寻找空槽，但可能导致表中产生大量空洞。 2. 再哈希法：使用多个不同的哈希函数，直到找到无冲突的哈希地址。 3. 拉链法（链地址法）：HashMap所用，同一哈希值的元素形成链表。 4. 建立公共溢出区：分为主表和溢出表，溢出数据存入溢出区。 加载因子设置为0.75是为了平衡空间和时间效率。加载因子越小，触发扩容的阈值越低，浪费空间；反之，加载因子越大，查找效率下降，哈希冲突概率增加。12作为初始容量是因为12 * 0.75 = 9，这意味着当HashMap填满九个元素时就会触发第一次扩容，确保在平均情况下每个桶的元素不会太多。 哈希表计算哈希值通常使用对象的hashCode()方法，这是Object类中的一个方法，所有类都可以继承并重写。哈希算法的设计目标是尽可能让不同对象生成不同的哈希码，以减少冲突。当然，除了内置的hashCode()之外，还可以自定义哈希算法，如MD5、SHA系列等加密算法，但这通常不是常规HashMap操作的首选。 HashMap的高效性能依赖于良好的哈希函数设计、数据结构的优化（如链表和红黑树的结合）以及合适的加载因子设置。理解这些知识点对于开发人员来说至关重要，能帮助他们在实际编程中更好地利用HashMap并优化程序性能。