- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
Map 是一种存储键值对的集合。Map 集合可以根据 key 快速查找对应的 value 值。HashMap 是 Map 类型的一中.
HashMap 的底层存储结构是:数组 + 链表 + 红黑树.
下面我们通过 HashMap 的新增操作、查找操作来看 HashMap 的底层存储结构.
当调用 HashMap 的 put() 方法时,put() 方法的处理逻辑如下:
首先,它会调用 hash() 方法根据 key 计算出 hash 值,然后根据计算出的 hash 值计算出 key 对应的数组索引 i:
计算出 key 对应的数组索引 i 之后,它根据数组在索引 i 上的值进行处理:
接上一步骤,如果数组在索引 i 上的值不为 null.
接上一步骤,如果索引 i 上的结构是普通链表,则把新生成的节点加到链表的末尾之后,需要判断是否需要将链表转为红黑树:
将节点加入 HashMap 集合之后,put() 方法的最后一步,如果 HashMap 中元素的数量超过了扩容的阈值(threshold),那么它会调用 resize() 方法执行扩容操作.
当调用 HashMap 的 put() 方法时,如果 HashMap 中已经存在要新增的 key,并且方法的入参 onlyIfAbsent 为 false,则替换旧值,并返回旧值.
HashMap 中调用 hash() 方法根据 key 计算出 hash 值的规则是:
i = hash & (n - 1)
)。减少了碰撞的可能性。
// 向 HashMap 集合中新增键值对
// 如果 HashMap 集合中已经存在该键,那么旧的值将被替换
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
当调用 HashMap 的 put() 方法时,将节点加入 HashMap 集合之后,如果 HashMap 中元素的数量超过了扩容的阈值(threshold),那么它会调用 resize() 方法执行扩容操作.
HashMap 的扩容机制是扩容为原来容量的 2 倍。resize() 方法会重新计算每个元素的 hash 值,将元素重新放入新的位置,并更新下次扩容的阈值(threshold 成员变量)为原来阈值的 2 倍。初始扩容阈值 threshold = loadFactor * 数组的长度.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// 将节点加入 HashMap 集合
++modCount;
if (++size > threshold) {
// 执行扩容操作
resize();
}
afterNodeInsertion(evict);
return null;
}
当调用 HashMap 的 get() 方法时,get() 方法的处理逻辑如下:
面试中如何通过 HashMap 展示你在数据结构方面的功底?-极客时间 (geekbang.org) 。
当 HashMap 的 key 为自定义类型时,我们需要重写(Override)该类的 equals() 方法和 hashCode() 方法。因为:
HashMap 的数组长度总是为 2 的幂次方。不论传入的初始容量是否为 2 的幂次方,最终都会转化为 2 的幂次方.
HashMap 中根据 key 计算出 hash 值,然后根据计算出的 hash 值计算出 key 对应的数组索引 i 时,通过 hash 值 和 数组的长度 - 1 做与运算获得 key 对应的数组索引 i ,即 i = hash & (n - 1) .
HashMap 设计的非常巧妙:
i = hash & (n - 1)
)。减少了碰撞的可能性。 i = hash & (n - 1)
。由于数组的长度 n 是 2 的幂次方,n - 1 可以保证它的二进制的后几位都是 1,n 的这一位及之前的位都是 0。因此,计算出的数组索引 i 和 hash 值的二进制表示中后几位有关,而与前面的二进制位无关 a % b == a & (b - 1)
。CPU 处理位运算比处理数学运算的速度更快,效率更高。 HashMap 的死循环问题说的是,多个线程同时操作一个 HashMap,当 HashMap 中的键值对数量达到一定程度需要进行扩容操作时,HashMap 有可能会进入一个无限循环,导致程序无法正常执行.
这是因为多个线程同时操作一个 HashMap,多个线程调用 HashMap 的 resize() 执行扩容操作,HashMap 中的链表有可能成环,程序无法从遍历链表中退出,从而导致程序进入死循环.
最后此篇关于Java集合-HashMap的文章就讲到这里了,如果你想了解更多关于Java集合-HashMap的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我有不同的结构,它们都包含一个 HashMap与 String作为键,但具有不同的值类型。例如,一个结构有一个类型为 HashMap 的成员, 另一个将有一个 HashMap 类型的成员, 等等。 我
我想制作一个包含学生姓名和科目的板,每个学生在每个科目中都有一个成绩(或者没有..他可以离开考试而不写,然后他的案子将是空的)。我只想使用 HashMap。我的意思是,它会是这样的: HashMap>
是否有内存和速度高效的方法来在 HashMap 中动态存储唯一键:值对? key 保证是唯一的,但它们的数量经常变化。插入和删除必须很快。 我所做的是包含有符号距离场的八叉树(非线性/完整)。八叉树经
有谁知道为什么选择通过 LinkedList 而不是另一个 Hashmap 来实现 HashMap 的存储桶。如果桶本身变成了 HashMap,那么 contains 或 get 的时间复杂度似乎是
我想创建一个具有嵌套结构的 HashMap,就像这个复杂的示例: { type: boy name: Phineas father: type: man
这个问题在这里已经有了答案: How do I create a global, mutable singleton? (7 个答案) 关闭 7 年前。 我想要一个可扩展的字典,将 Object 与
HashMap> hm = new HashMap>(); hm.put("Title1","Key1"); for(int i=0;i hm1 = new H
我必须修改当前代码以适应 Spring MVC。我有 HashMap hashmap = new HashMap(); request.setAttribute("dslrErrors", hashm
我正在尝试进行一些错误捕获。 错误应该检查数组的长度是否小于 2,并检查 HashMap 是否包含用户输入的键。 捕获的错误必须仅使用 if 语句,并且必须使用 .length() 方法,并且必须使用
在 stackoverflow 上提出另一个问题后,(Java- Why this program not throwing concurrent Modification exception)我开始
我有两个类,想使用 org.dozer.Mapper( http://dozer.sourceforge.net/ ) 将 Female 对象的属性映射到 Male 对象。 第一类是: public
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be
是否有任何方法可以检查 HashMap 是否包含一组特定的键(这些键是在数组中给出的)。当我尝试类似下面的代码时,它返回 false。 map.containsKey(arrayOf("2018-01
跟进我的问题:How To Access hash maps key when the key is an object 我想尝试这样的事情:webSearchHash.put(xfile.getPa
我有一个可扩展的 ListView ,对于每个 child ,我需要有 4 个“额外”或字符串或其他名称来调用它:- 子标题- 描述- 链接1- 链接2 跟着教程,创建 ListView 、不同的 p
我想确保这是正确的,因为如果不正确,它可能会破坏我的应用程序。 我有这个: private static HashMap> balance = new HashMap<>(); 如果我得到这样的值:
我想做以下事情: 为某个键查找Vec,并将其存储以备后用。 如果它不存在,则为键创建一个空的 Vec,但仍将其保存在变量中。 如何有效地做到这一点?自然地,我认为我可以使用 match: use st
我想做以下事情: 为某个键查找Vec,并将其存储以备后用。 如果它不存在,则为键创建一个空的 Vec,但仍将其保存在变量中。 如何有效地做到这一点?自然地,我认为我可以使用 match: use st
我想做以下事情: 为某个键查找Vec,并将其存储以备后用。 如果它不存在,则为键创建一个空的 Vec,但仍将其保存在变量中。 如何有效地做到这一点?自然地,我认为我可以使用 match: use st
我想做以下事情: 为某个键查找Vec,并将其存储以备后用。 如果它不存在,则为键创建一个空的 Vec,但仍将其保存在变量中。 如何有效地做到这一点?自然地,我认为我可以使用 match: use st
我是一名优秀的程序员,十分优秀!