HashMap系列：负载因子0.75

（一）HashMap系列：负载因子0.75
（二）HashMap系列：树化阀值8，退化阀值6
（三）HashMap系列：2次方扩容
（四）HashMap系列：put元素（不看完将后悔一生！）

红黑树系列：
一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除

一、前言

HashMap在JDK7与JDK8有些不同，主要是在 hash 冲突后，数据结构的改变：

• JDK7：数组 + 单链表；
• JDK8：数组 + 单链表 + 红黑树；

本篇的主题是负载因子（0.75），因此是针对数组来分析，为何是0.75这个值！

二、负载因子的作用

在HashMap中，所有的对象都存储在类型为 Node 的变量名为 table 的数组中：

transient Node<K,V>[] table;

该数组初始大小（capacity = 16）。

当 hash(key) 算出来的值，与已存在的发生冲突时，会在冲突的结点后添加新的结点，此时就变成了链表。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

每个 Node 对象初始时的 next 为 null ，只有在冲突时，next 才会指向下一个相同 hash(key) 但 key 不同的新的 Node 对象。
当链表长度超过 8 时，将转成『红黑树』；当『红黑树』的个数低于 6 时，会重新转化为链表；

随着 table 中的数据越来越多，冲突会越来越频繁，就会影响 HashMap 的执行效率，无非时间或者空间，那到底是如何影响的呢？

2.1、负载因子 = 1.0

负载因子为1.0时，意味着，只有当 table 全部被填满，table 才会扩容；当 table 中的元素越来越多时，会出现大量的冲突：

• 若此时是链表，则查询效率是 O(n)，即线性；（插入/删除结点也要遍历到链表）；
• 若此时是红黑树，查询效率是 O(logN)，但红黑树的插入与删除就异常复杂，每次都要调整树；

因此，负载因子1.0，实际是牺牲了时间，但保证了空间的利用率。

2.2、负载因子 = 0.5

负载因子为0.5时，意味着，当 table 中的元素达到一半时，就发生扩容，table 容量扩大一倍：

• hash 冲突减少；
• 链表长度不会很长；
• 即便链表长度超过8时转成红黑树，树的高度也不会很高；

查询效率提高了，但这里，我们发现，会有大量的内存浪费，因为数组中的个数永远小于数组长度的一半。
因此，负载因子0.5，实际是牺牲了空间，但保证了时间效率。

2.3、负载因子 = 0.75

经过上面的分析，我们发现 [0.5 , 1.0] 对应着 [时间极端, 空间极端]，那我们就需要找一个平衡点，这个点就是合理的负载因子值。
源码中有解释：

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

其意思为：负载因子0.75较好的平衡了时间和空间成本，因子太高增加了查询成本。