Hashtable 和 ConcurrentHashMap

╰半夏微凉° 2022-06-16 07:15 206阅读 0赞

相同点： Hashtable 和 ConcurrentHashMap都是线程安全的，可以在多线程环境中运行； key跟value都不能是null

区别： 两者主要是性能上的差异，Hashtable的所有操作都会锁住整个对象，虽然能够保证线程安全，但是性能较差； ConcurrentHashMap内部使用Segment数组，每个Segment类似于Hashtable，在“写”线程或者部分特殊的“读”线程中锁住的是某个Segment对象，其它的线程能够并发执行其它的Segment对象。

下面从下面两个问题来具体了解下Hashtable和ConcurrentHashMap

1， Hashtable怎样实现线程安全？

2，ConcurrentHashMap怎样实现线程安全？为什么性能会比Hashtable好？

先来看第一个问题： Hashtable怎样实现线程安全？

下面是Hashtable的get和put方法

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  /\*\* 
2.      \* The hash table data. 
3.      \*/  
4.     //Hashtable使用Entry数组来保存数据  
5.     private transient Entry\[\] table;  
6.    
7.  ublic synchronized V get(Object key) \{  
8.  Entry tab\[\] = table;  
9.  int hash = key.hashCode();  
10.        //通过求模运算得到下标的索引值，保证下标在 【0，tab.length）  
11. int index = (hash & 0x7FFFFFFF) % tab.length;  
12. for (Entry<K,V> e = tab\[index\] ; e != null ; e = e.next) \{  
13.     if ((e.hash == hash) && e.key.equals(key)) \{  
14.     return e.value;  
15.     \}  
16. \}  
17. return null;  
18.    \}  
19.   
20.   
21. ublic synchronized V put(K key, V value) \{  
22. // Make sure the value is not null  
23. if (value == null) \{  
24.     throw new NullPointerException();  
25. \}  
26.   
27. // Makes sure the key is not already in the hashtable.  
28. Entry tab\[\] = table;  
29. int hash = key.hashCode();  
30. int index = (hash & 0x7FFFFFFF) % tab.length;  
31. for (Entry<K,V> e = tab\[index\] ; e != null ; e = e.next) \{  
32.     if ((e.hash == hash) && e.key.equals(key)) \{  
33.     V old = e.value;  
34.     e.value = value;  
35.     return old;  
36.     \}  
37. \}  
38.   
39. modCount++;  
40.        //元素数量超过阀值，需要增大散列表的大小  
41. if (count >= threshold) \{  
42.     // Rehash the table if the threshold is exceeded  
43.     rehash();  
44.   
45.            tab = table;  
46.            index = (hash & 0x7FFFFFFF) % tab.length;  
47. \}  
48.   
49. // Creates the new entry.  
50. Entry<K,V> e = tab\[index\];  
51. tab\[index\] = new Entry<K,V>(hash, key, value, e);  
52. count++;  
53. return null;  
54.    \}

可以看到，Hashtable的方法都是声明为synchronized的，这样就能够保证Hashtable是线程安全的。 Hashtable的内部结构如下图所示：

![16df2026-761e-3028-89b1-8d90e3685aa5.png][]

Hashtable在put元素时，会根据定义的方法计算hash值，如果这个位置没有元素，直接添加，如d1，如果已经有元素，会按照链表的方式将元素插在链表的头部，如aa。

再来看第二个问题： ConcurrentHashMap怎样实现线程安全？为什么性能会比Hashtable好？

1，下面是ConcurrentHashMap的put方法

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  // ConcurrentHashMap的key 跟 value都不能是null   
2.  public V put(K key, V value) \{  
3.          if (value == null)  
4.              throw new NullPointerException();  
5.          int hash = hash(key.hashCode());  
6.          return segmentFor(hash).put(key, hash, value, false);  
7.      \}

