转载

使用HashMap的时候小心点

Map家族介绍

我们都知道 HashMap 是线程不安全的，但是 HashMap 的使用频率在所有 Map 中确实属于比较高的。因为它可以满足我们大多数的场景了。

看一眼Map家族的关系图：

使用HashMap的时候小心点

Map 是一个接口，我们常用的实现类有 HashMap 、 LinkedHashMap 、 TreeMap ， HashTable 。

HashMap

HashMap 根据 key 的·值来保存value，需要注意的是， HashMap 不保证遍历的顺序和插入的顺序是一致的。 HashMap 允许有一条记录的 key 为 null ，但是对值是否为 null 不做要求。

HashTable

HashTable 类是线程安全的，它使用 synchronize 来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下 hashtable 的效率是比较低下的。因为当一个线程访问 hashtable 的同步方法时，其他线程再次尝试访问的时候，会进入阻塞或者轮询状态，比如当线程1使用put进行元素添加的时候，线程2不但不能使用put来添加元素，而且不能使用get获取元素。所以，竞争会越来越激烈。相比之下， ConcurrentHashMap 使用了分段锁技术来提高了并发度，不在同一段的数据互相不影响，多个线程对多个不同的段的操作是不会相互影响的。每个段使用一把锁。所以在需要线程安全的业务场景下，推荐使用 ConcurrentHashMap ，而 HashTable 不建议在新的代码中使用，如果需要线程安全，则使用 ConcurrentHashMap ，否则使用 HashMap 就足够了。

LinkedHashMap

LinkedHashMap 属于 HashMap 的子类，与 HashMap 的区别在于 LinkedHashMap 保存了记录插入的顺序。

TreeMap

TreeMap 实现了 SortedMap 接口， TreeMap 有能力对插入的记录根据 key 排序，默认按照升序排序，也可以自定义比较强，在使用 TreeMap 的时候， key 应当实现 Comparable 。

HashMap的实现

Java7 和 Java7 在实现 HashMap 上有所区别，当然 Java7 的效率要更好一些，主要是 Java7 的 HashMap 在 Java7 的基础上增加了红黑树这种数据结构，使得在桶里面查找数据的复杂度从 O(n) 降到 O(logn) ，当然还有一些其他的优化，比如 resize 的优化等。介于 Java7 的 HashMap 较为复杂，本文将基于 Java7 的 HashMap 实现来说明，主要的实现部分还是一致的， Java7 的实现上主要是做了一些优化，内容还是没有变化的，依然是线程不安全的。 HashMap 的实现使用了一个数组，每个数组项里面有一个链表的方式来实现，因为 HashMap 使用 key 的 hashCode 来寻找存储位置，不同的 key 可能具有相同的 hashCode ，这时候就出现哈希冲突了，也叫做哈希碰撞，为了解决哈希冲突，有开放地址方法，以及链地址方法。 HashMap 的实现上选取了链地址方法，也就是将哈希值一样的 entry 保存在同一个数组项里面，可以把一个数组项当做一个桶，桶里面装的 entry 的 key 的 hashCode 是一样的。

使用HashMap的时候小心点

上面的图片展示了我们的描述，其中有一个非常重要的数据结构 Node<K,V> ，这就是实际保存我们的 key-value 对的数据结构，下面是这个数据结构的主要内容：

final int hash;  
final K key;  
V value;  
Node<K,V> next;

一个 Node 就是一个链表节点，也就是我们插入的一条记录，明白了 HashMap 使用链地址方法来解决哈希冲突之后，我们就不难理解上面的数据结构， hash 字段用来定位桶的索引位置， key 和 value 就是我们的数据内容，需要注意的是，我们的 key 是 final 的，也就是不允许更改，这也好理解，因为 HashMap 使用 key 的 hashCode 来寻找桶的索引位置，一旦key被改变了，那么 key 的 hashCode 很可能就会改变了，所以随意改变key会使得我们丢失记录（无法找到记录）。 next 字段指向链表的下一个节点。

HashMap 的初始桶的数量为 16 ， loadFact 为 0.75 ,当桶里面的数据记录超过阈值的时候， HashMap 将会进行扩容则操作，每次都会变为原来大小的 2倍 ，直到设定的最大值之后就无法再 resize 了。

下面对 HashMap 的实现做简单的介绍，具体实现还得看代码，对于 Java7 中的 HashMap 实现，还需要能理解红黑树这种数据结构。

1、根据 key 的 hashCode 来决定应该将该记录放在哪个桶里面，无论是插入、查找还是删除，这都是第一步，计算桶的位置。因为 HashMap 的 length 总是 2的n 次幂，所以可以使用下面的方法来做模运算：

h & (length-1)

h 是 key 的 hashCode 值，计算好 hashCode 之后，使用上面的方法来对桶的数量取模，将这个数据记录落到某一个桶里面。当然取模是 Java7 中的做法， Java7 进行了优化，做得更加巧妙，因为我们的 length 总是 2的n 次幂，所以在一次 resize 之后，当前位置的记录要么保持当前位置不变，要么就向前移动 length 就可以了。所以 Java7 中的 HashMap 的 resize 不需要重新计算 hashCode 。我们可以通过观察java7中的计算方法来抽象出算法，然后进行优化，具体的细节看代码就可以了。

2、 HashMap 的 put 方法

使用HashMap的时候小心点

上图展示了 Java7 中 put 方法的处理逻辑，比 Java7 多了红黑树部分，以及在一些细节上的优化， put 逻辑和 Java7 中是一致的。

3、 resize 机制

HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。后面会讲到，HashMap之所以线程不安全，就是resize这里出的问题。

为什么HashMap线程不安全？

上面说到， HashMap 会进行 resize 操作，在 resize 操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。

1、put的时候导致的多线程数据不一致。这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个 key-value 对到 HashMap 中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%），具体分析如下：

下面的代码是resize的核心内容：

void transfer(Entry[] newTable, boolean rehash) {  
    int newCapacity = newTable.length;  
    for (Entry<K,V> e : table) {  
        while(null != e) {  
            Entry<K,V> next = e.next;           
            if (rehash) {  
                e.hash = null == e.key ? 0 : hash(e.key);  
            }  
            int i = indexFor(e.hash, newCapacity);   
            e.next = newTable[i];  
            newTable[i] = e;  
            e = next;  
        } 
    }  
}

这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。

使用HashMap的时候小心点

多线程HashMap的resize：我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为： [3,A] ， [7,B] ， [5,C] ，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。假设线程thread1执行到了 transfer 方法的 Entry next = e.next 这一句，然后时间片用完了，此时的 e = [3,A] , next = [7,B] 。线程 thread2 被调度执行并且顺利完成了 resize 操作，需要注意的是，此时的 [7,B] 的 next 为 [3,A] 。此时线程 thread1 重新被调度运行，此时的 thread1 持有的引用是已经被 thread2 resize 之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理 [7,B] ，而 [7,B] 被链接到了 [3,A] 的后面，处理完 [7,B] 之后，就需要处理 [7,B] 的 next 了啊，而通过 thread2 的 resize 之后， [7,B] 的 next 变为了 [3,A] ，此时， [3,A] 和 [7,B] 形成了环形链表，在 get 的时候，如果 get 的 key 的桶索引和 [3,A] 和 [7,B] 一样，那么就会陷入死循环。