HashMap 详解

一、核心特性

HashMap集合的key是无序不可重复的。

    ①无序：插入顺序和取出顺序不一定相同。

     ②不可重复：key具有唯一性。

向HashMap集合中put时，key如果重复的话，value会覆盖。

二、HashMap集合的key具有唯一性，向key部分插入自定义的类型会怎样？

当向 HashMap 的 key 部分插入自定义类型时，其行为取决于你是否正确重写了 hashCode() 和 equals() 方法。以下是不同场景下的表现：

1. 未重写 hashCode 和 equals

默认使用 Object 类的 hashCode()（基于内存地址生成哈希值）和 equals()（比较内存地址是否相同）。
结果：
即使两个对象的内容完全相同，也会被 HashMap 视为不同的 key，导致重复插入，破坏 key 的唯一性

示例代码：

User类：

public class User {private String name;private int age;public User(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}
}

测试类：

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型Map<User, Integer> map = new HashMap<>();// 准备User对象User user1 = new User("zhangsan", 20);User user2 = new User("lisi", 22);User user3 = new User("wangwu", 21);User user4 = new User("zhaoliu", 19);User user5 = new User("zhaoliu", 19);// 向Map集合中put：key+valuemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历Set<User> users = map.keySet();for(User user : users){Integer value = map.get(user);System.out.println(user + "====>" + value);}}
}

运行结果：

2. 仅重写 equals，未重写 hashCode

若两个对象 equals() 返回 true，但 hashCode() 不同，HashMap 会将它们分配到不同的哈希桶中。
结果：
HashMap 无法正确识别它们是“相同”的 key，仍会重复插入。

User类

