HashMap底层

article/2025/9/22 0:52:48

1、HashMap底层数据结构

JDK1.7的底层是 数组+链表；

JDK1.8之后 数组 + 链表 + 红黑树；

数组特点：具有随机访问的特点，能达到O(1)的时间复杂度，数组查询快，增删比较麻烦；

链表特点：与数组恰恰相反，链表的时间复杂度达到O(n)，只能顺着节点依次的找下去，增删比较快，查询比较慢；

都知道 Map 是以键值对的形式存储的 num（key，value），key值不可以重复，假设下载有两个key一样被hash（key）作为同一个下标 i ，这是数组下标 i 只可以保存一个元素，此时链表就发挥作用了，加入链表来解决hash冲突，两个key会用next连接起来，当key被连接成一个链表时，每次只能从第一个Node开始寻找，查询就会很低，为了解决这个问题 JDK1.8之后引入了 红黑树 数据结构来解决这个问题。

1.1、为什么HashMap的负载因子是0.75

在HashMap中有个默认的 DEFAULT_LOAD_FACTOR 负载因子为 0.75；

假设我们将负载因子设置为1，那么HashMap的容量需要全部装满，才会允许扩容，HashMap的容量如果全部装满再扩容会伴随着大量的hash冲突，这时候put和get操作效率就回低下。

如果将负载因子设置为0.5，这时HashMap的容量达到50%就会进行扩容，这样虽然减少了hash冲突概率，但是会存在一半空间还没有被用到就扩容，会造成空间利用率低。

既然0.5和1都不行那么就取中间数0.75，显然不是这样的，而是根据一个数学公式（牛顿二项式）推理出一个数字，是0.693，而0.75是为了后期使用时为了方便计算而做出的。

HashMap的put操作（添加）：

代码： 

//put操作
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}//计算key对象的hash值
static final int hash(Object key) { int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//进行与操作
}//具体添加细节
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; //创建数组Node<K,V> p; //新节点int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; //对数组进行初始化if ((p = tab[i = (n - 1) & hash]) == null) //(n - 1) & hash 求数组的下标，判断是否有元素。没有tab[i] = newNode(hash, key, value, null);  //直接放入else { //有元素Node<K,V> e; K k;//判断存储的节点是否已存在。//1.两个对象的hash值不同，一定不是同一个对象//2.hash值相同，两个对象也不一定相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p; //存储的节点的key的已存在，直接进行替换else if (p instanceof TreeNode) //存储的节点的key的不存在，判断是否为树节点（是不是已经转化为红黑树）e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//即不存在。也不是树节点，for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { //直接找到链表的尾部，直接插入p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 判断链表的长度是否大于可以转化为树结构的阈值treeifyBin(tab, hash); //树化break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) //判断是否和插入对象相同break;p = e;}}if (e != null) { // existing mapping for key 存在映射的key，覆盖原值，将原值返回V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold) //hashmap的容量大于阈值resize(); //扩容afterNodeInsertion(evict);return null;}

第一种情况：当hash值相同，且key一样，说明要做value的替换，这个时候会走最下面的if语句，使用 e.value = value来替换元素；

第二种情况：如果key不相等，这个时候就是添加元素，当该列已经树化，那么直接调用 putTreeVal() 方法即可；

第三种情况：如果要添加元素，此时不是树的情况，就需要考虑链表的长度是否会造成树化，还有链表当中不存在这个key，如果大于8了，会变成红黑树调用treeifyBin()方法，如果链表hash值相同并且key也相同，就会进行替换。

resize()扩容：

 代码：

	final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//进行数组的扩容，长度为原来的2倍，阈值为原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;**//进行数组的初始化，容量为默认值16，阈值为16*0.75**else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//把原数组的元素调整到新数组中@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//判断当前索引j的位置是否存在元素eif ((e = oldTab[j]) != null) {oldTab[j] = null;//判断 e.next是不是有值，简而言之，就是判断当前位置是否是树或者链表if (e.next == null)//调整到新数组中newTab[e.hash & (newCap - 1)] = e;//如果是红黑树，进行树的拆分（具体不讲了）else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//如果是链表else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;//遍历链表do {next = e.next;//生成低位链表if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//生成高位链表else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//将低位链表调整到新数组if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//将高位链表调整到新数组if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

HashMap的gut操作(查询)：

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}//计算key的hash值
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//具体实现final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { //数组不能为空并且当前索引位置的元素不能为空；如果为空，直接返回null值if (first.hash == hash && // always check first node//检查第一个元素，如果是，直接返回((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {//向下寻找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

由上面的源码可知,，当通过Key获取值时，我们通过hash()计算出Key所对应的hash值，然后去调用getNode（）真正的执行get操作。

HashMap为什么初始化大小是16：

当我们看hashMap的源码可知当新 put 一个数据时会进行计算位于table数组中的下标：int index =key.hashCode()&(length-1)；每次扩容都是以2的整数次幂进行扩容。

