哈希表（Hashtable）核心知识点详解

1. 基本概念

• 定义：通过键（Key）直接访问值（Value）的数据结构，基于哈希函数将键映射到存储位置。

• 核心操作：

  • put(key, value)：插入键值对

  • get(key)：获取键对应的值

  • remove(key)：删除键值对

• 时间复杂度（平均）：

  • 插入、查找、删除：O(1)

  • 最坏情况（哈希冲突严重时）：O(n)

---

2. 哈希函数设计

• 作用：将任意大小的键转换为固定大小的哈希值（通常为整数）。

• 设计要求：

  • 一致性：相同键必须产生相同哈希值

  • 均匀性：不同键应均匀分布，减少冲突

• 常见哈希函数：

  // Java的String.hashCode()实现
  public int hashCode() {int h = 0;for (char c : value) {h = 31 * h + c;}return h;
  }

---

3. 哈希冲突解决

当不同键映射到同一位置时：

• 链地址法（Separate Chaining）：

  • 每个桶（bucket）存储链表或红黑树（如Java 8+的HashMap）

  • 冲突时，新元素添加到链表末尾

• 开放寻址法：

  • 线性探测：冲突后顺序查找下一个空槽

  • 平方探测：按平方步长跳跃查找

---

4. 负载因子与扩容

• 负载因子（Load Factor）：

  • 定义：元素数量 / 桶数量（默认0.75）

  • 作用：触发扩容的阈值（如Java HashMap）

• 扩容机制：

  • 新容量通常为原来的2倍

  • 重新计算所有键的哈希位置（rehash）

---

5. 常见实现对比

	HashMap	Hashtable	ConcurrentHashMap
线程安全	不安全	安全（全表锁）	安全（分段锁）
Null键值	允许	不允许	不允许
性能	高	低	中等

---

6. Java中的关键实现细节

• HashMap的树化优化：

  • 当链表长度≥8且桶数量≥64时，链表转为红黑树（防止DoS攻击）

• 哈希扰动函数：

  
  static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  • 通过异或高位和低位，减少哈希冲突

---

7. 经典应用场景

1. 快速查找：

   • 如两数之和（LeetCode 1）

   
   // 两数之和解法
   Map<Integer, Integer> map = new HashMap<>();
   for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);
   }

2. 缓存实现（如LRU Cache）

3. 去重统计（如统计词频）

---

8. 常见面试问题

• Q1：HashMap如何解决哈希冲突？
  A：链地址法（链表+红黑树）。

• Q2：为什么负载因子默认是0.75？
  A：空间和时间成本的折中（数学证明较优）。

• Q3：HashMap为什么线程不安全？
  A：多线程扩容可能导致死循环或数据丢失。

---

9. 手写简易Hashtable（Java示例）

class MyHashtable<K, V> {private Node<K,V>[] table;private int size;private static final int DEFAULT_CAPACITY = 16;static class Node<K,V> {final K key;V value;Node<K,V> next;// 构造方法...}public V put(K key, V value) {int hash = key.hashCode();int index = (table.length - 1) & hash;Node<K,V> node = table[index];while (node != null) {if (node.key.equals(key)) {V oldValue = node.value;node.value = value;return oldValue;}node = node.next;}Node<K,V> newNode = new Node<>(key, value, table[index]);table[index] = newNode;size++;return null;}
}

---

掌握这些核心知识点后，你就能在面试和实际开发中游刃有余地使用哈希表！