迟到一年HashMap解读

2024-02-09 07:08
文章标签 解读 hashmap 一年 迟到

本文主要是介绍迟到一年HashMap解读，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HashMap和List这两个类是我们在Java语言编程时使用的频率非常高集合类。“知其然，更要知其所以然”。HashMap认识我已经好多年了，对我在工作中一直也尽心尽力的提供帮助。我从去年开始就想去它家拜访来着，可是经常因为各种各样的原因让其遗忘在路过的风景中。（文章大部分源码基于jdk1.7）。

Map&Set

HashMap概述：

HashMap是基于哈希表实现的键值对的集合，继承自AbstractMap并的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的特殊存储结构使得在获取指定元素的前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量的比较即可得到元素，这使得HashMap的查找效率很高。

HashMap的特点

  • 底层实现JDK1.8之前是数组加链表，之后是数组加红黑树。
  • key是用Set进行存储的，所以不允许重复（可以允许null作为key）。
  • 元素的存储是无序的，每次重新扩容元素位置可能改变。
  • 插入、获取的时间复杂度基本是O(1)（提前试有适当的哈希函数，让元素均匀分布分布）。
  • 两个关键因子：初始容量，加载因子。

HashMap的数据结构

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable
{static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final Entry<?,?>[] EMPTY_TABLE = {};transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;transient int size;int threshold;final float loadFactor;transient int modCount;static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;/**********部分代码省略**********/static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;/**********部分代码省略**********/}/**********部分代码省略**********/
}

HashMap中主要存储着一个Entry的数组table，Entry就是数组中的元素，Entry实现了Map.Entry所以其实Entry就是一个key-value对，并且它持有一个指向下一个元素的引用，这样构成了链表（在java8中Entry改名为Node，因为在Java8中Entry不仅有链表形式还有树型结构，对应的类为TreeNode）。
HashMap的数据结构

HashMap的构造

/*** Constructs an empty <tt>HashMap</tt> with the specified initial* capacity and load factor.** @param  initialCapacity the initial capacity* @param  loadFactor      the load factor* @throws IllegalArgumentException if the initial capacity is negative*         or the load factor is nonpositive*/
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;threshold = initialCapacity;init();
}
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);inflateTable(threshold);putAllForCreate(m);
}

主要有两个参数，initialCapacity初始容量、loadFactor加载因子。
这两个属性在类定义时候都赋有默认值分别为16和0.75。
table数组默认值为EMPTY_TABLE，在添加元素的时候判断table是否为EMPTY_TABLE来调用inflateTable。在构造HashMap实例的时候默认threshold阈值等于初始容量。当构造方法的参数为Map时，调用inflateTable(threshold)方法对table数组容量进行设置：

/*** Inflates the table.*/
private void inflateTable(int toSize) {// Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize);//更新阈值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new Entry[capacity];initHashSeedAsNeeded(capacity);
}
//返回一个比初始容量大的最小的2的幂数,如果number为2的整数幂值那么直接返回，最小为1，最大为2^31。
private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

//返回一个不大于i的2的整数次幂
public static int highestOneBit(int i) {// HD, Figure 3-1i |= (i >>  1);//i的二进制右边2位为1 。i |= (i >>  2);//i的二进制右边4位为1。i |= (i >>  4);//i的二进制右边8位为1。i |= (i >>  8);//i的二进制右边16位为1。i |= (i >> 16);//i的二进制右边32位为1。//这样5次移位后再进行与操作，i的所有非0低位全部变成1；return i - (i >>> 1);//i减去所有底位的1，只留一个高为的1
}

为什么桶的容量要是2的指数，后面会讲到这样有助于添加元素时减少哈希冲突。

HashMap的存取实现

HashMap的put方法

  • 获取key的hashcode
  • 二次hash
  • 通过hash找到对应的index
  • 插入链表
