HashMap源码分析(hashmap,编程语言)

HashMap源码深度剖析

HashMap底层数据结构(为什么引入红黑树、存储数据的过程、哈希碰撞相关问题)
HashMap成员变量(初始化容量是多少、负载因子、数组长度为什么是2的n次幂)
HashMap扩容机制(什么时候需要扩容？怎么进行扩容？)
JDK7与Jdk8比较，JDK8进行了什么优化？

1 定义

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

• JDK1.7 HashMap数据结构：数组 + 链表

• JDK1.8 HashMap数据结构：数组 + 链表 / 红黑树

思考：为什么1.8之后，HashMap的数据结构要增加红黑树？

2 哈希表

Hash表也称为散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中的一个位置来访问记录，以此来加快查找的速度。在链表、数组等数据结构中，查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级

哈希表，它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表，只需要O(1)的时间级

思考：多个 key 通过散列函数会得到相同的值，这时候怎么办？

解决：

（1）开放地址法

（2）链地址法

对于开放地址法，可能会遇到二次冲突，三次冲突，所以需要良好的散列函数，分布的越均匀越好。对于链地址法，虽然不会造成二次冲突，但是如果一次冲突很多，那么会造成子数组或者子链表很长，那么我们查找所需遍历的时间也会很长。

3 JDK1.8前HashMap的数据结构

• JDK 8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

• 当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，极端情况HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

4 JDK1.8后HashMap的数据结构

• JDK 8 后 HashMap 的实现是 数组+链表+红黑树

• 桶中的结构可能是链表，也可能是红黑树，当链表长度大于阈值(或者红黑树的边界值，默认为8)并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

5. 类构造器

publicclassHashMap<K,V>extendsAbstractMap<K,V>
implementsMap<K,V>,Cloneable,Serializable{

　JDK 为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。

HashMap 集合实现了 Cloneable 接口以及 Serializable 接口，分别用来进行对象克隆以及将对象进行序列化。

注意：HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？

据java集合框架的创始人JoshBloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

6 字段属性

 //序列化和反序列化时，通过该字段进行版本一致性验证
privatestaticfinallongserialVersionUID=362498820763181265L;
//默认HashMap集合初始容量为16（必须是2的倍数）
staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16
//集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
staticfinalintMAXIMUM_CAPACITY=1<<30;
//默认的填充因子
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
//当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
staticfinalintTREEIFY_THRESHOLD=8;
//当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
staticfinalintUNTREEIFY_THRESHOLD=6;
/*(JDK1.8新增)
当集合中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，
而不是树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于4TREEIFY_THRESHOLD
*/
staticfinalintMIN_TREEIFY_CAPACITY=64;
/**
初始化使用，长度总是2的幂
/
transientNode<K,V>[]table;
/*
保存缓存的entrySet（）
*/
transientSet<Map.Entry<K,V>>entrySet;
/*
此映射中包含的键值映射的数量。（集合存储键值对的数量）
*/
transientintsize;
/*
跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
主要用于迭代器中的快速失败
/
transientintmodCount;
/*
调整大小的下一个大小值（容量加载因子）。capacityloadfactor
*/
intthreshold;
/
散列表的加载因子。
/
finalfloatloadFactor;

　下面我们重点介绍上面几个字段：

　　①、Node<K,V>[] table

　　我们说 HashMap 是由数组+链表+红黑树组成，这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 声明数组的长度总是 2的n次方(一定是合数)，为什么这里要求是合数，一般我们知道哈希算法为了避免冲突都要求长度是质数，这里要求是合数，下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。

　　②、size*

　　集合中存放key-value 的实时对数。

　　③、loadFactor

　　装载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。

　　默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1。

　　④、threshold

　　计算公式：capacity loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

7 构造函数

①、默认无参构造函数

/
默认构造函数，初始化加载因子loadFactor=0.75
/
publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;
}

②、指定初始容量的构造函数

/

