Java 中 Map 常用类和数据结构详解

1. 引言

在Java编程中，Map是一种重要的数据结构，广泛应用于各种场景，Map实现了键值对（key-value）的存储方式，使得开发者能够快速检索、更新和操作数据。本篇文章将详细讲解Java中常用的Map类及其底层数据结构，并通过电商交易系统中的实际应用场景来分析每种Map的使用场景和区别。

2. HashMap

2.1 HashMap 的实现原理

HashMap 是 Java 中常用的一个用于存储键值对的集合类，它以哈希表的形式实现，能够提供快速的数据访问。HashMap 通过键的哈希码（hash code）来定位存储的桶（bucket），并通过不同的处理机制来处理哈希冲突。

2.1.1 HashMap 的基本原理

HashMap 的基本结构是一个数组，每个数组位置称为一个桶（bucket）。每个桶存储的内容可以是一个单独的键值对，也可以是多个键值对的链表或红黑树。在插入数据时，HashMap 首先通过哈希函数根据键的哈希码计算出该键应该存储在哪个桶中，然后将该键值对存储在相应的桶里。

当多个键通过哈希函数得到的桶索引相同时，称为哈希冲突。为了解决哈希冲突，早期版本的HashMap会将所有冲突的键值对存储为一个链表，从 Java 8 开始，HashMap在链表长度超过一定阈值后（默认是8），将链表转换为红黑树来优化查询效率。

2.1.2 Java 7及之前的实现

在 Java 7 及之前，HashMap 的每个桶只包含一个简单的链表结构。当出现哈希冲突时，不同的键值对会通过链表链接在一起。链表的结构如下：

• 每个桶包含一个链表的头节点。
• 链表中的每个节点包含了键、值和指向下一个节点的指针。
• 插入和查询操作在链表中都是线性查找，时间复杂度为 O(n)，其中 n 是链表的长度。

这种结构在数据量小或冲突少的情况下效率较高，但在哈希冲突严重时，查找的性能会迅速下降为 O(n)，因为需要遍历链表的所有节点。

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}// Map.Entry接口的实现方法
}

2.1.3 Java 8 之后的实现

在 Java 8 中，为了解决哈希冲突严重时性能退化的问题，HashMap 引入了红黑树。当单个桶中的元素数量超过一定阈值（默认是8个）时，HashMap 会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，能够保证在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log n)。

核心变化：

• 当链表中的节点数小于阈值时，依旧使用链表。
• 当链表中的节点数超过阈值时，链表转换为红黑树，保证查找和插入操作的效率为 O(log n)。
• 当红黑树的节点数量减少到阈值以下时，会重新退化为链表。

链表转红黑树：

if (binCount >= TREEIFY_THRESHOLD - 1) {treeifyBin(tab, hash);
}

红黑树的结构： 红黑树的实现通过 TreeNode 类完成，TreeNode 继承自 HashMap.Node，其结构与普通的链表节点不同，额外增加了指向父节点、左子节点和右子节点的引用，以维护红黑树的平衡。

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;TreeNode(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}
}

2.1.4 链表与红黑树的区别

• 结构不同：链表是线性的，红黑树是一种平衡的二叉树。
• 性能差异：链表的查找时间复杂度是 O(n)，而红黑树的查找时间复杂度是 O(log n)。因此，红黑树在元素数量多时性能优于链表。
• 存储结构的转换：当桶中的元素数量超过 8 个时，链表会转换为红黑树；当数量少于 6 个时，红黑树会退化为链表。

2.1.5 详细实现机制

HashMap 的哈希函数和哈希冲突处理机制是其核心部分。HashMap 通过对键的哈希码进行一系列运算，来确保散列的均匀性并避免哈希冲突。在处理冲突时，如果桶中的元素较少，HashMap 采用链表结构；如果元素较多，则采用红黑树，以保证性能的稳定性。

以下是HashMap中几个重要的阈值：