好的hash算法很重要（对于Hashtable，HashMap等也同样），如果冲突的概率大，会严重影响性能，下面是ConcurrentHashMap的hash算法，不过为什么会冲突较小就不明白了![皱眉][smiley-frown.gif]，望高手解决

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  private static int hash(int h) \{  
2.        // Spread bits to regularize both segment and index locations,  
3.        // using variant of single-word Wang/Jenkins hash.  
4.        h += (h <<  15) ^ 0xffffcd7d;  
5.        h ^= (h >>> 10);  
6.        h += (h <<   3);  
7.        h ^= (h >>>  6);  
8.        h += (h <<   2) + (h << 14);  
9.        return h ^ (h >>> 16);  
10.   \}  
11.   
12.   /\*\* 
13.    \* Returns the segment that should be used for key with given hash 
14.    \* @param hash the hash code for the key 
15.    \* @return the segment 
16.    \*/  
17.   final Segment<K,V> segmentFor(int hash) \{  
18.       return segments\[(hash >>> segmentShift) & segmentMask\];  
19.   \}

在segmentFor的方法中，变量segmentShift和segmentMask在创建ConcurrentHashMap的时候初始化, 如下所示

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  //initialCapacity： 初始容量大小，默认为16  
2.  //loadFactor： 跟threshold的值相关，控制是否需要扩容的阀门值，默认为0.75f  
3.  //concurrencyLevel： the estimated number of concurrently updating threads， 跟Segment数组大小相关，默认为16  
4.  public ConcurrentHashMap(int initialCapacity,  
5.                               float loadFactor, int concurrencyLevel) \{  
6.          if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)  
7.              throw new IllegalArgumentException();  
8.    
9.          if (concurrencyLevel > MAX\_SEGMENTS)  
10.             concurrencyLevel = MAX\_SEGMENTS;  
11.   
12.         // Find power-of-two sizes best matching arguments  
13.         int sshift = 0;  
14.         int ssize = 1;  
15.         while (ssize < concurrencyLevel) \{  
16.             ++sshift;  
17.             ssize <<= 1;   //获取不小于concurrencyLevel的最小的2的幂，跟segmentFor计算相关  
18.         \}  
19.         segmentShift = 32 - sshift;  
20.         segmentMask = ssize - 1; //二进制的低位都为1，在segmentFor方法中，保证(hash >>> segmentShift) & segmentMask结果在0～ssize-1之间（很好的算法，比求模的运算效率高）  
21.         this.segments = Segment.newArray(ssize);  
22.   
23.         if (initialCapacity > MAXIMUM\_CAPACITY)  
24.             initialCapacity = MAXIMUM\_CAPACITY;  
25.         int c = initialCapacity / ssize;  
26.         if (c \* ssize < initialCapacity)  
27.             ++c;  
28.         int cap = 1;  
29.         while (cap < c)  
30.             cap <<= 1;  
31.   
32.         for (int i = 0; i < this.segments.length; ++i)  
33.             this.segments\[i\] = new Segment<K,V>(cap, loadFactor);  
34.     \}

如果使用默认的参数构造ConcurrentHashMap，即initialCapacity=16，loadFactor=0.75f，concurrencyLevel=16， 得到的ssize=16，sshift=4， segmentMask=15， Segment数组长度为16。在表达式(hash >>> segmentShift) & segmentMask中，segmentMask的二进制为 00000000  00000000  00000000  00001111，通过位与运算得到的结果范围为0～15，相比Hashtable的模运算，效率更高。 但是可能会有疑问，为何需要保证ssize为2的幂？如果ssize不是2的幂，得到的segmentMask低位不是全部为1，比如ssize=14，segmentMask=13，二进制为00000000  00000000  00000000  00001101，此时位与运算肯定无法得到索引为 00000000  00000000  00000000  0000\*\*1\*的数值，比如2、3、6、7、10、11、14，会导致Segment数组的利用率低，产生较大的hash冲突。

