热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

图解HashMap

什么是HashMap,文章内HashMap源码主要来自Android7.0HashMap是开发中常用的一个类,那么他究竟是什么呢?HashMap是一个存储key-value的集合,
什么是HashMap,文章内HashMap源码主要来自Android 7.0

HashMap是开发中常用的一个类,那么他究竟是什么呢?

HashMap是一个存储key-value的集合,底层实现的是数组,所以可以看作HashMap是对数组的一种封装。

构造方法

《图解HashMap》 HashMap构造函数.png

《图解HashMap》 HashMap构造函数.png

不管调用的是哪一个方法, 最终都会回调两个参数的这个构造函数,第一个参数是容量,第二个参数是阈值(用于扩容的时候计算容量)

先看看HashMap主要的成员变量

/**
* HashMap默认容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* HashMap最大可存储的容量值 1<<30
*/
static final int MAXIMUM_CAPACITY = 1 <<30;
/**
* 加载因子(阈值)如果put进来的元素数量>=总数量*0.75的时候, 就会进行扩容了
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* EMPTY_TABLE 看了一下,好像没啥用。。。
*/
static final HashMapEntry[] EMPTY_TABLE = {};
transient HashMapEntry[] table = (HashMapEntry[]) EMPTY_TABLE;
/**
* 这个size表示容量值,put了几次,这个size就是几,所以我们方法中用的size() 就是返回的这个值
*/
transient int size;

因为HashMap常用的就是get和put,所以主要分析一下这两个方法,在讲这个之前,先看一下HashMapEntry这个类吧

HashMapEntry

HashMapEntry继承自Map.Entry

static class HashMapEntry implements Map.Entry {
final K key;
V value;
HashMapEntry next;
int hash;
...
}

HashMapEntry的结构是链表(在api25之前是链表,在api26开始引入了红黑树, 当节点>8个的时候会转为红黑树, 节点<6个的时候又会转回为链表, 红黑树跳这里HashMap在Api26后的应用&#8212;红黑树篇),所以存储数据的时候是这样的

《图解HashMap》 存储结构.png

关于链表可参考其他文章

现在来讲一讲HashMap的put和get

put

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}

整个put的方法并不长,首次进来时会判断table是不是EMPTY_TABLE,就是上面那两数组,然后会执行inflatetable方法,这个方法就不看了。。。只有第一次put时候才会进入,因为只有那个时候table==EMPTY_TABLE,在inflatetable里,table就会被重新赋值
接下来看第二个判断 key==null
看看这个方法putForNullKey()

