HashMap跟ConcurrentHashMap浅析

HashMap和ConcurrentHashMap浅析

HashMap

?

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

看3段重要代码摘要：

a：

public HashMap(int initialCapacity, float loadFactor) { int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }

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

b:

public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }

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

c:

public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

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

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

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

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

下面看添加一个map元素

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

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

void resize(int newCapacity) { Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }

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

void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }

将原来数组中的链表一个个取出，然后遍历链表中每个元素，重新计算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加锁，避免多线程锁得几率，提高并发效率。

public V get(Object key) { int hash = hash(key.hashCode()); return segmentFor(hash).get(key, hash); } final Segment<K,V> segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask]; }

?

in class Segment：

V get(Object key, int hash) { if (count != 0) { // read-volatile HashEntry<K,V> e = getFirst(hash); while (e != null) { if (e.hash == hash && key.equals(e.key)) { V v = e.value; if (v != null) return v; return readValueUnderLock(e); // recheck } e = e.next; } } return null; } /** * Reads value field of an entry under lock. Called if value * field ever appears to be null. This is possible only if a * compiler happens to reorder a HashEntry initialization with * its table assignment, which is legal under memory model * but is not known to ever occur. */ V readValueUnderLock(HashEntry<K,V> e) { lock(); try { return e.value; } finally { unlock(); } }

?

注意，这里在并发读取时，除了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覆盖，是可以立刻看到的。

?

?

public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); } V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c = count; if (c++ > threshold) // ensure capacity rehash(); HashEntry<K,V>[] tab = table; int index = hash & (tab.length - 1); HashEntry<K,V> first = tab[index]; HashEntry<K,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue; if (e != null) { oldValue = e.value; if (!onlyIfAbsent) e.value = value; } else { oldValue = null; ++modCount; tab[index] = new HashEntry<K,V>(key, hash, first, value); count = c; // write-volatile } return oldValue; } finally { unlock(); } }

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

?

?

还有一点不理解的地方：

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

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

++modCount; HashEntry<K,V> newFirst = e.next; for (HashEntry<K,V> p = first; p != e; p = p.next) newFirst = new HashEntry<K,V>(p.key, p.hash, newFirst, p.value); tab[index] = newFirst; count = c; // write-volatile

?

?

?