HashMap
HashMap 与 HashSet 一样，不保证存储的顺序，因为底层是以 hash 表的方式存储的；
HashMap 底层存储结构为 数组 + 链表+红黑树 （Java 8）；
HashMap 存储的 key-value 数据类型为 HashMap$Node 类型，该类型实现了 Map$Entry 接口；
HashMap 没有实现同步，因此是线程不安全的；
HashMap 中的几个常量/变量 1 2 3 4 5 6 7 8 9 10 11 12 13 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的 table 数组容量 aka 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子为 0.75 static final int MAXIMUM_CAPACITY = 1 << 30; // 集合最大容量的上限是：2的30次幂（符号位为0） static final int TREEIFY_THRESHOLD = 8; // 链表树化临界值 static final int UNTREEIFY_THRESHOLD = 6; // 树转成链表的临界值 static final int MIN_TREEIFY_CAPACITY = 64; // 树化时数组的最小长度 transient Node<K,V>[] table; // 存放元素的数组 transient Set<Map.Entry<K,V>> entrySet; // 存放元素的缓存 transient int size; // HashMap 中实际元素个数 transient int modCount; // HashMap 修改次数，每个扩容和更改map结构的计数器 int threshold; // table 扩容临界值 数组长度 * 加载因子 final float loadFactor; // table 加载因子
初始化及扩容机制
HashMap 是用一个 Node 类型的数组 table 来存储元素的，每一个元素的类型为 Node；
1 transient Node<K,V>[] table;
创建 HashMap 对象时，数组 table 默认为 null，加载因子 loadfactor 默认为 0.75；
1 2 3 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
第一次添加元素时，判断 table 为空数组，默认将 table 扩容到 16，阈值 threshold 为数组长度与加载因子的积 12（resize() 方法）；
当添加元素 key-value 时，通过 key 的 hash 值计算该元素在 table 中的索引位置，判断该索引位置是否存在 Node 结点，没有则直接添加；
如果索引位置有结点，则判断要添加的元素的 key 与该节点的 key 是否相同，如果相同，则将 value 替换到当前结点，如果不相同，则判断当前结点是否是树结构，是树结构则执行添加树结点操作；
如果不是，判断为链表结构，且要添加的元素和链表第一个结点不同，遍历链表判断 key 是否存在，不存在则向链表插入元素，并判断当前链表是否满足树化条件（链表长度大于等于8），如果存在执行替换操作；
当 table 长度大于阈值 threshold 时，则执行 resize() 方法给 table 进行扩容，扩容大小为原来的 2 倍，同时阈值更新为当前数组长度乘以加载因子；
1 2 3 // putVal() 添加元素成功,table长度加1, 判断是否扩容 if (++size > threshold) resize();
当 table 某个节点的链表长度超过 TREEIFY_THRESHOLD（默认 8）后，判断 table 的容量是否达到 MIN_TREEIFY_CAPACITY（默认 64），达到则对当前结点的链表进行树化；否则对 table 扩容；
当树的元素减少到 UNTREEIFY_THRESHOLD = 6 时，会进行剪枝操作（转回链表）
阿里巴巴编码规约-初始化指定容量 【推荐】集合初始化时，指定集合初始值大小。
说明：HashMap 使用 HashMap(int initialCapacity) 初始化。
正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。
注意负载因子（即 loader factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。
反例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大，resize 需要重建 hash 表，严重影响性能。
主要方法源码分析 HashMap() - 构造器
无参构造
1 2 3 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
指定初始容量的构造器
1 2 3 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
指定初始容量和加载因子的构造器
1 2 3 4 5 6 7 8 9 10 11 12 13 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) // 异常:初始容量小于0 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 指定容量大于数组最大容量,初始化为最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 异常:加载因子小于0 or NaN Not a Number throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 指定加载因子大小 // 计算 table 的大小,确保为2的n次幂, // 这里赋值给临界值,在第一次添加元素的时候会初始化为table大小 this.threshold = tableSizeFor(initialCapacity); }
putVal() - 添加元素 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 /** * Implements Map.put and related methods. * * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义辅助变量 // 0. 这里是判断table是否初始化，table = null or table.length = 0 初始化table if ((tab = table) == null || (n = tab.length) == 0) // table:存放元素的Node[]数组 n = (tab = resize()).length; // resize():扩容-数组为空给table初始化16个空间 // 根据key的hash值计算索引值,将table中该索引位置的结点赋值给p,并判断p是否为空 if ((p = tab[i = (n - 1) & hash]) == null) //若p为null(当前位置没有元素)则创建新的结点Node保存当前要添加的数据,存储到当前索引位置 tab[i] = newNode(hash, key, value, null); else { // 这里说明table当前索引位置的结点已经存在数据，下面分情况判断添加元素 Node<K,V> e; K k; // 1. 判断要添加的元素(key)与table中当前索引位置的Node结点是否相同 // condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 元素重复 // 2. 判断当前索引位置元素结点是否是红黑树类型 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 3. 说明当前索引位置结点为链表,且第一个结点与要添加的元素key不同,就遍历链表判断key是否存在 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 如果key和链表中所有节点元素都不相同，则添加到链表最后 p.next = newNode(hash, key, value, null); // 添加元素后判断当前链表是否已经有了8个节点，够8个则将当前链表转成红黑树 // 这里调用treeifyBin()方法会判断table大小是否足够64个，到达64个才会树化 // 不满 64 个空间，会先给 table 扩容 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; // 退出 for 循环 } // 如果要添加的元素key在链表中已经存在，则直接退出循环 // condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等) if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 当前节点后移 } } // 要添加的元素 key 已存在，则将重复的元素返回 if (e != null) { // existing mapping for key V oldValue = e.value; // 将要添加的 value 替换掉旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 修改次数 // 添加元素成功,table长度加1, 判断是否扩容 数组长度是否大于阈值 if (++size > threshold) resize(); afterNodeInsertion(evict); // HashMap 没有实现该方法, 供子类实现扩充功能 // return null 表示要添加的元素在table中不存在, 添加成功 return null; }
resize() - table 扩容 给 table 初始化或者将数组大小翻倍，如果 table 为null，则根据默认值指定初始容量和边界值；否则，因为我们的 table 数组容量是 2 的 n 次幂，所以每个 bin 中的元素一定保持相同的索引，或者在新 table 中移动 2 的 n 次幂的偏移量（元素在新数组中的索引位置为 原来的索引 或者是 原来的索引 + 原容量大小）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 /** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 保存之前数组元素 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 保存旧容量 int oldThr = threshold; // 保存旧临界值 int newCap, newThr = 0; if (oldCap > 0) { // 将新容量和新边界值扩大为原来2倍(<<1 == *2) // 旧容量已经到达最大容量就扩大临界值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 将容量和临界值扩大2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 将旧临界值赋值给新容量，这里的场景为初始化时使用了带参数的构造器-tableSizeFor() else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 数组初始化 else { // zero initial threshold signifies using defaults 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"}) // 创建新 table 容量为默认初始容量或之前容量的2倍 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 原数组不为null，说明是扩容-遍历之前的table 赋值给新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 当前索引存在元素 e oldTab[j] = null; // 方便回收空间 // 1. 当前索引位置只有一个元素，没有下一个结点 if (e.next == null) // 重新计算当前元素在新table中的索引，将当前索引结点放到新table newTab[e.hash & (newCap - 1)] = e; // 2. 当前索引位置有下一个结点，且是红黑树,指定树的操作 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 3. 当前索引位置有下一个结点，这里是链表类型 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; // 取出下一个结点 // 扩容核心操作查看：https://www.yuque.com/zhangshuaiyin/java/sv07ip#DYnvE // 判断当前元素在新数组的索引是否改变 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; }
treeifyBin() - 树化 树化-将数组中的链表转成红黑树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 树化判断，table 数组的长度是否大于等于 64，未达到则进行数组扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 判断当前索引位置结点不为null else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; // 头尾节点 do { // 将链表结点转换为树结点类型 TreeNode TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; // 给头节点赋值为当前索引结点 else { // 将树结点连接起来 p.prev = tl; tl.next = p; } tl = p; // 给尾结点赋值 } while ((e = e.next) != null); // 链表结点后移 // 将树的头节点放在数组的当前索引位置，然后转换成红黑树 if ((tab[index] = hd) != null) hd.treeify(tab); } } // For treeifyBin TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }
remove() - 根据key删除 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } 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; // 辅助变量 // table 不为空，且指定key的hash计算的索引位置有元素 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; // 辅助变量 // 1 判断要删除的元素是否是指定索引链表的第一个元素 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // 2 不是第一个元素，判断链表是否还有其他元素 else if ((e = p.next) != null) { // 2.1 有其他元素且为树结点 if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 2.2 有其他元素，为链表结构 do { // 遍历链表，依次判断要删除的元素的位置 // 根据hash、key的值找到要删除的元素 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; // 找到，退出 } p = e; // p 是要删除节点的上一个节点 } 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; ++modCount; // 计数器+1 --size; // 长度 -1 afterNodeRemoval(node); return node; } } return null; }
get() - 根据key获取 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 数组不为空，且根据hash计算的索引位置有结点 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 查询的key与该索引位置的元素相同 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 不是数组当前索引位置的元素，且有下一个结点 if ((e = first.next) != null) { if (first instanceof TreeNode) // 树结点 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { // 遍历链表 找到对应的key if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
HashMap继承关系 HashMap继承关系如下图所示：
说明：
Cloneable 空接口，表示可以克隆。 创建并返回 HashMap 对象的一个副本。
Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化。
AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。
table 数组容量必须是 2 的 n 次幂 HashMap 在添加元素的时候，添加到数组的索引位置是根据 key 的 hash 值与数组长度减一 做按位与操作计算得来的（hash & (length - 1)）。为了使元素更加分散的添加到数组中，当数组长度为 2 的 n 次幂时，计算索引的结果和 hash % length 相等(取余效率低)，这样能够减少哈希碰撞。
也就是说，当 length 为 2 的 n 次幂时 hash & (length - 1) = hash % length；
1 2 3 4 5 6 00010000 # length = 16 00001111 # length - 1 = 15 & 10101010 # hash 示例的一个hash --------------------------------- 00001010 # 即hash值的后四位作为下标，而后四位取值范围就是0-15也就是hash % length取余的值
而当我们手动传入数组长度不是 2 的 n 次幂时，HashMap 底层会执行什么样的操作呢？
由于 HashMap 提供了传递数组长度的构造器，所以我们可以手动给 HashMap 传递 table 长度，而数组长度必须是 2 的 n 次幂，当我们传入其他值时，HashMap 会通过一系列的 位移运算 和 或运算 得到比传递值大且最接近指定大小的 2 的 n 次幂的数值；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 // 创建HashMap集合的对象，指定数组长度是10，不是2的幂 HashMap hashMap = new HashMap(10); public HashMap(int initialCapacity) { // initialCapacity=10 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { // 10, 0.75 if (initialCapacity < 0) // false throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) // false initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) // false throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); // initialCapacity=10 } /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { // int cap = 10 // 这里防止cap已经是2的n次幂, 2的n次幂执行下面操作会扩大2倍 int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
通过 位移运算 和 或运算 最终得到的结果为从二进制最左侧的1开始，右边全部为1；
1 2 3 00000000 00000000 00000000 00001001 // 9 00000000 00000000 00000000 00001101 // 9 | 9 >>> 1 = 13 00000000 00000000 00000000 00001111 // 13 | 13 >>> 2 = 15
为什么链表长度为 8 时进行树化？ 在 HashMap 源码中有这样一段描述：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million * * The root of a tree bin is normally its first node. However, * sometimes (currently only upon Iterator.remove), the root might * be elsewhere, but can be recovered following parent links * (method TreeNode.root()). */
因为树结点 TreeNode 占用空间大小比链表结点 Node 大两倍，所以在结点够多时才使用树结点。并且当树结点太少（由于删除或者调整大小）也会被转换为普通的 bins。在hashCode 分布均匀时，树 bins 很少使用。理想情况下，在随机的 hashCode 中，bins 中结点存放的概率服从 泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，默认调整阈值为0.75，平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，列表大小k的预期出现次数是(exp(-0.5)*pow (0.5, k)/factorial(k))。
根据注释中的说明，在 hashCode 离散型很好的时候，链表中存储到第八个索引的概率极小，树化的概率非常小。选择大小 8 是从概率学的角度出发，进行的空间与时间的权衡。
数组扩容后如何计算元素的新索引 在 JDK 1.7 是采用重新计算 hash 的方式，这样要对数组中所有的元素重新计算 hash 值，影响效率，Java 8 对计算索引做了优化。
HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1) & hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到”原位置+旧容量 “这个位置。
举例：
正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1 bit 是 0还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的节点分散到新的桶中了。
思考 hashmap初始化 put方法：
当用户调用hashmap的无参构造函数的时候 数组table默认为空 负载因子赋值为0.75（若有参构造 会分配一个长度为2的n次方且大于等于参数的最小值）
用户第一次调用put方法时，
首先会判断table是否为空，若为空，为数组扩容，默认大小为16，然后计算阈值为16*0.75 = 12
当添加元素的时候 根据key的hashcode 获取元素在数组中的位置，判断该位置是否有元素，没有直接添加，
如果有元素，判断该元素 的key 和我要插入的元素的key是否相同，如果相同我就直接替换，如果不同
判断该节点是否是树结构，如果是树结构就直接添加树节点
否则就为链表结构，遍历链表看有没有相同的key，如果有就替换，没有就添加
添加完了之后 看是否要执行树化操作，也就是链表长度大于等于8 满足条件进行扩容
扩容大小为当前长度的二倍，同时更新阈值为当前长度*0.75
hashmap 扩容方法
正常情况下：当触发扩容机制的时候 ，会创建一个新的哈希表，容量为久容量*2 ，新的哈希表创建完后，下一步就是将老表的元素移到新表中，移动分俩种情况：1、如果旧槽中只有一个元素，则直接将这个元素移动到新槽中作为首元素。（是否会冲突？同一个槽位中的元素只有俩种情况 1、位置不变 2、原位置 + 旧的容量 所以不会出现俩个元素在同一个槽位）2、槽位上是链表或者树 会拆分成俩个放到俩个插槽中(将位置不变的元素和位置发生改变的元素拿出来)。如果红黑树的节点数少于6个红黑树退化为链表。
扩展 为什么hashmap线程不安全 JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。
数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。
JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。
举个例子：
两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ... // 判断是否出现 hash 碰撞 // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 桶中已经存在元素（处理hash冲突） else { // ... }
还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：
线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 HashMap 中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ... // 实际大小大于阈值则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; }
由于整数最大位数为 32,因此最大值为 32 个 1,这时已经变成负数了,返回之前会判断。如果为负数，返回1；如果大于等于 MAXIMUM_CAPACITY 2^30 ，返回 MAXIMUM_CAPACITY ，否则返回 n + 1；最终赋值给 threshold 临界值，在第一次添加元素给数组 table 扩容的时候，赋值给 table 的长度值，并计算新的临界值 threshold 为 数组长度乘以加载因子。
