如果面试也能这样说HashMap，那么就不会有那么多遗憾！（上）:https://developer.aliyun.com/article/1413687
问题：为什么Map桶中节点个数超过8才转为红黑树？
8这个阈值定义在HashMap中，针对这个成员变量，在源码的注释中只说明了8是bin（bin就是bucket(桶)）从链表转成树的阈值，但是并没有说明为什么是8：
在HashMap中有一段注释说明： 我们继续往下看 :
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: 因为树节点的大小大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点(参见TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时，就会被转换回普通的桶。在使用分布良好的用户hashcode时，很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布 (http://en.wikipedia.org/wiki/Poisson_distribution)，默认调整阈值为0.75，平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k))。 第一个值是: 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
TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
这样就解释了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是权衡，空间和时间的权衡。
这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，不是随便决定的，而是根据概率统计决定的。由此可见，发展将近30年的Java每一项改动和优化都是非常严谨和科学的。
也就是说：选择8因为符合泊松分布，超过8的时候，概率已经非常小了，所以我们选择8这个数字。
另一种说法是在调研这个问题的时候，在一些资料上翻阅得到的
红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
6.当链表的值小于6则会从红黑树转回链表
//当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6;
7.当Map里面的数量超过这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，而不是树形化
//桶中结构转化为红黑树对应的数组长度最小的值 static final int MIN_TREEIFY_CAPACITY = 64;
8、table用来初始化(必须是二的n次幂)(重点)
//存储元素的数组 transient Node<K,V>[] table;
9、 HashMap中存放元素的个数(重点)
//存放元素的个数，注意这个不等于数组的长度。 transient int size;
size为HashMap中K-V的实时数量，不是数组table的长度。
10、 用来记录HashMap的修改次数
// 每次扩容和更改map结构的计数器 transient int modCount;
11、 用来调整大小下一个容量的值计算方式为(容量*负载因子)
// 临界值 当实际大小(容量*负载因子)超过临界值时，会进行扩容 int threshold;
12 哈希表的加载因子(重点)
// 加载因子 final float loadFactor;
说明：
1.loadFactor加载因子，是用来衡量 HashMap 满的程度，表示HashMap的疏密程度，影响hash操作到同一个数组位置的概率，计算HashMap的实时加载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。
loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。，所以开发中尽量减少扩容的次数，可以通过创建HashMap集合对象时指定初始容量来尽量避免。
同时在HashMap的构造器中可以定制loadFactor。
构造方法： HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。
2.为什么加载因子设置为0.75,初始化临界值是12？
loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
如果希望链表尽可能少些。要提前扩容，有的数组空间有可能一直没有存储数据。加载因子尽可能小一些。
举例：
例如：加载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。 加载因子是0.9。 那么16*0.9---->14 那么这样就会导致链表有点多了。导致查找元素效率低。
所以既兼顾数组利用率又考虑链表不要太多，经过大量测试0.75是最佳方案。
4.2构造方法
HashMap 中重要的构造方法，它们分别如下：
构造一个空的 HashMap ，默认初始容量（16）和默认负载因子（0.75）。
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的加载因子0.75赋值给loadFactor，并没有创建数组 }
构造一个具有指定的初始容量和默认负载因子（0.75） HashMap。
// 指定“容量大小”的构造函数 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
构造一个具有指定的初始容量和负载因子的 HashMap。我们来分析一下。
/* 指定“容量大小”和“加载因子”的构造函数 initialCapacity: 指定的容量 loadFactor:指定的加载因子 */ public HashMap(int initialCapacity, float loadFactor) { //判断初始化容量initialCapacity是否小于0 if (initialCapacity < 0) //如果小于0，则抛出非法的参数异常IllegalArgumentException throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂 if (initialCapacity > MAXIMUM_CAPACITY) //如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity initialCapacity = MAXIMUM_CAPACITY; //判断负载因子loadFactor是否小于等于0或者是否是一个非数值 if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } 最后调用了tableSizeFor，来看一下方法实现： /** * Returns a power of two size for the given target capacity. 返回比指定初始化容量大的最小的2的n次幂 */ static final int tableSizeFor(int cap) { 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; }
说明：
对于 this.threshold = tableSizeFor(initialCapacity); 疑问解答：
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指 定初始化容量大的最小的2的n次幂。这点上述已经讲解过。 但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边 界值了。有些人会觉得这里是一个bug,应该这样书写： this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。 但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推 迟到了put方法中，在put方法中会对threshold重新计算，put方法的具体实现我们下面会进行讲解
包含另一个“Map”的构造函数
//构造一个映射关系与指定 Map 相同的新 HashMap。 public HashMap(Map<? extends K, ? extends V> m) { //负载因子loadFactor变为默认的负载因子0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
最后调用了putMapEntries，来看一下方法实现：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //获取参数集合的长度 int s = m.size(); if (s > 0) { //判断参数集合的长度是否大于0，说明大于0 if (table == null) // 判断table是否已经初始化 { // pre-size // 未初始化，s为m的实际元素个数 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 计算得到的t大于阈值，则初始化阈值 if (t > threshold) threshold = tableSizeFor(t); } // 已初始化，并且m元素个数大于阈值，进行扩容处理 else if (s > threshold) resize(); // 将m中的所有元素添加至HashMap中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
注意：
float ft = ((float)s / loadFactor) + 1.0F;这一行代码中为什么要加1.0F ？
s/loadFactor的结果是小数，加1.0F与(int)ft相当于是对小数做一个向上取整以尽可能的保证更大容量，更大的容量能够减少resize的调用次数。所以 + 1.0F是为了获取更大的容量。
例如：原来集合的元素个数是6个，那么6/0.75是8，是2的n次幂，那么新的数组大小就是8了。然后原来数组的数据就会存储到长度是8的新的数组中了，这样会导致在存储元素的时候，容量不够，还得继续扩容，那么性能降低了，而如果+1呢，数组长度直接变为16了，这样可以减少数组的扩容。
这也是设计的最佳准则
4.3成员方法
4.3.1增加方法
put方法是比较复杂的，实现步骤大致如下：
1）先通过hash值计算出key映射到哪个桶；
2）如果桶上没有碰撞冲突，则直接插入；
3）如果出现碰撞冲突了，则需要处理冲突：
a:如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
b:否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；
4）如果桶中存在重复的键，则为该键替换新值value；
5）如果size大于阈值threshold，则进行扩容；
具体的方法如下：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
说明：
1）HashMap只提供了put用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。 所以我们重点看putVal方法。
2）我们可以看到在putVal()方法中key在这里执行了一下hash()方法,来看一下Hash方法是如何实现的。
static final int hash(Object key) { int h; /* 1）如果key等于null： 可以看到当key等于null的时候也是有哈希值的，返回的是0. 2）如果key不等于null： 首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的 hash值 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
从上面可以得知HashMap是支持Key为空的，而HashTable是直接用Key来获取HashCode所以key为空会抛异常。
{其实上面就已经解释了为什么HashMap的长度为什么要是2的幂因为HashMap 使用的方法很巧妙，它通过 hash & (table.length -1)来得到该对象的保存位，前面说过 HashMap 底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当 length 总是2的n次方时，hash & (length-1)运算等价于对 length 取模，也就是hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。}
解读上述hash方法：
我们先研究下key的哈希值是如何计算出来的。key的哈希值是通过上述方法计算出来的。
这个哈希方法首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的 hash值。计算过程如下所示：
static final int hash(Object key) { int h; /* 1）如果key等于null： 可以看到当key等于null的时候也是有哈希值的，返回的是0. 2）如果key不等于null： 首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的 hash值 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
在putVal函数中使用到了上述hash函数计算的哈希值：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 。。。。。。。。。。。。。。 if ((p = tab[i = (n - 1) & hash]) == null)//这里的n表示数组长度16 。。。。。。。。。。。。。。 }
计算过程如下所示：
说明：
1）key.hashCode()；返回散列值也就是hashcode。假设随便生成的一个值。
2）n表示数组初始化的长度是16
3）&（按位与运算）：运算规则：相同的二进制数位上，都是1的时候，结果为1，否则为零。
4）^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为0，不同为1。
简单来说就是：
- 高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）
问题：为什么要这样操作呢？
如果当n即数组长度很小，假设是16的话，那么n-1即为 —》1111 ，这样的值和hashCode()直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。 (其实本质上就是充分利用了 hash的高位 和 低位，充分吸收其 特点)
例如上述： hashCode()值： 1111 1111 1111 1111 1111 0000 1110 1010 & n-1即16-1--》15： 。。。。。。。。。。。。。。。。。。。。。。1111 ------------------------------------------------------------------- 0000 0000 0000 0000 0000 0000 0000 1010 ----》10作为索引 其实就是将hashCode值作为数组索引，那么如果下个高位hashCode不一致，低位一致的话，就会造成计算的索引还是10,从而造成了哈希冲突了。降低性能。
putVal()方法源代码如下所示：
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) { Node<K,V>[] tab; Node<K,V> p; int n, i; /* 1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。 2）(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null，第一次肯定是 null 3）(n = tab.length) == 0 表示将数组的长度0赋值给n,然后判断n是否等于0，n等于0 由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化。 并将初始化好的数组长度赋值给n. 4）执行完n = (tab = resize()).length，数组tab每个空间都是null */ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /* 1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中 2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p 3) (p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null，如果为null，则执行代 码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中 小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置 */ if ((p = tab[i = (n - 1) & hash]) == null) //创建一个新的节点存入到桶中 tab[i] = newNode(hash, key, value, null); else { // 执行else说明tab[i]不等于null，表示这个位置已经有值了。 Node<K,V> e; K k; /* 比较桶中第一个元素(数组中的结点)的hash值和key是否相等 1）p.hash == hash ：p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个 hash值是否相等 说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } 而在Node类中具有成员变量hash用来记录着之前数据的hash值的 2）(k = p.key) == key ：p.key获取原来数据的key赋值给k key 表示后添加数据的key 比较两 个key的地址值是否相等 3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后 添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等 */ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) /* 说明：两个元素哈希值相等，并且key的值也相等 将旧的元素整体对象赋值给e，用e来记录 */ e = p; // hash值不相等或者key不相等；判断p是否为红黑树结点 else if (p instanceof TreeNode) // 放入树中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 说明是链表节点 else { /* 1)如果是链表的话需要遍历到最后节点然后插入 2)采用循环遍历的方式，判断链表中是否有重复的key */ for (int binCount = 0; ; ++binCount) { /* 1)e = p.next 获取p的下一个元素赋值给e 2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元 素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键 将该键值对插入链表中 */ if ((e = p.next) == null) { /* 1）创建一个新的节点插入到尾部 p.next = newNode(hash, key, value, null); Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } 注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个节点肯定是 null 2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素 */ p.next = newNode(hash, key, value, null); /* 1)节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于 则将链表转换为红黑树 2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历节点的个 数。值是0表示第一个节点，1表示第二个节点。。。。7表示第八个节点，加上数组中的的一 个元素，元素个数是9 TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7 如果binCount的值是7(加上数组中的的一个元素，元素个数是9) TREEIFY_THRESHOLD - 1也是7，此时转换红黑树 */ if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //转换为红黑树 treeifyBin(tab, hash); // 跳出循环 break; } /* 执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插 入的元素的key值是否相等 */ if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等，跳出循环 /* 要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了 直接执行下面的if语句去替换去 if (e != null) */ break; /* 说明新添加的元素和当前节点不相等，继续查找下一个节点。 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表 */ p = e; } } /* 表示在桶中找到key值、hash值与插入元素相等的结点 也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值 这里完成了put方法的修改功能 */ if (e != null) { // 记录e的value V oldValue = e.value; // onlyIfAbsent为false或者旧值为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 //e.value 表示旧值 value表示新值 e.value = value; // 访问后回调 afterNodeAccess(e); // 返回旧值 return oldValue; } } //修改记录次数 ++modCount; // 判断实际大小是否大于threshold阈值，如果超过则扩容 if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; }
如果面试也能这样说HashMap，那么就不会有那么多遗憾！（下）:https://developer.aliyun.com/article/1413692
