聊聊HashMap、ConcurrentHashMap和HashTable

1、HashMap
1.1、了解HashMap首先了解以下几个参数:
①capacity 容量 默认是static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16(最大1<<30)
②loadFactor 装载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;
③threshold 阈值 即装载因子与容量乘积

1.2、看一下putVal方法
聊聊HashMap、ConcurrentHashMap和HashTable_第1张图片
用流程图的方式分析一下:
聊聊HashMap、ConcurrentHashMap和HashTable_第2张图片

再看一下HashMap底层数据结构就一目了然了:
聊聊HashMap、ConcurrentHashMap和HashTable_第3张图片
hash+key保证唯一性,next实现单链表结构。
1.3、resize操作
聊聊HashMap、ConcurrentHashMap和HashTable_第4张图片
聊聊HashMap、ConcurrentHashMap和HashTable_第5张图片

以下对resize做分析:
聊聊HashMap、ConcurrentHashMap和HashTable_第6张图片

1.4、HashMap的遍历
for (Map.Entry entry: map.entrySet()) {entry.getKey();}
字节码层面也是使用了迭代器:

聊聊HashMap、ConcurrentHashMap和HashTable_第7张图片
再看看代码:
聊聊HashMap、ConcurrentHashMap和HashTable_第8张图片
将table以链表的形式链起来,进行遍历。
2、HashTable
2.1、整理过HashMap,HashTable的设计就很好理解了。HashTable底层主要是由数组+链表的方式实现,不会再做任何优化。此外,所有访问内容的方法都加了synchronized关键字,实现线程安全。synchronized的jvm优化就暂时不讲。
2.2、初始size为11,扩容:newsize = olesize 2+1,value不能为null,key设置null运行会报NPE。
3、ConcurrentHashMap
3.1、实在因为自身水平有限,这部分内容配合了Ouka傅大哥的博文ConcurrentHashMap源码分析(1.8)才能勉强理解。
3.2、首先来看看几个属性:
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
static final int MOVED = -1; // 表示正在转移
static final int TREEBIN = -2; // 表示已经转换成树
static final int RESERVED = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
transient volatile Node[] table;//默认没初始化的数组,用来保存元素
private transient volatile Node[] nextTable;//转移的时候用的数组
/
*
* 用来控制表初始化和扩容的,默认值为0,当在初始化的时候指定了大小,这会将这个大小保存在sizeCtl中,大小为数组的0.75
* 当为负的时候,说明表正在初始化或扩张,
* -1表示初始化
* -(1+n) n:表示活动的扩张线程
*/
private transient volatile int sizeCtl;
3.2、三个方法:
聊聊HashMap、ConcurrentHashMap和HashTable_第9张图片

tabAt和setTabAt其实类似于get/set操作,调用了更为底层的getObjectVolatile/putObjectVolatile native方法,我们姑且顾名思义,这两个操作类似于java的volatile关键字,即线程可见性,实现并发。casTabAt,调用native方法compareAndSwapObject,即比较再交换,实现并发。
3.3、再来看看put操作:
聊聊HashMap、ConcurrentHashMap和HashTable_第10张图片
聊聊HashMap、ConcurrentHashMap和HashTable_第11张图片

过程:table为null先做初始化,若不为null且hash对应数组节点为null,直接cas进去,并跳出循环。若数组节点已有值,先判断当前是否是MOVE,如若是,先helpTransfer帮助转换。再一次循环,应已转移完毕,对数组节点上锁(synchronized),再次判断节点是否变化(可能因扩容变化),若变化再次循环。未变化,判断hash值是否大于0(MOVED,TREEBIN,RESERVED)是否都完成,遍历链表或者红黑树,完成put操作。
3.4、看看get读操作:
聊聊HashMap、ConcurrentHashMap和HashTable_第12张图片
完全没有上锁,只使用tabAt即volatile操作。
3.5、为什么说ConcurrentHashMap的性能要优于HashMap?个人愚见,对于get操作,完全没有使用锁,跟HashMap平手;对于put操作,ConcurrentHashMap使用cas操作也未上锁;扩容或树形过程,多线程helpTransfer,加速扩容和树形化过程,特别在大数据级别上,性能要明显优于HashMap。以上,未经验证,个人猜测。
4、总结
本篇文章首先对HashMap做简要分析,从底层数据结构、put操作、resize操作和Iterator四个点着手,简单介绍了散列集的实现方案。再对HashTable做简要介绍。最后通过 Ouka傅大哥的博文,对ConcurrentHashMap的并发特性做简单剖析,介绍基本的get/put操作,了解了其中的实现原理。

你可能感兴趣的