关于hashmap:HashMap底层原理

一、存储构造

HashMap 是数据结构散列表在 Java 中的实现版本，通过对键值进行哈希函数计算出键值对在散列表中的下标地位，能够快速访问到相应数据，工夫复杂度为 O(1)。

但因散列表数组长度无限，不同键值通过哈希函数计算出的下标地位可能统一，引发哈希抵触，为了解决这个问题，通常将哈希抵触的数据组成一个链表挂到散列表桶节点上，jdk7 及以前版本都是如此解决，工夫复杂度为 O(n)，构造如下图：

jdk8 中对链表构造做了优化，在肯定条件下将链表转为红黑树，晋升查问效率。红黑树是一种二叉均衡树，工夫复杂度为 O(logn)，构造如下图：

二、存取原理

put() 办法

1. 调用哈希函数 hash(key) 计算出键值 key 的哈希值 hash，再用此哈希值 hash 和散列表长度 -1 做与运算失去数组下标；
2. 依据数组下标找到指标 bucket，如果 bucket 上没有任何元素，就依据键值对创立一个新节点 Node，赋值给该 bucket 上；
3. 如果以后 bucket 上有链表，且头结点就匹配（哈希值 hash 相等，key 值雷同或 equals 相等），那么就将头结点上的值 value 替换；
4. 若第 2、3 步不满足，以后 bucket 上的头结点是树结构结点类型 TreeNode，则转为红黑树的插入操作；

5. 若第 2、3、4 步都不满足，则对链表做遍历操作；

   ​ 1）若链表中有节点匹配，则做 value 替换；

   ​ 2）若没有结点匹配，则在链表开端追加；（jdk7 应用头插法，jdk8 应用尾插法）

   ​ 3）查看链表长度是否超过 TREEIFY_THRESHOLD（默认大小为 8），若超过则执行红黑树转换操作；

6. 以上操作执行完之后，再查看以后键值对的数量比例是否超过了负载因子，若超出，则进行扩容。

get() 办法

1. 依据 key 计算出 hash 值，进一步计算失去哈希表的指标下标 index；
2. 若指标 bucket 头结点匹配，就返回头结点的 value；
3. 若指标 bucket 上为红黑树，则在红黑树上查找；若不是红黑树，遍历链表；
4. 若都没匹配到，返回 null；

三、扩容

个别状况下，当键值对数量比例超过负载因子便会触发扩容。每次扩容后的容量都是之前容量的 2 倍。

四、线程不平安