//HashMap添加元素
public V put(K key, V value) {//table没有初始化size=0，先调用inflateTable对table容器进行扩容if (table == EMPTY_TABLE) {inflateTable(threshold);}//在hashMap增加key=null的键值对if (key == null)return putForNullKey(value);//计算key的哈希值int hash = hash(key);//计算在table数据中的bucketIndexint i = indexFor(hash, table.length);//遍历table[i]的链表，如果节点不为null，通过循环遍历链表的下一个元素for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//找到对应的key，则将value进行替换if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//没有找到对应的key的Entry，则需要对数据进行modify,modCount加一modCount++;//将改key，value添加入table中addEntry(hash, key, value, i);return null;
}
//添加Entry
void addEntry(int hash, K key, V value, int bucketIndex) {//当前桶的长度大于于阈值，而且当前桶的索引位置不为null。则需要对桶进行扩容if ((size >= threshold) && (null != table[bucketIndex])) {//对桶进行扩容resize(2 * table.length);//重新计算hash值hash = (null != key) ? hash(key) : 0;//重新计算当前需要插入的桶的位置bucketIndex = indexFor(hash, table.length);}//在bucketIndex位置创建EntrycreateEntry(hash, key, value, bucketIndex);
}
//创建Entry
void createEntry(int hash, K key, V value, int bucketIndex) {//找到当前桶的当前链表的头节点Entry<K,V> e = table[bucketIndex];//新创建一个Entry将其插入在桶的bucketIndex位置的链表的头部table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}

获取key的hashcode并进行二次hash

final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

为什么这么进行二次hash，目的是唯一的就是让产生的hashcode散列均匀。在网络上也找了一些关于hash值获取的介绍，下边是我找到感觉比较靠谱的一篇文章中关于hash算法的解析：

假设h^key.hashCode()的值为：0x7FFFFFFF，table.length为默认值16。
上面算法执行
image.png

得到当前的索引index=15 ，index = h & (length-1)，h&15等于获取h的二进制的后4位。
我们对其中h\^(h>>>7)^(h>>>4)的结果中的位运行标识是把h>>>7换成 h>>>8来看一下：
即最后h\^(h>>>8)^(h>>>4) 运算后hashCode值每位数值如下：

8=8
7=7^8
6=678
5=5^8^7^6
4=4^7^6^5^8
3=3^8^6^5^8^4^7 ------------> 3^4^5^6^7
2=2^7^5^4^7^3^8^6 ---------> 2^3^4^5^6^8
1=1^6^4^3^8^6^2^7^5 ------> 1^2^3^4^5^7^8

算法中是采用h>>>7而不是h>>>8的算法，应该是考虑1、2、3三位出现重复位\^运算的情况。使得最低位上原hashCode的8位都参与了\^运算，所以在table.length为默认值16的情况下面，hashCode任意位的变化基本都能反应到最终hash table定位算法中，这种情况下只有原hashCode第3位高1位变化不会反应到结果中，即：0x7FFFF7FF的index=15。

从整个二次hash的解析过程来看，通过多次位移和多次与操作获取的hashcode。每当key的hashcode有任何变化的时候都能影响到二次hash后的底位的不同，这样在下边根据hash获取在桶上的索引的时候最大减少哈希冲突。

获取hash在桶上的索引：

当我们想找一个hash函数想让均匀分布在桶中时，我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大。而JDK中的实现hash根数组的长度-1做一次“&”操作。

//找到当前的hash在桶的分布节点位置
static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);
}

这里需要讲一下为什么index=h&(length-1)呢？因为HashMap中的数组长度为2的指数。（lenth-1）的值恰好是数组能容纳的最大容量，且在二进制下每位都是1。所以在经过二次hash之后所获取的code，就能通过一次与操作（取hash值的底位）让其分布在table桶中。

HashMap的get方法

在理解了put之后，get就很简单了。大致思路如下：
bucket里的第一个节点，直接命中；

  • 如果有冲突，则通过key.equals(k)去查找对应的entry
  • 若为树，则在树中通过key.equals(k)查找，O(logn)；
  • 若为链表，则在链表中通过key.equals(k)查找，O(n)。
//HashMap的get方法
public V get(Object key) {//获取key为null的valueif (key == null)return getForNullKey();//获取key对应的Entry实例Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();
}
//获取Entry
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}//计算key的hash值int hash = (key == null) ? 0 : hash(key);//根据hash调用indexFor方法找到当前key对应的桶的index，遍历该节点对应的链表for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;//判断当前Entry的hash、key的hash和Entry的key、key是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;
}

HashMap的扩容

当HashMap中的元素越来越多的时候，因为数组的长度是固定的所以hash冲突的几率也就越来越高，桶的节点处的链表就越来越长，这个时候查找元素的时间复杂度相应的增加。为了提高查询的效率，就要对HashMap的数组进行扩容（这是一个常用的操作，数组扩容这个操作也会出现在ArrayList中。），而在HashMap数组扩容之后，最消耗性能的地方就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

当HashMap中的元素个数超过阈值时，就会进行数组扩容，【loadFactor】加载因子的默认值为0.75，【threshold】阈值等于桶长乘以loadFactor这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，

