HashMap源码研读笔记

Spring Wu 371 2021-02-03

基本原理

HashMap是一种key-value形式的键值对数据结构,每个键值对都是Entry,而Entry是一个链表,当hash过的key是相同的话,会放在Entry的next中。其实这也是因为hash碰撞的原因,使用hash虽然可以将数据均衡散列,但是也会避免不了通过hash算法得到的值是相同的情况。所以需要使用到链表结构,将hash相同但是key不相同的值放在同一个Entry链表中,也就是bucket中。其中HashMap默认容量是2 << 4也就是16,负载因子为0.75。阈值 = HashMap容量*负载因子。

put(K key, V value)

JDK1.7的方式

在1.7中存放数据的数组为Entry[] table

当put一个数据时,如果key是null的话会调用putForNullKey(value)插入值,put方法允许存储key和value为null的数据,当key为null时。最后插入在数组index = 0这个位置上,并直接覆盖之前的value,然后把旧的oldValue返回。如果key不为null,那么HashMap通过hash(key)得到一个hash,再根据该hash值通过indexFor(hash, tableLenth ),其中tableLength就是Entry数组的初始容量,初始容量为16。然后获取到当前数据需要插入到table数组中的位置。

如果hash(key)得到一个与Entry数组中相同的hash值,会创建新的Entry并加入到之前具有相同hash值的Entry中,存储的方式是头插入的方式,也就是最后进来该链表的数据插入在最前面。

JDK1.8的方式

在JDK1.8中存放数据的地方是Node<K, V> table。该Node对象与JDK1.7的Entry是一样的,只是换了个名字而已。只是在JDK1.8中。Entry作为了Map接口的一个内部接口。

当put一个数据时,如果该hashMap是第一次使用,会初始化table,如果通过hash值得到的index,该index对应的table位置为null,则会新建一个Node,该数据成为该Node的头节点。反之,如果index对应的位置有值的话,先判断key是否相同,如果key相同,则直接覆盖之前的value,如果key不相同,则获取当前节点的下一个节点,当下一个节点为null时,就把当前要put的value插入在这个节点中。如果节点长度大于等于8了,则自动把整个节点转换为红黑树节点。

最后如果HashMap的容量大于了阈值,会调用resize()方法对HashMap进行扩容。

get(K key)

如果key为null,那么调用getForNullKey()方法返回value,如果key不为null,判断Entry的size是否为0,如果为0,则代表Entry中没有值,直接返回null。
如果Entry的size不为0,那么通过hash计算出key的hash值,然后通过hash值使用indexFor(hash,tableLength)方法计算得到index,然后根据该index取得Entry数组中对应位置的Entry链表。然后根据key迭代判断Entry链表中key是否相同,如果key相同并且hash值也相同的话,那么就是需要的值,然后返回value。

remove(key)

通过key的hash及key本身去找到数据并从HashMap中移除。

JDK1.7的实现方式

根据key得到hash,迭代table,把hash值与table中Entry的hash值进行对比,如果hash相同,并且key也相同,则调用recordRemoval方法删除。

JDK1.8的实现方式

通过key,得到key的hash,把hash值与table中Node的hash值进行对比,如果hash值相同,并且key也相同,则说明是需要删除的节点,把该节点取出来,然后调用afterNodeRemoval(node)方法进行删除。如果该node是TreeNode的实例,则代表该node是红黑树,那么调用removeTreeNode方法进行删除。

resize()

该方法是HashMap的扩容方法,该方法主要的作用是,当之前的table(1.7以前是Entry[],1.8是Node[])的容量达到指定的容量阈值后,创建一个新的table,该table的容量是之前的两倍,阈值也为之前的两倍。然后把旧的table的数据,全部移到新的table中。在把旧数据移到新table的过程中,会进行rehash(rehash的方式为旧数据的hash & 新表的length-1)的操作,以便hash得出的index能更好的分布在新table中。如果当table的容量达到230后,会修改阈值为231-1,此后该table不会再进行扩容。