HashMap是一种基于哈希表的数据结构,它通过哈希函数将键映射到数组中的位置来存储和检索键值对。HashMap的扩容机制是其自我调整和优化的重要部分,它可以在需要时重新分配更大的数组,并将原有元素重新计算哈希值并插入到新的数组中。
在JDK1.7中,HashMap的扩容机制具有以下特点:
- 初始容量默认是16,负载因子默认是0.75,阈值默认是12(16*0.75)。
- HashMap的容量必须是2的幂次方,这样可以保证哈希值和数组长度取模时只需要进行位运算,提高效率。
- 当HashMap中的元素个数超过阈值时,就会触发扩容,新的容量是原来的2倍,新的阈值也是原来的2倍。
- 在扩容过程中,HashMap会遍历原来的数组中的每个链表,并将链表中的每个节点重新计算哈希值,找到新数组中对应的位置,以头插法插入到新链表中。这样做可能会导致链表反转和多线程环境下的死循环问题。
在JDK1.8中,HashMap的扩容机制有以下改进:
- HashMap在第一次调用put方法时才会初始化数组,而不是在创建对象时就初始化。这样可以减少内存占用和提高初始化效率。
- HashMap在初始化或扩容时,会根据指定或默认的容量找到不小于该容量的2的幂次方,并将其赋值给阈值。然后在第一次调用put方法时,会将阈值赋值给数组长度,并让新的阈值等于数组长度乘以负载因子。这样可以更好地控制负载因子和数组长度的关系。
- 在扩容过程中,HashMap不需要重新计算节点的哈希值,而是根据哈希值最高位判断节点在新数组中的位置,要么在原位置,要么在原长度加上原位置处。这样可以减少哈希值的计算量,提高扩容效率。
- 在扩容过程中,HashMap会正序遍历原来的数组,并保持链表中节点的相对顺序不变。这样可以保证链表中的节点顺序不变,避免出现链表反转的问题。
- 如果某个链表中的节点数超过8个,并且数组长度大于等于64,则会将链表转化为红黑树,提高查找效率。这样可以优化长链表的查找性能,提高HashMap的整体效率。
总结起来,HashMap的扩容机制是为了适应数据增长而进行的自动调整。在JDK1.7中,扩容过程需要重新计算节点的哈希值并重新插入到新链表中,可能导致链表反转和多线程环境下的死循环问题。而在JDK1.8中,扩容机制进行了优化改进,通过减少哈希值计算量、保持链表节点顺序不变和将长链表转化为红黑树等方法提高扩容效率和整体性能。了解HashMap的扩容机制有助于更好地理解和使用这个数据结构。