Java哈希表入门详解（Hash） - 指南

一、什么是哈希表？

想象一下你正在图书馆里。

• 数组：就像一排编号从0到N的书架。如果你知道你想找的书在第100号书架，你可以直接走过去拿到它，非常快（这就是数组的“随机访问”）。但如果你只知道书名，你就得从第一个书架开始一个一个找，直到找到为止，这非常慢（这就是数组按内容查找的缺点，时间复杂度 O(n)）。

• 哈希表：就像一个非常聪明的图书管理员。你只需要告诉他书名（比如 《Java编程思想》），他瞬间就能告诉你这本书在 “J-15” 这个书架上。

这个“聪明的图书管理员”就是哈希函数（Hash Function）。

二、哈希表的核心机制

1. 哈希函数 (Hash Function)

一个好的哈希函数应该：

• 确定性：相同的键必须总是产生相同的哈希值。

• 高效：计算速度要快。

• 均匀分布：能将不同的键均匀地映射到不同的索引上，减少“冲突”。

在 Java 中，每个对象都有一个 .hashCode() 方法，它返回一个 int 类型的哈希值。哈希表内部就是利用这个方法来定位的。

2. 哈希冲突 (Hash Collision)

冲突是不可避免的。因为哈希值是一个 int，而键的可能性是无限的（比如字符串可以是任意长度），所以不同的键完全有可能计算出相同的哈希值（从而得到相同的数组索引）。

例如：“Aa” 和 “BB” 这两个字符串的 .hashCode() 在 Java 中都是 2112。

那么如何处理冲突呢？主要有两种方法：

a) 链地址法 (Separate Chaining)

- Java HashMap 采用的方法
数组的每个桶里不再直接存储值，而是存储一个链表（或一棵红黑树）的头节点。当发生冲突时，新的键值对会被添加到对应桶的链表（或树）中。

b) 开放地址法 (Open Addressing)

当发生冲突时，它会寻找数组中的“下一个”空桶，直到找到空位为止。寻找下一个位置的方法有线性探测、二次探测等。Java 中的 ThreadLocalMap 使用了这种方法。

三、Java 中的实现：HashMap

1.如何理解HashMap

在 Java 中，最常用、最重要的哈希表实现是 HashMap 类（位于 java.util 包中）。

我们可以把 HashMap 想象成一个“字典”或者一个“储物柜”。

• 字典：你通过一个“字”（称为 Key，键）来查找这个字的“解释”（称为 Value，值）。

• 储物柜：你通过一个“柜号”（Key）来存取你存放的“物品”（Value）。

HashMap 就是这样一个存储“键值对（Key-Value Pairs）”的容器。它的设计初衷就是为了能通过 键（Key） 来快速查询、插入和删除其对应的值（Value）。

2.核心特性

1. 键不可重复：同一个 HashMap 中，每个键（Key）都是唯一的。如果你放入两个相同的 Key，后一个 Value 会覆盖前一个。

2. 允许 null 键和 null 值：HashMap 允许你使用 null 作为 Key，也允许使用 null 作为 Value。

3. 无序：HashMap 不记录元素的插入顺序，也不会自己进行排序。遍历它的时候，顺序是不可预测的。（如果你需要有序，可以使用 LinkedHashMap）。

4. 非线程安全：HashMap 不是为多线程环境设计的。如果多个线程同时操作同一个 HashMap 且没有做同步处理，可能会导致数据不一致。在多线程环境下应使用 ConcurrentHashMap。

3.HashMap 的创建

在使用前，需要先导入它所在的包（Java 集合框架的一部分）：

import java.util.HashMap;

创建 HashMap 对象的语法：

// 基本语法：Key 和 Value 的类型需要指定
HashMap map = new HashMap<>();
// 示例：创建一个 Key 是 String 类型，Value 是 Integer 类型的 HashMap
HashMap priceMap = new HashMap<>();
// 也可以在创建时指定初始容量（可选的优化参数，初学者可先忽略）
HashMap userMap = new HashMap<>(20);

4.基本常用方法（CRUD）

CRUD 代表 Create（创建）、Read（读取）、Update（更新）、Delete（删除），这是最核心的操作。

假设我们创建一个管理水果价格的 Map：

HashMap fruitPrices = new HashMap<>();

（1） 添加/更新元素：put(K key, V value)

// 添加键值对
fruitPrices.put("Apple", 5);   // -> {Apple=5}
fruitPrices.put("Banana", 3);  // -> {Apple=5, Banana=3}
fruitPrices.put("Orange", 4);  // -> {Apple=5, Banana=3, Orange=4}
// 更新：使用已存在的 Key 放入新的 Value
fruitPrices.put("Apple", 6);   // -> {Apple=6, Banana=3, Orange=4}
// Apple 的价格从 5 更新为 6

（2） 获取元素：get(Object key)

