ITPub博客

首页 > 应用开发 > IT综合 > ConcurrentHashMap 源码分析

ConcurrentHashMap 源码分析

原创 IT综合 作者:dustinny 时间:2021-03-06 16:17:31 0 删除 编辑

  和HashMap不同的是,ConcurrentHashMap采用分段加锁的方式保障线程安全,JDK 1.8之后,ConcurrentHashMap的底层数据结构从1.8开始跟HashMap差不多。

  HashTable也是线程安全的,存储Key-Value键值对的数据结构,Key和Value都不能为空,但不推荐使用,因为其所有的方法采用synchronized修饰,效率低。

  Key和Value都不能为Null的原因是:如果map.get(key)返回null,可以认为是value的值本来就是null,也可以认为map中不存在key的存储数据,因此具有二义性,但HashMap在单线程环境,可以通过map.containsKey(key)判断,消除而已性。

  但在多线程环境中,map.get(key)和map.containsKey(key)是非原子的操作,可能在线程A的两个语句运行之间,其他线程B运行map.put(key,value),导致线程A无法消除上面的二义性。

  下图是ConcurrentHashMap的UML关系图。

  image-20200809215755661

  1、底层存储结构

  1.1、JDK 1.7的存储结构,了解即可

  在JDK 1.7,ConcurrentHashMap通过对Segment的分段加锁实现线程安全。一个Segment里面就是HashMap的存储结构,可以扩容。Segment的数据量初始化以后不可以更改,默认值16,因此默认支持16个线程同时操作ConcurrentHashMap。

  img

  1.2 JDK 1.8的存储结构

  JDK 1.8之后,存储结构变化比较大,跟HashMap类似。红黑树节点小于某个数(默认值6)又会转换为链表。

  image-20200809221531416

  []ConcurrentHashMap的主要成员变量,类似HashMap,补上注释

  2、ConcurrentHashMap的构造方法

  ConcurrentHashMap的默认构造容量为16,在初始化的时候并不会初始化table数组。同HashMap一样,在put第一个元素的时候才会initTable()初始化数组。

  /**Creates a new,empty map with the default initial table size(16).*/

  public ConcurrentHashMap(){

  }

  //设置初始化大小的构造函数

  public ConcurrentHashMap(int initialCapacity){

  this(initialCapacity,LOAD_FACTOR,1);

  }

  //根据传入的map初始化

  public ConcurrentHashMap(Map<?extends K,?extends V>m){

  this.sizeCtl=DEFAULT_CAPACITY;

  putAll(m);

  }

  //设置初始容量和加载因子的大小

  public ConcurrentHashMap(int initialCapacity,float loadFactor){

  this(initialCapacity,loadFactor,1);

  }

  //初始容量、加载因子、并发级别

  public ConcurrentHashMap(int initialCapacity,

  float loadFactor,int concurrencyLevel){

  //数据校验

  if(!(loadFactor>0.0f)||initialCapacity<0||concurrencyLevel<=0)

  throw new IllegalArgumentException();

  //如果初始容量小于并发级别

  if(initialCapacity<concurrencyLevel)//Use at least as many bins

  initialCapacity=concurrencyLevel;//as estimated threads

  //一些比较

  long size=(long)(1.0+(long)initialCapacity/loadFactor);

  int cap=(size>=(long)MAXIMUM_CAPACITY)?

  MAXIMUM_CAPACITY:tableSizeFor((int)size);

  this.sizeCtl=cap;

  }

  3、get、put方法

  3.1 get方法,根据key找value,没有返回null

  get的流程总体和HashMap差不多,只不过是通过头结点的hash值判断是红黑树还是链表。

  static final int MOVED=-1;//转发节点?TODO作用?

  static final int TREEBIN=-2;//跟节点

  static final int RESERVED=-3;//临时保留的节点?TODO作用?

  static final int HASH_BITS=0x7fffffff;//hash的扰动函数spread()计算用的

  //根据key获取value值

  public V get(Object key){

  Node<K,V>[]tab;Node<K,V>e,p;int n,eh;K ek;

  //计算hash值

  int h=spread(key.hashCode());

  //集散所在的hash桶

  if((tab=table)!=null&&(n=tab.length)>0&&

  (e=tabAt(tab,(n-1)&h))!=null){

  if((eh=e.hash)==h){

  //头结点,刚好是要找的节点

  if((ek=e.key)==key||(ek!=null&&key.equals(ek)))

  return e.val;

  }

  else if(eh<0)

  //头结点hash值小于0,说明正在扩容或者是红黑树,find查找

  return(p=e.find(h,key))!=null?p.val:null;

  while((e=e.next)!=null){

  //链表遍历查找

  if(e.hash==h&&

  ((ek=e.key)==key||(ek!=null&&key.equals(ek))))

  return e.val;

  }

  }

  return null;

  }

  3.2、put方法

  put方法的流程跟HashMap的流程差不多,不同点在于线程安全,自旋,CAS,synchronized

  onlyIfAbsent如果为true,如果已经存在了key,不会替换旧的值。

  public V put(K key,V value){

  return putVal(key,value,false);

  }

  /**Implementation for put and putIfAbsent*/

  final V putVal(K key,V value,boolean onlyIfAbsent){

  //key和value都不能为null

  if(key==null||value==null)throw new NullPointerException();

  //计算hash(key)的扰动函数

  int hash=spread(key.hashCode());

  //离岸边的长度

  int binCount=0;

  for(Node<K,V>[]tab=table;;){

  Node<K,V>f;int n,i,fh;K fk;V fv;

  //如果table还没有初始化,就初始化table(自旋+CAS)

  if(tab==null||(n=tab.length)==0)

  tab=initTable();

  else if((f=tabAt(tab,i=(n-1)&hash))==null){

  //如果当前hash桶为null,直接放入,CAS加入,成功了就直接break

  if(casTabAt(tab,i,null,new Node<K,V>(hash,key,value)))

  break;//no lock when adding to empty bin

  }

  //TODO:

  else if((fh=f.hash)==MOVED)

  tab=helpTransfer(tab,f);

  else if(onlyIfAbsent//check first node without acquiring lock

  &&fh==hash

  &&((fk=f.key)==key||(fk!=null&&key.equals(fk)))

  &&(fv=f.val)!=null)

  return fv;

  else{

  //旧的值

  V oldVal=null;

  //加锁

  synchronized(f){

  if(tabAt(tab,i)==f){

  if(fh>=0){

  binCount=1;

  for(Node<K,V>e=f;;++binCount){

  K ek;

  //如果存在hash(key)和key对应的节点,直接更改value值

  if(e.hash==hash&&

  ((ek=e.key)==key||

  (ek!=null&&key.equals(ek)))){

  oldVal=e.val;

  if(!onlyIfAbsent)

  e.val=value;

  break;

  }

  Node<K,V>pred=e;

  if((e=e.next)==null){

  //不存在直接放入,因为前面加锁了

  pred.next=new Node<K,V>(hash,key,value);

  break;

  }

  }

  }

  //如果是红黑树,红黑树插入

  else if(f instanceof TreeBin){

  Node<K,V>p;

  binCount=2;

  if((p=((TreeBin<K,V>)f).putTreeVal(hash,key,

  value))!=null){

  oldVal=p.val;

  if(!onlyIfAbsent)

  p.val=value;

  }

  }

  else if(f instanceof ReservationNode)

  throw new IllegalStateException("Recursive update");

  }

  }

  if(binCount!=0){

  //是否要转为红黑树

  if(binCount>=TREEIFY_THRESHOLD)

  treeifyBin(tab,i);

  //旧的值

  if(oldVal!=null)

  return oldVal;

  break;

  }

  }

  }

  addCount(1L,binCount);

  return null;

  }

  4、TODO ConcurrentHashMap的扩容方法

  ConcurrentHashMap也是默认扩容2倍,扩容的方法transfer()

  Node<K,V>[]nt=(Node<K,V>[])new Node<?,?>[n<<1];

  5、总结

  ConcurrentHashMap在JDK 1.7和1.8变化很大,在JDK 1.7中,采用Segment分段存储数据,也通过Segment分段加锁。

  而在JDK 1.8中,使用synchronized锁定hash桶的链表的首节点/红黑树的根节点,只要hash(key)不冲突,就不会影响其他线程。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69995861/viewspace-2761551/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2021-03-05

  • 博文量
    11
  • 访问量
    4101