• DEFAULT_INITIAL_CAPACITY：默认的初始容量为 16。
• DEFAULT_LOAD_FACTOR：默认的负载因子为 0.75。
• TREEIFY_THRESHOLD：链表转为红黑树的阈值为 8。
• UNTREEIFY_THRESHOLD：红黑树转为链表的阈值为 6。
• MIN_TREEIFY_CAPACITY：最小的树化容量为 64，避免在低容量时频繁转换。

2.1.6 HashMap 底层结构类图

2.1.7 总结

• Java 7及之前：HashMap 通过链表处理哈希冲突，查找时间复杂度为 O(n)。
• Java 8及之后：HashMap 引入了红黑树，当冲突较少时使用链表，冲突严重时使用红黑树，查找时间复杂度优化为 O(log n)。
• 链表与红黑树的转换：当链表节点超过阈值时会转换为红黑树，红黑树的查找和插入效率更高；当树中节点减少时，会退化为链表。

通过这种机制，HashMap 在 Java 8 之后进一步提升了在高冲突情况下的性能，使其在大规模数据存储中更高效。

2.2 适用场景

适用于大多数查询操作频繁的场景，例如订单查询、商品详情查询等。

2.2.1 提高性能的 HashMap List 转 Map 的电商案例

在电商系统中，我们经常需要处理大量的商品信息。通常商品信息以 List 形式存储，但在查询某个商品时，List 结构的查询效率较低，需要遍历整个列表。如果能将 List 转换为 Map，利用 HashMap 的 O(1) 查询效率，可以显著提升性能。

问题描述：

在一个电商系统中，商品信息通常以 List 形式存储。当用户进行商品搜索时，系统需要根据商品 ID 获取详细信息。假设我们有大量商品数据，List 结构下每次搜索都需要遍历列表，导致查询速度较慢，如何提高查询效率？

示例：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;class Product {String id;String name;double price;public Product(String id, String name, double price) {this.id = id;this.name = name;this.price = price;}public String getId() {return id;}@Overridepublic String toString() {return "Product{id='" + id + "', name='" + name + "', price=" + price + '}';}
}public class ListToMapExample {// 模拟一个获取商品列表的操作public static List<Product> getProductList() {List<Product> productList = new ArrayList<>();productList.add(new Product("101", "Laptop", 999.99));productList.add(new Product("102", "Smartphone", 699.99));productList.add(new Product("103", "Tablet", 299.99));return productList;}// 将List转换为Map，商品ID为key，商品对象为valuepublic static Map<String, Product> convertListToMap(List<Product> productList) {Map<String, Product> productMap = new HashMap<>();for (Product product : productList) {productMap.put(product.getId(), product);}return productMap;}public static void main(String[] args) {List<Product> productList = getProductList();// 转换 List 为 MapMap<String, Product> productMap = convertListToMap(productList);// 根据商品ID查询商品String searchId = "102";if (productMap.containsKey(searchId)) {System.out.println("Product found: " + productMap.get(searchId));} else {System.out.println("Product not found");}}
}

解决方式：

• 使用 HashMap 代替 List 作为商品存储的结构，将商品 ID 作为 HashMap 的键，这样在查询商品时只需 O(1) 的复杂度，而不再需要遍历整个列表。
• 示例中展示了如何将 List 转换为 HashMap，并基于商品 ID 高效查询商品信息。

优化效果：

相比原先的 List 结构，使用 HashMap 之后的查询性能显著提升，尤其在处理大规模商品数据时更加高效。

2.2.2 使用 HashMap 提高楼梯算法的查询效率

问题描述：

楼梯问题是经典的递归问题：假设楼梯有 n 级台阶，每次可以走 1 级或 2 级，问有多少种走法？在大规模计算时，递归方式效率较低。如何通过 HashMap 来加速查询，提高算法性能？

示例问题：

你需要通过递归计算楼梯的走法总数。然而，随着台阶数的增加，递归的重复计算严重影响了效率。如何优化这个过程？

楼梯问题递归解法：

