前面已经对常用的各种map进行了介绍，现在将这些遇到的map放在一起进行对比，这样便于学习和记忆。
1.基本属性
| 类 | 并发性 | 有序性 | 底层数据结构 | 初始容量 | 负载因子 | 实例化方式 | 一致性 | 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 |
2.组成结构
在此对各Map的组成进行回顾：
2.1 HashMap
HashMap主要有由数组table和链表/红黑树组成，当链表的长度为8的时候开始转为红黑树，当红黑树的长度小于等于6则转化为链表。
主要节点Node、TreeNode。组成如下图：
HashMap结构
2.2 LinkedHashMap
LinkedHashMap是在HashMap的数组+链表的基础上，再将全部节点按插入顺序/或者访问顺序构成双向链表。
其组成如下图:
LinkedHashMap
2.3 TreeMap
TreeMap本身就是一颗红黑树结构。
TreeMap
2.4 ThreadLocalMap
ThreadLocalMap采用数组和开放定址法。hash碰撞之后向后加1。其结构如下：
ThreadLocalMap
2.5 HashTable
Hashtable比较简单，就是普通的数组+链表结构。
HashTable
2.6 ConcurrentHashMap(1.7)
ConcurrentHashMap(1.7)采用分段锁+数组/链表构成。
ConcurentHashMap1.7
2.7 ConcurrentHashMap(1.8)
在1.8中对ConcurrentHashMap的结构进行了修改，不再使用分段锁，而是使用cas+synchronized的方式。
ConcurrentHashMap1.8
与HashMap一样，当链表长度大于等于8的时候且size大于64则转化为红黑树。当红黑树长度小于等于6则退化为链表。
同时，使用了一些特殊的结构如ForwardingNode在扩容中使用：
ConcurrentHashMap1.8扩容
2.8 ConcurrentSkipListMap
ConcurrentSkipListMap采用跳跃表实现。结构如下：
ConcurrentSkipListMap
3.hashcode及扩容位运算
3.1 HashMap
使用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。
3.2 LinkedHashMap
除红黑树部分之外与HashMap相同。
3.3 TreeMap
其put和get过程中，按照key的值进行排序，实际上没用到hashcode。
Entry的Hashcode为：
keyHash ^ valueHash
不涉及到位运算。
3.4 ThreadLocalMap
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);
由于没有采用拉链法，因此会根据这个值还要对后面的值进行判断。
3.5 HashTable
hashcode即为key的hashCode。
计算index:
index = (hash & 0x7FFFFFFF) % tab.length
扩容：逐个遍历：
index = (e.hash & 0x7FFFFFFF) % newCapacity
采用这个方法挨个计算新的bucket索引。
3.6 ConcurrentHashMap(1.7)
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
3.7 ConcurrentHashMap(1.8)
hash计算方法：
h=key.hashCode，hash = (h ^ (h >>> 16)) & 0x7fffffff
索引计算：
i = (n - 1) & hash
与HashMap一样，当链表长度大于8且size大于64的时候就会树化，反之当红黑树size小于等于6的时候就会转化为链表。扩容的方式与HashMap一致。
但是要注意HashMap两个版本的区别：
- 1.锁机制不一样：1.7分段锁，不能动态扩容，1.8 cas+synchronized可以动态调整。
- 2.2.扩容机制不一样，1.7只有每个bucket自己扩容，而且是单线程扩容，1.8支持多线程扩容，采用标志位来进行，每次分配一定数量的bucket给使用的线程，提升了性能。
- 3.性能不一样，1.7固定的分段锁，随着数据量的增加性能急剧下降，1.8可以完美避免因为容量不足导致的hash碰撞情况，而且多线程扩容，性能提升了很多。
- 4.一致性支持不同，1.7是分段锁 强一致性。1.8则是弱一致性。
- 5.size方法实现不同，1.7通过分段锁累加计数器。1.8增加了CountCell的特殊类的数组，随着table的扩容而一并扩容。
3.8 ConcurrentSkipListMap
采用skipList结构，由于底层不用hashcode。也不涉及到位运算。
4.性能比较
| 类 | 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) |
以上仅限个人愚见，如有不足，请斧正。
网友评论