前言
HashMap一直是面试必问的知识点,也有不少刁钻的问题,同时,工作中几乎每天都会用到,索性做个总结。但是,我不推荐新手一上来就阅读源码,哪怕我现在有一定的经验了,也有不少源码是看不懂的。但我相信,随着经验的积累(头发的减少),会慢慢全部看懂的。
存储结构
jdk1.8中的hashmap采用 数组+链表+红黑树,数组的一个元素又称为:桶。
源码解析
属性
构造方法
put方法
从上述源码可知,put共分为三种情况:
table尚未初始化,调用resize()方法,对数据进行初始化
table已经初始化,且通过 hash算法 找到 下标所在的位置数据为空,直接将数据存放到指定位置
table已经初始化,且通过hash算法找到下标所在的位置数据不为空,发生hash冲突(碰撞),发生碰撞后,会执行以下操作:
如果桶中第一个元素的key,与待插入元素的key相同,则用 节点e 指向第一个元素的键值对
如果桶中第一个元素是树节点,则调用树节点的插入方法
如果是链表,则进行遍历:
如果链表中节点的key值,与待插入元素的key值相等,则跳出循环
如果达到了链表尾部,则在尾部插入该元素,并判断链表长度是否大于 8, 大于的话链表转换为红黑树
(如果在链表中找到了与待插入元素相等的节点,则记录旧值,判断是否用新值替换旧值,最后返回旧值)
(如果程序走到这,说明没有在链表中找到与待插入元素相等的节点,而是已经直接插入了。所以修改次数+1,元素数量+1,并判断是否需要扩容,最后返回null)
resize方法
从上述源码可知,resize过程大致可分为两个步骤:
先判断当前table是否初始化过(判断旧table的长度),如果没有初始化,就进行初始化;如果已经初始化了,就进行扩容,为原来的2倍
扩容后创建新的table,并迁移旧table中的数据
如果桶中只有一个元素,则重新计算位置hash&(newCap – 1),插入到新table
如果桶中第一个元素是树节点,则打散成两棵树再插入
如果桶中的元素是个链表,则重新计算下标,分成两个链表(低位和高位),插入到新table中
get方法
从上述源码可知,get的过程比put要简单得多,大致分为三步:
计算key得hash值
如果第一个元素是待查找元素,直接返回
如果是树节点,就按照树节点的方式查找,否则遍历链表,进行查找
remove方法
从上述源码可知,删除的过程为:
如果第一个节点是待删除的节点,则记录此节点
如果不是,则判断是否是树节点和链表
如果是树节点,则以树的方式查找节点
如果是链表,则遍历,查找待删除的节点
如果找到了待删除的节点,则根据节点的类型,进行删除
如果是树节点,则调用树节点的删除方法
如果第一个节点为待删除的节点,则把第二个元素移到第一的位置
以链表的方式删除节点