前面已经对常用的各种map进行了介绍,现在将这些遇到的map放在一起进行对比,这样便于学习和记忆。
类 | 并发性 | 有序性 | 底层数据结构 | 初始容量 | 负载因子 | 实例化方式 | 一致性 | k/v是否可为null |
---|---|---|---|---|---|---|---|---|
HashMap | 不支持 | 无序 | 数组+链表/红黑树 | 16 | 0.75 | 懒加载 | - | k/v可为null |
LinkedHashMap | 不支持 | 有序(插入序或者访问序) | 数组+单向链表+双向链表 | - | - | - | - | k/v可为null |
TreeMap | 不支持 | 自然序(左小右大) | 红黑树 | - | - | - | - | 仅v能为null |
ThreadLocalMap | 不支持 | 无序 | 数组 | 16 | 0.75 | 懒加载 | - | 仅v能为null |
HashTable | 支持 | 无序 | 数组加链表 | 11 | 0.75 | 初始化创建 | 强一致性 | 均不能为null |
ConcurrentHashMap(1.7) | 支持 | 无序 | 分段锁+数组+链表 | 16 | 0.75 | 懒加载 | 强一致性 | 均不能为null |
ConcurrentHashMap(1.8) | 支持 | 无序 | 数组+链表/红黑树+特殊结构 | 16 | 0.75 | 懒加载 | 弱一致性 | 均不能为null |
ConcurrentSkipListMap | 支持 | 自然序(左小右大) | 跳跃表 | - | - | - | 弱一致性 | 均不能为null |
在此对各Map的组成进行回顾:
HashMap主要有由数组table和链表/红黑树组成,当链表的长度为8的时候开始转为红黑树,当红黑树的长度小于等于6则转化为链表。 主要节点Node、TreeNode。组成如下图:
LinkedHashMap是在HashMap的数组+链表的基础上,再将全部节点按插入顺序/或者访问顺序构成双向链表。 其组成如下图:
TreeMap本身就是一颗红黑树结构。
ThreadLocalMap采用数组和开放定址法。hash碰撞之后向后加1。其结构如下:
Hashtable比较简单,就是普通的数组+链表结构。
ConcurrentHashMap(1.7)采用分段锁+数组/链表构成。
在1.8中对ConcurrentHashMap的结构进行了修改,不再使用分段锁,而是使用cas+synchronized的方式。
与HashMap一样,当链表长度大于等于8的时候且size大于64则转化为红黑树。当红黑树长度小于等于6则退化为链表。 同时,使用了一些特殊的结构如ForwardingNode在扩容中使用:
ConcurrentSkipListMap采用跳跃表实现。结构如下:
使用key的hashcode,同时将高位右移参与运算。
hashcode=(h = key.hashCode()) ^ (h >>> 16)
计算index的时候采用位运算:
i = (n - 1) & hash
扩容resize,采用位移的方式按2的幂进行位移:
newCap = oldCap << 1
仅仅只有一个元素的时候:
index=e.hash & (newCap - 1)
否则高低位计算进行扩容:
(e.hash & oldCap) == 0
上述判断为真则在低位,index不变,否则在高位index=index+oldCap。
除红黑树部分之外与HashMap相同。
其put和get过程中,按照key的值进行排序,实际上没用到hashcode。 Entry的Hashcode为:
keyHash ^ valueHash
不涉及到位运算。
hashcode采用每次加上固定的魔数值:
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
由于key就是ThreadLocal本身,因此这个hashcode实际上是在调用threadLocal的时候就已经产生了。 通过如下方式计算index:
key.threadLocalHashCode & (table.length - 1);
由于没有采用拉链法,因此会根据这个值还要对后面的值进行判断。
hashcode即为key的hashCode。 计算index:
index = (hash & 0x7FFFFFFF) % tab.length
扩容:逐个遍历:
index = (e.hash & 0x7FFFFFFF) % newCapacity
采用这个方法挨个计算新的bucket索引。
hashcode为key.hashCode 加上特殊的计算方法。
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
get、set、remove均需要两次hash,第一次得到Segment的位置,第二次再计算出HashEntry中的索引。 第一次计算:
j = (hash >>> segmentShift) & segmentMask
第二次计算:
index = (tab.length - 1) & hash
hash计算方法:
h=key.hashCode,hash = (h ^ (h >>> 16)) & 0x7fffffff
索引计算:
i = (n - 1) & hash
与HashMap一样,当链表长度大于8且size大于64的时候就会树化,反之当红黑树size小于等于6的时候就会转化为链表。扩容的方式与HashMap一致。 但是要注意HashMap两个版本的区别:
采用skipList结构,由于底层不用hashcode。也不涉及到位运算。
类 | get | put | remove |
---|---|---|---|
HashMap | >=O(1) | O(1)~O(log n) | O(1)~O(log n) |
LinkedHashMap | >=O(1) | O(1)~O(log n) | O(1)~O(log n) |
TreeMap | O(log n) | O(log n) | O(log n) |
ThreadLocalMap | O(1)~O(n) | O(1)~O(n) | O(1)~O(n) |
HashTable | >O(1) | O(1)~O(n) | O(1)~O(n) |
ConcurrentHashMap(1.7) | >O(1) | O(1)~O(log n) | O(1)~O(log n) |
ConcurrentHashMap(1.8) | >O(1) | O(1)~O(log n) | O(1)~O(log n) |
ConcurrentSkipListMap | O(log n) | O(log n) | O(log n) |
以上仅限个人愚见,如有不足,请斧正。