loadFactor 负载因子
对于 HashMap 来说，负载因子是一个很重要的参数，该参数反应了 HashMap 桶数组的使用情况。通过调节负载因子，可使 HashMap 时间和空间复杂度上有不同的表现。
当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。
相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。至于负载因子怎么调节，这个看使用场景了。
一般情况下，我们用默认值就可以了。大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。
查找
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } // 获取hash值 static final int hash(Object key) { int h; // 拿到key的hash值后与其五符号右移16位取与 // 通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 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 && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 桶中不止一个结点 if ((e = first.next) != null) { // 是否是红黑树，是的话调用getTreeNode方法 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; }
注意：
- HashMap的hash算法(
hash()方法)。
(n - 1) & hash等价于对 length 取余。
添加
public V put(K key, V value) { // 调用hash(key)方法来计算hash return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 容量初始化：当table为空，则调用resize()方法来初始化容器 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<K,V> e; K k; // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对 e = p; // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法 else if (p instanceof TreeNode) // 放入树中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //对链表进行遍历，并统计链表长度 for (int binCount = 0; ; ++binCount) { // 到达链表的尾部 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值与插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //判断要插入的键值对是否存在 HashMap 中 if (e != null) { // existing mapping for key V oldValue = e.value; // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 键值对数量超过阈值时，则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
事实上，new HashMap();完成后，如果没有put操作，是不会分配存储空间的。
- 当桶数组 table 为空时，通过扩容的方式初始化 table
- 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
- 如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
- 判断键值对数量是否大于阈值，大于的话则进行扩容操作
扩容机制
在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。
HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。
final Node<K,V>[] resize() { // 拿到数组桶 Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 如果数组桶的容量大与0 if (oldCap > 0) { // 如果比最大值还大，则赋值为最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 如果扩容后小于最大值 而且 旧数组桶大于初始容量16， 阈值左移1(扩大2倍) else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 如果数组桶容量<=0 且 旧阈值 >0 else if (oldThr > 0) // initial capacity was placed in threshold // 新容量=旧阈值 newCap = oldThr; // 如果数组桶容量<=0 且 旧阈值 <=0 else { // zero initial threshold signifies using defaults // 新容量=默认容量 newCap = DEFAULT_INITIAL_CAPACITY; // 新阈值= 负载因子*默认容量 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新阈值为0 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 覆盖数组桶 table = newTab; // 如果旧数组桶不是空，则遍历桶数组，并将键值对映射到新的桶数组中 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; }
整体步骤：
- 计算新桶数组的容量 newCap 和新阈值 newThr
- 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
- 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。
总结起来，一共有三种扩容方式：
- 使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值
DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
- 指定初始容量的构造方法初始化
HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） * DEFAULT_LOAD_FACTOR。
- HashMap不是第一次扩容。如果
HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。
细心点的人会很好奇，为什么要判断loadFactor为0呢？
loadFactor小数位为 0，整数位可被2整除且大于等于8时，在某次计算中就可能会导致 newThr 溢出归零。
疑问和进阶
1. JDK1.7是基于数组+单链表实现（为什么不用双链表）
首先，用链表是为了解决hash冲突。
单链表能实现为什么要用双链表呢?(双链表需要更大的存储空间)
2. 为什么要用红黑树，而不用平衡二叉树？
插入效率比平衡二叉树高，查询效率比普通二叉树高。所以选择性能相对折中的红黑树。
3. 重写对象的Equals方法时，要重写hashCode方法，为什么？跟HashMap有什么关系？
equals与hashcode间的关系:
- 如果两个对象相同（即用equals比较返回true），那么它们的hashCode值一定要相同；
- 如果两个对象的hashCode相同，它们并不一定相同(即用equals比较返回false)
因为在 HashMap 的链表结构中遍历判断的时候，特定情况下重写的 equals 方法比较对象是否相等的业务逻辑比较复杂，循环下来更是影响查找效率。所以这里把 hashcode 的判断放在前面，只要 hashcode 不相等就玩儿完，不用再去调用复杂的 equals 了。很多程度地提升 HashMap 的使用效率。
所以重写 hashcode 方法是为了让我们能够正常使用 HashMap 等集合类，因为 HashMap 判断对象是否相等既要比较 hashcode 又要使用 equals 比较。而这样的实现是为了提高 HashMap 的效率。
附上源码图：
4. HashMap为什么不直接使用对象的原始hash值呢?
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
我们发现，HashMap的哈希值是通过上面的方式获取，而不是通过key.hashCode()方法获取。
原因：
通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。
5. 既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树？
因为红黑树需要进行左旋，右旋操作， 而单链表不需要。
以下都是单链表与红黑树结构对比。
如果元素小于8个，查询成本高，新增成本低。
如果元素大于8个，查询成本低，新增成本高。
至于为什么选数字8，是大佬折中衡量的结果-.-，就像loadFactor默认值0.75一样。