@paraminitialCapacity指定初始化容量
@paramloadFactor加载因子0.75
/
publicHashMap(intinitialCapacity,floatloadFactor){
//初始化容量不能小于0，否则抛出异常
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
//如果初始化容量大于2的30次方，则初始化容量都为2的30次方
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
//如果加载因子小于0，或者加载因子是一个非数值，抛出异常
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
//返回大于等于initialCapacity的最小的二次幂数值。
//>>>操作符表示无符号右移，高位取0。
//|按位或运算
staticfinalinttableSizeFor(intcap){
intn=cap-1;
n|=n>>>1;
n|=n>>>2;
n|=n>>>4;
n|=n>>>8;
n|=n>>>16;
return(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;
}

8 确定哈希桶数组索引位置

前面我们讲解哈希表的时候，我们知道是用散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合，我们希望在有限个数组位置时，尽量每个位置的元素只有一个，那么当我们用散列函数求得索引位置的时候，我们能马上知道对应位置的元素是不是我们想要的，而不是要进行链表的遍历或者红黑树的遍历，这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法：

staticfinalinthash(Objectkey){
inth;
return(key==null)?0:(h=key.hashCode())^(h>>>16);
}
i=(table.length-1)&hash;//这一步是在后面添加元素putVal()方法中进行位置的确定

主要分为三步：

　　①、取 hashCode 值： key.hashCode()

　　②、高位参与运算：h>>>16

　　③、取模运算：(n-1) & hash

　　这里获取 hashCode() 方法的值是变量，但是我们知道，对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

　　为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，取模运算相对开销还是很大的，那该如何优化呢？

　　HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，也就是 hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

　　这也解释了为什么要保证数组的长度总是2的n次方。

　　再就是在 JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位 异或 低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

　　下面举例说明下，n为table的长度：

9 添加元素

//hash(key)就是上面讲的hash方法，对其进行了第一步和第二步处理
publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}
/*

@paramhash索引的位置
@paramkey键
@paramvalue值
@paramonlyIfAbsenttrue表示不要更改现有值
@paramevictfalse表示table处于创建模式
@return
/
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,
booleanevict){
Node<K,V>[]tab;Node<K,V>p;intn,i;
//如果table为null或者长度为0，则进行初始化
//resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;
//注意：这里用到了前面讲解获得key的hash码的第三步，取模运算，下面的if-else分别是tab[i]为null和不为null
if((p=tab[i=(n-1)&hash])==null)
tab[i]=newNode(hash,key,value,null);//tab[i]为null，直接将新的key-value插入到计算的索引i位置
else{//tab[i]不为null，表示该位置已经有值了
Node<K,V>e;Kk;
if(p.hash==hash&&
((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;//节点key已经有值了，直接用新值覆盖
//该链是红黑树
elseif(pinstanceofTreeNode)
e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
//该链是链表
else{
for(intbinCount=0;;++binCount){
if((e=p.next)==null){
p.next=newNode(hash,key,value,null);
//链表长度大于8，转换成红黑树
if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st
treeifyBin(tab,hash);
break;
}
//key已经存在直接覆盖value
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
break;
p=e;
}
}
if(e!=null){//existingmappingforkey
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);
returnoldValue;
}
}
++modCount;//用作修改和新增快速失败
if(++size>threshold)//超过最大容量，进行扩容
resize();
afterNodeInsertion(evict);
returnnull;
}

①、判断键值对数组 table 是否为空或为null，否则执行resize()进行扩容；

②、根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③、判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④、判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤、遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥、插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，进行扩容。

⑦、如果新插入的key不存在，则返回null，如果新插入的key存在，则返回原key对应的value值（注意新插入的value会覆盖原value值）

注意1：其中代码：

if(++size>threshold)//超过最大容量，进行扩容
resize();

这里有个考点，我们知道 HashMap 是由数组+链表+红黑树（JDK1.8）组成，如果在添加元素时，发生冲突，会将冲突的数放在链表上，当链表长度超过8时，会自动转换成红黑树。

　　那么有如下问题：数组上有5个元素，而某个链表上有3个元素，问此HashMap的 size 是多大？

　　我们分析代码，很容易知道，只要是调用put() 方法添加元素，那么就会调用 ++size(这里有个例外是插入重复key的键值对，不会调用，但是重复key元素不会影响size),所以，上面的答案是 7。

10 扩容机制

扩容（resize），我们知道集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity loadFactor），这里的threshold不是数组的最大长度。那么必须扩大数组的长度，Java中数组是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组，就好比以前是用小桶装水，现在小桶装不下了，我们使用一个更大的桶。

JDK1.8融入了红黑树的机制，比较复杂，这里我们先介绍 JDK1.7的扩容源码，便于理解，然后在介绍JDK1.8的源码。

//参数newCapacity为新数组的大小
voidresize(intnewCapacity){
Entry[]oldTable=table;//引用扩容前的Entry数组
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){//扩容前的数组大小如果已经达到最大(2^30)了
threshold=Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[]newTable=newEntry[newCapacity];//初始化一个新的Entry数组
transfer(newTable,initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
table=newTable;
threshold=(int)Math.min(newCapacityloadFactor,MAXIMUM_CAPACITY+1);//修改阈值
}
voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
for(Entry<K,V>e:table){//遍历数组
while(null!=e){
Entry<K,V>next=e.next;
if(rehash){
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);//重新计算每个元素在数组中的索引位置
e.next=newTable[i];//标记下一个元素，添加是链表头添加
newTable[i]=e;//将元素放在链上
e=next;//访问下一个Entry链上的元素
}
}
}

通过方法我们可以看到，JDK1.7中首先是创建一个新的大容量数组，然后依次重新计算原集合所有元素的索引，然后重新赋值。如果数组某个位置发生了hash冲突，使用的是单链表的头插入方法，同一位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。

下面我们在看看JDK1.8的。

finalNode<K,V>[]resize(){
Node<K,V>[]oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;//原数组如果为null，则长度赋值0
intoldThr=threshold;
intnewCap,newThr=0;
if(oldCap>0){//如果原数组长度大于0
if(oldCap>=MAXIMUM_CAPACITY){//数组大小如果已经大于等于最大值(2^30)
threshold=Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
returnoldTab;
}
//原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方
elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&
oldCap>=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1;//阀值扩大1倍
}
elseif(oldThr>0)//旧阀值大于0，则将新容量直接等于就阀值
newCap=oldThr;
else{//阀值等于0，oldCap也等于0（集合未进行初始化）
newCap=DEFAULT_INITIAL_CAPACITY;//数组长度初始化为16
newThr=(int)(DEFAULT_LOAD_FACTORDEFAULT_INITIAL_CAPACITY);//阀值等于160.75=12
}
//计算新的阀值上限
if(newThr==0){
floatft=(float)newCaploadFactor;
newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?
(int)ft:Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[]newTab=(Node<K,V>[])newNode[newCap];
table=newTab;
if(oldTab!=null){
//把每个bucket都移动到新的buckets中
for(intj=0;j<oldCap;++j){
Node<K,V>e;
if((e=oldTab[j])!=null){
oldTab[j]=null;//元数据j位置置为null，便于垃圾回收
if(e.next==null)//数组没有下一个引用（不是链表）
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofTreeNode)//红黑树
((TreeNode<K,V>)e).split(this,newTab,j,oldCap);
else{//preserveorder
Node<K,V>loHead=null,loTail=null;
Node<K,V>hiHead=null,hiTail=null;
Node<K,V>next;
do{
next=e.next;
//原索引
if((e.hash&oldCap)==0){
if(loTail==null)
loHead=e;
else
loTail.next=e;
loTail=e;
}
//原索引+oldCap
else{
if(hiTail==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
}while((e=next)!=null);
//原索引放到bucket里
if(loTail!=null){
loTail.next=null;
newTab[j]=loHead;
}
//原索引+oldCap放到bucket里
if(hiTail!=null){
hiTail.next=null;
newTab[j+oldCap]=hiHead;
}
}
}
}
}
returnnewTab;
}

该方法分为两部分，首先是计算新桶数组的容量 newCap 和新阈值 newThr，然后将原集合的元素重新映射到新集合中。

相比于JDK1.7，1.8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

11 删除元素

HashMap 删除元素首先是要找到 桶的位置，然后如果是链表，则进行链表遍历，找到需要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行平衡调节，注意，当红黑树的节点数小于 6 时，会转化成链表。

publicVget(Objectkey){
Node<K,V>e;
return(e=getNode(hash(key),key))==null?null:e.value;
}
finalNode<K,V>getNode(inthash,Objectkey){
Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;
if((tab=table)!=null&&(n=tab.length)>0&&
(first=tab[(n-1)&hash])!=null){
//根据key计算的索引检查第一个索引
if(first.hash==hash&&//alwayscheckfirstnode
((k=first.key)==key||(key!=null&&key.equals(k))))
returnfirst;
//不是第一个节点
if((e=first.next)!=null){
if(firstinstanceofTreeNode)//遍历树查找元素
return((TreeNode<K,V>)first).getTreeNode(hash,key);
do{
//遍历链表查找元素
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}while((e=e.next)!=null);
}
}
returnnull;
}

12 查找元素

①、通过 key 查找 value

首先通过 key 找到计算索引，找到桶位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回 null。

publicVget(Objectkey){
Node<K,V>e;
return(e=getNode(hash(key),key))==null?null:e.value;
}
finalNode<K,V>getNode(inthash,Objectkey){
Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;
if((tab=table)!=null&&(n=tab.length)>0&&
(first=tab[(n-1)&hash])!=null){
//根据key计算的索引检查第一个索引
if(first.hash==hash&&//alwayscheckfirstnode
((k=first.key)==key||(key!=null&&key.equals(k))))
returnfirst;
//不是第一个节点
if((e=first.next)!=null){
if(firstinstanceofTreeNode)//遍历树查找元素
return((TreeNode<K,V>)first).getTreeNode(hash,key);
do{
//遍历链表查找元素
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}while((e=e.next)!=null);
}
}
returnnull;
}