private V putForNullKey(V value) {
for (HashMapEntry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

如果已经有了一个 key为null的元素,那么就会替换他的value值,所以HashMap只能由一个空key。
sun.misc.Hashing.singleWordWangJenkinsHash(key);这个方法就是根据key计算hash值,然后通过indexFor方法算出key在table中的下标。由于数组的存储方式大概是这样的

《图解HashMap》 image.png

但是由于下标是根据key的hash和数组长度计算来的,所以有可能下标会一样,这个时候HashMapEntry这个链表的用处就体现出来了,如果下标一样的时候,那么就会比对HashMapEntry的key值是否一致,如果一致,就替换原key-value,如果没有与新添加的key一致的值,就会在HashMapEntry中新加一个节点,所以现在的存储方式变成了这样

《图解HashMap》 hashmap存储方式.png

如果是替换就value,会直接吧旧的value返回回去,如果不是的话就会走addEntry方法, 这个方法有三个作用

  • 扩容
  • 拷贝数据
  • 插入新数据
    跟进一下addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}

首先判断的是size是否大于阈值(总容量*0.75),并且table[bucketIndex]!=null, 所以只有两个条件成立的时候才会进行扩容

resize()

void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

newCapacity的大小等于就数组长度*2, 所以下方构建的newTable的长度就是原数组的长度两倍,到这里,就进行扩容完毕了,但是新数组是有了,但是没数据啊!不急,看transfer方法

transfer()

void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry e : table) {
while(null != e) {
HashMapEntry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

看到了吧,或进行一个双层循环,先循环数组,然后在循环里面节点,直到next==null的时候,会跳出当前循环,进行下一次循环,直到循环完毕,也就是新数据赋值完毕
再回到resize方法,再看下面的代码,把新数组newTable又给了table,threshold又得到了扩容后新的阈值,到这一步,扩容和拷贝数据就已经完成了。
再回看addEntry方法,又会更具新数组的大小和key的hash值重新计算下标,传递给createEntry(hash, key, value, bucketIndex)方法中,

void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}

到此,hashmap的put就结束了,回头看看。。。其实还算蛮简单的哈

《图解HashMap》 毛骨悚然.png

那么get方法呢?

get

final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

get方法最终会调用这个getEntry方法,看看里面的方法是不是很眼熟,计算hash,比对key。

《图解HashMap》

对!就是这么简单,同样也是根据hash和数组长度获取下标,然后就是这么一个循环,只要hash值一样并且key有一样的就会返回这个元素,否则就是返回null

总结一下:
put添加元素的操作为:

计算key的hash ==> 根据hash和数组长度计算对应的数组下标 ==> 如果当前下标内容为null,就直接添加,否则的话会进入一个循环,在这个循环中去寻找链表内有没有当前key值,有的话替换原value,没有的话插入到最后一个节点

《图解HashMap》 put步骤.png

get获取元素

计算key的hash ==> 根据hash和数组长度计算对应的数组下标 ==> 如果当前下标元素不为null,进入循环,在这个循环中去寻找链表内有没有当前key值,有的话返回,没有的话就返回null
get就不画了啊 自行体会

《图解HashMap》

话说你们画图都用啥啊。。。 我这大晚上的用截图工具扣扣画画好累,win10自带的画图工具感觉用不来


推荐阅读
  • 手写HashMap,快手面试官直呼内行
    手写HashMap,快手面试官直呼内行-手写HashMap?这么狠,面试都卷到这种程度了?第一次见到这个面试题,是在某个不方便透露姓名的Offer收割机大佬的文章:这……我当 ... [详细]
  • Java之HashMap在多线程情况下导致死循环的问题
    PS:不得不说Java编程思想这本书是真心强大..学习内容:1.HashMap<K,V>在多线程的情况下出现的死循环现象当初学Java的时候只是知道HashMap< ... [详细]
  • 转载自:http:www.blogjava.netCarpenterLeearchive20160427430268.html总体介绍之所以把HashSet和HashMa ... [详细]
  • 缓存这个东西就是为了提高运行速度的,由于缓存是在寸土寸金的内存里面,不是在硬盘里面,所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List:每 ... [详细]
  • 01Map集合概述A:Map集合概述:我们通过查看Map接口描述,发现Map接口下的集合与Collection接口下的集合,它们存储数据的形式不同a:Collection中的集合 ... [详细]
  • 在Java中有多种遍历HashMap的方法,注意Java中所有的Map类型都实现了共有的Map接口,所以接下来方法适用于所有Map(如:HaspMap,TreeMap,Linked ... [详细]
  • 本文介绍了在 Java 编程中遇到的一个常见错误:对象无法转换为 long 类型,并提供了详细的解决方案。 ... [详细]
  • 在分析Android的Audio系统时,我们对mpAudioPolicy->get_input进行了详细探讨,发现其背后涉及的机制相当复杂。本文将详细介绍这一过程及其背后的实现细节。 ... [详细]
  • 本文介绍如何使用 Python 的 DOM 和 SAX 方法解析 XML 文件,并通过示例展示了如何动态创建数据库表和处理大量数据的实时插入。 ... [详细]
  • MySQL 5.7 学习指南:SQLyog 中的主键、列属性和数据类型
    本文介绍了 MySQL 5.7 中主键(Primary Key)和自增(Auto-Increment)的概念,以及如何在 SQLyog 中设置这些属性。同时,还探讨了数据类型的分类和选择,以及列属性的设置方法。 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 开机自启动的几种方式
    0x01快速自启动目录快速启动目录自启动方式源于Windows中的一个目录,这个目录一般叫启动或者Startup。位于该目录下的PE文件会在开机后进行自启动 ... [详细]
  • 属性类 `Properties` 是 `Hashtable` 类的子类,用于存储键值对形式的数据。该类在 Java 中广泛应用于配置文件的读取与写入,支持字符串类型的键和值。通过 `Properties` 类,开发者可以方便地进行配置信息的管理,确保应用程序的灵活性和可维护性。此外,`Properties` 类还提供了加载和保存属性文件的方法,使其在实际开发中具有较高的实用价值。 ... [详细]
  • 如何将TS文件转换为M3U8直播流:HLS与M3U8格式详解
    在视频传输领域,MP4虽然常见,但在直播场景中直接使用MP4格式存在诸多问题。例如,MP4文件的头部信息(如ftyp、moov)较大,导致初始加载时间较长,影响用户体验。相比之下,HLS(HTTP Live Streaming)协议及其M3U8格式更具优势。HLS通过将视频切分成多个小片段,并生成一个M3U8播放列表文件,实现低延迟和高稳定性。本文详细介绍了如何将TS文件转换为M3U8直播流,包括技术原理和具体操作步骤,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 将学生对象和学生的归属地通过键与值存储到map集合中。importjava.util.HashMap;importjava.util.Iterator;importjava.uti ... [详细]
author-avatar
boybeta
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有