文档章节

HashMap工作原理

凯尔特Queen
 凯尔特Queen
发布于 2017/11/17 14:17
字数 675
阅读 14
收藏 1

 

HashMap底层数据是基于散列表的结构形式,如下图所示:

当往HashMap存值的时候调用到put(K key,V value)方法,JDK 1.7源码如下:

初始化HashMap类的时候会伴随着Entry类实例化,这也由Map的数据结构决定的,执行的流程为以下:

1.首先判断key是否位为空,如果是把table[0]位置上创建一个默认hash值为0的Entry

2.其次是计算出key的hash值以及其在table表中的索引位置即bucket

3.然后遍历bucket出的连表,如果是连表对应value不为空并且value值有更新的话,则更新该key对应的value值,如果没有还是原来是value值

如果value值为空的话则在连表对应位置出创建一个Entry

HashMap默认的table size为16,默认加载因子是0.75,当数据的大小超过容量*加载因子的时候就会发生扩容,容量大小是之前的2倍

HashMap put值的时候会存在hash冲突(两个key的hash值相同),所以才对应有连表结构

一般来说 hash值相同equals可能不同 equals相同hash值一定相同,但是重写Hash和equals的情况下就另外说

另外Map扩容的时候会可能导致死循环,当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。

总结:

HashMap的工作原理: HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

© 著作权归作者所有

共有 人打赏支持
凯尔特Queen
粉丝 40
博文 24
码字总数 6242
作品 0
浦东
程序员
私信 提问

暂无文章

python 利用 descriptor 实现自己的 property

1.概念简介 1.1 property 在 python 代码中,property 是非常常见的一个内置函数。property 可以为一个 python 类的 attribute 设置 getter/setter,可以类比之 C# 的 properties。 见下面的...

御坂网络路由器
45分钟前
3
0
xssfilter-代码段

class XssHttpServletRequestWrapper extends HttpServletRequestWrapper { /** * @param request */ public XssHttpServletRequestWrapper(HttpServletRequest request) { super(request); ......

qiang123
50分钟前
3
0
05 分支管理 —— 分支管理策略

05 分支管理 —— 分支管理策略 分支管理策略 通常合并分支时,可能Git会用Fast forward模式,但这种模式下,删除分支后,会丢掉分支信息。 如果要强制禁用Fast forward模式,Git就会在merge...

lwenhao
55分钟前
4
0
lareval nginx 配置

在centos上成功编译安装nginx 1.4、php 5.4并成功启动nginx和php-fpm后,访问php提示"File not found.",同时在错误日志中看到: 代码如下: 2013/10/22 20:05:49 [error] 12691#0: *6 FastC......

李佳顺
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部