金三银四精选面试题-Java中的HashMap内部是如何工作的

Java中的HashMap内部是如何工作的

在JDK8中,HashMap底层是采用“数组+链表+红黑树”来实现的。

HashMap是基于哈希算法来确定元素的位置（槽）的,当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定槽的位置。

如果元素发生碰撞,也就是这个槽已经存在其他的元素了,则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧,某个链表的长度达到了8,则HashMap会创建红黑树来代替这个链表,从而提高对这个槽中数据的查找的速度。

HashMap中,数组的默认初始容量为16,这个容量会以2的指数进行扩容。

具体来说,当数组中的元素达到一定比例的时候HashMap就会扩容,这个比例叫做负载因子,默认为0.75。

Put()方法的执行过程中,主要包含四个步骤：

1. 判断数组,若发现数组为空,则进行首次扩容。

2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。

3. 判断头节点,若发现头节点非空,则将元素插入槽内。

• 1. 若元素的key与头节点一致,则直接覆盖头节点。

• 2. 若元素为树型节点,则将元素追加到树中。

• 3. 若元素为链表节点,则将元素追加到链表中。（追加后,需要判断链表长度以决定是否转为红黑树。若链表长度达到8、数组容量未达到64,则扩容。若链表长度达到8、数组容量达到64,则转为红黑树。）
• 4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。

扩容机制 向HashMap中添加数据时,有三个条件会触发它的扩容行为：

1. 如果数组为空,则进行首次扩容。

2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。

3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。 并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。由于HashMap中数组的容量为2^N