// 通过 Key 来获取对应的 Value
int applePrice = fruitPrices.get("Apple"); // applePrice = 6
int bananaPrice = fruitPrices.get("Banana"); // bananaPrice = 3
// 如果获取一个不存在的 Key，会返回 null
Integer unknownPrice = fruitPrices.get("Mango"); // unknownPrice = null
// 注意：如果用 int 类型接收 null，会抛出 NullPointerException
// 所以更安全的做法是使用 Integer 类型接收，或者先判断

（3）判断键是否存在：containsKey(Object key)

// 在获取之前，最好先检查 Key 是否存在，避免 NullPointerException
if (fruitPrices.containsKey("Mango")) {System.out.println("Mango price: " + fruitPrices.get("Mango"));
} else {System.out.println("We don't have mango.");
}

（4） 删除元素：remove(Object key)

// 删除指定 Key 对应的键值对
fruitPrices.remove("Orange"); // -> {Apple=6, Banana=3}
// 键值对 "Orange=4" 被移除了

（5） 获取大小：size()

// 返回 Map 中键值对的数量
int size = fruitPrices.size(); // size = 2

（6） 判断是否为空：isEmpty()

// 判断 Map 是否没有任何键值对
boolean isEmpty = fruitPrices.isEmpty(); // isEmpty = false

（7）清空所有元素：clear()

fruitPrices.clear(); // -> {}
System.out.println(fruitPrices.isEmpty()); // 输出 true

5.遍历 HashMap

遍历是非常常见的操作，有几种主要方式：

假设我们有如下 Map：

HashMap fruitPrices = new HashMap<>();
fruitPrices.put("Apple", 5);
fruitPrices.put("Banana", 3);
fruitPrices.put("Orange", 4);

方法 1：遍历所有的 Key — keySet()

keySet() 方法返回一个包含所有 Key 的 Set 集合。

for (String fruit : fruitPrices.keySet()) {System.out.println("Fruit: " + fruit);// 通过 Key 可以再获取 ValueSystem.out.println("Price: " + fruitPrices.get(fruit));
}

方法 2：遍历所有的 Value — values()

values() 方法返回一个包含所有 Value 的 Collection 集合。（不常用，因为丢失了 Key 的信息）

for (Integer price : fruitPrices.values()) {System.out.println("Price: " + price);
}

方法 3（最常用、最高效）：遍历所有的键值对 — entrySet()

entrySet() 方法返回一个包含所有“键值对入口”（Map.Entry 对象）的 Set 集合。每个 Entry 对象都有 getKey() 和 getValue() 方法。

for (HashMap.Entry entry : fruitPrices.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + " costs $" + value);
}
// 输出：
// Apple costs $5
// Banana costs $3
// Orange costs $4

为什么推荐这个方法？ 因为在遍历时直接拿到了 Key 和 Value，无需再通过 get(key) 去查询，效率更高。

6.一个完整的代码示例

import java.util.HashMap;
public class HashMapDemo {public static void main(String[] args) {// 1. 创建 HashMapHashMap capitalCities = new HashMap<>();// 2. 添加键值对capitalCities.put("England", "London");capitalCities.put("Germany", "Berlin");capitalCities.put("Norway", "Oslo");capitalCities.put("USA", "Washington DC");System.out.println("Initial Map: " + capitalCities); // 直接打印整个Map// 3. 获取元素String capitalOfGermany = capitalCities.get("Germany");System.out.println("Capital of Germany is: " + capitalOfGermany);// 4. 删除元素capitalCities.remove("England");System.out.println("After removing England: " + capitalCities);// 5. 检查大小和是否为空System.out.println("Size: " + capitalCities.size());System.out.println("Is empty? " + capitalCities.isEmpty());// 6. 检查键是否存在if (capitalCities.containsKey("USA")) {System.out.println("USA is in the map.");}// 7. 遍历 Map (推荐方式)System.out.println("\nTraversing the map:");for (HashMap.Entry entry : capitalCities.entrySet()) {System.out.println("Country: " + entry.getKey() + " -> Capital: " + entry.getValue());}// 8. 清空 MapcapitalCities.clear();System.out.println("After clear: " + capitalCities);}
}

7、hashmap总结

1. 创建：HashMap<KeyType, ValueType> map = new HashMap<>();

2. 增/改：map.put(key, value);

3. 查：map.get(key);

4. 删：map.remove(key);

5. 遍历：首选for (Map.Entry<KeyType, ValueType> entry : map.entrySet()) { ... }

6. 判断存在：map.containsKey(key)

四、哈希表总结

1. 首选 HashMap：在绝大多数不需要线程安全的场景下，都使用 HashMap。

2. 正确重写 hashCode() 和 equals()：如果你要用自定义的类（比如 Student, Employee）作为 HashMap 的键，你必须同时重写这个类的 hashCode() 和 equals() 方法。

   • hashCode() 决定了键值对存放在哪个桶里。

   • equals() 用于在发生哈希冲突时，在链表中比较两个键是否真正相等。

   • 规则：如果两个对象通过 equals() 比较是相等的，那么它们的 hashCode() 也必须相等。

3. 理解基本原理：明白哈希、冲突、扩容这些概念，能帮助你更好地使用和理解 HashMap 的行为，而不是仅仅死记硬背API。