理论上，HashMap的链表是有可能性超过8的，比如长度为9

HashMap的链表长度为8并不是绝对的

• HashMap的数据结构
• • HashMap为什么会快
  • 何时转红黑树
  • 理论分析
  • 实验论证

    HashMap的数据结构

    在jdk8之前，HashMap的数据结构还是以数组加链表的方式存储，到8之后呢，由于链表需要迭代查询，链表就需要转红黑树，从而实现时间复杂度上的提升。尽管链表的长度越长，hash冲突概率越小，也无法阻挡官方为了这个细节做出结构上的变化。所以当链表长度达到8时会转成红黑树，但并不是绝对的。

    HashMap为什么会快

    其实这是一个老生长谈的问题：

    1. 合理的数据结构：数组、链表、红黑树
    2. 采用hash算法：第一次放值时，将key的hashcode高16位和低16位做异或求出hash值，和数组最大下标与运算，当再次扩容时使用hash值与旧数组长度与运算，求出新的下标值，存在两种可能性，与运算为0，还是旧数组下标位置，是1，为旧数组下标位置+旧数组长度
    3. 底层采用位运算：不管是求下标位置还是扩容计算都采用位运算，这也是为什么数组长度为2的n次方的原因之一。

    何时转红黑树

    当链表长度超过8时，会调用treeifyBin方法，从这个方法可以看出转红黑树时还需要保证数组长度大于等于64，否则会进行resize。

    final void treeifyBin(Node[] tab, int hash) {        int n, index; Node e;        if (tab == null || (n = tab.length)  
    理论分析
     
    如果现在有一个数组长度为16的HashMap，连续放入8的key-value键值对，根据hash算法(n - 1) & hash求出索引下标值，假设这8个元素都放在同一个下标位置，产生了链表，其本质上是这8个key的hash值的低四位是一样的，这理论上是有可能的，但实际上很难出现。如果此时又放入了1个key的低四位和这8个一样的元素，此时会触发调用treeifyBin方法，但是检查数组长度时发现此时远小于64，就会进行resize，官方这种做法其实我个人理解是，如果数组长度很小，hash计算的低位就少，有大概率冲突，所以先进行扩容，看是否能将一条超过8的链表进行扩容打散，打散到旧数组下标位置、旧数组下标位置+旧数组长度这两个位置，但是此时会有多种排列分布：【0,9】、【1,8】、【2,7】、【3,6】、【4,5】，所以【0,9】分布呢，本质上是这9个元素key的hash的低五位是一样的，此时就已经说明了链表长度已经超过8了。因此，在HashMap中链表长度不会超过8，这种可能性并不是绝对的。
     
    实验论证
     
    首先呢，定义了一个Key1这个类，用做HashMap的key，重写equals和hashCode方法，并且保证所有key的hashCode的值一样，这样他们的hash值也就一样了，但是equals需要保证不能相等，因此给了一个int属性k。然后定义一个长度为16的map，进行debug，从图中resize后可以看出此时长度为9的链表。
     
    public static void main(String[] args) {  Map map = new HashMap(16);  for (int i = 0; i