//HashMap扩容
void resize(int newCapacity) {//引用备份Entry[] oldTable = table;//原来桶的长度int oldCapacity = oldTable.length;//判断是否已经扩容到极限if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//根据容器大小创新的建桶Entry[] newTable = new Entry[newCapacity];//transfer(newTable, initHashSeedAsNeeded(newCapacity));//重置桶的引用table = newTable;//重新计算阈值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//用于初始化hashSeed参数.
//其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。
//这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突。
final boolean initHashSeedAsNeeded(int capacity) {boolean currentAltHashing = hashSeed != 0;boolean useAltHashing = sun.misc.VM.isBooted() &&(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean switching = currentAltHashing ^ useAltHashing;if (switching) {hashSeed = useAltHashing? sun.misc.Hashing.randomHashSeed(this): 0;}return switching;
}
//桶中数据的迁移
void transfer(Entry[] newTable, boolean rehash) {//新的痛长int newCapacity = newTable.length;for (Entry<K,V> e : table) {//遍历桶的没一个节点的链表while(null != e) {Entry<K,V> next = e.next;//重新计算哈希值if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//找到当前Entry在新桶中的位置int i = indexFor(e.hash, newCapacity);//将Entry添加在当桶中的bucketIndex处的链表的头部e.next = newTable[i];//将产生的新链表赋值为桶的bucketIndex处newTable[i] = e;//遍历当前链表的下一个节点e = next;}}
}
  • 假设hash算法就是最简单的 key mod table.length（也就是数组的长度）。
  • 最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在mod 2以后碰撞发生在 table[1]
  • 接下来的三个步骤是 Hash表 resize 到4，并将所有的 <key,value> 重新resize到新Hash表的过程

resize

在HashMap进行扩容的时候有一个点大家发现没，所有Entry的hash值是不需要重新计算的。因为hash值与（length - 1）取的总是hash值的二进制右边底位，扩容一次向左多取一位二进制。

有关HashMap的思考

  • 什么时候会使用HashMap？他有什么特点？

是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

  • 你知道HashMap的工作原理吗？

通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

  • 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

  • 你知道hash的实现吗？为什么要这样实现？

在通过hashCode()的高位与底位进行异或，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

  • 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

JDK1.8对HashMap的改进

代码实现的不同之处

//链表切换为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树切花为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树上的节点个数满足时对整个桶进行扩容
static final int MIN_TREEIFY_CAPACITY = 64;
//红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;/*************部分代码省略*****************/
}
//获取key的hashCode,并进行二次hash。二次hash只是将hashcode的高16位于第16位进行异或
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//resize时hash冲突使用的是红黑树
final Node<K,V>[] resize() {/*************部分代码省略*****************/
}

性能的提升

哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)，而使用红黑树代替链表查找时间会变为O(logn)。

参考文章：
主题：HashMap hash方法分析

文章到这里就全部讲述完啦，若有其他需要交流的可以留言哦！！

想阅读作者的更多文章，可以查看我 个人博客 和公共号：
振兴书城

这篇关于迟到一年HashMap解读的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/693487。

相关文章

MCU7.keil中build产生的hex文件解读

MCU7.keil中build产生的hex文件解读

1.hex文件大致解读 闲来无事,查看了MCU6.用keil新建项目的hex文件 用FlexHex打开 给我的第一印象是:经过软件的解释之后,发现这些数据排列地十分整齐 :02000F0080FE71:03000000020003F8:0C000300787FE4F6D8FD75810702000F3D:00000001FF 把解释后的数据当作十六进制来观察 1.每一行数据
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
GPT系列之：GPT-1，GPT-2，GPT-3详细解读

GPT系列之：GPT-1，GPT-2，GPT-3详细解读

一、GPT1 论文：Improving Language Understanding by Generative Pre-Training 链接：https://cdn.openai.com/research-covers/languageunsupervised/language_understanding_paper.pdf 启发点：生成loss和微调loss同时作用，让下游任务来适应预训
阅读更多...
LLM系列 | 38：解读阿里开源语音多模态模型Qwen2-Audio

LLM系列 | 38：解读阿里开源语音多模态模型Qwen2-Audio

引言 模型概述 模型架构 训练方法 性能评估 实战演示 总结 引言 金山挂月窥禅径，沙鸟听经恋法门。 小伙伴们好，我是微信公众号《小窗幽记机器学习》的小编：卖铁观音的小男孩，今天这篇小作文主要是介绍阿里巴巴的语音多模态大模型Qwen2-Audio。近日，阿里巴巴Qwen团队发布了最新的大规模音频-语言模型Qwen2-Audio及其技术报告。该模型在音频理解和多模态交互
阅读更多...
文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路，具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python
阅读更多...
速通GPT-3：Language Models are Few-Shot Learners全文解读

速通GPT-3：Language Models are Few-Shot Learners全文解读

文章目录 论文实验总览1. 任务设置与测试策略2. 任务类别3. 关键实验结果4. 数据污染与实验局限性5. 总结与贡献 Abstract1. 概括2. 具体分析3. 摘要全文翻译4. 为什么不需要梯度更新或微调⭐ Introduction1. 概括2. 具体分析3. 进一步分析 Approach1. 概括2. 具体分析3. 进一步分析 Results1. 概括2. 具体分析2.1 语言模型
阅读更多...
HashMap中常用的函数

HashMap中常用的函数

假设如下HashMap<String, Integer> map = new HashMap<>();获取value值1、返回key为a的valueget(a)2、返回key为a的value，若没有该key返回0getOrDefault(a,0)新增键值对1、新增键值对(a,1)put(a,1)2、如果key为a的键不存在，则存入键值对(a,1)putIfAbsent(a,1)3
阅读更多...
Open-Sora代码详细解读(1)：解读DiT结构

Open-Sora代码详细解读(1)：解读DiT结构

Diffusion Models专栏文章汇总：入门与实战 前言：目前开源的DiT视频生成模型不是很多，Open-Sora是开发者生态最好的一个，涵盖了DiT、时空DiT、3D VAE、Rectified Flow、因果卷积等Diffusion视频生成的经典知识点。本篇博客从Open-Sora的代码出发，深入解读背后的原理。 目录 DiT相比于Unet的关键改进点 Token化方
阅读更多...
hashmap的存值，各种遍历方法

hashmap的存值，各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null，把
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2