当前位置： 首页 > news >正文

HashMap详解

news 2025/7/16 7:55:13

HashMap

学习HashMap需要先知道HashMap的一些基本知识点，首先HashMap的数据结构：数组+链表+红黑树（JDK1.8之后），HashMap的存取是无序的在一个数组中通过Hash算法把数据存入，HashMap的键和值都是可以为NULL的，但是键位置只能是一个NULL，HashMap是有阈值的也就是说当数组长度大于64，并且值大于8时，就会变成将链表变成红黑树，当红黑树节点 ≤6 时退化为链表。才会将链表转换成红黑树，目的是为了更加高效的查询。

当我们创建HashMap对象的时候，在JDK8之前，就是在构造方法当中创建一个长度为16的Entry[] Table用来存储键值对数据，JDK8以后就不是在HashMap构造方法创建数组了，是在第一次put方法的时候穿件数组，同时创建的是Node[] table，底层实现上还是Entry数组。

当我们使用HashMap的put的时候，可能会出现下面的操作。

当我们哈希碰撞的时候，就会比较内容，底层就会调用key值锁属于类型的equals方法来进行比较它们的value值是否相等，如果想等那么就会取代value1成为value2，假如说不相同，那么就会继续在这个链表上面进行比较，如果都不相同就会出现一个新的节点来进行存储。

注意！

我们来看一下put的时候会经历什么

首先开始的时候先判断是否创建的有Map假如说没有的话就会进行扩容，扩容到原来的二倍，初始为8，当我们进行存入的时候会通过Hash Code计算如果索引为空插入，不是的话就会通过equals方法来比较原来的key与插入的key一样的话直接覆盖，不一样的话，先判断这个数组下面是链表还是红黑树，如果是红黑树直接插入，不是的话开始遍历这个链表，遍历的时候判断链表长度是否大于8，是的话转换成红黑树，然后插入，不是的话链表插入插入之后会对这个数组的大小进行判断，如果键值对达到了临界值就会对HashMap进行扩容，这个临界值（threshold）=容量（capacity）*加载因子(load Factor)，也就是已经占用的数组的最大值，扩容依旧是两倍。

HashMap的继承关系

我们通过HashMap可以得知

  • Cloneable 空接口，表示可以克隆。创建并返回HashMap对象的一个副本。

  • Serializable 序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化

  • Abstract Map 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

我们实际上可以发现一个问题也就是HashMap本事就有实现一个Map接口，但是继承的父类里面还是实现着一个Map接口，为什么要这样？

实际上这是一个官方的小错误JAVA集合框架的创始人Josh Bloch描述这样的写法是一个失误，在java集合框架中，类似的写法也有很多，在设计之初，他认为这样写在某些地方可能是有价值的，知道他意识到并没有，显然JDK的维护者， Oracle 公司后来认为这样小小的错误不值得去修改，所以就这样保存了下来。

HashMap集合类的成员

成员变量

1.序列化版本号，HashMap实现这个接口的时候自带的一个默认版本号。

private static final long serialVersionUID = 362498820763181265L;

2.数组的长度（2^N）

默认的初始化容量是16。

为什么这个数组的长度应该是2的n次幂呢？

HashMap(int initialcapacity)构造一个带指定初始容量和默认加载因子(0.75)的空 Hashap。

我们通过底层可以得知，在向HashMap进行添加元素的时候，根绝key的hash值去确定在数组中的具体位置，HashMap为了存取的高效，要尽量避免减少哈希碰撞，每个链表的长度大致相同，为了实现这一功能，算法采用了取模hash%length，但是计算机中直接求余效率不如进行位移运算，所以源码中使用了hash&（length-1），而hash%length=hash&（length-1）的前提就是length是2的n幂。

我们来进行验证，我们取哈希值为2和3进行运算,下面是我们通过length为2的n次幂来计算没有出现哈希碰撞。

hash=3 & (8-1)
步骤1: 转换为二进制
hash = 3    →  0000 0011
length-1 =7 →  0000 0111
​
步骤2: 按位与运算0000 0011  (3)
& 0000 0111  (7)
-----------0000 0011  (3) → 最终索引为3hash=2 & (8-1)
步骤1: 转换为二进制
hash = 2    →  0000 0010
length-1 =7 →  0000 0111
​
步骤2: 按位与运算0000 0010  (2)
& 0000 0111  (7)
-----------0000 0010  (2) → 最终索引为2