因为是将二进制进行按位与，（16-1）是1111，末尾是1，这样可以保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散、均匀，那么 按位与 的时候index就会减少重复，这样就减少了hash的碰撞以及hashMap的查询效率。


http://chatgpt.dhexx.cn/article/2b6u8kHL.shtml

相关文章

HashMap底层实现和原理（源码解析）

HashMap底层实现和原理（源码解析）

Note&#xff1a;文章的内容基于JDK1.7进行分析&#xff0c;1.8做的改动文章末尾进行讲解。 大家可以看一下:https://www.imooc.com/article/267756 一、先来熟悉一下我们常用的HashMap 1、概述 HashMap基于Map接口实现&#xff0c;元素以键值对的方式存储&#xff0c;并且…
阅读更多...
HashMap 底层原理

HashMap 底层原理

前言 HashMap 源码和底层原理在现在面试中是必问的。因此&#xff0c;我们非常有必要搞清楚它的底层实现和思想&#xff0c;才能在面试中对答如流&#xff0c;跟面试官大战三百回合。文章较长&#xff0c;介绍了很多原理性的问题&#xff0c;希望对你有所帮助~ 正文 **说明&a…
阅读更多...
HashMap底层原理剖析(面试收藏！！！)

HashMap底层原理剖析(面试收藏！！！)

