HashMap 哈希碰撞、负载因子、插入方式、扩容倍数

桃扇骨 2024-02-21 12:16 11阅读 0赞

## HashMap 怎么解决的哈希碰撞问题？ ##

主要采用了链地址法。具体来说：

1.  每个哈希桶不仅存储一个键-值对，而是存储一个链表或树结构。这样，具有相同哈希值的键-值对可以被存储在同一个哈希桶中，并通过链表或树结构来解决碰撞。
2.  当哈希碰撞发生时，新的键-值对会被添加到哈希桶的链表或树的末尾。这确保了相同哈希值的键-值对都能被正确存储和检索。
3.  如果链表的长度超过了某个阈值，Java 8 中的 HashMap 会将链表转化为红黑树，以提高检索性能。这是 Java 8 的一个优化，它降低了最坏情况下的时间复杂度。

这个改进使 Java 8 中的 HashMap 在处理哈希碰撞时更加健壮，尤其是在哈希表的负载因子（load factor）较高的情况下。哈希表的负载因子是键-值对数量与桶数量的比值，当负载因子过高时，哈希碰撞可能会频繁发生，导致性能下降。通过将链表转化为红黑树，Java 8 的 HashMap 能够更好地处理这种情况。

## HashMap的负载因子默认是多少？默认初始容量? ##

HashMap 的默认负载因子是 `0.75`，默认的初始容量为 `16`。初始容量是指 HashMap 在创建时的初始桶数量。负载因子用于确定何时触发扩容操作。

负载因子 `0.75` 意味着当 HashMap 中的元素数量达到当前容量的 `75%` 时，HashMap 将自动进行扩容操作，以保持性能。这是一个平衡的值，通常在性能和内存占用之间提供了合理的折中。

HashMap 的容量总是2的幂，这有助于哈希值与桶的索引之间的关系更加高效。因此，默认初始容量 `16` 是2的幂。如果以不是2的幂的值创建 HashMap，它将自动向上取最接近的2的幂的值。

## 插入之前还是之后去检查是否需要扩容？ ##

在 Java 8 中的 HashMap 实现中，插入操作发生后，HashMap 会首先插入新元素到合适的桶中，然后再检查是否需要进行扩容。如果在插入之后元素数量达到或超过了负载因子乘以当前容量，HashMap 就会触发扩容操作。

这种在插入之后进行扩容检查的方式有助于减少插入操作的复杂性，并使 HashMap 在处理插入操作时能够更高效地运行。

## 链表插入方式？红黑树插入方式？ ##

当发生哈希碰撞时，会根据链表长度或者树结构的情况，采用不同的方式来插入元素：

1.  **链表插入方式**：
    
     *  当哈希桶中的键值对数量较少，并且链表长度小于等于8时，新的键值对会被插入到链表的末尾。
     *  这种方式保持了链表的顺序，没有破坏原有的插入顺序，但当链表长度超过一定阈值（8）& 数组长度 > 64时，会触发链表转化为红黑树的操作。
2.  **红黑树插入方式**：
    
     *  当链表长度超过了一定阈值（8），HashMap 会将链表转化为红黑树（红黑树是一种自平衡的二叉搜索树）。
     *  新的键值对会按照红黑树的规则插入到红黑树中，以提高检索性能。红黑树的平均检索时间复杂度是 O(log n)。
     *  当红黑树的元素数量减少到一定程度（6），会将红黑树转换回链表，以节省内存。

## 哈希表的扩容倍数 ##

哈希表的扩容倍数是 2。这意味着当哈希表需要进行扩容时，它会将当前的容量翻倍。这是为了确保哈希表能够保持较低的负载因子，以提高性能。

例如，如果初始容量为 16，当元素数量达到或超过 16 \* 0.75 = 12 时，HashMap 将触发扩容操作。在这种情况下，HashMap 会创建一个新的容量为 32 的哈希表，然后重新分配元素到新的桶中。