当我们不按照这样来进行运算,我们将length变成9

hash=3 & (9-1)
步骤 1: 转换为二进制
hash = 3 → 0000 0011
length-1 =8 → 0000 1000
​
步骤 2: 按位与运算0000 0011 (3)
& 0000 1000 (8)
-------------------0000 0000 (0) → 最终索引为 0
​
hash=2 & (9-1)
步骤 1: 转换为二进制
hash = 2 → 0000 0010
length-1 =8 → 0000 1000
​
步骤 2: 按位与运算0000 0010 (2)
& 0000 1000 (8)
----------------0000 0000 (0) → 最终索引为 0

上面两个例子我们可以看的出来如果数组的长度不是2的n次幂，那么就容易出现哈希碰撞。本质是：当数组长度为 2 的幂时，hash & (length - 1) 能让哈希值低位充分参与运算，索引分布更均匀，减少冲突；若长度非 2 的幂，length - 1 二进制含无效高位 0，会压缩索引范围，增大冲突概率，这也是哈希表（如 HashMap ）设计中优先选 2 的幂为数组长度的核心原因 。

注意：如果不考虑效率的话，那么长度就可以随便设置了。

当我们初始化默认值就不是2的n次幂的时候底层怎么办？

我们通过HashMap的底层我们就可以知道

它底层会先进行判断，之后就会进行移位操作

