详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)

2023-09-26 17:25:05 57

HashMap本质是数组加链表，根据key取得hash值，然后计算出数组下标，如果多个key对应到同一个下标，就用链表串起来，新插入的在前面。

ConcurrentHashMap在HashMap的基础上将数据分为多个segment，默认16个，然后每次操作对一个segment加锁，避免多线程锁的几率，提高并发效率。

1.HashMap的数据结构

HashMap底层就是一个数组结构，数组中存放的是一个Entry对象，如果产生的hash冲突，这时候该位置存储的就是一个链表了。

HashMap中Entry类的代码：

staticclassEntryimplementsMap.Entry{
finalKkey;
Vvalue;
Entrynext;
finalinthash;
/**
*Createsnewentry.
*/
Entry(inth,Kk,Vv,Entryn){
value=v;
next=n;//hash值冲突后存放在链表的下一个
key=k;
hash=h;
}
.........
}

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

2.HashMap源码分析

下面是HashMap类中的一些关键属性：

transientEntry[]table;//存储元素的实体数组
transientintsize;//存放元素的个数
intthreshold;//临界值，当实际大小超过临界值时，会进行扩容，threshold=loadFactor*容量
finalfloatloadFactor;//加载因子
transientintmodCount;//被修改的次数

如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。

下面是HashMap的几个构造方法：

publicHashMap(intinitialCapacity,floatloadFactor){
//确保数字合法
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);

//Findapowerof2>=initialCapacity
intcapacity=1;//初始容量
while(capacity
默认初始容量为16，加载因子为0.75。上面代码中13-15行，这段代码的作用是确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂。
下面看看HashMap存储数据的过程是怎样的，首先看看HashMap的put方法：
publicVput(Kkey,Vvalue){
if(key==null)//如果键为null的话，调用putForNullKey(value)
returnputForNullKey(value);
inthash=hash(key.hashCode());//根据键的hashCode计算hash码
inti=indexFor(hash,table.length);
for(Entrye=table[i];e!=null;e=e.next){//处理冲突的，如果hash值相同，则在该位置用链表存储
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){//如果key相同则覆盖并返回旧值
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}

modCount++;
addEntry(hash,key,value,i);
returnnull;
}
当我们往HashMap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置，然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。从HashMap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
具体的实现是：当你的key为null时，会调用putForNullKey，HashMap允许key为null，这样的对象是放在table[0]中。如果不为空，则调用inthash=hash(key.hashCode());这是HashMap的一个自定义的hash方法，在key.hashCode()基础上进行二次hash，源码如下：
staticinthash(inth){
h^=(h>>>20)^(h>>>12);
returnh^(h>>>7)^(h>>>4);
}
得到hash码之后就会通过hash码去计算出应该存储在数组中的索引，计算索引的函数如下：
staticintindexFor(inth,intlength){
returnh&(length-1);
}
它通过h&(table.length-1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h&(length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。当数组长度为2的n次幂的时候，不同的key算出的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
下面继续回到put方法里面，前面已经计算出索引的值了，看到第6到14行，如果数组中该索引的位置的链表已经存在key相同的对象，则将其覆盖掉并返回原先的值。如果没有与key相同的键，则调用addEntry方法创建一个Entry对象，addEntry方法如下：
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
Entrye=table[bucketIndex];//如果要加入的位置有值，将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
table[bucketIndex]=newEntry<>(hash,key,value,e);
if(size++>=threshold)//如果大于临界值就扩容
resize(2*table.length);//以2的倍数扩容
}
参数bucketIndex就是indexFor函数计算出来的索引值，第2行代码是取得数组中索引为bucketIndex的Entry对象，第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置，并且将该位置原先的对象设置为新对象的next构成链表。第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容，HashMap扩容是扩为原来的两倍。resize()方法如下：
voidresize(intnewCapacity){
Entry[]oldTable=table;
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
return;
}
8
Entry[]newTable=newEntry[newCapacity];
transfer(newTable);//用来将原先table的元素全部移到newTable里面
table=newTable;//再将newTable赋值给table
threshold=(int)(newCapacity*loadFactor);//重新计算临界值
}
扩容是需要进行数组复制的，上面代码中第10行为复制数组，复制数组是非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。下面是get方法的源码：
publicVget(Objectkey){
if(key==null)
returngetForNullKey();
inthash=hash(key.hashCode());
//找到数组的下标，进行遍历
for(Entrye=table[indexFor(hash,table.length)];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k)))
returne.value;//找到则返回
}
returnnull;//否则，返回null
}
以上这篇详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)

热门推荐

随机推荐