哈希map底层原理

### 哈希 Map 的底层实现原理 #### 数据结构 哈希 Map 是基于 **哈希表**（Hash Table）实现的键值对存储结构。其核心思想是通过一个哈希函数将键（Key）映射到数组的一个索引位置，从而实现快速的查找、插入和删除操作。在 Java 中，HashMap 使用了 **数组 + 链表 + 红黑树** 的混合数据结构来优化性能[^2]。 - **数组**：用于存储主桶（Bucket），每个桶对应一个索引。 - **链表**：当发生哈希冲突时，使用链表来存储多个键值对。 - **红黑树**：当链表长度超过阈值（默认为 8）时，链表会转换为红黑树以提高查找效率[^1]。 #### 冲突解决方法 由于哈希函数可能会导致不同的键映射到相同的索引位置，因此需要有效的冲突解决机制。常见的冲突解决策略包括以下几种： 1. **链地址法（Separate Chaining）** - 每个桶维护一个链表或红黑树，所有映射到同一位置的键值对都会被存储在这个链表中。 - 在 Java 的 HashMap 中，当链表长度超过一定阈值时，链表会转换为红黑树以提升查询性能[^1]。 2. **开放地址法（Open Addressing）** - 当发生冲突时，在数组中寻找下一个空闲槽位进行存储。常见的探测方式包括线性探测、二次探测和双重哈希等。 - 这种方法不需要额外的数据结构，但在负载因子较高时容易产生聚集现象，影响性能[^4]。 3. **再哈希法（Rehashing）** - 引入第二个哈希函数重新计算冲突键的位置，减少冲突概率。 - 虽然可以缓解聚集问题，但增加了哈希计算的开销[^4]。 4. **公共溢出区（Overflow Area）** - 设置一个专门的区域用于存放冲突的键值对。 - 适用于冲突较少的情况，但在高冲突场景下会导致性能下降[^3]。 #### 负载因子与扩容机制 负载因子（Load Factor）是衡量哈希表填充程度的一个指标，通常定义为 **元素数量 / 数组容量**。当哈希表中的元素数量超过当前容量乘以负载因子时，哈希表会触发扩容操作。 - **Java HashMap 默认负载因子为 0.75**，这是一个在时间和空间上取得平衡的折中值[^1]。 - 扩容时，HashMap 会创建一个新的数组，并将原有数据重新哈希分配到新数组中，这一过程称为 **rehashing**。 示例代码片段展示了 HashMap 的基本插入逻辑： ```java public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } ``` #### 渐进式扩容 在一些语言如 Go 中，map 的实现采用了 **渐进式扩容**（Incremental Resizing）策略。即在扩容过程中不会一次性迁移所有数据，而是逐步将旧数据迁移到新数组中。这种方式可以避免在扩容时阻塞整个 map 的访问，提升并发性能。 --- ###