HashMap和ConcurrentHashMap源码学习

开篇:之前在从事传统软件开发时,使用最多的是HashMap进行存储。到了互联网公司之后发现许多map都为CouncurrentHashMap所以想研究明白。

 

经过查看源码可知:

HashMap

其实是对一个Entry类型的数组进行操作,所有的get、put、remove都是通过二次HASH后定位进行链表操作。当然也是非线程安全的。

put

 

[java] view plaincopy

  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.         modCount++;
  16.         addEntry(hash, key, value, i);
  17.         return null;
  18.     }

 

get

 

[java] view plaincopy

  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.     }

迭代

 

 

[java] view plaincopy

  1. final Entry<K,V> nextEntry() {
  2.             if (modCount != expectedModCount)
  3.                 throw new ConcurrentModificationException();
  4.             Entry<K,V> e = next;
  5.             if (e == null)
  6.                 throw new NoSuchElementException();
  7.             if ((next = e.next) == null) {
  8.                 Entry[] t = table;
  9.                 while (index < t.length && (next = t[index++]) == null)
  10.                     ;
  11.             }
  12.         current = e;
  13.             return e;
  14.         }

从nextEntry代码可以看出在迭代开始时会对expectedModCount进行赋值,如果在迭代期间发生结构性变化,会抛出ConcurrentModificationException。

 

另外put、remove、 未加任何锁。 所以在高并发环境下是没有保证的。

 

注:HashTable,单纯的对put 、get、remove进行syncronized进行同步,大大降低效率。

 

ConcurrentHashMap

学习内容引用 http://www.iteye.com/topic/344876

首先通过源码学习了ConcurrentHashMap的实现

ConcurrentHashMap实现思路是对HashEntry[] 进行分段。进行结构性调整操作时如put、remove只会锁住本段对象。

 

 

[java] view plaincopy

  1. /**
  2.      * The default initial capacity for this table,
  3.      * used when not otherwise specified in a constructor.
  4.      */
  5.     static final int DEFAULT_INITIAL_CAPACITY = 16;
  6.     /**
  7.      * The default load factor for this table, used when not
  8.      * otherwise specified in a constructor.
  9.      */
  10.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  11.     /**
  12.      * The default concurrency level for this table, used when not
  13.      * otherwise specified in a constructor.
  14.      */
  15.     static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  16.     /**
  17.      * The maximum capacity, used if a higher value is implicitly
  18.      * specified by either of the constructors with arguments.  MUST
  19.      * be a power of two <= 1<<30 to ensure that entries are indexable
  20.      * using ints.
  21.      */
  22.     static final int MAXIMUM_CAPACITY = 1 << 30;
  23.     /**
  24.      * The maximum number of segments to allow; used to bound
  25.      * constructor arguments.
  26.      */
  27.     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
  28.     /**
  29.      * Number of unsynchronized retries in size and containsValue
  30.      * methods before resorting to locking. This is used to avoid
  31.      * unbounded retries if tables undergo continuous modification
  32.      * which would make it impossible to obtain an accurate result.
  33.      */
  34.     static final int RETRIES_BEFORE_LOCK = 2;

常量定义:默认容量16、默认负载因子0.75、默认并发级别、最大容量2^30、最大并发段2^16。

 

 

[java] view plaincopy

  1. final int segmentMask;
  2.     /**
  3.      * Shift value for indexing within segments.
  4.      */
  5.     final int segmentShift;
  6.     /**
  7.      * The segments, each of which is a specialized hash table
  8.      */
  9.     final Segment<K,V>[] segments;

Segment<K,V>[] 段的数组。segmentMash段的数组下标长度。

 

 

segment常量

 

[java] view plaincopy

  1. transient volatile int count;
  2.        /**
  3.         * Number of updates that alter the size of the table. This is
  4.         * used during bulk-read methods to make sure they see a
  5.         * consistent snapshot: If modCounts change during a traversal
  6.         * of segments computing size or checking containsValue, then
  7.         * we might have an inconsistent view of state so (usually)
  8.         * must retry.
  9.         */
  10.        transient int modCount;
  11.        /**
  12.         * The table is rehashed when its size exceeds this threshold.
  13.         * (The value of this field is always <tt>(int)(capacity *
  14.         * loadFactor)</tt>.)
  15.         */
  16.        transient int threshold;
  17.        /**
  18.         * The per-segment table.
  19.         */
  20.        transient volatile HashEntry<K,V>[] table;
  21.        /**
  22.         * The load factor for the hash table.  Even though this value
  23.         * is same for all segments, it is replicated to avoid needing
  24.         * links to outer object.
  25.         * @serial
  26.         */
  27.        final float loadFactor;

 

put操作

 

[java] view plaincopy

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

put操作首先会对容量进行校验,然后查找是否有相同key的值,如果存在在根据需要是否替换旧值,如果不存在则新增,整个过程是加锁状态进行。

 