static final int tableSizeFor(int cap) {int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这个tableSizeFor方法的作用是返回大于或等于给定容量cap的最小 2 的幂。也就是说会返回包含你所设置的最小2的n次幂，比方说初始6，那么就会返回8,初始为10返回16，numberOfLeadingZeros这个方法的底层就是所谓的移位操作。

当我们cap为6的时候

cap = 6;  
n = cap - 1; // 5 → 二进制 0000 0101  
​
n |= n >>> 1;  
原n:       0000 0101  
右移1位:   0000 0010  
按位或后:  0000 0111  
​
n |= n >>> 2;  
当前n:     0000 0111  
右移2位:   0000 0001  
按位或后:  0000 0111  
​
n |= n >>> 4;  
当前n:     0000 0111  
右移4位:   0000 0000  
按位或后:  0000 0111  
​
n |= n >>> 8;  
当前n:     0000 0111  
右移8位:   0000 0000  
按位或后:  0000 0111  
​
n |= n >>> 16;  
当前n:     0000 0111  
右移16位:  0000 0000  
按位或后:  0000 0111  
​
n = n + 1;  
结果:      0000 1000 → 8（2³，是≥6的最小2的幂）  

3.默认加载因子

也就是说当集合的容量大于0.75倍的总长的时候就会进行扩容，比方说总长16达到12的时候就会进行扩容。

默认加载因子为什么是0.75？

首先0.75是官方经过计算得到的一个比较好的临界值，假如说比0.75小的话可能会出现你的数组空的太多，造成资源的浪费，大于0.75的话就可能会出现数组过于臃肿，也就是说当我们达到阈值的时候，数组上的链表红黑树可能过多造成效率的降低，同时数组过于饱满，数组的扩容会比较麻烦所以0.75是经过计算的比较好的值。

4.集合的最大容量

集合的最大·容量上限是2^30

5.当链表的值超过8则会转化成红黑树

为什么Map桶中的节点个数超过8才转为红黑树？

我们对这段注释进行翻译

因为树的节点比较普通的链表节点大是两倍，所以我们只在存储的数据过多的时候才转换成红黑树，事实上在理想情况下，再随机哈希码的情况下，节点分布的概率是服从泊松分布的，也就是说在红黑树之前的链表上面，它的概率是依次递减，可以看到当链表长度为8的时候概率就已经很小了。

所以只有我们的集合包含足够多的节点的时候才会变成红黑树，只有链表长度达到8的时候就会转换成红黑树，长度降低到·6的时候就会又变成链表了。这是时间，空间的权衡之后的结果，红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时平均查找长度为8/2=4，这才有转换成树的必要;链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

HashMap中使用的计算哈希值的方法的剖析

/*** Computes key.hashCode() and spreads (XORs) higher bits of hash* to lower.  Because the table uses power-of-two masking, sets of* hashes that vary only in bits above the current mask will* always collide. (Among known examples are sets of Float keys* holding consecutive whole numbers in small tables.)  So we* apply a transform that spreads the impact of higher bits* downward. There is a tradeoff between speed, utility, and* quality of bit-spreading. Because many common sets of hashes* are already reasonably distributed (so don't benefit from* spreading), and because we use trees to handle large sets of* collisions in bins, we just XOR some shifted bits in the* cheapest possible way to reduce systematic lossage, as well as* to incorporate impact of the highest bits that would otherwise* never be used in index calculations because of table bounds.*/
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们查看put的源码会发现put的底层是一个putVal方法，里面的hash值算法如上

1.key.hashCode();返回散列值也就是hashcode。假设随便生成的一个值。

2.n表示数组初始化的长度是16

3.&(按位与运算):运算规则:相同的二进制数位上，都是1的时候，结果为1，否则为零。

4.^(按位异或运算):运算规则:相同的二进制数位上，数字相同，结果为0，不同为1。

hashCode的底层就是调用的c++的native方法

简单的对hash方法的解析就是：高16 bit 不变，低16 bit 和高16 bit 做了一个异或(得到的 hashcode 转化为32位二进制，前16位和后16位低，16 bit和高16 bit做了一个异或。

HashMap的扩容机制

扩容机制

当HashMap中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16x0.75=12(这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为2x16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。

补充: 当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。

HashMap的扩容是什么

进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的(n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量”这个位置。怎么理解呢?例如我们从16扩展为32时，具体的变化如下所示:

在原来长度的集合情况下，我们就发现了，在同一块数组空间下是有可能出现链表情况的，当我们进行扩容之后，在进行计算就会发现，原先在一个链表之内的数据最后可能会出现在原来的位置和旧位置+旧数组容量，所以扩容之后在一个链表上的数据的索引位置要么是原来索引，要么是原来索引+旧数组的容量。

事实上我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。如下图：

正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。

删除方法（remove）

删除的话就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于6的时候要转链表。

/*** Removes the mapping for the specified key from this map if present.** @param  key key whose mapping is to be removed from the map* @return the previous value associated with {@code key}, or*         {@code null} if there was no mapping for {@code key}.*         (A {@code null} return can also indicate that the map*         previously associated {@code null} with {@code key}.)*/
public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}

removeNode方法：

/*** 实现Map接口的remove方法及相关操作* * @param hash 键的哈希值（经过二次哈希处理）* @param key 要删除的键对象* @param value 若matchValue为true，则需要匹配此值才删除* @param matchValue 是否需要匹配值（true表示必须键值都匹配才删除）* @param movable 若为false，则删除时不移动其他节点（用于红黑树优化）* @return 被删除的节点，若未找到则返回null*/
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;// 步骤1：定位键所在的桶// 检查哈希表是否初始化且当前桶不为空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 步骤2：检查桶的第一个节点是否就是目标节点if (p.hash == hash &&  // 哈希值相等((k = p.key) == key || (key != null && key.equals(k))))  // 键相等（引用相等或值相等）node = p;  // 找到目标节点// 步骤3：如果第一个节点不是目标，则遍历后续节点else if ((e = p.next) != null) {// 情况1：如果当前是红黑树节点，调用红黑树的查找方法if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);// 情况2：如果是链表结构，遍历链表查找else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;  // 找到目标节点break;}p = e;  // 记录前驱节点} while ((e = e.next) != null);  // 继续遍历}}// 步骤4：找到节点后，根据条件删除节点if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {// 情况1：如果是红黑树节点，调用红黑树的删除逻辑if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);// 情况2：如果是链表的头节点，直接将桶指向头节点的下一个节点else if (node == p)tab[index] = node.next;// 情况3：如果是链表的中间节点，将前驱节点的next指向目标节点的下一个节点elsep.next = node.next;// 更新修改计数和大小++modCount;--size;// 回调方法，用于LinkedHashMap等子类实现删除后的操作afterNodeRemoval(node);return node;  // 返回被删除的节点}}return null;  // 未找到目标节点
}

查找元素方法（get）

通过元素key找到value

/*** Returns the value to which the specified key is mapped,* or {@code null} if this map contains no mapping for the key.** <p>More formally, if this map contains a mapping from a key* {@code k} to a value {@code v} such that {@code (key==null ? k==null :* key.equals(k))}, then this method returns {@code v}; otherwise* it returns {@code null}.  (There can be at most one such mapping.)** <p>A return value of {@code null} does not <i>necessarily</i>* indicate that the map contains no mapping for the key; it's also* possible that the map explicitly maps the key to {@code null}.* The {@link #containsKey containsKey} operation may be used to* distinguish these two cases.** @see #put(Object, Object)*/
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode方法

/*** 实现 Map.get 及相关方法的核心逻辑* * @param hash  键的哈希值（经过扰动函数处理）* @param key   要查找的键对象* @return      找到的节点，未找到则返回 null*/
final Node<K,V> getNode(int hash, Object key) {// 定义局部变量Node<K,V>[] tab;  // 哈希桶数组Node<K,V> first;  // 目标桶的第一个节点Node<K,V> e;      // 遍历链表的当前节点int n;            // 数组长度K k;              // 临时存储键对象
​// 步骤1：检查哈希表是否已初始化且目标桶非空if ((tab = table) != null           // 1.1 哈希表不为空&& (n = tab.length) > 0         // 1.2 数组长度>0&& (first = tab[(n - 1) & hash]) != null) {  // 1.3 计算桶位置并获取首节点
​// 步骤2：总是先检查首节点（快速路径）if (first.hash == hash &&  // 2.1 哈希值匹配((k = first.key) == key ||  // 2.2 键对象地址相同(key != null && key.equals(k))))  // 2.3 或equals匹配return first;  // 直接返回首节点
​// 步骤3：处理桶中的冲突节点if ((e = first.next) != null) {  // 3.1 存在后续节点// 3.2 如果是红黑树节点if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);  // 树查找// 3.3 链表遍历do {if (e.hash == hash &&  // 3.3.1 哈希匹配((k = e.key) == key ||  // 3.3.2 地址相同(key != null && key.equals(k))))  // 3.3.3 或equals匹配return e;  // 返回找到的节点} while ((e = e.next) != null);  // 遍历直到链表末尾}}// 步骤4：未找到匹配节点return null;
}

遍历HashMap的几种方式

1. 使用 entrySet() 迭代（推荐）

特点：

  • 直接获取键值对，效率最高

  • 适合需要同时访问 key 和 value 的场景

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
​
// 方式1：显式迭代器
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {Map.Entry<String, Integer> entry = it.next();System.out.println(entry.getKey() + ": " + entry.getValue());
}
​
// 方式2：for-each循环（更简洁）
for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());
}

