### HashMap简介 从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现；本质上是基于hash表实现； > Hash表的读写性能在很大程度上依赖HashCode的随机性，即HashCode越随机散列，Hash表的冲突就越少，读写性能也就越高 HashMap基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap类与Hashtable 大致相同）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。 ``` Map map = Collections.synchronizedMap(new HashMap()); ``` ### HashMap的数据结构 HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。 下面一幅图，形象的反映出HashMap的数据结构：数组加链表实现  ### HashMap属性 ``` //树化链表节点的阈值，当某个链表的长度大于或者等于这个长度，则扩大数组容量，或者树化链表 static final int TREEIFY_THRESHOLD = 8; //初始容量，必须是2的倍数，默认是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大所能容纳的key-value 个数 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //存储数据的Node数组，长度是2的幂。 transient Node<K,V>[] table; //keyset 方法要返回的结果 transient Set<Map.Entry<K,V>> entrySet; //map中保存的键值对的数量 transient int size; //hashmap 对象被修改的次数 transient int modCount; // 容量乘以装载因子所得结果，如果key-value的 数量等于该值，则调用resize方法，扩大容量，同时修改threshold的值。 int threshold; //装载因子 final float loadFactor; ``` ### 构造方法 ``` public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } ``` 注意：使用指定的初始容量和默认的加载因子初始化HashMap，这里需要注意的是，并不是你指定的初始容量是多少那么初始化之后的HashMap的容量就是多大，例如new HashMap\(20,0.8\); 那么实际的初始化容量是32，因为tableSizeFor\(\)方法会严格要求把初始化的容量是以2的次方数成长只能是16、32、64、128...... 在HashMap中，哈希桶数组table的长度length大小必须为2的n次方\(一定是合数\) ### 主要方法  * **put\(K key, V value\)**  执行逻辑： 1\) 根据key计算hash值，用于定位对象在HashMap数组的哪个节点。 2）判断table有没有初始化，如果没有初始化，则调用resize\(\)方法为table初始化容量，以及threshold的值。 3）根据hash值定位该key对应的数组索引，如果对应的数组索引位置无值，则调用newNode\(\)方法，为该索引创建Node节点 4）如果根据hash值定位的数组索引有Node，并且Node中的key和需要新增的key相等，则将对应的value值更新。 5）如果在已有的table中根据hash找到Node，其中Node中的hash值和新增的hash相等，但是key值不相等的，那么创建新的Node，放到当前已存在的Node的链表尾部。如果当前Node的长度大于8,则调用treeifyBin\(\)方法扩大table数组的容量，或者将当前索引的所有Node节点变成TreeNode节点，变成TreeNode节点的原因是由于TreeNode节点组成的链表索引元素会快很多。 6）将当前的key-value 数量标识size自增，然后和threshold对比，如果大于threshold的值，则调用resize\(\)方法，扩大当前HashMap对象的存储容量。 7）返回oldValue或者null； ``` /** * Implements Map.put and related methods * * @param key的hash值 * @param key值 * @param value值 * @param onlyIfAbsent如果是true，则不修改已存在的value值 * @param evict if false, the table is in creation mode. * @return 返回被修改的value，或者返回null。 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //如果是第一次调用，则会调用resize 初始化table 以及threshold n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) //如果对应的索引没有Node，则新建Node放到table里面。 tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果hash值与已存在的hash相等，并且key相等，则准备更新对应Node的value e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果hash值一致，但是key不一致，那么将新的key-value添加到已有的Node的最后面 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // 当某个节点的链表长度大于8，则扩大table 数组的长度或者将当前节点链表变成树节点链表 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //hash值和key值相等的情况下，更新value值 e.value = value; //留给LinkedHashMap实现 afterNodeAccess(e); //返回旧的value return oldValue; } } //修改次数加1 ++modCount; //判断table的容量是否需要扩展 if (++size > threshold) resize(); //留给LinkedHashMap扩展 afterNodeInsertion(evict); return null; } ``` * **resize\(\)** 上面调用到了一个resize方法， 我们来看看这个方法里面做了什么，实现逻辑如下： 1）如果当前数组为空，则初始化当前数组 2）如果当前table数组不为空，则将当前的table数组扩大两倍，同时将阈值（threshold）扩大两倍 ``` /** * 初始化，或者是扩展table 的容量。 * table的容量是按照2的指数增长的。 * 当扩大table 的容量的时候，元素的hash值以及位置可能发生变化。 */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //当前table 数组的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //当前的阈值 int oldThr = threshold; int newCap, newThr = 0; //如果table数组已有值，则将其容量（size）和阈值（threshold）扩大两倍 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; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // 当第一次调用resize的时候会执行这个代码，初始化table容量以及阈值 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; //重新分配table 的容量 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //将以前table中的值copy到新的table中去 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } ``` * **get\(Object key\)** 根据key的hash值和key，可以唯一确定一个value，下面我们来看看get方法执行的逻辑 1）根据key计算hash值 2）根据hash值和key确定所需要返回的结果，如果不存在，则返回空 ``` /** * Implements Map.get and related methods * * @param key 的hash值 * @param key的值 * @return 返回由key和hash定位的Node，或者null */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // 如果索引到的第一个Node，key 和 hash值都和传递进来的参数相等，则返回该Node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //如果索引到的第一个Node 不符合要求，循环变量它的下一个节点。 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } ``` * **remove\(Object key\)** 执行逻辑： 1）根据key得到key的hash值 2）根据key 和hash值定位需要remove的Node 3\) 将Node从对应的链表移除，然后再将Node 前后的节点对接起来 4）返回被移除 的Node 5）key-value的数量减一，修改次数加一 ``` /** * Implements Map.remove and related methods * * @param key的hash值 * @param key值 * @param 需要remove 的value， * @param 为true时候，当value相等的时候才remove * @param 如果为false 的时候，不会移动其他节点。 * @return 返回被移除的Node，或者返回null */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && //如果定位到的第一个元素符合条件，则跳出if else ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do {//定位到的第一个Node元素不符合条件，则遍历其链表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //移除符合要求的节点，将链表重新连接起来 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; //修改次数加1 ++modCount; //当前的key-value 对数减一 --size; afterNodeRemoval(node); return node; } } return null; ``` ### 总结 * HashMap默认初始容量是16； * HashMap默认加载因子是0.75； * HashMap非线程安全； * 如果自定义对象作为Map的键，那么必须重写hashCode和equals； * HashMap允许使用null值和null键； * HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变； * HashMap的底层主要是基于数组和链表来实现； * HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表； * 容量取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列； * 如果key为null的话，hash值为0，对象存储在数组中索引为0的位置。即table\[0\]； #### loadFactor加载因子取值影响 * 如果加载因子越大,填满的元素越多,好处是空间利用率高了,但冲突的机会加大了.链表长度会越来越长,查找效率降低。 * 如果加载因子越小,填满的元素越少,好处是冲突的机会减小了,但空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了） * 冲突的机会越大,则查找的成本越高 #### HashMap$Node 定义： ``` static class Node<K,V> implements Map.Entry<K,V> { final int hash; // hash值 final K key; V value; Node<K,V> next; //当hash值相同时，next存储链表的下一个节点的引用 ...... } ``` #### HashMap扩容 当HashMap中的元素个数超过数组大小\*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16\*0.75=12的时候，就把数组的大小扩展为 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，扩容是需要进行数组复制的，复制数组是非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能 #### 源码分析 ``` transient Node<K,V>[] table; //存储元素的实体数组 final float loadFactor; //加载因子 ``` #### 通过反射获取HashMap的table ``` public class Appliction { public static void main(String[] args) throws Exception { HashMap<Integer, String> m = new HashMap(); Random random = new Random(); for (int i = 0; i < 10000; i++) { int nextInt = random.nextInt(); m.put(nextInt, nextInt + ""); } Class cls = HashMap.class; // System.err.println("HashMap class ===>" + cls); Field table = cls.getDeclaredField("table"); table.setAccessible(true); Class cs = Class.forName("java.util.HashMap$Node"); // System.err.println("HashMap$Node class ===>" + cs); Object[] object = (Object[]) table.get(m); System.err.println(object.length); for (Object obj : object) { if (Objects.nonNull(obj)) { // System.err.println(obj); Field hash = cs.getDeclaredField("hash"); hash.setAccessible(true); // System.err.println("hash==>" + hash.get(obj)); Field next = cs.getDeclaredField("next"); next.setAccessible(true); Object nextValue = next.get(obj); if (Objects.nonNull(nextValue)) { System.err.println("next===>" + nextValue); } } } } } ``` ### 为什么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%），具体分析如下： > 注意： > 在jdk1.8之前新加入的冲突元素将会插到原有链表的头部，当时设计HashMap的大叔采用头插法而没有采用尾插法有一点考虑是性能优化，认为最近put进去的元素，被get的概率相对较其他元素大，采用头插法能够更快得获取到最近插入的元素；但头插法的设计有一个特点，就是扩容之后，链表上的元素顺序会反过来，这也是死循环的一个重要原因； > 在jdk1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率），会先进行插入再进行扩容，执行的是尾插法，直接插到链表尾部/红黑数树，不会出现逆序和环形链表死循环问题 下面的代码是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; } } } ``` 这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去  我们假设有两个线程同时需要执行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\]一样，那么就会陷入死循环。 _**参考资料**_ [https://www.jianshu.com/p/e2f75c8cce01](https://www.jianshu.com/p/e2f75c8cce01)