如何进行HashMap的源码剖析

如何进行HashMap的部分源码剖析,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

巩义网站建设公司成都创新互联,巩义网站设计制作,有大型网站制作公司丰富经验。已为巩义上千余家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的巩义做网站的公司定做!

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。HashMap的结构如下:

如何进行HashMap的源码剖析

我们可以看到HashMap的结构主要分为两大部分:左侧的table和右侧的链表,下面重点分析HashMap的源码。

1.常量

如何进行HashMap的源码剖析

2.常用的构造方法

如何进行HashMap的源码剖析

3.常用方法

(1)、final int hash(Object k),此方法用来计算key的哈希值,由方法最后的几行可以看到,为了保证key的均匀散列,并没有使用hashCode%length的方法,因为移位运算符不仅可以更均匀的散列而且匀速速度也比hashCode%length更快。

如何进行HashMap的源码剖析

(2)、public V get(Object key)

如何进行HashMap的源码剖析

我们看到,get方法首先判断key是否为null,如果为null,则调用getForNullKey(),否则调用getEntry(key)方法获取value,让我们来继续分析getForNullKey的源码:

private V getForNullKey() 

如何进行HashMap的源码剖析

可见:循环遍历table[0]的那个链表,直到找到key==null的Entry,否则返回null;为什么是table[0]呢?因为在put的时候如果key==null,直接将entry存储在table[0]的位置,我们在后面分析put方法。接下来再分析getEntry(key)方法:

如何进行HashMap的源码剖析

通过key的Hash值计算Entry所在table的小标,请注意计算下标的方法通过indexFor()方法得到,然后遍历Entry,直到找到hash和equals都相等的Entry后返回,否则返回null;

好了,get方法基本就是这样,接下来我们一起来分析put方法。

(3)、 public V put(K key, V value)

如何进行HashMap的源码剖析

put方法的大致流程是:

①、首先判断key是否为null,如果为null,调用putForNullKey(value)方法,请大家注意,putForNullKey和上面的getForNullKey的逻辑是一一对应的哦。

②、计算key的Hash值,通过indexFor()方法定位到元素存储在table的位置table[i]。

③、循环遍历table[i],如果新值和旧值相等,覆盖旧值后返回旧值

④、modCount++,操作次数+1,调用addEntry将新值插入到链表。

让我们来分析putForNullKey(value)方法源码:

如何进行HashMap的源码剖析

请看,这里又是table[0],和getForNullKey中的table[0]对称,遍历-->新值覆盖旧值-->返回旧值-->操作数+1-->插入新元素,很容易理解。

接下来重点来了,让我们来分析addEntry方法中的一系列逻辑:

如何进行HashMap的源码剖析

首先,threshold=capacity * load factor,也就是临界值=容量*加载因子=16*0.75f, map中使用量超过threshold,会扩容为原来的2倍。resize是一个非常复杂的过程,涉及到rehash等,后面我在介绍,现在咱们重点看addEntry()。bucketIndex是元素存储在table的下标,也就是将元素存储在table[bucketIndex]。最后调用createEntry将新元素存储在HashMap中,createEntry的源码如下:

如何进行HashMap的源码剖析

通过new Entry(hash,key,value,e),将新元素插到table[bucketIndex]中,我们来看Entry的构造方法:

如何进行HashMap的源码剖析

重点在next = n这行,看到到插入元素到链表中使用的头插法,不用尾插的目的估计是为了节省遍历链表的开销吧。

好了,put方法就是这样,其实也特别好理解,接下来我们来分析Entry这类。

4.Entry内部类

HashMap有一个变量:transient Entry[] table,可以看到table是一个Entry的数组,并且Entry本身是一个链表的一个元素。Entry implements Map.Entry,而Map.Entry是一个接口。Entry包含四个元素,final K key; V value; Entry next;int hash;hash是这个元素的hash值,其余的三个元素就不解释了。Entry类的方法基本上都很简单,大家可以通过阅读源码来理解,我重点解释一下equals和hashCode这两个方法,源码如下:

如何进行HashMap的源码剖析比较连个Entry是否相等就是通过if中的条件,比较容易理解,hashCode源码:

如何进行HashMap的源码剖析

最后,重点分析rehash方法,在分析rehash时,我先解释一下什么是rehash:当我们的HashMap的使用量超过了threshold=capacity * load factor,也就是临界值=容量*加载因子=16*0.75f,就会发生rehash,将容量扩大为原来的两倍,然后所有的元素根据新的hash规则重新散列到不同的table[i]中。但是rehash有很大的性能消耗,所以如果我们在使用HashMap时能预测到元素的个数,最好在构造时就指定HashMap的大小。rehash的源码如下:

如何进行HashMap的源码剖析

Entry[] newTable = new Entry[newCapacity],常见一个新的table,很消耗内存的!!!前面容易理解,重点看transfer方法,这个方法才是将元素重新散列的方法,源码如下:

如何进行HashMap的源码剖析

循环遍历table(旧数组),计算出newTable的下标,将旧元素e存储到newTable中,这里有一个细节要注意,在我讲put方法时提到过,插入元素的方法时头插法,就是新的元素被添加到链表的头部,但我们通过transfer方法可分析出:在rehash的时候,之前在头部的元素会先进行rehash,在尾部的元素会最后rehash,所以当rehash结束后,之前在头部的元素会沉到尾部,之前在尾部的元素会上升到头部。

关于如何进行HashMap的部分源码剖析问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注创新互联行业资讯频道了解更多相关知识。


标题名称:如何进行HashMap的源码剖析
文章起源:http://scyanting.com/article/jchcso.html