并且put是直接把HashEntry放到链首。

注:count是volatile的,并且对count的赋值一定要在操作的最后,以保证读取count总是最新的。

引:写volatile变量和它之前的读写操作是不能reorder的,读volatile变量和它之后的读写操作也是不能reorder的。
修改modCount发生在修改count之前,由于count是volatile变量,修改modCount不能和写count的操作reorder,读取count和它之后的操作,比如读取modCount,不能reorder。有了这两个不能reorder才能保证读取了count之后,能读到线程在写count之前的写入的modCount值,这个modCount值是几乎最新的。
如果在读modCount之前不读count,读modCount甚至可能会reorder到写modCount之前。

用reorder解释总是太复杂了,不如用happens-before来得简洁。当一个线程I对count的读时,它读到的值必定是另一个线程,假设是线程II,最近对count的写。这个两个操作存在happens-before关系,即线程II对count的写happens-before线程I对count的读,记作:II:W(count) < I:R(count)。单线程的happens-before规则,又有II:W(modCount) < II:W(count)(查看源代码会发现在写count之前必定有写modCount),以及 I:R(count) < I:R(modCount),根据传递规则有,II:W(modCount) < I:R(modCount),这就是说线程I至少能够读取到线程II写count之前的modCount值。我曾经写了一篇关于happens-before的文章,有些表达可能有误,但大致还是对的,http://www.iteye.com/topic/260515。

 

containsValue

 

[java] view plaincopy

  1. public boolean containsValue(Object value) {
  2.         if (value == null)
  3.             throw new NullPointerException();
  4.         // See explanation of modCount use above
  5.         final Segment<K,V>[] segments = this.segments;
  6.         int[] mc = new int[segments.length];
  7.         // Try a few times without locking
  8.         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
  9.             int sum = 0;
  10.             int mcsum = 0;
  11.             for (int i = 0; i < segments.length; ++i) {
  12.                 int c = segments[i].count;
  13.                 mcsum += mc[i] = segments[i].modCount;
  14.                 if (segments[i].containsValue(value))
  15.                     return true;
  16.             }
  17.             boolean cleanSweep = true;
  18.             if (mcsum != 0) {
  19.                 for (int i = 0; i < segments.length; ++i) {
  20.                     int c = segments[i].count;
  21.                     if (mc[i] != segments[i].modCount) {
  22.                         cleanSweep = false;
  23.                         break;
  24.                     }
  25.                 }
  26.             }
  27.             if (cleanSweep)
  28.                 return false;
  29.         }
  30.         // Resort to locking all segments
  31.         for (int i = 0; i < segments.length; ++i)
  32.             segments[i].lock();
  33.         boolean found = false;
  34.         try {
  35.             for (int i = 0; i < segments.length; ++i) {
  36.                 if (segments[i].containsValue(value)) {
  37.                     found = true;
  38.                     break;
  39.                 }
  40.             }
  41.         } finally {
  42.             for (int i = 0; i < segments.length; ++i)
  43.                 segments[i].unlock();
  44.         }
  45.         return found;
  46.     }

 

为了取到最新的modCount 必须在读取前获取count。原因参考上面的引。

判断是否包含某value时,进行2次尝试,如果中间存在修改。则加锁在判断一次。

 

remove

 

[java] view plaincopy

  1. V remove(Object key, int hash, Object value) {
  2.             lock();
  3.             try {
  4.                 int c = count – 1;
  5.                 HashEntry<K,V>[] tab = table;
  6.                 int index = hash & (tab.length – 1);
  7.                 HashEntry<K,V> first = tab[index];
  8.                 HashEntry<K,V> e = first;
  9.                 while (e != null && (e.hash != hash || !key.equals(e.key)))
  10.                     e = e.next;
  11.                 V oldValue = null;
  12.                 if (e != null) {
  13.                     V v = e.value;
  14.                     if (value == null || value.equals(v)) {
  15.                         oldValue = v;
  16.                         // All entries following removed node can stay
  17.                         // in list, but all preceding ones need to be
  18.                         // cloned.
  19.                         ++modCount;
  20.                         HashEntry<K,V> newFirst = e.next;
  21.                         for (HashEntry<K,V> p = first; p != e; p = p.next)
  22.                             newFirst = new HashEntry<K,V>(p.key, p.hash,
  23.                                                           newFirst, p.value);
  24.                         tab[index] = newFirst;
  25.                         count = c; // write-volatile
  26.                     }
  27.                 }
  28.                 return oldValue;
  29.             } finally {
  30.                 unlock();
  31.             }
  32.         }

删除节点:由于HashEntry的next节点为fina引用l不可修改,所以当删除节点时候被删除节点之前的节点都要复制一遍。

 

为什么要定义成FINAL:网上有解释为 因为next属性为final的,不可以被重置。直接删除,就无法保持链结果的连续性了。 这点我不太理解。因为删除操作加锁了并发不会出现问题。这块有待研究。

标签