HashMap HashMap底层原理剖析(超详细&#xff01;&#xff01;&#xff01;)一、散列表结构二、什么是哈希&#xff1f;三、HashMap原理讲解3.1继承体系图3.2Node数据结构分析3.3底层存储结构3.4put数据原理分析3.5什么是哈希碰撞&#xff1f;3.6JDK8为什么引入红黑树&#xff…
阅读更多...
HashMap底层原理

HashMap底层原理

文章目录 1.HashMap的概念2.底层数据结构2.JDK1.8之前存在的问题&#xff1f;3.问题&#xff1a;加载因子为什么默认值为0.75f &#xff1f;4.问题&#xff1a;如果得到key的hash值&#xff08;哈希码&#xff09;5.问题&#xff1a;如何得到插入元素在数组中的下标6.问题&…
阅读更多...
HashMap 的底层结构和原理

HashMap 的底层结构和原理

1. 讲讲 HashMap 的底层结构和原理 HashMap 就是以 Key-Value 的方式进行数据存储的一种数据结构嘛&#xff0c;在我们平常开发中非常常用&#xff0c;它在 JDK 1.7 和 JDK 1.8 中底层数据结构是有些不一样的。总体来说&#xff0c;JDK 1.7 中 HashMap 的底层数据结构是数组 …
阅读更多...
HashMap底层原理（详细介绍）

HashMap底层原理（详细介绍）

数组&#xff1a;其实所谓的数组指的就是一组相关类型的变量集合&#xff0c;并且这些变量彼此之间没有任何的关联。存储区间连续&#xff0c;占用内存严重&#xff0c;数组有下标&#xff0c;查询数据快&#xff0c;但是增删比较慢&#xff1b; 链表&#xff1a;一种常见的基…
阅读更多...
HashMap底层详解

HashMap底层详解

1、HashMap底层存储原理详解 HashMap存储原理 ☆获取到传过来的key&#xff0c;调用hash算法获取到hash值 ☆获取到hash值之后调用indexFor方法&#xff0c;通过获取到的hash值以及数组的长度算出数组的下标 (把哈希值和数组容量转换为二进&#xff0c;再在数组容量范围内与哈…
阅读更多...
Java基础——工厂模式、单例模式、懒汉模式、饿汉模式

Java基础——工厂模式、单例模式、懒汉模式、饿汉模式

案例&#xff1a; 这里有Factory类、Goods接口、Foods类、Drink类以及Others类。其中&#xff0c;Foods类、Drink类和Others类继承Goods接口&#xff0c;实现各自对应的方法。然后&#xff0c;在测试类中&#xff0c;创建Goods接口指向三个子类中的某一个&#xff0c;通过Facto…
阅读更多...
单例模式——饿汉模式和懒汉模式

单例模式——饿汉模式和懒汉模式

目录 &#x1f95d;线程安全的单例模式&#x1f95d;饿汉模式&#x1f95d;懒汉模式&#x1f95d; 懒汉模式总结 &#x1f95d;线程安全的单例模式 线程安全的单例模式是面试中常见的问题,所以熟练掌握这种单例模式尤为重要 什么叫单例模式? 单例模式就是一种设计模式,写代码时…
阅读更多...
C# 设计模式之单例模式（懒汉模式、饿汉模式、静态内部类模式）

C# 设计模式之单例模式（懒汉模式、饿汉模式、静态内部类模式）

C# 设计模式之单例模式&#xff08;懒汉模式、饿汉模式、静态内部类模式&#xff09; 应用场景&#xff1a;在整个软件运行生命周期内&#xff0c;一个类只允许一次实例化&#xff0c;例如数据库连接池的连接对象创建&#xff1b;通过使用单例模式来避免反复创建连接对象&#…
阅读更多...
muduo源码剖析——Singleton单例模式之懒汉模式与DCL双重检查

muduo源码剖析——Singleton单例模式之懒汉模式与DCL双重检查

0 懒汉与饿汉 对于Singleton单例模式我们并不陌生&#xff0c;但我们常用的多是饿汉模式&#xff1a; Singleton实例的声明和实例化在instance()函数中同时完成。而懒汉模式要求&#xff0c;Singleton实例的声明和实例化分开&#xff1a; 先声明Singleton实例对象&#xff0…
阅读更多...
C++单例模式 : 懒汉模式 与 饿汉模式

C++单例模式 : 懒汉模式 与 饿汉模式

单例模式&#xff1a; 只能有一个实例&#xff0c;有懒汉和饿汉区分&#xff0c;实现核心思想&#xff1a; 1.构造函数私有化 2.使用静态函数作为接口来获取类对象 1、懒汉模式&#xff1a; 由调用者实例&#xff0c;多线程情况下会存在线程安全问题&#xff0c;需要加互斥锁进…
阅读更多...
单例模式的创建(饿汉模式懒汉模式)

单例模式的创建(饿汉模式懒汉模式)

&#x1f388;专栏链接:多线程相关知识详解 目录 一.什么是单例模式 二.用static来创建单例模式 三.饿汉模式与懒汉模式 四.饿汉模式与懒汉模式的线程安全问题 五.New引发的指令重排序问题 六.小结 一.什么是单例模式 单例模式就是指某个类有且只有一个实例(instance…
阅读更多...
单例模式：懒汉模式

单例模式：懒汉模式

所谓“懒汉式”与“饿汉式”的区别&#xff0c;是在与建立单例对象的时间的不同。 “懒汉式”是在你真正用到的时候才去建这个单例对象“饿汉式是在类创建的同时就已经创建好一个静态的对象&#xff0c;不管你用的用不上&#xff0c;一开始就建立这个单例对象 代码实现&#x…
阅读更多...
java 单例模式 之懒汉模式

java 单例模式 之懒汉模式

单例模式&#xff1a;一个类&#xff0c;始终仅仅对外提供自己的一个实例&#xff0c;这样的设计方案&#xff0c;就称单例模式。 懒汉模式&#xff1a; 构造函数私有 声明私有的本类静态实例 定义静态的方法&#xff0c;在方法中创建本类实例&#xff0c;并返回该实例 pu…
阅读更多...
单例模式饿汉模式与懒汉模式

单例模式饿汉模式与懒汉模式

目录 1.什么是单例模式 2.为什么需要单例模式&#xff1f; 3.如何实现单例模式 3.1饿汉方式 3.2懒汉模式 1.什么是单例模式 单例模式是一种设计模式&#xff0c;单例模式能保证某个类在程序中只存在唯一一份实例, 而不会创建出多个实例。单例模式的具体实现又分为饿汉模式…
阅读更多...
关于Java中单例模式(饿汉模式和懒汉模式)的简析

关于Java中单例模式(饿汉模式和懒汉模式)的简析

目录 一.什么是单例模式 二.饿汉模式和懒汉模式 饿汉模式 代码 懒汉模式 代码 关于多线程安全的问题 如何解决懒汉模式多线程安全问题 双if判断 一.什么是单例模式 简单来说,就是我们在程序中通过代码进行限制,在该程序中 只能创建一个对象 二.饿汉模式和懒汉模式 …
阅读更多...
java设计模式之单例模式|单例模式之饿汉模式、懒汉模式、枚举方式|最详细的6种懒汉模式详解

java设计模式之单例模式|单例模式之饿汉模式、懒汉模式、枚举方式|最详细的6种懒汉模式详解

目录 一、单例模式 二、饿汉模式和懒汉模式 1、饿汉模式&#xff0c;线程安全 2、懒汉模式 懒汉模式1&#xff0c;线程不安全&#xff08;不常用&#xff09; 懒汉模式2&#xff0c;线程安全&#xff08;不常用&#xff09; 懒汉模式3&#xff0c;线程安全&#xff0c;双…
阅读更多...
全志F1C100s主线linux入坑记录 （10）调试串口更改

全志F1C100s主线linux入坑记录 （10）调试串口更改

调试串口更改 百度网站 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 调试串口更改前言uboot 修改一、修改设备树二、修改文件3. 修改内核传递参数 内核修改参考 前言 未完成版本 未完成版本 未完成版本 未完成…
阅读更多...
f1c100s 调试问题汇总

f1c100s 调试问题汇总

问题 usb无法识别 windows显示无法识别的usb设备 解决&#xff1a; 卸载设备&#xff0c;插拔一下&#xff0c;就可以识别了&#xff0c;之后就会自动安装驱动。 umount失败 fuser ./d2 可以显示出当前哪个程序在使用磁盘上的某个文件、挂载点、甚至网络端口&#xff0c;并…
阅读更多...
推荐文章

Copyright @ 2022~2023