HashMap底层原理 hashmapjava

一、存储结构
HashMap是数据结构散列表在Java中的实现版本，通过对键值进行哈希函数计算出键值对在散列表中的下标位置，可以快速访问到相应数据，时间复杂度为O(1)。
但因散列表数组长度有限，不同键值经过哈希函数计算出的下标位置可能一致，引发哈希冲突，为了解决这个问题，通常将哈希冲突的数据组成一个链表挂到散列表桶节点上，jdk7及以前版本都是如此处理，时间复杂度为O(n)，结构如下图：

文章图片

jdk8中对链表结构做了优化，在一定条件下将链表转为红黑树，提升查询效率。红黑树是一种二叉平衡树，时间复杂度为O(logn)，结构如下图：

文章图片

二、存取原理
put()方法

调用哈希函数hash(key)计算出键值key的哈希值hash，再用此哈希值hash和散列表长度-1 做与运算得到数组下标；
根据数组下标找到目标bucket，如果bucket上没有任何元素，就根据键值对创建一个新节点Node，赋值给该bucket上；
如果当前bucket上有链表，且头结点就匹配（哈希值hash相等，key值相同或equals相等），那么就将头结点上的值value替换；
若第2、3步不满足，当前bucket上的头结点是树结构结点类型TreeNode，则转为红黑树的插入操作；
若第2、3、4步都不满足，则对链表做遍历操作；
? 1）若链表中有节点匹配，则做value替换；
? 2）若没有结点匹配，则在链表末尾追加；（jdk7使用头插法，jdk8使用尾插法）
? 3）检查链表长度是否超过TREEIFY_THRESHOLD（默认大小为8），若超过则执行红黑树转换操作；
以上操作执行完之后，再检查当前键值对的数量比例是否超过了负载因子，若超出，则进行扩容。

get()方法