首页 > Java开发 > HashMap和ConcurrentHashMap源码学习

HashMap和ConcurrentHashMap源码学习

孤风一剑 5月 24, 2013 270 0

开篇：之前在从事传统软件开发时，使用最多的是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.         }
  16.         modCount++;
  17.         addEntry(hash, key, value, i);
  18.         return null;
  19.     }

 

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();
  8.             if ((next = e.next) == null) {
  9.                 Entry[] t = table;
  10.                 while (index < t.length && (next = t[index++]) == null)
  11.                     ;
  12.             }
  13.         current = e;
  14.             return e;
  15.         }

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

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

 

 

[java] view plaincopy

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

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

 

 

segment常量

 

[java] view plaincopy

  1. transient volatile int count;
  3.        /**
  4.         * Number of updates that alter the size of the table. This is
  5.         * used during bulk-read methods to make sure they see a
  6.         * consistent snapshot: If modCounts change during a traversal
  7.         * of segments computing size or checking containsValue, then
  8.         * we might have an inconsistent view of state so (usually)
  9.         * must retry.
  10.         */
  11.        transient int modCount;
  13.        /**
  14.         * The table is rehashed when its size exceeds this threshold.
  15.         * (The value of this field is always <tt>(int)(capacity *
  16.         * loadFactor)</tt>.)
  17.         */
  18.        transient int threshold;
  20.        /**
  21.         * The per-segment table.
  22.         */
  23.        transient volatile HashEntry<K,V>[] table;
  25.        /**
  26.         * The load factor for the hash table.  Even though this value
  27.         * is same for all segments, it is replicated to avoid needing
  28.         * links to outer object.
  29.         * @serial
  30.         */
  31.        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;
  14.                 V oldValue;
  15.                 if (e != null) {
  16.                     oldValue = e.value;
  17.                     if (!onlyIfAbsent)
  18.                         e.value = value;
  19.                 }
  20.                 else {
  21.                     oldValue = null;
  22.                     ++modCount;
  23.                     tab[index] = new HashEntry<K,V>(key, hash, first, value);
  24.                     count = c; // write-volatile
  25.                 }
  26.                 return oldValue;
  27.             } finally {
  28.                 unlock();
  29.             }
  30.         }

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

 

为了取到最新的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;
  12.                 V oldValue = null;
  13.                 if (e != null) {
  14.                     V v = e.value;
  15.                     if (value == null || value.equals(v)) {
  16.                         oldValue = v;
  17.                         // All entries following removed node can stay
  18.                         // in list, but all preceding ones need to be
  19.                         // cloned.
  20.                         ++modCount;
  21.                         HashEntry<K,V> newFirst = e.next;
  22.                         for (HashEntry<K,V> p = first; p != e; p = p.next)
  23.                             newFirst = new HashEntry<K,V>(p.key, p.hash,
  24.                                                           newFirst, p.value);
  25.                         tab[index] = newFirst;
  26.                         count = c; // write-volatile
  27.                     }
  28.                 }
  29.                 return oldValue;
  30.             } finally {
  31.                 unlock();
  32.             }
  33.         }

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

 

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

标签

相关推荐

标签

.NET (32) ActiveMQ (34) AJAX (29) android (463) android开发 (34) ASP.NET (58) C# (153) CSS (21) eclipse (50) Hadoop (23) Hibernate (51) HTML (30) html5 (29) IOS (48) JAVA (378) JavaScript (87) JQuery (85) js (53) json (26) jsp (28) Linux (70) ListView (28) mvc (28) myeclipse (25) MySQL (151) oracle (181) PHP (158) spring (84) SQL (62) SQL Server (28) string (20) Struts2 (39) Tomcat (39) Ubuntu (20) WEB (28) webservice (29) Windows (27) XML (36) 多线程 (21) 存储过程 (22) 实例 (24) 数据库 (89) 服务器 (31) 算法 (34) 设计模式 (23)

文章归档