public class StaircaseProblem {// 递归实现楼梯走法public static int countWays(int n) {if (n == 0 || n == 1) {return 1;}return countWays(n - 1) + countWays(n - 2);}public static void main(String[] args) {int n = 10;  // 假设楼梯有10级System.out.println("Ways to climb " + n + " stairs: " + countWays(n));}
}

问题分析：

上述递归实现效率较低，因为每次计算都会重复进行许多不必要的运算。比如，计算 countWays(10) 会调用多次 countWays(9) 和 countWays(8)，导致大量重复计算。

解决方式：使用 HashMap 优化递归（记忆化递归）

通过 HashMap 来缓存已经计算过的楼梯走法，将之前计算过的结果存储起来，避免重复计算。

优化后的代码：

import java.util.HashMap;
import java.util.Map;public class OptimizedStaircaseProblem {// 使用 HashMap 缓存已计算的结果private static Map<Integer, Integer> memo = new HashMap<>();public static int countWays(int n) {if (n == 0 || n == 1) {return 1;}// 如果已经计算过，直接返回缓存的结果if (memo.containsKey(n)) {return memo.get(n);}// 计算结果并存入缓存int result = countWays(n - 1) + countWays(n - 2);memo.put(n, result);return result;}public static void main(String[] args) {int n = 10;System.out.println("Ways to climb " + n + " stairs: " + countWays(n));}
}

优化方式分析：

• 使用 HashMap 来缓存已经计算过的台阶数对应的走法数。
• 每次递归时，先检查 HashMap 是否已经包含结果，如果有，直接返回，不再重复计算。
• 通过记忆化递归，极大减少了重复计算的次数，从而提升了算法效率。

解决效果：

通过使用 HashMap，我们将原本的递归解法优化为一种动态规划的思路，大幅度降低了时间复杂度，从指数级（O(2^n)）降低为线性级（O(n)），适合在大规模输入下的高效计算。

3. LinkedHashMap

LinkedHashMap 是 Java 集合框架中的一种基于 HashMap 实现的有序映射类。与 HashMap 不同，LinkedHashMap 维护了键值对的插入顺序或访问顺序，因此它提供了一个有序的迭代方式。LinkedHashMap 的主要特点是能够在保证键值对唯一性的同时，还能按顺序访问键值对。

3.1 LinkedHashMap 的特点

1. 有序性
   LinkedHashMap 保证了元素的迭代顺序。默认情况下，元素的迭代顺序与插入顺序一致。但可以通过构造函数设置为根据访问顺序（即最近最少使用策略 LRU）来迭代元素。
2. 插入和访问顺序的选择
   可以选择在元素被访问后（如通过 get()、put() 等方法）将该元素移到链表的尾部，从而按照访问顺序来迭代元素。适用于实现缓存等场景。
3. 线程不安全
   与 HashMap 类似，LinkedHashMap 也是线程不安全的。如果在多线程环境中使用 LinkedHashMap，需要对其进行手动同步或者使用 ConcurrentHashMap 作为替代。

3.2 LinkedHashMap 的适用场景

1. 缓存系统
   LinkedHashMap 非常适合实现缓存系统，尤其是那些基于 LRU 策略的缓存。通过 LinkedHashMap 的 removeEldestEntry 方法，可以实现当元素数量超过某个限制时自动移除最旧的元素。
2. 需要按顺序遍历的场景
   在一些需要按插入顺序或访问顺序来遍历键值对的场景，LinkedHashMap 可以很好地满足需求。

3.3 在电商系统中的应用

在电商系统中，用户的购物车是一种常见的缓存场景。为了优化性能，可以将用户最近添加到购物车的商品信息缓存到内存中。当购物车中的商品数量超过一定数量时，自动移除最早加入的商品。

代码示例：购物车缓存系统

以下示例代码展示了如何使用 LinkedHashMap 实现一个购物车的缓存系统，当购物车中的商品数量超过 5 时，自动移除最早加入的商品。

