1.7 HashMap的线程不安全
所有人都知道HashMap是线程不安全的，我们应该使用ConcurrentHashMap。但是为什么HashMap是线程不安全的呢？
首先需要强调一点，HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，然而1.8中仍会有数据覆盖的问题，即在并发执行HashMap的put操作时会发生数据覆盖的情况。
首先扩容会造成HashMap的线程不安全，根源就在JDK1.7的transfer函数中。transfer方法将原有Entry数组的元素拷贝到新的Entry数组里。JDK1.7中HashMap的transfer函数源码如下：
void transfer(Entry[] newTable) { //src引用了旧的Entry数组 Entry[] src = table; int newCapacity = newTable.length; //遍历旧的Entry数组 for (int j = 0; j < src.length; j++) { //取得旧Entry数组的每个元素 Entry<K,V> e = src[j]; if (e != null) { src[j] = null; //释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象） do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); //重新计算每个元素在数组中的位置 e.next = newTable[i]; //标记[1] newTable[i] = e; //将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } } }
这段代码是HashMap的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是在多线程环境下会形成死循环的关键点。扩容造成死循环和数据丢失的详细过程这里不再赘述，可以搜索很多分析这个过程的文章。
JDK1.8的源码中已经没有transfer函数，因为JDK1.8直接在resize函数中完成了数据迁移。此外JDK1.8在进行元素插入时使用的是尾插法。为什么多线程环境下JDK1.8的HashMap会出现数据覆盖的情况呢，我们来看一下JDK1.8中的putVal源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //第一次put元素时，table数组为空，先调用resize生成一个指定容量的数组 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //hash值和n-1的与运算结果为桶的位置，如果该位置空就直接放置一个Node if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //如果计算出的bucket不空，即发生哈希冲突，就要进一下判断 else { Node<K,V> e; K k; //判断当前Node的key与要put的key是否相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断当前Node是否是红黑树的节点 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //以上都不是，说明要new一个Node，加入到链表中 else { for (int binCount = 0; ; ++binCount) { //进入这个if说明是到达链表尾部 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //在链表中继续判断是否已经存在完全相同的key if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //走到这里，说明本次put是更新一个已存在的键值对的value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //在hashMap中，afterNodeAccess方法体为空，交给子类去实现 afterNodeAccess(e); return oldValue; } } //下面两个自增操作都不是原子的 ++modCount; if (++size > threshold) resize(); //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现 afterNodeInsertion(evict); return null; }
其中if((p = tab[i = (n - 1) & hash]) == null)是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完这行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所以此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
除此之外，还有就是代码的末尾部分有个++size，我们这样想，还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的size大小为10，当线程A执行到size自增这行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，由于size不是volatile修改的变量，然后线程A再次拿到CPU后不会再从主内存中加载一次size的值，而是使用自己工作内存中的副本，继续执行加1，当执行完put操作后，还是将size=11写回主内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。
2、LinkedHashMap概述
HashMap是Java Collection Framework的重要成员，也是Map族中我们最为常用的一种。不过遗憾的是，HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序==。特别地，==该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
更直观地，下图很好地还原了LinkedHashMap的原貌：HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。
特别地，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，LinkedHashMap 也是 Map 的一个非同步的实现。此外，LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法。
2.1、LinkedHashMap定义及构造函数
本质上，HashMap和双向链表合二为一即是LinkedHashMap。JDK1.8中LinkedHashMap的定义源码如下：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * HashMap.Node subclass for normal LinkedHashMap entries. */ static class Entry<K,V> extends HashMap.Node<K,V> { //再加两个引用，分别指向前一个插入的Entry与后一个插入的Entry Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } /** * The head (eldest) of the doubly linked list. * 头节点引用 */ transient LinkedHashMap.Entry<K,V> head; /** * The tail (youngest) of the doubly linked list. * 尾节点引用 */ transient LinkedHashMap.Entry<K,V> tail; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * true表示按照访问顺序迭代，false时表示按照插入顺序 * @serial */ final boolean accessOrder; ... }
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了Entry。LinkedHashMap中的Entry继承了HashMap.Node，但增加了两个指针before 和 after，它们分别用于维护双向链接列表。特别需要注意的是，next用于维护HashMap各个Node的连接顺序，before、after用于维护Entry插入的先后顺序。
LinkedHashMap的5大构造函数都是在HashMap的构造函数的基础上实现的，分别如下：
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
2.2、LinkedHashMap的快速存取
在HashMap中最常用的两个操作就是：put(Key,Value) 和 get(Key)。同样地，在LinkedHashMap 中最常用的也是这两个操作。对于put(Key,Value)方法而言，LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法，只是对putVal(hash,key, value, onlyIfAbsent,evict)方法所调用的afterNodeAccess方法和afterNodeInsertion方法进行了重写；对于get(Key)方法，LinkedHashMap则直接对它进行了重写。下面我们结合JDK源码看 LinkedHashMap 的存取实现。
HashMap的putVal源码，上一节中已经分析过，直接来看LinkedHashMap对afterNodeAccess和afterNodeInsertion方法的实现：
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } /** * 如果map应该删除最老的节点，返回true * 这个方法在被put和putAll方法被调用，当向map中插入一个新的entry时被执行。这个方法提供了当一个新的entry被添加到linkedHashMap中，删除最老节点的机会。 * * 这个方法是很有用的，可以通过删除最老节点来减少内存消耗，避免溢出。 * * 简单的例子：这个方法的重写将map的最大值设为100，到100时，每次增一个entry，就删除一次最老节点。 * * private static final int MAX_ENTRIES = 100; * * protected boolean removeEldestEntry(Map.Entry eldest) { * return size() > MAX_ENTRIES; * } * * 这个方法一般不会直接修改map，而是通过返回true或者false来控制是否修改map。 * * * @param eldest 最老的节点（即头节点） * @return 如果map应该删除头节点就返回true，否则返回false */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
2.3、LinkedHashMap与LRU算法
到此为止，我们已经分析完了LinkedHashMap的存取实现，这与HashMap大体相同。LinkedHashMap区别于HashMap最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap增加了两个属性用于保证顺序，分别是双向链表头结点header和标志位accessOrder。我们知道，header是LinkedHashMap所维护的双向链表的头结点，而accessOrder用于决定具体的迭代顺序。
我们知道，当accessOrder标志位为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有判断accessOrder的值。如果accessOrder为true，put时将新插入的元素放入到双向链表的尾部，get时将当前访问的Entry移到双向链表的尾部。当标志位accessOrder的值为false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序。
测试代码
@Test public void testLinkedHashMap() { Map<String, String> map = new HashMap<>(128); System.out.println("------HashMap------"); map.put("first", "a"); map.put("second", "b"); map.put("third", "c"); map.put("fourth", "d"); map.put("fifth", "e"); map.put("sixth", "f"); map.forEach((key,value) -> { System.out.println("key=" + key + ",value=" + value); }); map.clear(); System.out.println("------LinkedHashMap------"); map = new LinkedHashMap<>(128); map.put("first", "a"); map.put("second", "b"); map.put("third", "c"); map.put("fourth", "d"); map.put("fifth", "e"); map.put("sixth", "f"); map.forEach((key,value) -> { System.out.println("key=" + key + ",value=" + value); }); }
运行结果如下，HashMap不保证有序而LinkedHashMap默认按迭代顺序和插入的顺序一致。
前面介绍的LinkedHashMap的五种构造方法，前四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的；而第五个构造方法可以自定义传入的accessOrder的值。当我们要用LinkedHashMap实现LRU算法时，就需要调用该构造方法并将accessOrder置为true。
使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾。这样，我们便把最近使用的Entry放入到了双向链表的后面。多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除最前面的Entry即可，因为它就是最近最少使用的Entry。
public class SomeTest { @Test public void testLru() { LRU<Character, Integer> lru = new LRU<>(8); String s = "abcdefghijkl"; for (int i = 0; i < s.length(); i++) { lru.put(s.charAt(i), i + 1); } System.out.println("LRU的大小： " + lru.size()); System.out.println(lru); System.out.println("LRU的中key为h的value值： " + lru.get('h')); System.out.println(lru); lru.put('z', 26); System.out.println(lru); } public static class LRU<K, V> extends LinkedHashMap<K, V> { private int cacheSize; public LRU(int cacheSize) { super(cacheSize, 0.75f, true); this.cacheSize = cacheSize; } /** * 重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余cacheSize个时，删除最老的节点（即最不经常使用的元素） * @param eldest * @return */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > getCacheSize(); } public int getCacheSize() { return cacheSize; } } }
运行结果：
LRU的大小：8 {e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12} LRU的中key为h的value值：8 {e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8} {f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}