public class User {private String name;private int age;public User(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic boolean equals(Object obj) {//如果name一样，age也一样，就表示同一个用户if(obj==null)return false;if(obj==this)return true;if(obj instanceof User){User user=(User) obj;return user.getName().equals(this.getName())&&user.getAge()==this.getAge();}return false;}}

测试类：

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型Map<User, Integer> map = new HashMap<>();// 准备User对象User user1 = new User("zhangsan", 20);User user2 = new User("lisi", 22);User user3 = new User("wangwu", 21);User user4 = new User("zhaoliu", 19);User user5 = new User("zhaoliu", 19);// 向Map集合中put：key+valuemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历Set<User> users = map.keySet();for(User user : users){Integer value = map.get(user);System.out.println(user + "====>" + value);}}
}

运行结果：

3. 正确重写 hashCode 和 equals

如果equals方法返回的结果是true。

那么hashCode()方法返回的结果就必须相同。这样才能保证key是不重复的。

存放在HashMap集合key部分的元素，以及存储在HashSet集合中的元素，都需要同时重写hashCode+equals

HashMap 通过以下步骤保证 key 的唯一性：

1. 计算哈希值：用 hashCode() 确定 key 所属的哈希桶。

2. 冲突处理：在同一个哈希桶内，用 equals() 检查是否存在内容相同的 key。

结果：
内容相同的 key 会被视为同一个 key，后插入的 value 会覆盖之前的 value。

User类：重写了equals方法和hashcode方法

import java.util.Objects;public class User {private String name;private int age;public User(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;User user = (User) o;return age == user.age && Objects.equals(name, user.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}
}

测试类：

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest1 {public static void main(String[] args) {// Map集合的key部分存储的是自定义的类型Map<User, Integer> map = new HashMap<>();// 准备User对象User user1 = new User("zhangsan", 20);User user2 = new User("lisi", 22);User user3 = new User("wangwu", 21);User user4 = new User("zhaoliu", 19);User user5 = new User("zhaoliu", 19);// 向Map集合中put：key+valuemap.put(user1, 110);map.put(user2, 111);map.put(user3, 112);map.put(user4, 113);map.put(user5, 114);// 遍历Set<User> users = map.keySet();for(User user : users){Integer value = map.get(user);System.out.println(user + "====>" + value);}}
}

运行结果：

三、HashMap 底层数据结构详解

HashMap 的底层实现是一个高效的哈希表结构，结合了 数组、链表和红黑树 的优势，具体设计如下：

1. 核心结构：数组 + 链表 + 红黑树

数组（哈希桶）
数组是哈希表的主干，每个数组元素称为一个 桶（Bucket）。通过哈希函数将键（Key）映射到数组的特定索引位置，实现 O(1) 时间复杂度的快速定位。

Node<K,V>[] table; // 数组结构，每个元素是一个链表的头节点或红黑树的根节点

链表
当不同的键映射到同一个桶时（哈希冲突），这些键值对会以 链表 形式存储。链表解决冲突，但查询效率为 O(n)。

static class Node<K,V> { // 链表节点结构final int hash;final K key;V value;Node<K,V> next;
}

红黑树
Java 8 优化：当链表长度 ≥8 且数组长度 ≥64 时，链表转换为 红黑树，查询效率提升至 O(logn)；当节点数 ≤6 时，红黑树退化为链表。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { // 红黑树节点TreeNode<K,V> parent;TreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;
}

2.哈希表存储原理

(1) 哈希表（Hash Table）

• 本质：一种结合 数组快速定位 和 链表/红黑树动态扩展 的数据结构。

• 核心组成：

  • 数组：用于直接定位元素（时间复杂度 O(1)）。

  • 链表/红黑树：解决哈希冲突，平衡查询与插入效率。

(2) 哈希函数（Hash Function）

• 作用：将任意对象映射为一个整数（哈希值）。

• Java 实现：hashCode() 方法返回初始哈希值，但 HashMap 会进一步处理：

// HashMap 内部对哈希值的优化处理（扰动函数）
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 要求：好的哈希函数应让不同对象尽量映射到不同的哈希值，减少碰撞。

(3) 哈希碰撞（Hash Collision）

• 定义：不同对象计算出的 数组索引相同（即 (hash & (n-1)) 结果相同）。

• 解决方式：

  • 链表法：同一索引位置的元素形成链表（Java 8 前）。

  • 红黑树优化：链表长度 ≥8 且数组长度 ≥64 时，转为红黑树（Java 8+）。

3.重写规范

• 规则 1：若 equals() 返回 true，则 hashCode() 必须相同。

• 规则 2：hashCode() 相同的对象，equals() 不一定返回 true（允许哈希碰撞）。

正确示例：

class Student {String id;@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return Objects.equals(id, student.id);}@Overridepublic int hashCode() {return Objects.hash(id); // 基于 id 生成哈希值}
}

4. 哈希碰撞的底层处理流程

(1) 插入键值对 (key, value)

1. 计算哈希值：hash = hash(key.hashCode())。

2. 定位桶索引：index = (n - 1) & hash（等价于 hash % n）。

3. 处理冲突：

   • 情况 1：桶为空 → 直接插入新节点。

   • 情况 2：桶为链表 → 遍历链表，若找到相同 key 则覆盖 value；否则添加到链表尾部。

   • 情况 3：桶为红黑树 → 调用红黑树的插入方法。

(2) 链表转红黑树的阈值

条件	动作
链表长度 ≥8 且 数组长度 ≥64	链表 → 红黑树
红黑树节点数 ≤6	红黑树 → 链表

5.HashMap集合的key可以是null吗？ 

 可以key是null，但肯定是只能有一个。

规则：如果key是null，直接存到下标为0的数组里

public class oop3 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put(null, "zhangsan");map.put(null, "lisi");map.put(null, "wangwu");map.put(null, "zhaoliu");System.out.println(map.size());Set<Map.Entry<String, String>> entries = map.entrySet();for(Map.Entry<String, String> entry : entries){System.out.println(entry.getKey() + "=" + entry.getValue());}}
}

运行结果;

四、手写HashMap

MyHashMap类：

/*** 手写HashMap集合的put方法和get方法。*/
public class MyHashMap<K,V> {/*** 哈希表*/private Node<K,V>[] table;/*** 键值对的个数*/private int size;@SuppressWarnings("unchecked")public MyHashMap() {// 注意：new数组的时候，不能使用泛型。这样写是错误的：new Node<K,V>[16];this.table = new Node[16];}static class Node<K,V>{/*** key的hashCode()方法的返回值。* 哈希值,哈希码*/int hash;/*** key*/K key;/*** value*/V value;/*** 下一个结点的内存地址*/Node<K,V> next;/*** 构造一个结点对象* @param hash 哈希值* @param key 键* @param value 值* @param next 下一个结点地址*/public Node(int hash, K key, V value, Node<K, V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}@Overridepublic String toString(){return "["+key+", "+value+"]";}}/*** 获取集合中的键值对的个数* @return 个数*/public int size(){return size;}/*** 向MyHashMap集合中添加一个键值对。* @param key 键* @param value 值* @return value，如果key重复，则返回oldValue，如果key不重复，则返回newValue*/public V put(K key, V value){/*【第一步】：处理key为null的情况如果添加键值对的key就是null，则将该键值对存储到table数组索引为0的位置。【第二步】：获得key对象的哈希值如果添加键值对的key不是null，则就调用key的hashcode()方法，获得key的哈希值。【第三步】：获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外，因此我们就需要将获得的哈希值转化为[0，数组长度-1]范围的整数，那么可以通过取模法来实现，也就是通过“哈希值 % 数组长度”来获得索引位置（i）。【第四步】：将键值对添加到table数组中当table[i]返回结果为null时，则键键值对封装为Node对象并存入到table[i]的位置。当table[i]返回结果不为null时，则意味着table[i]存储的是单链表。我们首先遍历单链表，如果遍历出来节点的key和添加键值对的key相同，那么就执行覆盖操作；如果遍历出来节点的key和添加键值对的key都不同，则就将键键值对封装为Node对象并插入到单链表末尾。*/if(key == null){return putForNullKey(value);}// 程序执行到此处说明key不是null// 获取哈希值int hash = key.hashCode();// 将哈希值转换成数组的下标int index = Math.abs(hash % table.length);// 取出下标index位置的NodeNode<K,V> node = table[index];if(null == node){table[index] = new Node<>(hash, key, value, null);size++;return value;}// 有单向链表（遍历单向链表，尾插法）Node<K,V> prev = null;while(null != node){if(node.key.equals(key)){V oldValue = node.value;node.value = value;return oldValue;}prev = node;node = node.next;}prev.next = new Node<>(hash, key, value, null);size++;return value;}private V putForNullKey(V value) {Node<K,V> node = table[0];if(node == null){table[0] = new Node<>(0, null,value,null);size++;return value;}// 程序可以执行到此处，说明下标为0的位置上有单向链表Node<K, V> prev = null;while(node != null){if(node.key == null){V oldValue = node.value;node.value = value;return oldValue;}prev = node;node = node.next;}prev.next = new Node<>(0, null,value,null);size++;return value;}/*** 通过key获取value* @param key 键* @return 值*/public V get(K key){/*【第一步】：处理key为null的情况如果查询的key就是null，则就在table数组索引为0的位置去查询。【第二步】：获得key对象的哈希值如果查询的key不是null，则就调用key的hashcode()方法，获得key的哈希值。【第三步】：获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外，因此我们就需要将获得的哈希值转化为[0，数组长度-1]范围的整数，那么可以通过取模法来实现，也就是通过“哈希值 % 数组长度”来获得索引位置（i）。【第四步】：遍历单链表，根据key获得value值如果table[i]返回的结果为null，则证明单链表不存在，那么返回null即可如果table[i]返回的结果不为null时，则证明单链表存在，那么就遍历整个单链表。如果遍历出来节点的key和查询的key相同，那么就返回遍历出来节点的value值；如果整个单链表遍历完毕，则遍历出来节点的key和查询的key都不相等，那么就证明查询key在链表中不存在，则直接返回null即可。*/if(null == key){Node<K,V> node = table[0];if(null == node){return null;}// 程序执行到这里，数组下标为0的位置不是null。就是有单向链表。while(node != null){if(null == node.key){return node.value;}node = node.next;}}// key不是nullint hash = key.hashCode();int index = Math.abs(hash % table.length);Node<K,V> node = table[index];if(null == node){return null;}while(null != node){if(node.key.equals(key)){return node.value;}node = node.next;}return null;}/*** 重写toString方法，直接输出Map集合是会调用。* @return ""*/@Overridepublic String toString(){StringBuilder sb = new StringBuilder();for (int i = 0; i < table.length; i++) {Node<K,V> node = table[i];// 如果node不是空，就遍历整个单向链表while(node != null){sb.append(node);node = node.next;}}return sb.toString();}
}

MyHashMapTest类：

/*** 测试自己编写的HashMap集合的方法。*/
public class MyHashMapTest {public static void main(String[] args) {MyHashMap<String,String> map = new MyHashMap<>();map.put("110", "张三");map.put("120", "李四");map.put("130", "王五");map.put("140", "赵六");map.put("110", "张三2");map.put(null, "钱七1");map.put(null, "钱七2");map.put(null, "钱七3");map.put(null, "钱七4");System.out.println(map);System.out.println(map.get(null));System.out.println(map.get("110"));System.out.println(map.get("120"));MyHashMap<User, String> userMap = new MyHashMap<>();User user1 = new User("张三", 20);User user2 = new User("李四", 22);User user3 = new User("王五", 23);User user4 = new User("王五", 23);userMap.put(user1, "110");userMap.put(user2, "120");userMap.put(user3, "130");userMap.put(user4, "abc");System.out.println(userMap);}
}

五、HashMap在Java8后的改进（包含Java8）

1.初始化时机：

Java8之前，构造方法执行时初始化table数组。

Java8之后，第一次调用put方法时初始化table数组。

2.插入法：

Java8之前，头插法

Java8之后，尾插法

3.数据结构：

Java8之前：数组 + 单向链表

Java8之后：数组 + 单向链表 + 红黑树。

最开始使用单向链表解决哈希冲突。如果结点数量 >= 8，并且table的长度 >= 64。单向链表转换为红黑树。

当删除红黑树上的结点时，结点数量 <= 6 时。红黑树转换为单向链表。

六、HashMap初始化容量永远都是2的次幂

HashMap集合初始化容量16（第一次调用put方法时初始化）

HashMap集合的容量永远都是2的次幂，假如给定初始化容量为31，它底层也会变成32的容量。

将容量设置为2的次幂作用是：加快哈希计算，减少哈希冲突。

为什么会加快哈希计算？

首先你要知道，使用二进制运算是最快的。

当一个数字是2的次幂时，例如数组的长度是2的次幂：

hash & (length-1) 的结果和 hash % length的结果相同。

注意：只有是2的次幂时，以上等式才会成立。因为了使用 & 运算符，让效率提升，因此建议容量一直是2的次幂。

为什么会减少哈希冲突？

底层运算是：hash & length - 1

如果length是偶数：length-1后一定是奇数，奇数二进制位最后一位一定是1,1和其他二进制位进行与运算，结果可能是1，也可能是0，这样可以减少哈希冲突，让散列分布更加均匀。

如果length是奇数：length-1后一定是偶数，偶数二进制位最后一位一定是0,0和任何数进行与运算，结果一定是0，这样就会导致发生大量的哈希冲突，白白浪费了一半的空间。

/*** 测试：HashMap集合的容量是否一直都是2的次幂。*      为什么？原因有二：*          第一：提高哈希计算的效率。（位运算肯定比%取模操作速度快。）*          第二：减少哈希冲突。让散列分布更加均匀。*/
public class oop3 {public static void main(String[] args) {Map<String, String> map = new HashMap<>(50);int length = (int)Math.pow(2, 6);System.out.println(length); // 2048// 使用取模 % 进行哈希计算int hash = "张三".hashCode();int index = hash % length;System.out.println(index); // 745// 使用 & 进行哈希计算/*假设length是偶数，length - 1结果一定是奇数。hash & length - 1;这个式子中 length - 1 是奇数。奇数的二进制位的最后一位一定是1.length - 1计算之后的结果对应的二进制位最低位一定是1.也就是：xxxxxxxxxxxxxxxxxxxx1然后拿着这个二进制位和hash进行与操作：hash可能得二进制位是：yyyyyyyyyyyyyyyyyyyy0也可能是：yyyyyyyyyyyyyyyyyyyy1xxxxxxxxxxxxxxxxxxxx1  (length - 1)& yyyyyyyyyyyyyyyyyyyy0  hash----------------------------zzzzzzzzzzzzzzzzzzzz0 (index) 是偶数xxxxxxxxxxxxxxxxxxxx1  (length - 1)& yyyyyyyyyyyyyyyyyyyy1  hash-----------------------------zzzzzzzzzzzzzzzzzzzz1（index）是奇数假设length是奇数，那么lenght - 1一定是偶数。它一定是：xxxxxxxxxxxxxxxxxxxxx0hash值可能是：yyyyyyyyyyyyyyyyyyyyy1也可能是：yyyyyyyyyyyyyyyyyyyyy0xxxxxxxxxxxxxxxxxxxxx0   length-1yyyyyyyyyyyyyyyyyyyyy1   hash-------------------------------zzzzzzzzzzzzzzzzzzzzz0   一定是偶数xxxxxxxxxxxxxxxxxxxxx0   length-1yyyyyyyyyyyyyyyyyyyyy0   hash-------------------------------zzzzzzzzzzzzzzzzzzzzz0   一定是偶数*/int index2 = hash & length - 1;System.out.println(index2); // 745}
}

运行结果;

七、关于 HashMap 初始化容量

当创建一个 HashMap 对象并设置初始容量为 15 时，哈希表的实际容量会被自动调整为 16。

原因解析

HashMap 的容量（即底层数组的长度）必须为 2 的幂次方（如 16、32、64 等）。这一设计的核心目的是优化哈希计算和元素分布：

1. 哈希计算优化：通过位运算 (n - 1) & hash 替代取模运算 hash % n，效率更高。

2. 均匀分布元素：当 n 是 2 的幂次方时，n - 1 的二进制形式为全 1（例如 16-1=15 → 1111），与哈希值的与运算能更均匀地分散元素到不同桶中。

若用户指定的初始容量不是 2 的幂次方，HashMap 会通过 tableSizeFor() 方法自动调整为 大于等于该值的最小 2 的幂次方。例如：

• 指定容量为 15 → 实际容量为 16。

• 指定容量为 17 → 实际容量为 32。

---

底层源码验证

HashMap 的 tableSizeFor() 方法负责调整容量：

static final int tableSizeFor(int cap) {int n = cap - 1; // 防止 cap 本身是 2 的幂次方时重复扩容n |= n >>> 1;    // 通过位运算将最高位后的所有位变为 1n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

示例计算（cap = 15）：

1. n = 15 - 1 = 14（二进制 1110）。

2. 依次右移并执行按位或操作：

   n |= n >>> 1 → 1110 | 0111 = 1111
   n |= n >>> 2 → 1111 | 0011 = 1111
   ...（后续操作不再改变结果）

1. 最终 n + 1 = 15 + 1 = 16。

---

性能优化建议

• 避免频繁扩容：
  若预计存储 N 个元素，建议设置初始容量为 N / loadFactor + 1（向上取整到最近的 2 的幂次方）。
  示例：

  • 预计存储 1000 个元素，负载因子默认 0.75：
    初始容量 = 1000 / 0.75 + 1 ≈ 1334 → 调整为 2048（最近的 2 的幂次方）。

• 权衡空间与时间：
  过大的初始容量会浪费内存，需根据实际场景平衡。

---

总结

用户指定容量	HashMap 实际容量	调整规则
15	16	大于等于 15 的最小 2 的幂
17	32	大于等于 17 的最小 2 的幂
1024	1024	本身已是 2 的幂

理解这一机制，可以更精准地设置初始容量，避免扩容带来的性能损耗。