手撕Java系列之HashMap：设计思路、深入解析、性能评估与代码实现

HashMap 的设计理念

在Java集合框架中具有重要地位的是HashMap类，在其背后有着丰富的设计理念支撑着这一高效的数据结构实现

1. 高效的键值对存储和检索

• 散列结构：Java中的HashMap基于散列表技术实现。它使用Hash函数将关键（key）映射到特定的位置，并利用这些Hash值确定相应记录的插入位置或更新位置。
  • 平均时间复杂度 O(1) ：在理想情况下。
    • HashMap 的 get 和 put 操作的时间复杂度为 O(1)。
    • 其高效的原因在于利用了高效的Hash算法来确定关键的位置。

2. 解决哈希冲突

• 拉链法：当多个键产生相同的哈希码或尽管哈希码不同但存储位置一致时（即发生哈希冲突），HashMap 采 用拉链法来处理此问题。具体而言，在 HashMap 中，默认情况下每一个数组单元（bucket）实际上都是一条链表（或可变长的红黑树），所有被映射到同一单元中的键值对都会被链接到这条链表中。
  • 红黑树优化：当某条链表长度达到或超过某个设定值时（默认情况下设 定为8），该条链表会被升级为红黑树以进一步提升性能表现。这种红黑树是一种自平衡二叉搜索 树结构，在 O(log n) 的时间复杂度内实现查找