import java.util.LinkedHashMap;
import java.util.Map;public class ShoppingCart {private static final int MAX_CART_SIZE = 5;// 使用 LinkedHashMap 实现购物车缓存，并设置访问顺序private LinkedHashMap<String, Integer> cart = new LinkedHashMap<String, Integer>(MAX_CART_SIZE, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {return size() > MAX_CART_SIZE;}};// 添加商品到购物车public void addToCart(String product, int quantity) {cart.put(product, quantity);System.out.println("Added to cart: " + product + ", Quantity: " + quantity);displayCart();}// 显示购物车public void displayCart() {System.out.println("Current cart contents: " + cart);}public static void main(String[] args) {ShoppingCart cart = new ShoppingCart();cart.addToCart("ProductA", 1);cart.addToCart("ProductB", 2);cart.addToCart("ProductC", 3);cart.addToCart("ProductD", 4);cart.addToCart("ProductE", 5);cart.addToCart("ProductF", 6);  // 此时最早加入的 ProductA 将被移除}
}

代码说明：

• LinkedHashMap 通过重写 removeEldestEntry 方法实现了当元素数量超过 MAX_CART_SIZE（5 个）时，自动移除最旧的商品。
• addToCart 方法用于将商品添加到购物车，displayCart 方法用于显示当前购物车内容。
• 当加入第 6 个商品时，购物车中最早添加的商品 ProductA 会被移除。

3.4 LinkedHashMap 的性能分析

LinkedHashMap 在保证有序性的同时，仍然保留了 HashMap 的高效特性，即 O(1) 的查找和插入性能。它通过维护一个双向链表来记录元素的顺序，因而在保持插入和访问顺序的同时，性能损耗较小，非常适合实现有序的缓存系统。

4. TreeMap

TreeMap 是 Java 集合框架中的一个基于红黑树实现的有序映射类。与 LinkedHashMap 按插入顺序或访问顺序进行排序不同，TreeMap 根据键的自然顺序或通过自定义的比较器对键进行排序。

4.1 TreeMap 的特点

1. 有序性
   TreeMap 保证键的顺序，并且可以根据键的自然排序或通过提供的自定义比较器进行排序。
2. 基于红黑树实现
   TreeMap 的底层实现基于红黑树（Red-Black Tree），它是一种自平衡二叉搜索树，因此 TreeMap 的所有操作（如插入、删除、查找等）都具有 O(log n) 的时间复杂度。
3. 线程不安全
   与 HashMap 和 LinkedHashMap 类似，TreeMap 也是线程不安全的，在多线程环境中使用时需要外部同步处理。

4.2 TreeMap 的适用场景

1. 需要有序存储的场景
   在某些需要按照键的自然顺序或自定义顺序进行排序的场景中，TreeMap 非常适合。例如，电商系统中可以用 TreeMap 来管理商品价格或时间敏感的库存。
2. 范围查询
   由于 TreeMap 是有序的，它支持高效的范围查询操作。比如可以在某个范围内查找所有满足条件的键值对，这在一些统计或筛选场景中非常有用。

4.3 在电商系统中的应用

假设在一个电商系统中，我们需要根据商品价格对商品进行排序，并提供按价格范围进行商品筛选的功能。TreeMap 可以轻松实现这一功能。

代码示例：商品价格排序和筛选

以下示例代码展示了如何使用 TreeMap 来管理和筛选商品价格。

import java.util.Map;
import java.util.TreeMap;public class ProductCatalog {// 使用 TreeMap 管理商品价格，并根据价格排序private TreeMap<Double, String> productPrices = new TreeMap<>();// 添加商品及其价格public void addProduct(String product, double price) {productPrices.put(price, product);System.out.println("Added: " + product + " with price: " + price);}// 显示所有商品及其价格public void displayProducts() {for (Map.Entry<Double, String> entry : productPrices.entrySet()) {System.out.println("Product: " + entry.getValue() + ", Price: " + entry.getKey());}}// 按价格范围筛选商品public void filterProductsByPrice(double minPrice, double maxPrice) {Map<Double, String> filteredProducts = productPrices.subMap(minPrice, maxPrice);System.out.println("Products in price range [" + minPrice + ", " + maxPrice + "]:");for (Map.Entry<Double, String> entry : filteredProducts.entrySet()) {System.out.println("Product: " + entry.getValue() + ", Price: " + entry.getKey());}}public static void main(String[] args) {ProductCatalog catalog = new ProductCatalog();catalog.addProduct("ProductA", 10.99);catalog.addProduct("ProductB", 15.99);catalog.addProduct("ProductC", 5.49);catalog.addProduct("ProductD", 25.00);System.out.println("All Products:");catalog.displayProducts();System.out.println("\nProducts in price range [10, 20]:");catalog.filterProductsByPrice(10.00, 20.00);}
}

