Java HashMap深入解析：结构与Hash原理

“HashMap.pdf 是一份自学笔记，涵盖了 HashMap 的结构、Hash 理论以及 put 数据过程等内容。笔记中提到了 HashMap 在 JDK 1.7 和 1.8 中的不同实现，以及树化和扩容的条件。此外，还讨论了 Hash 算法的基本特性，包括不可逆性、敏感性和效率要求。” HashMap 是 Java 中广泛使用的数据结构，用于存储键值对。在 JDK 1.7 中，HashMap 的内部结构是一个数组加链表的形式。每个元素是一个 Node 对象，包含键、值、哈希值和指向下一个节点的引用。当多个键映射到同一个索引位置时，这些 Node 会形成链表，插入时采用尾插法。 在 JDK 1.8 中，HashMap 的实现进行了优化，除了链表外，还引入了红黑树。当链表长度达到 8 且数组容量达到 64 时，链表会转换为红黑树，以减少查找时间。相反，当链表长度减小到 6 时，会将红黑树转换回链表。这种设计是为了平衡查找效率和内存开销。 HashMap 的扩容条件是当加载因子（元素个数除以数组长度）达到 0.75 时，HashMap 将进行扩容。扩容过程中，原有的元素会重新计算哈希值并分配到新的数组中，以确保所有元素仍然能被正确找到。 Hash 算法是 HashMap 的核心，它将任意长度的输入转化为固定长度的输出，即哈希值。理想的哈希函数应满足以下特点： 1. 哈希值不能逆向推导出原始数据。 2. 输入数据的微小变化会导致哈希值的显著不同，而相同输入应得到相同哈希值。 3. 哈希算法执行快速，即使处理大量数据也能迅速计算哈希值。 4. 冲突概率低，但由于哈希空间小于输入空间，冲突是不可避免的。 内部 Node 类是 HashMap 的基础单元，实现了 Map.Entry 接口，包含键、值、哈希值和指向下一个节点的引用。在 put 过程中，新键值对会被封装为 Node 对象，根据哈希值插入到数组的相应位置。如果发生哈希冲突，新的 Node 将通过 next 引用链接到已存在的链表或树中。 HashMap 的设计和实现是为了解决高效存储和查找键值对的问题，通过巧妙的哈希函数和数据结构优化来平衡查找速度和内存使用。在实际应用中，理解其工作原理有助于更好地利用这一强大的工具。