2. 使用 keySet() 遍历键

特点：

  • 仅需访问 key 时使用

  • 获取 value 需额外查询（性能略低）

for (String key : map.keySet()) {Integer value = map.get(key); // 需要重新哈希计算System.out.println(key + ": " + value);
}

3. 使用 values() 遍历值

特点：

  • 仅需访问 value 时使用

  • 无法直接获取对应的 key

for (Integer value : map.values()) {System.out.println("Value: " + value);
}

4. Java 8+ Lambda 表达式

特点：

  • 代码简洁，适合函数式编程

  • 无法在遍历中修改 Map

// 遍历键值对
map.forEach((key, value) -> {System.out.println(key + ": " + value);
});
​
// 仅遍历键
map.keySet().forEach(key -> System.out.println(key));
​
// 仅遍历值
map.values().forEach(value -> System.out.println(value));

如何设计多个非重复键值对要存储HashMap的初始化

当我们确切的知道我们有多少键值对需要存储，那么我们在初始化HashMap的时候应该指定它的容量，以防止HashMap自动扩容影响效率。

默认情况下HashMap的容量是16，但是，如果用户通过构造函数指定了一个数字作为容量，那么Hash会选择大于该数字的第一个2的幂作为容量。(3->4、7->8、9->16)这点我们在已经进行过了解。

《阿里巴巴]ava开发手册》中建议我们设置HashMap的初始化容量。

