HashMap源码解析与面试问题汇总

前言

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方法

从上述源码可知,删除的过程为:

如果第一个节点是待删除的节点,则记录此节点

如果不是,则判断是否是树节点和链表

如果是树节点,则以树的方式查找节点

如果是链表,则遍历,查找待删除的节点

如果找到了待删除的节点,则根据节点的类型,进行删除

如果是树节点,则调用树节点的删除方法

如果第一个节点为待删除的节点,则把第二个元素移到第一的位置

以链表的方式删除节点

面试题汇总

隐藏内容,您需要满足以下条件方可查看
End

人已赞赏
Mysql编程语言

Mysql面试题汇总

2020-5-27 9:30:26

数据结构编程语言

时间复杂度与空间复杂度

2020-5-30 20:29:41

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索