再来看下Segment的put方法

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  V put(K key, int hash, V value, boolean onlyIfAbsent) \{  
2.             lock();  
3.             try \{  
4.                 int c = count;  
5.                 // 判断是否需要扩容  
6.                 if (c++ > threshold) // ensure capacity  
7.                     rehash();  
8.                 HashEntry<K,V>\[\] tab = table;  
9.                 int index = hash & (tab.length - 1);  
10.                HashEntry<K,V> first = tab\[index\];  
11.                HashEntry<K,V> e = first;  
12.                while (e != null && (e.hash != hash || !key.equals(e.key)))  
13.                    e = e.next;  
14.   
15.                V oldValue;  
16.                if (e != null) \{  
17.                    oldValue = e.value;  
18.                    if (!onlyIfAbsent)  
19.                        e.value = value;  
20.                \}  
21.                else \{  
22.                    oldValue = null;  
23.                    ++modCount;  
24.                    tab\[index\] = new HashEntry<K,V>(key, hash, first, value);  
25.                    count = c; // write-volatile  
26.                \}  
27.                return oldValue;  
28.            \} finally \{  
29.                unlock();  
30.            \}  
31.        \}

在put方法中，使用ReentrantLock的 lock()和unlock（）方法控制同步，Segment的定义如下

Java代码   [![收藏代码][icon_star.png]][icon_star.png 1]

1.  /\*\* 
2.       \* Segments are specialized versions of hash tables.  This 
3.       \* subclasses from ReentrantLock opportunistically, just to 
4.       \* simplify some locking and avoid separate construction. 
5.       \*/  
6.      static final class Segment<K,V> extends ReentrantLock implements Serializable

从上面代码可知，ConcurrentHashMap在并发修改时，锁住的是当前Segment的对象，其它Segment中的并发操作可以同时执行，性能会比使用Hashtable好。 ConcurrentHashMap的结构如下所示：

![a2be1d2b-c660-35c3-bdda-af20351966d9.png][]

看到 [ kidneyball][kidneyball] 分析的一段话，写得很好，哈哈，就搬过来了（勿怪）。

Q：  Hashtable，ConcurrentHashMap 有什么区别，这两个都是hash表，都是同步的

A：  Hashtable的任何操作都会把整个表锁住，是阻塞的。好处是总能获取最实时的更新，比如说线程A调用putAll写入大量数据，期间线程B调用get，线程B就会被阻塞，直到线程A完成putAll，因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队，效率较低。  
     ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高。坏处 是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据，期间线程B调用get，则只能get到目前为止已经顺利插入的部分 数据。此外，使用默认构造器创建的ConcurrentHashMap比较占内存，如果程序需要创建巨量ConcurrentHashMap，应该在构造 时指定concurrencyLevel （详情参考 [ http://ria101.wordpress.com/2011/12/12/concurrenthashmap-avoid-a-common-misuse/][http_ria101.wordpress.com_2011_12_12_concurrenthashmap-avoid-a-common-misuse] ）。

[icon_star.png]: http://pi88dian88.iteye.com/images/icon_star.png
[icon_star.png 1]: /images/20220616/ea3d50498a9142eea849cdeabb7cdc33.png
[16df2026-761e-3028-89b1-8d90e3685aa5.png]: /images/20220616/2199604100c94995a05d662f8f2821cf.png
[smiley-frown.gif]: /images/20220616/2c8d4c5072bc4c2590cb842937b2cfd1.png
[a2be1d2b-c660-35c3-bdda-af20351966d9.png]: /images/20220616/5de39a65faf44db88d6d3ee133cf06b1.png
[kidneyball]: http://kidneyball.iteye.com/
[http_ria101.wordpress.com_2011_12_12_concurrenthashmap-avoid-a-common-misuse]: http://ria101.wordpress.com/2011/12/12/concurrenthashmap-avoid-a-common-misuse/