本文以JDK1.8进行阐述

HashMap数据结构主要是hashTable+鏈表或者红黑树组成示意图如下所示：

hashMap本身是非线程安全的，如果多线程访问需要从外部进行线程同步，如下提供一种线程安全的方式：

在resize函数中实现扩容扩容的同时伴随着重hash操作，hashTable通常扩容为原来的两倍如下代码片段所示：

插入操作通过调用putVal实现，插入步骤如下：

1）首先判断当前的hashTable是否为空或者长度为0如果是的话通过resize() 进行扩容

2）定位到当前key 在hashTable的位置，并判断节点是否为空如果是空则直接将当湔key-value值插入

3）第二步如果判断非空，那么会有三种情况：

a) hashTable所在位置和当前等待插入的的数据相同则根据onlyIfAbsent进行value覆盖或者不覆盖

c) 否则hashTable所在位置節点类型为Node链表节点，则插入到链表末尾如果链表长度大于等于8则会调用treeifyBin进行链表转红黑树操作

拉链转化为红黑树在treeifyBin函数中实现触发时机:当链表的個数大于等于8且hashTable的大小大于等于64的时候。

为何链表转红黑树的时候长度选擇8？

从源码说明看链表长度符合柏松分布如下所示: 显示链表长度k的概率分布

链表长度达到8的概率已经非常低，综合考虑转换为红黑树的性能和链表查询性能只有在极端情况下才进行转换，大部分情况下链表都不长