那么，为什么要这么建议?你有想过没有。

当然，以上建议也是有理论支撑的。我们上面介绍过，HashMap的扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数(size)超过临界值(threshold)时就会自动扩容。在HashMap中，threshold= loadFactor * capacity.

所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap会有可能发生多次扩容，而HashMap中的扩容机制决定了每次扩容都需要重建hash表，是非常影响性能的。

HashMap中容量的初始化

当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。那么，是不是我们只需要把已知的HashMap中即将存放的元素个数直接传给initialCapacity就可以了呢?

关于这个值的设置，在《阿里巴巴java开发手册》有以下建议:

正例:initialcapacity=(需要存储的元素个数 / 负载因子)+ 1.注意负载因子(即loaderfactor)默认为0.75，

也就是说，如果我们设置的默认值是7，经过]dk处理之后，会被设置成8，但是，这个HashMap在元素个数达到8*0.75=6的时候就会进行一次扩容，这明显是我们不希望见到的。我们应该尽量减少扩容。原因也已经分析过,。

如果我们通过initialcapacity/ 0.75F+1.0F计算，7/0.75+1=10,10经过Jdk处理之后，会被设置成16，这就大大的减少了扩容的几率。 当HashMap内部维护的哈希表的容量达到75%时(默认情况下)，会触发rehash，而rehash的过程是比较耗费时间的。所以初始化容量要设置成initialcapacity/0.75+1的话，可以有效的减少冲突也可以减小误差。

所以，我可以认为，当我们明确知道HashMap中元素的个数的时候，把默认容量设置成initialCapacity/ 0.75F +1.0F是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

我们想要在代码中创建一个HashMap的时候，如果我们已知这个Map中即将存放的元素个数，给HashMap设置初始容量可以在一定程度上提升效率。

但是，JDK并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个2的幂。原因也已经分析过。

但是，为了最大程度的避免扩容带来的性能消耗，我们建议可以把默认容量的数字设置成:initialcapacity/ 0.75F+1.0F 。

http://www.xdnf.cn/news/1126531.html

相关文章：

  • 优学教育官网搭建01首页
  • 多模态大语言模型arxiv论文略读（157）
  • Node.js 中http 和 http/2 是两个不同模块对比
  • React源码4 三大核心模块之一：Schedule，scheduleUpdateOnFiber函数
  • GBase 8a 与 Spring Boot + MyBatis 整合实战：从环境搭建到CRUD操作
  • Springboot集成SpringSecurity的介绍及使用
  • 【实时Linux实战系列】使用系统调用实现实时同步
  • 【PTA数据结构 | C语言版】前序遍历二叉树
  • 2025国自然青基、面上资助率，或创新低！
  • 板凳-------Mysql cookbook学习 （十一--------11)
  • C#，List＜T＞ 与 Vector＜T＞
  • 焊接机器人智能节气阀
  • 关于list
  • 微信小程序入门实例_____从零开始 开发一个每天记账的微信小程序
  • 【GPIO】从STM32F103入门GPIO寄存器
  • 153.在 Vue 3 中使用 OpenLayers + Cesium 实现 2D/3D 地图切换效果
  • 淘宝扭蛋机小程序开发：重构电商娱乐化体验的新范式
  • Kruskal重构树
  • Linux操作系统从入门到实战（九）Linux开发工具（中）自动化构建-make/Makefile知识讲解
  • 12.6 Google黑科技GShard：6000亿参数MoE模型如何突破显存限制？
  • 导出内存溢出案例分析
  • 学习秒杀系统-实现秒杀功能（商品列表，商品详情，基本秒杀功能实现，订单详情）
  • JavaScript认识+JQuery的依赖引用
  • ethers.js-8-bigNmber和callstatic模拟
  • 2025年最新香港站群服务器租用价格参考
  • 探索阿里云ESA：开启边缘安全加速新时代
  • 基于Ruoyi和PostgreSQL的统一POI分类后台管理实战
  • 论文阅读：arxiv 2025 A Survey on Data Contamination for Large Language Models
  • 从12kW到800V，AI服务器电源架构变革下，功率器件如何解题？
  • redisson 设置了过期时间，会自动续期吗