代码说明：

• ProductCatalog 类使用 TreeMap 管理商品价格，并根据商品价格进行排序。
• addProduct 方法将商品及其价格添加到 TreeMap 中。
• filterProductsByPrice 方法使用 subMap 来筛选出符合指定价格范围的商品。

4.4 TreeMap 自定义排序

在某些场景中，我们可能希望根据自定义的规则对商品进行排序，而不仅仅是按照自然排序（如价格）。通过提供自定义比较器，我们可以实现多种排序方式。

例如，假设我们需要根据商品名称的长度进行排序，以下是示例代码：

import java.util.Comparator;
import java.util.TreeMap;public class CustomSortProductCatalog {// 自定义比较器：根据商品名称长度排序private TreeMap<String, Double> productCatalog = new TreeMap<>(new Comparator<String>() {@Overridepublic int compare(String product1, String product2) {return Integer.compare(product1.length(), product2.length());}});// 添加商品public void addProduct(String product, double price) {productCatalog.put(product, price);System.out.println("Added: " + product + " with price: " + price);}// 显示商品public void displayProducts() {productCatalog.forEach((product, price) -> System.out.println("Product: " + product + ", Price: " + price));}public static void main(String[] args) {CustomSortProductCatalog catalog = new CustomSortProductCatalog();catalog.addProduct("Short", 10.99);catalog.addProduct("VeryLongProductName", 25.00);catalog.addProduct("Medium", 15.99);System.out.println("All Products sorted by name length:");catalog.displayProducts();}
}

代码说明：

• 通过自定义比较器，TreeMap 实现了根据商品名称长度对商品进行排序。

5. 深入理解 ConcurrentHashMap

在多线程编程中，线程安全和性能往往是一对矛盾。传统的 HashMap 在多线程环境下是非线程安全的，因此不能直接应用于高并发场景。而 ConcurrentHashMap 作为 Java 的并发集合，提供了线程安全的操作，并且在设计上优化了高并发环境下的性能。这使得它成为多线程程序中处理共享数据时的首选之一，尤其是在电商交易系统等高并发环境中有广泛应用。

5.1 ConcurrentHashMap 的特点

1. 线程安全
   ConcurrentHashMap 在底层通过分段锁（在 Java 8 之前）或 CAS 操作（在 Java 8 及之后）来实现线程安全，保证多个线程可以并发地对集合进行操作，而不会发生数据不一致的情况。相比于使用全局锁的 Hashtable，ConcurrentHashMap 允许更高的并发度，从而减少了性能瓶颈。
2. 高性能
   在 Java 8 之前，ConcurrentHashMap 使用了分段锁的机制，将哈希表划分成多个段，每个段都拥有自己的锁，这样不同线程在操作不同段的元素时可以并行工作，提升了并发性能。
   从 Java 8 开始，ConcurrentHashMap 不再使用分段锁，而是采用 CAS（Compare-And-Swap）操作以及红黑树优化，使得并发性和性能进一步提升。哈希桶中的链表在元素较多时会自动转换为红黑树，提高了大数据量下的查找效率。
3. 无锁读操作
   ConcurrentHashMap 的读操作不需要加锁，这是通过内部结构设计实现的。当多个线程同时读取数据时，读操作不会阻塞写操作，也不会引起锁竞争，从而提高了并发访问的效率。
4. 分片设计
   ConcurrentHashMap 通过分片（segments）的设计，将数据划分为多个小片，使得多个线程可以同时访问不同片的内容而不会互相阻塞。这种设计在多线程访问下可以显著减少锁争用，提升并发处理能力。
