HashMap是最经典的Map实现，下面以它的视角介绍put的过程：

  1. 首次扩容：

    先判断数组是否为空，若数组为空则进行第一次扩容（resize）；

  2. 计算索引：

    通过hash算法，计算键值对在数组中的索引；

  3. 插入数据：

  • 如果当前位置元素为空，则直接插入数据；

  • 如果当前位置元素非空，且key已存在，则直接覆盖其value；

  • 如果当前位置元素非空，且key不存在，则将数据链到链表末端；

  • 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；

  1. 再次扩容

    如果数组中元素个数（size）超过threshold，则再次进行扩容操作。

扩展阅读

HashMap添加数据的详细过程，如下图： alt