上几篇讨论了并发环境下list容器的操作, 本篇我们来聊下另外一个集合容器:Map ######家族体系 Map:以key-value对的形式存在,一种数据结构,一个key, 映射一个value值, map中不能包含重复的key值, 一个key最多只能映射到一个值。 常用方法有: 添加: V put(K key, V value); 删除: V remove(Object key); 修改: V put(K key, V value); 查询: V get(Object key); 常见的实现类: HashMap LinkedHashMap TreeMap Hashtable ConcurrentHashMap ######HashMap 要研究HashMap在并发环境下使用, 先得了解hashmap实现原理.HashMap是基于哈希表的 Map 接口的实现。([传送门：哈希表百度百科](https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869))，其底层维护一个数组与链表.源码说话: 注意: jdk8以前hashMap结构: 数组 + 链表 jdk8以后hashMap结构: 数组 + 链表 + 红黑树 此处源码使用的jdk8 源码: ```java public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { //初始容量, 默认16,俗称桶, 可以认为数组长度 //一个桶对应一条链表 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //真实的负载因子, 不特意指定是等于0.75f; final float loadFactor; //阈值:所能容纳kv对最大数量，超过这个值，则需扩容 //规则: threshold = capacity * loadFactor int threshold; //哈希表, 如果必要, 长度以2的n次方方式拓展 transient Node[] table; } ``` ```java static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } ``` HashMap运作规则:  1>HashMap 初始化时(不特意指定), 默认创建长度为16的一维数组, 用于保存Node(即kv对)/挂载链表投节点 ```java public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } ``` 2>map添加元素时map.put(key, value), 先通过哈希算法h = hash(key)计算出当前Node(key, value)在table数组中位置, 如果table[h]位置为null.table[h] = Node(key, value), 如果有值, 称之为碰撞, 则创建链表, 将当前Node(key, value) 拼接在链表后面. 3>JDK8的特性, 添加后,table某个位置的挂载链表个数大于等于TREEIFY_THRESHOLD=8时, 为提高查询效率,则将该位置下的链表转换成红黑树. ```java final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //创建新node p.next = newNode(hash, key, value, null); //如果node链表超过8 if (binCount >= TREEIFY_THRESHOLD - 1) //转换成红黑树 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果map的容量大于threshold, map扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } ``` 4> 添加后, 如果Map 的的size > threshold 阈值, 则需要对map扩容, 算法: 情况一:使用空参HashMap()构造器构建map/首次初始化 newSize = DEFAULT_INITIAL_CAPACITY = 16 newThreshold = newSize = oldSize* loadFactor 情况二:非空参构造器创建Map对象/后续初始化 newSize = oldSize * 2 //扩容2倍 newThreshold = oldThreshold * 2 ```java final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 2倍 } else if (oldThr > 0) newCap = oldThr; else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; //....省略数据拷贝 } ``` 到这大体了解HashMap底层实现, 细心的朋友应该可以看出来, hashMap所有的操作并没有使用synchronized修饰, 也就说, hashMap在高并发的环境下存在明显的线程安全问题. 场景1:多线程复合操作时 线程t1给map添加数据(key),而线程t2操作相同的key值, 先添加后获取. 某一时刻, t2先添加,如果此时切换到t1执行, t1会覆盖t2添加的数据, t2再次读取时, 数据被修改了, 出现脏读问题. ```java public class App { public static void main(String[] args) throws InterruptedException { final HashMap map = new HashMap<>(); Thread t1 = new Thread(new Runnable() { public void run() { map.put("key", "t1"); } }, "t1"); Thread t2 = new Thread(new Runnable() { public void run() { map.put("key", "t2"); try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(map.get("key")); //t1 } }, "t2"); t2.start(); Thread.sleep(2000); t1.start(); } } ``` 场景2:多线程同时添加相同hash 码值时 多个线程同时执行put操作时, 如果key的hash码一样时, 根据HashMap的实现，会有多个key添加到数组的同一个位置，如果此位置已经被占用,挂载新节点时,容易发生线程put的数据被覆盖。 ```java public class User { private String name; public User(String name) { this.name = name; } //保证hashMap调用hash算出的hashcode一致 public int hashCode() { return 1; } } ``` ```java public class App { public static void main(String[] args) throws InterruptedException { //final Hashtable map = new Hashtable<>(); final HashMap map = new HashMap<>(); //3个相同的线程, 同时往map中添加 new Thread(new Runnable() { public void run() { for (int i = 0; i < 1000; i++) { map.put(new User(1 + ""), i + "t1"); } System.out.println(Thread.currentThread().getName() + "..end..."); } }, "t1").start(); new Thread(new Runnable() { public void run() { for (int i = 0; i < 1000; i++) { map.put(new User(1 + ""), i + "t1"); } System.out.println(Thread.currentThread().getName() + "..end..."); } }, "t2").start(); new Thread(new Runnable() { public void run() { for (int i = 0; i < 1000; i++) { map.put(new User(1 + ""), i + "t1"); } System.out.println(Thread.currentThread().getName() + "..end..."); } }, "t3").start(); Thread.sleep(1000); System.out.println(map.size()); } } ``` JDK1.8计算的hash 码算法: ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` 上面程序运行存在几种结果: 1:结果为3000, 这是正确的 2:结果少于3000, 这就出现key值被覆盖了.原因:链表node移位时,出现并发问题. 3:报异常, 类转换异常.原因:前面说过,jdk8中hashmap同一个位置, 挂载大于等于8个节点会转换成红黑树, 多个线程争夺时,这个临界点会出问题. ```java java.lang.ClassCastException: HashMap$Node cannot be cast to HashMap$TreeNode ``` 4:报异常, 内存溢出异常, 这是场景3问题, map扩容造成的. ```java Exception in thread "t3" Exception in thread "t2" Exception in thread "t1" java.lang.StackOverflowError ``` 场景3:多线程同时扩容时 多线程刚好同时对hashMap进行扩容,最终只有一个线程扩容的table替换旧table数组, 那么其他线程put的数据会丢失.另外更有甚者, 可能会造成put操作的死循环(详细参考一个大牛写的:[HashMap死循环](https://coolshell.cn/articles/9606.html)) HashMap 在设计之初就没考虑过线程安全的问题, 所以在并发环境下HashMap并不是首选, 更多偏向下面几个Map. ##### HashTable&Collections.synchronizedMap HashTable 跟hashMap底层实现类似, 但在设计上考虑到线程安全操作, hashTable中所有的核心操作都加上synchronized修饰,确保操作的安全性. 所以并发环境下, hashTable不会出现场景2, 场景3 情况.而场景1中的复合操作还需要额外加锁, 确保操作安全. 具体操作, 参考上上遍并发中的list的案例. ```java public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry entry = (Entry)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } ``` Collections.synchronizedMap 的操作跟HashTable大同小异,都是通过synchronized给操作方加锁, 这里不累赘了. ######ConcurrentHashMap ConcurrentHashMap 是jdk1.5引入的并发map实现类, 该类的设计者推荐并发环境首选Map实现了, 那么它能解决上面场景1,场景2,场景3的并发为问么?篇幅所限, 我们下回分解.