哈希表（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. 常见实现对比

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;
    }
}

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