Java 中的 HashMap 是一种基于哈希表实现的键值对（key-value）映射结构，它允许我们快速地根据键来存储和检索值。下面详细介绍 HashMap 的工作原理：
1. 基本概念
- 哈希表：
HashMap内部使用数组作为基本数据结构，每个数组元素称为“桶”（bucket）。当向HashMap中添加键值对时，首先通过键计算出一个哈希码（hash code），然后根据这个哈希码决定该键值对应该放置在数组的哪个位置。 - 哈希冲突：由于不同的键可能产生相同的哈希码，这就导致了多个键值对需要被放置在同一个桶中，这种情况称为哈希冲突。
2. 数据结构
HashMap 使用了一个数组来存储键值对，数组中的每个元素是一个链表或红黑树（JDK 8 及之后版本）。当发生哈希冲突时，新的键值对会被添加到对应的链表末尾。如果链表长度超过一定阈值（默认为8），则会转换为红黑树以提高查找效率。
3. 核心方法
- put(K key, V value)：插入键值对。首先计算键的哈希值，并确定其在数组中的索引位置。如果有哈希冲突，则将新键值对添加到链表或红黑树中。
- get(Object key)：获取与指定键关联的值。同样先计算键的哈希值并找到对应的桶，然后遍历链表或搜索红黑树找到匹配的键值对。
4. 哈希函数
HashMap 使用键对象的 hashCode() 方法生成哈希码，并通过以下方式将其映射到数组索引：
int hash = key.hashCode();
int index = (hash ^ (hash >>> 16)) & (capacity - 1);这里采用了高16位与低16位异或的方式混合哈希值，目的是让高位也能参与影响最终的索引位置，从而减少哈希碰撞的概率。
5. 扩容机制
当 HashMap 中的元素数量超过了负载因子（load factor，默认为0.75）乘以当前容量时，会发生扩容操作。扩容时，HashMap 会创建一个新的更大容量的数组（通常是原容量的两倍），并将所有现有的键值对重新分配到新的数组中。
6. 性能特性
- 时间复杂度：理想情况下，
HashMap的get和put操作的时间复杂度均为 O(1)。但在最坏的情况下（如大量哈希冲突导致形成很长的链表），这些操作的时间复杂度可能会退化至 O(n)。不过，在实际应用中这种情况较为罕见，特别是在 JDK 8 引入红黑树优化后。 - 空间复杂度：
HashMap需要额外的空间来存储键值对以及处理哈希冲突所需的链表或红黑树结构。
了解这些原理有助于更有效地使用 HashMap，例如选择合适的初始容量和负载因子，避免不必要的性能损耗。此外，理解如何正确实现键类的 hashCode() 和 equals() 方法也是确保 HashMap 正常工作的关键。
THE END