5. 迭代器弱一致性
   在 ConcurrentHashMap 中，迭代器是弱一致的（weakly consistent）。这意味着在迭代过程中，如果有其他线程对集合进行修改，迭代器不会抛出 ConcurrentModificationException，但它也不会保证获取的内容完全反映当前集合的状态。迭代器所返回的数据是修改之前的快照，因此在高并发下，ConcurrentHashMap 可以保证迭代操作的稳定性。

5.2 ConcurrentHashMap 的适用场景

由于 ConcurrentHashMap 具有线程安全性和高性能的特点，它在以下场景中尤其适用：

1. 多线程读多写少的场景
   在一些多线程程序中，读操作远远多于写操作，比如缓存系统或者状态监控系统。在这种情况下，ConcurrentHashMap 的无锁读操作可以极大地提高性能，同时保证写操作的安全性。
2. 高并发环境中的共享数据
   在电商交易系统中，用户会频繁查询商品信息、订单状态等。这些数据往往需要通过共享的哈希表进行管理，因此使用 ConcurrentHashMap 可以确保在高并发下对数据进行安全访问。
3. 数据频繁更新和查询的场景
   例如，统计用户的在线人数、商品点击量等场景中，多个线程需要同时读取和更新数据，而 ConcurrentHashMap 可以高效地支持并发的读取和写入操作。

5.3 在电商系统中的应用

在一个电商交易系统中，商品库存管理是一个常见的高并发场景。假设有一个电商平台，成千上万的用户会同时访问某个热门商品的库存信息，甚至会同时进行下单操作。为了保证在高并发情况下库存信息的正确性，必须使用线程安全的数据结构。ConcurrentHashMap 是一个很好的选择，因为它可以保证多个用户同时访问和更新库存时的安全性。

代码示例：商品库存管理

以下是一个使用 ConcurrentHashMap 来管理商品库存的示例代码：

import java.util.concurrent.ConcurrentHashMap;public class InventoryService {// 使用 ConcurrentHashMap 来存储商品库存信息private ConcurrentHashMap<String, Integer> productStock = new ConcurrentHashMap<>();// 初始化库存public InventoryService() {productStock.put("productA", 100);productStock.put("productB", 200);}// 查询库存public int getStock(String productId) {return productStock.getOrDefault(productId, 0);}// 减少库存（下单操作）public boolean reduceStock(String productId, int quantity) {while (true) {Integer stock = productStock.get(productId);if (stock == null || stock < quantity) {return false; // 库存不足，返回失败}// 使用 CAS 操作更新库存int newStock = stock - quantity;if (productStock.replace(productId, stock, newStock)) {return true; // 更新成功，返回成功}}}// 增加库存（商品入库操作）public void addStock(String productId, int quantity) {productStock.merge(productId, quantity, Integer::sum);}public static void main(String[] args) {InventoryService inventoryService = new InventoryService();// 多线程下进行库存查询和更新操作Runnable checkStockTask = () -> {String productId = "productA";System.out.println("当前库存：" + inventoryService.getStock(productId));};Runnable reduceStockTask = () -> {String productId = "productA";boolean success = inventoryService.reduceStock(productId, 1);System.out.println("减少库存操作 " + (success ? "成功" : "失败"));};Thread t1 = new Thread(checkStockTask);Thread t2 = new Thread(reduceStockTask);t1.start();t2.start();}
}

代码说明：

• InventoryService 类用于管理商品库存，内部使用了 ConcurrentHashMap 来存储商品 ID 与对应的库存量。
• getStock 方法用于查询商品库存，使用 getOrDefault 方法确保即使商品不存在也能返回一个默认值。
• reduceStock 方法用于减少商品库存，模拟了用户下单时减少库存的操作。该方法使用了 CAS 操作，通过 replace 方法来确保并发下安全地更新库存。
• addStock 方法模拟了商品入库操作，使用 merge 方法来累加库存，这也是 ConcurrentHashMap 提供的一个便捷方法。