聊聊java中的哪些Map：（十）各种map的总结

前面已经对常用的各种map进行了介绍，现在将这些遇到的map放在一起进行对比，这样便于学习和记忆。

1.基本属性

类并发性有序性底层数据结构初始容量负载因子实例化方式一致性k/v是否可为nullHashMap不支持无序数组+链表/红黑树160.75懒加载-k/v可为nullLinkedHashMap不支持有序（插入序或者访问序）数组+单向链表+双向链表----k/v可为nullTreeMap不支持自然序（左小右大）红黑树----仅v能为nullThreadLocalMap不支持无序数组160.75懒加载-仅v能为nullHashTable支持无序数组加链表110.75初始化创建强一致性均不能为nullConcurrentHashMap(1.7)支持无序分段锁+数组+链表160.75懒加载强一致性均不能为nullConcurrentHashMap(1.8)支持无序数组+链表/红黑树+特殊结构160.75懒加载弱一致性均不能为nullConcurrentSkipListMap支持自然序(左小右大)跳跃表---弱一致性均不能为null

2.组成结构

在此对各Map的组成进行回顾：

2.1 HashMap

HashMap主要有由数组table和链表/红黑树组成，当链表的长度为8的时候开始转为红黑树，当红黑树的长度小于等于6则转化为链表。 主要节点Node、TreeNode。组成如下图：

2.2 LinkedHashMap

LinkedHashMap是在HashMap的数组+链表的基础上，再将全部节点按插入顺序/或者访问顺序构成双向链表。 其组成如下图:

2.3 TreeMap

TreeMap本身就是一颗红黑树结构。

2.4 ThreadLocalMap

ThreadLocalMap采用数组和开放定址法。hash碰撞之后向后加1。其结构如下：

2.5 HashTable

Hashtable比较简单，就是普通的数组+链表结构。

2.6 ConcurrentHashMap(1.7)

ConcurrentHashMap(1.7)采用分段锁+数组/链表构成。

2.7 ConcurrentHashMap(1.8)

在1.8中对ConcurrentHashMap的结构进行了修改，不再使用分段锁，而是使用cas+synchronized的方式。

与HashMap一样，当链表长度大于等于8的时候且size大于64则转化为红黑树。当红黑树长度小于等于6则退化为链表。 同时，使用了一些特殊的结构如ForwardingNode在扩容中使用：

2.8 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.性能比较

类getputremoveHashMap>=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)TreeMapO(log n)O(log n)O(log n)ThreadLocalMapO(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)ConcurrentSkipListMapO(log n)O(log n)O(log n)

以上仅限个人愚见，如有不足，请斧正。