文档章节

Java-深入HashMap原理及内部存储结构

 小刀爱编程
发布于 01/22 21:31
字数 1592
阅读 24
收藏 7

本文将通过如下简单的代码来分析HashMap的内部数据结构的变化过程。

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    for (int i = 0; i < 50; i++) {
        map.put("key" + i, "value" + i);
    }
}
复制代码

1 数据结构说明

HashMap中本文需要用到的几个字段如下:

下面说明一下几个字段的含义

1)table

// HashMap内部使用这个数组存储所有键值对
transient Node<K,V>[] table;
复制代码

Node的结构如下:

可以发现,Node其实是一个链表,通过next指向下一个元素。

2)size

记录了HashMap中键值对的数量

3)modCount

记录了HashMap在结构上更改的次数,包括可以更改键值对数量的操作,例如put、remove,还有可以修改内部结构的操作,例如rehash。

4)threshold

记录一个临界值,当已存储键值对的个数大于这个临界值时,需要扩容。

5)loadFactor

负载因子,通常用于计算threshold,threshold=总容量*loadFactor。

2.new HashMap

new HashMap的源码如下:

/**
* The load factor used when none specified in constructor.
* 负载因子,当 已使用容量 > 总容量 * 负载因子 时,需要扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
复制代码

此时,HashMap只初始化了负载因子(使用默认值0.75),并没有初始化table数组。 其实HashMap使用的是延迟初始化策略,当第一次put的时候,才初始化table(此时table是null)。

3.table数组的初始化

当第一次put的时候,HashMap会判断当前table是否为空,如果是空,会调用resize方法进行初始化。 resize方法会初始化一个容量大小为16 的数组,并赋值给table。 并计算threshold=16*0.75=12。 此时table数组的状态如下:

4.put过程

map.put("key0", "value0");
复制代码

首先计算key的hash值,hash("key0") = 3288451 计算这次put要存入数组位置的索引值:index=(数组大小 - 1) & hash = 3 判断 if (table[index] == null) 就new一个Node放到这里,此时为null,所以直接new Node放到3上,此时table如下:

然后判断当前已使用容量大小(size)是否已经超过临界值threshold,此时size=1,小于12,不做任何操作,put方法结束(如果超过临界值,需要resize扩容)。

继续put。。。

map.put("key1", "value1");
复制代码

map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
map.put("key8", "value7");
map.put("key9", "value9");
map.put("key10", "value10");
map.put("key11", "value11");
复制代码

此时size=12,下一次put后size为13,大于当前threshold,将触发扩容(resize)

map.put("key12", "value12");
复制代码

计算Key的hash值,hash("key12")=101945043,计算要存入table位置的索引值 = (总大小 - 1) & hash = (16 - 1) & 101945043 = 3 从目前的table状态可知,table[3] != null,但此时要put的key与table[3].key不相等,我们必须要把他存进去,此时就产生了哈希冲突(哈希碰撞)。

这时链表就派上用场了,HashMap就是通过链表解决哈希冲突的。 HashMap会创建一个新的Node,并放到table[3]链表的最后面。 此时table状态如下:

5.resize扩容

此时table中一共有13个元素,已经超过了threshold(12),需要对table调用resize方法扩容。 HashMap会创建一个容量为之前两倍(16 2=32)的table,并将旧的Node复制到新的table中,新的临界值(threshold)为24(32 0.75)。

下面主要介绍一下复制的过程(并不是原封不动的复制,Node的位置可能发生变化)

先来看源码:

for (int j = 0; j < oldCap; ++j) { // oldCap:旧table的大小 =16
    Node<K,V> e;
    if ((e = oldTab[j]) != null) { // oldTab:旧table的备份
        oldTab[j] = null;
        // 如果数组中的元素没有后继节点,直接计算新的索引值,并将Node放到新数组中
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e;
        // 忽略这个else if。其实,如果链表的长度超过8,HashMap会把这个链表变成一个树结构,树结构中的元素是TreeNode
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // 有后继节点的情况
        else { // preserve order
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                // 【说明1】
                if ((e.hash & oldCap) == 0) {
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                }
                else {
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
            } while ((e = next) != null);
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) {
                hiTail.next = null;
                //【说明2】
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}
复制代码

【说明1】遍历链表,计算链表每一个节点在新table中的位置。

计算位置的方式如下:

1)如果节点的 (hash & oldCap) == 0,那么该节点还在原来的位置上,为什么呢?

因为oldCap=16,二进制的表现形式为0001 0000,任何数&16,如果等于0,那么这个数的第五个二进制位必然为0。

以当前状态来说,新的容量是32,那么table的最大index是31,31的二进制表现形式是00011111。 计算index的方式是 hash & (容量 - 1),也就是说,新index的计算方式为 hash & (32 - 1) 假设Node的hash = 01101011,那么

01101011
& 00011111
----------
  00001011 = 11
复制代码

2)下面再对比(hash & oldCap) != 0的情况

如果节点的(hash & oldCap) != 0,那么该节点的位置=旧index + 旧容量大小

假设Node的hash = 01111011,那么

01111011
& 00011111
----------
  00011011 = 27
复制代码

上一个例子的hash值01101011跟这个例子的hash值01111011只是在第5位二进制上不同,可以发现,这两个值在旧的table中,是在同一个index中的,如下:在此我向大家推荐一个架构学习交流裙。交流学习裙号:687810532,里面会分享一些资深架构师录制的视频录像

01101011
& 00001111
----------
  00001011 = 11
复制代码
01111011
& 00001111
----------
  00001011 = 11
复制代码

由于扩容总是以2倍的方式进行,也就是:旧容量 << 1,这也就解释了【说明2】,当(hash & oldCap) != 0时,这个Node的新index = 旧index + 旧容量大小。

扩容后,table状态如下所示:

最终,重新分配完所有的Node后,扩容结束。

© 著作权归作者所有

共有 人打赏支持
粉丝 82
博文 97
码字总数 286130
作品 0
黄浦
私信 提问
ThreadLocal原理深入解析

1. 从一次项目经历说起 在上家公司做spark的任务调度系统时,碰到过这么一个需求: 1.任务由一个线程执行,同时在执行过程中会创建多个线程执行子任务,子线程在执行子任务时又会创建子线程执行子...

takumiCX
2018/07/16
0
0
分享一份非常强势的Android面试题

马上步入金九银十了,是时候看一些面试题去鹅厂了,接下来我将分享一些面试题,每天总结一点点,希望对大家有所帮助! ListView和RecyclerView区别 参考链接: blog.csdn.net/shu_lance/a… ...

codeGoogle
2018/08/23
0
0
学Android开发,入门语言java知识点

Android是一种以Linux为基础的开源码操作系统,主要使用于便携设备,而linux是用c语言和少量汇编语言写成的,如果你想研究Android,就去学java语言吧。 Android开发入门教程 -Java语言,最差...

抉择很难
2015/12/11
185
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
2018年Java编程学习面试最全知识点总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰
2018/05/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Android的WIFI局域网对讲机

https://blog.csdn.net/z979451341/article/details/79280749 (三)Android局域网内语音对讲 基于UDP语音传输 https://blog.csdn.net/stormxiaofeng/article/details/80513947 Android7.0手......

shzwork
35分钟前
1
0
vuex

一直有个误区 vuex既然页面刷新会丢失 那还有什么意义 。 重新翻看了下文档才恍然大误,vuex主要解决的是不同组件间的通信。 跨页面数据共享本质上还是用sessionStorage/localStorage...

东东笔记
今天
3
0
网站漏洞检测之WordPress 5.0.0 修复方案

2019年正月刚开始,WordPress最新版本存在远程代码注入获取SHELL漏洞,该网站漏洞影响的版本是wordpress5.0.0,漏洞的产生是因为image模块导致的,因为代码里可以进行获取目录权限,以及文件...

网站安全
今天
3
0
MySql 优化 group by 语句

默认情况下,Mysql 对所有 group by 的字段进行排序,如果查询包括 group by ,用户想要避免排序结果的消耗。可以指定 order by null 禁止排序。 mysql> EXPLAIN select * from sys_log gro...

嘴角轻扬30
今天
15
0
Linux分区&格式化&文件系统&LVM&扩容

硬件 磁盘由 盘片组、主轴马达、机械臂、磁头、驱动芯片和电路、接口等构成 2. 磁盘的分割 每个盘片很多同心圆分割为磁道 Trace 一组盘片的同径磁道叫做一个柱面 Cylinder 每个磁道又被分为很...

可数局部基
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部