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