HashMap和ConcurrentHashMap

我会带着你远行 2022-09-26 14:56 218阅读 0赞

**[http://blog.csdn.net/zldeng19840111/article/details/6703104][http_blog.csdn.net_zldeng19840111_article_details_6703104]**

**HashMap**

hashmap本质数据加链表。根据key取得hash值，然后计算出数组下标，如果多个key对应到同一个下标，就用链表串起来，新插入的在前面。

看3段重要代码摘要：

a：

**\[java\]** [view plain][] [copy][view plain]

1.  **public** HashMap(**int** initialCapacity, **float** loadFactor) \{ 
2.  **int** capacity = 1; 
3.  **while** (capacity < initialCapacity) 
4.   capacity <<= 1; 
5.  
6.  **this**.loadFactor = loadFactor; 
7.   threshold = (**int**)(capacity \* loadFactor); 
8.   table = **new** Entry\[capacity\]; 
9.   init(); 
10. \}

有3个关键参数：  
capacity：容量，就是数组大小  
loadFactor：比例，用于扩容  
threshold:=capacity\*loadFactor 最多容纳的Entry数，如果当前元素个数多于这个就要扩容（capacity扩大为原来的2倍）

**\[java\]** [view plain][] [copy][view plain]

1.  **public** V get(Object key) \{ 
2.  **if** (key == **null**) 
3.  **return** getForNullKey(); 
4.  **int** hash = hash(key.hashCode()); 
5.  **for** (Entry<K,V> e = table\[indexFor(hash, table.length)\]; 
6.   e != **null**; 
7.   e = e.next) \{ 
8.   Object k; 
9.  **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
10. **return** e.value; 
11.  \} 
12. **return****null**; 
13. \}

根据key算hash值，再根据hash值取得数组下标，通过数组下标取出链表，遍历链表用equals取出对应key的value。

**\[java\]** [view plain][] [copy][view plain]

1.  **public** V put(K key, V value) \{ 
2.  **if** (key == **null**) 
3.  **return** putForNullKey(value); 
4.  **int** hash = hash(key.hashCode()); 
5.  **int** i = indexFor(hash, table.length); 
6.  **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{ 
7.   Object k; 
8.  **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{ 
9.   V oldValue = e.value; 
10.  e.value = value; 
11.  e.recordAccess(**this**); 
12. **return** oldValue; 
13.  \} 
14.  \} 
15. 
16.  modCount++; 
17.  addEntry(hash, key, value, i); 
18. **return****null**; 
19.  \}

从数组（通过hash值）取得链表头，然后通过equals比较key，如果相同，就覆盖老的值，并返回老的值。（该key在hashmap中已存在）

否则新增一个entry，返回null。新增的元素为链表头，以前相同数组位置的挂在后面。

另外：modCount是为了避免读取一批数据时，在循环读取的过程中发生了修改，就抛异常

if (modCount != expectedModCount)  
throw new ConcurrentModificationException();

下面看添加一个map元素

**\[html\]** [view plain][] [copy][view plain]

1.  void addEntry(int hash, K key, V value, int bucketIndex) \{ 
2.   Entry**<****K**,V**>**e = table\[bucketIndex\]; 
3.   table\[bucketIndex\] = new Entry**<****K**,V**>**(hash, key, value, e); 
4.   if (size++ **>**= threshold) 
5.   resize(2 \* table.length); 
6.  \}

新增后，如果发现size大于threshold了，就resize到原来的2倍

**\[java\]** [view plain][] [copy][view plain]

1.  **void** resize(**int** newCapacity) \{ 
2.  
3.   Entry\[\] newTable = **new** Entry\[newCapacity\]; 
4.   transfer(newTable); 
5.   table = newTable; 
6.   threshold = (**int**)(newCapacity \* loadFactor); 
7.  \}

新建一个数组，并将原来数据转移过去

**\[java\]** [view plain][] [copy][view plain]

1.  **void** transfer(Entry\[\] newTable) \{ 
2.   Entry\[\] src = table; 
3.  **int** newCapacity = newTable.length; 
4.  **for** (**int** j = 0; j < src.length; j++) \{ 
5.   Entry<K,V> e = src\[j\]; 
6.  **if** (e != **null**) \{ 
7.   src\[j\] = **null**; 
8.  **do** \{ 
9.   Entry<K,V> next = e.next; 
10. **int** i = indexFor(e.hash, newCapacity); 
11.  e.next = newTable\[i\]; 
12.  newTable\[i\] = e; 
13.  e = next; 
14.  \} **while** (e != **null**); 
15.  \} 
16.  \} 
17.  \}

将原来数组中的链表一个个取出，然后遍历链表中每个元素，重新计算index并放入新数组。每个处理的也放链表头。

在取出原来数组链表后，将原来数组置空（为了大数据量复制时更快的被垃圾回收？）

还有两点注意：

static class Entry<K,V> implements Map.Entry<K,V>是hashmap的静态内部类，iterator之类的是内部类，因为不是每个元素都需要持有map的this指针。

HashMap把 transient Entry\[\] table;等变量置为transient，然后override了readObject和writeObject，自己实现序列化。

**ConcurrentHashMap：**

在hashMap的基础上，ConcurrentHashMap将数据分为多个segment，默认16个（concurrency level），然后每次操作对一个segment加锁，避免多线程锁得几率，提高并发效率。

**\[java\]** [view plain][] [copy][view plain]

1.  **public** V get(Object key) \{ 
2.  **int** hash = hash(key.hashCode()); 
3.  **return** segmentFor(hash).get(key, hash); 
4.   \} 
5.  
6.  **final** Segment<K,V> segmentFor(**int** hash) \{ 
7.  **return** segments\[(hash >>> segmentShift) & segmentMask\]; 
8.   \}

in class Segment：

**\[java\]** [view plain][] [copy][view plain]

1.  V get(Object key, **int** hash) \{ 
2.  **if** (count != 0) \{ // read-volatile
3.   HashEntry<K,V> e = getFirst(hash); 
4.  **while** (e != **null**) \{ 
5.  **if** (e.hash == hash && key.equals(e.key)) \{ 
6.   V v = e.value; 
7.  **if** (v != **null**) 
8.  **return** v; 
9.  **return** readValueUnderLock(e); // recheck
10.  \} 
11.  e = e.next; 
12.  \} 
13.  \} 
14. **return****null**; 
15.  \}

**\[java\]** [view plain][] [copy][view plain]

1.  /\*\*
2.   \* Reads value field of an entry under lock. Called if value
3.   \* field ever appears to be null. This is possible only if a
4.   \* compiler happens to reorder a HashEntry initialization with
5.   \* its table assignment, which is legal under memory model
6.   \* but is not known to ever occur.
7.   \*/
8.   V readValueUnderLock(HashEntry<K,V> e) \{ 
9.   lock(); 
10. **try** \{ 
11. **return** e.value; 
12.  \} **finally** \{ 
13.  unlock(); 
14.  \} 
15.  \}

注意，这里在并发读取时，除了key对应的value为null之外，并没有使用锁，如何做到没有问题的呢，有以下3点：  
1. HashEntry<K,V> getFirst(int hash) \{  
HashEntry<K,V>\[\] tab = table;  
return tab\[hash & (tab.length - 1)\];  
\}  
这里如果在读取时数组大小（tab.length）发生变化，是会导致数据不对的，但transient volatile HashEntry<K,V>\[\] table;是volatile得，数组大小变化能立刻知道

2. static final class HashEntry<K,V> \{  
final K key;  
final int hash;  
volatile V value;  
final HashEntry<K,V> next;  
这里next是final的，就保证了一旦HashEntry取出来，整个链表就是正确的。

3.value是volatile的，保证了如果有put覆盖，是可以立刻看到的。

**\[html\]** [view plain][] [copy][view plain]

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

这里除了加锁操作，其他和普通HashMap原理上无太大区别。

还有一点不理解的地方：

对于get和put/remove并发发生的时候，如果get的HashEntry<K,V> e = getFirst(hash);链表已经取出来了，这个时候put放入一个entry到链表头，如果正好是需要取的key，是否还是会取不出来？

remove时，会先去除需要remove的key，然后把remove的key前面的元素一个个接到链表头，同样也存在remove后，以前的head到了中间，也会漏掉读取的元素。

**\[java\]** [view plain][] [copy][view plain]

1.  \++modCount; 
2.   HashEntry<K,V> newFirst = e.next; 
3.  **for** (HashEntry<K,V> p = first; p != e; p = p.next) 
4.   newFirst = **new** HashEntry<K,V>(p.key, p.hash, 
5.   newFirst, p.value); 
6.   tab\[index\] = newFirst; 
7.   count = c; // write-volatile

[http_blog.csdn.net_zldeng19840111_article_details_6703104]: http://blog.csdn.net/zldeng19840111/article/details/6703104
[view plain]: http://blog.csdn.net/zldeng19840111/article/details/6703104#