HashMap

在 Java 中，HashMap 是 Java 集合框架中的一个重要类，用于存储键值对 (key-value pairs) 的数据结构。它是基于哈希表 (hash table) 实现的，允许通过键快速访问对应的值。以下是关于 HashMap 的详细介绍：

1. 基本特性

• 存储结构：HashMap 使用哈希表作为其底层数据结构。哈希表通过对键进行哈希运算（通过键的 hashCode() 方法），将键值对存储在一个数组中，并以链表的形式处理哈希冲突。

• 允许 null 键和值：HashMap 允许 null 键和 null 值，但 null 键只能有一个，而 null 值可以有多个。

• 非线程安全：HashMap 不是线程安全的。如果需要线程安全的版本，可以使用 Collections.synchronizedMap() 方法将其包装成线程安全的集合，或使用 ConcurrentHashMap 类。

• 无序：HashMap 中的键值对是无序存储的，顺序不能保证。若要保持插入顺序，可使用 LinkedHashMap。

2. 工作原理

• 哈希函数：当插入键值对时，HashMap 会根据键的 hashCode() 生成哈希值，并将其与内部数组的长度进行取模运算，找到该键值对存储的位置。如果两个不同的键有相同的哈希值（即哈希冲突），它们将存储在同一个数组桶中，并通过链表或红黑树来管理。

• 哈希冲突：HashMap 通过链表来处理冲突。在 Java 8 及更高版本中，如果冲突过多且链表长度超过 8，链表会自动转换为红黑树，以提高查找效率。

3. 主要方法

• put(K key, V value)：将键 key 与值 value 存入 HashMap。如果键已存在，则更新其对应的值。

• get(Object key)：根据键返回对应的值。如果键不存在，则返回 null。

• remove(Object key)：根据键移除键值对。

• containsKey(Object key)：判断 HashMap 中是否包含某个键。

• containsValue(Object value)：判断 HashMap 中是否包含某个值。

• size()：返回 HashMap 中键值对的数量。

• isEmpty()：判断 HashMap 是否为空。

4. 扩容机制

HashMap 初始容量默认是 16，当存储的键值对数超过容量 * 负载因子 (load factor, 默认 0.75) 时，HashMap 会进行扩容，新的容量为当前容量的两倍。扩容时，所有键值对将被重新分配到新的数组中，因此扩容是一项比较耗时的操作。

5. 性能

• 时间复杂度：

  • 插入、删除、查找操作的平均时间复杂度为 O(1)，但在最坏情况下（大量哈希冲突时），复杂度会退化为 O(n)。

• 空间复杂度：由于底层使用数组和链表，HashMap 的空间复杂度主要取决于存储的键值对数量和数组容量。

6. 使用场景

• 当需要通过键快速查找值的情况下，HashMap 是一个非常好的选择。

• 它广泛应用于缓存、数据库索引等场景中，能够提供高效的查找、插入和删除操作。

7. 与其他集合的比较

• 与 HashTable：HashMap 是非线程安全的，而 Hashtable 是线程安全的（但效率较低）。另外，HashMap 允许 null 键和值，而 Hashtable 不允许。

• 与 TreeMap：TreeMap 是基于红黑树实现的，提供键的自然顺序或自定义比较器顺序。与 HashMap 相比，TreeMap 的插入、删除和查找操作时间复杂度为 O(log n)。

• 与 LinkedHashMap：LinkedHashMap 是 HashMap 的子类，除了具有 HashMap 的特性外，还维护了键值对的插入顺序或访问顺序。