---

HashMap结构

IDEA查看集合结构

如果IDEA的debug调试模式断点看不到HashMap中的数组属性，可以这么操设置：
settings ==> Build,Execution.Deployment ==> Debugger ==> Data Views ==> Java ==> Enable alternative view for Collections classes（去掉勾选）

另外，Hide null elements in arrays and collections（去掉勾选）可展示空元素。

HashMap一些属性

• DEFAULT_INITIAL_CAPACITY：默认初始容量，值为16
• DEFAULT_LOAD_FACTOR：负载因子，值为0.75
• MAXIMUM_CAPACITY：最大容量，值为2^30
• TREEIFY_THRESHOLD：链表转换为红黑树的链表长度阈值，值为8
• UNTREEIFY_THRESHOLD：红黑树转换为链表的链表长度阈值，值为6
• MIN_TREEIFY_CAPACITY：链表转换为红黑树的容量阈值，值为64

扩容

HashMap每次扩容后，容量变为原来的2倍。扩容操作主要发生在put操作中。

触发扩容的条件

• 键值对个数超过当前容量*负载因子（假如当前容量为16，16*0.75=12）时，触发一次扩容

• 当链表长度超过8，但容量没达到64时，只触发一次扩容，不触发树化

  当容量达到64后，链表长度再+1时，才触发树化。

HashMap为何没有缩容

网上有很多分析，这里整理几条自己觉得比较合理的：

• 如果要缩容，肯定是在remove方法中操作，这会导致时间复杂度从O(1)变成O(n)，这是不可接受的（Java在大部分情况下都是用空间换时间的，缩容却要用时间换空间）
• remove的时候，会将Node实体的指针已经置为null，GC会释放实体，所以缩容缩的只是那个已经分配的数组，意义不大（最占空间的是那个Node实体，而不是已分配的数组空位置）

树化

将单向链表转化为红黑树。树化操作主要发生在put操作中。

触发树化的条件

• 当链表长度超过8，且容量达到64时，触发树化

红黑树重新转为链表

将红黑树转化为单向链表主要发生在remove操作和resize（扩容）操作中。

• 在resize操作中，如果节点为TreeNode（红黑树），会执行TreeNode的split方法分割红黑树。

  split方法会先根据hash取模的值将红黑树分割为两个红黑树，然后判断这两个新的红黑树长度如果小于等于6，会将红黑树转化为单向链表。

• 在remove操作中，进入到removeNode方法，判断要删除的节点是否为TreeNode，如果是则进入删除红黑树节点的removeTreeNode方法，方法中判断是否要解除红黑树的条件为：根节点为空或者根节点的右节点为空或根节点的左节点为空或根节点的左节点的做左节点为空。
  

  if (root == null || root.right == null ||
      (rl = root.left) == null || rl.left == null) {
      tab[index] = first.untreeify(map);
      return;
  }
  1
  2
  3
  4
  5

  上面四个位置只要有一个为空，就会解除红黑树。

HashMap为何不直接使用红黑树

• 时间维度：当链表长度很小时，即使遍历，查询速度也非常快O(n)；当链表不断变长，对查询性能有一定的影响，而转成树，能使查询性能提升到O(log(n))。
• 空间维度：因为红黑树需要进行左旋，右旋操作，本来就是以空间换时间。所以红黑树的空间成本比链表更大。

理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，在负载因子0.75的情况下，链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，是根据概率统计决定的，是为了让树化的几率足够小。

红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

综上所述：

• 链表空间成本相比更低，但如果长度过程，时间成本会变高；红黑树空间成本更高，但可以降低时间成本；
• 当数据量少的时候，两者觉得时间成本都差不多且都比较低。所以没必要使用红黑树（更高的空间成本）；当数据量大的时候链表的时间成本明显高于红黑树，这时使用红黑树（用更高的空间成本来换取时间成本的降低）才有意义。

所以，HashMap选择先使用链表，只有达到一定长度后，时间成本变高才会使用红黑树，用更大的空间成本来换取时间成本的降低。

链表与红黑树转换阈值

为什么链表转换为红黑树的阈值是8，而红黑树重新转换为链表的阈值是6，而不是7之类的？

个人认为，阈值有间隔主要是为了避免因为频繁的插入和删除操作二导致链表和红黑树之间频繁的转换，影响效率。
HashMap的一下几点设计可以佐证：

• HashMap根据阈值6，从红黑树转换为链表发生在扩容操作的时候，而不是删除操作的时候。因为扩容的频率更低
• HashMap删除操作的时候，是否将红黑树转换为链表并不是根据阈值6来判断的（具体判断规则参数上文内容），这种判断降低了红黑树转换为链表的概率。

参考文章：HashMap 链表与红黑树转换