03-哈希表

💡 核心结论

哈希表本质

  • 原理：通过哈希函数将key映射到数组索引，O(1)访问

  • 性能：平均O(1)查找/插入/删除，最坏O(n)

  • 核心：好的哈希函数 + 合适的冲突解决 = 高性能

  • 负载因子：α = n/m，α < 0.75性能良好，超过需扩容

  • 应用：缓存、去重、计数、索引

冲突解决

  • 链地址法：每个槽位存链表，简单但指针开销大

  • 开放寻址：线性探测/二次探测/双重哈希，缓存友好但聚集问题

  • 选择：链地址法更常用（Java HashMap、Python dict）

哈希函数要求

  1. 确定性：相同输入→相同输出

  2. 均匀分布：减少冲突

  3. 快速计算：保证O(1)

  4. 雪崩效应：输入微变化→输出巨变

性能关键

因素

影响

好的哈希函数

减少冲突

低负载因子

减少冲突

合理扩容

保持性能

冲突解决方法

最坏情况性能

🎯 哈希表原理

核心思想

通过哈希函数将key映射到数组索引，实现O(1)的查找、插入、删除。

key --[hash function]--> index --> value
"John" --> 哈希 --> 5 --> {name: "John", age: 30}

时间复杂度

操作

平均

最坏

查找

O(1)

O(n)

插入

O(1)

O(n)

删除

O(1)

O(n)

🔑 哈希函数

好的哈希函数特点

  1. 确定性：相同输入产生相同输出

  2. 快速计算

  3. 均匀分布

  4. 雪崩效应：输入微小变化导致输出巨大变化

常见哈希函数

# 除法哈希
def hash_division(key, table_size):
    return key % table_size

# 乘法哈希
def hash_multiplication(key, table_size):
    A = 0.6180339887  # (√5 - 1) / 2
    return int(table_size * ((key * A) % 1))

# 字符串哈希
def hash_string(s, table_size):
    hash_val = 0
    for char in s:
        hash_val = (hash_val * 31 + ord(char)) % table_size
    return hash_val

💥 冲突解决

1. 链地址法（Chaining）

Index | Linked List
------|-------------
  0   | -> key1 -> key5
  1   | -> key2
  2   | (empty)
  3   | -> key3 -> key6 -> key8
  4   | -> key4

优点：

  • 实现简单

  • 对哈希函数要求低

  • 负载因子可以>1

缺点：

  • 额外指针开销

  • 缓存性能差

2. 开放寻址法（Open Addressing）

线性探测

hash(key) = h
探测序列: h, h+1, h+2, h+3, ...

优点：缓存友好 缺点：聚集问题

二次探测

探测序列: h, h+1², h+2², h+3², ...

双重哈希

h1(key) = key % m
h2(key) = 1 + (key % (m-1))
探测序列: h1, h1+h2, h1+2h2, h1+3h2, ...

📊 负载因子

负载因子 α = n / m
n: 已存储元素数
m: 哈希表大小

链地址法：α < 1.0 性能良好
开放寻址：α < 0.7 性能良好

扩容触发：α > 0.75（Java HashMap）

🔧 动态扩容

扩容策略

  1. 创建新表（通常2倍大小）

  2. 重新哈希所有元素（rehash）

  3. 替换旧表

Rehash过程

def resize(self):
    old_table = self.table
    self.capacity *= 2
    self.table = [[] for _ in range(self.capacity)]
    self.size = 0
    
    for bucket in old_table:
        for key, value in bucket:
            self.insert(key, value)

💡 应用场景

缓存

  • LRU缓存

  • Redis

  • Memcached

数据库索引

  • Hash索引

  • 快速查找

去重

  • 统计不重复元素

  • 集合运算

计数

  • 词频统计

  • 投票系统

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2哈希表实现（链地址法）
  3"""
  4
  5class HashTable:
  6    """哈希表实现"""
  7    
  8    def __init__(self, capacity=16):
  9        """初始化
 10        
 11        Args:
 12            capacity: 初始容量
 13        """
 14        self.capacity = capacity
 15        self.size = 0
 16        self.table = [[] for _ in range(capacity)]
 17        self.load_factor_threshold = 0.75
 18    
 19    def _hash(self, key):
 20        """哈希函数
 21        
 22        Args:
 23            key: 键（支持字符串和整数）
 24            
 25        Returns:
 26            哈希值
 27        """
 28        if isinstance(key, str):
 29            hash_val = 0
 30            for char in key:
 31                hash_val = (hash_val * 31 + ord(char)) % self.capacity
 32            return hash_val
 33        else:
 34            return hash(key) % self.capacity
 35    
 36    def _resize(self):
 37        """扩容并重新哈希"""
 38        old_table = self.table
 39        self.capacity *= 2
 40        self.table = [[] for _ in range(self.capacity)]
 41        self.size = 0
 42        
 43        for bucket in old_table:
 44            for key, value in bucket:
 45                self.insert(key, value)
 46    
 47    def insert(self, key, value):
 48        """插入键值对
 49        
 50        Args:
 51            key: 键
 52            value: 值
 53        """
 54        # 检查是否需要扩容
 55        if self.size / self.capacity > self.load_factor_threshold:
 56            self._resize()
 57        
 58        index = self._hash(key)
 59        bucket = self.table[index]
 60        
 61        # 更新已存在的key
 62        for i, (k, v) in enumerate(bucket):
 63            if k == key:
 64                bucket[i] = (key, value)
 65                return
 66        
 67        # 插入新key
 68        bucket.append((key, value))
 69        self.size += 1
 70    
 71    def get(self, key):
 72        """获取值
 73        
 74        Args:
 75            key: 键
 76            
 77        Returns:
 78            值
 79            
 80        Raises:
 81            KeyError: 键不存在
 82        """
 83        index = self._hash(key)
 84        bucket = self.table[index]
 85        
 86        for k, v in bucket:
 87            if k == key:
 88                return v
 89        
 90        raise KeyError(f'Key {key} not found')
 91    
 92    def remove(self, key):
 93        """删除键值对
 94        
 95        Args:
 96            key: 键
 97            
 98        Raises:
 99            KeyError: 键不存在
100        """
101        index = self._hash(key)
102        bucket = self.table[index]
103        
104        for i, (k, v) in enumerate(bucket):
105            if k == key:
106                del bucket[i]
107                self.size -= 1
108                return
109        
110        raise KeyError(f'Key {key} not found')
111    
112    def contains(self, key):
113        """检查键是否存在
114        
115        Args:
116            key: 键
117            
118        Returns:
119            bool
120        """
121        try:
122            self.get(key)
123            return True
124        except KeyError:
125            return False
126    
127    def keys(self):
128        """返回所有键"""
129        result = []
130        for bucket in self.table:
131            for k, v in bucket:
132                result.append(k)
133        return result
134    
135    def values(self):
136        """返回所有值"""
137        result = []
138        for bucket in self.table:
139            for k, v in bucket:
140                result.append(v)
141        return result
142    
143    def items(self):
144        """返回所有键值对"""
145        result = []
146        for bucket in self.table:
147            for item in bucket:
148                result.append(item)
149        return result
150    
151    def __len__(self):
152        return self.size
153    
154    def __str__(self):
155        items = [f"{k}: {v}" for k, v in self.items()]
156        return "{" + ", ".join(items) + "}"
157
158
159def demo():
160    """演示哈希表的使用"""
161    print("=== 哈希表演示 ===\n")
162    
163    ht = HashTable(4)
164    
165    # 插入
166    print("插入键值对:")
167    ht.insert("apple", 5)
168    print(f"  apple: 5")
169    ht.insert("banana", 3)
170    print(f"  banana: 3")
171    ht.insert("orange", 7)
172    print(f"  orange: 7")
173    
174    print(f"\n哈希表: {ht}")
175    print(f"大小: {len(ht)}, 容量: {ht.capacity}\n")
176    
177    # 查找
178    print(f"查找 'apple': {ht.get('apple')}")
179    print(f"包含 'grape': {ht.contains('grape')}\n")
180    
181    # 更新
182    print("更新 'apple' 为 10")
183    ht.insert("apple", 10)
184    print(f"哈希表: {ht}\n")
185    
186    # 继续插入触发扩容
187    print("继续插入触发扩容:")
188    ht.insert("grape", 8)
189    ht.insert("melon", 6)
190    print(f"哈希表: {ht}")
191    print(f"大小: {len(ht)}, 容量: {ht.capacity}\n")
192    
193    # 删除
194    print("删除 'banana'")
195    ht.remove("banana")
196    print(f"哈希表: {ht}\n")
197    
198    # 遍历
199    print("所有键:", ht.keys())
200    print("所有值:", ht.values())
201
202
203if __name__ == '__main__':
204    demo()
205

C++ 实现

  1/**
  2 * 哈希表实现（链地址法）
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <list>
  8#include <string>
  9#include <stdexcept>
 10
 11template<typename K, typename V>
 12class HashTable {
 13private:
 14    struct Entry {
 15        K key;
 16        V value;
 17        Entry(K k, V v) : key(k), value(v) {}
 18    };
 19    
 20    std::vector<std::list<Entry>> table;
 21    int size;
 22    int capacity;
 23    double load_factor_threshold;
 24    
 25    int hash(const K& key) const {
 26        return std::hash<K>{}(key) % capacity;
 27    }
 28    
 29    void resize() {
 30        int old_capacity = capacity;
 31        capacity *= 2;
 32        
 33        std::vector<std::list<Entry>> old_table = table;
 34        table = std::vector<std::list<Entry>>(capacity);
 35        size = 0;
 36        
 37        for (const auto& bucket : old_table) {
 38            for (const auto& entry : bucket) {
 39                insert(entry.key, entry.value);
 40            }
 41        }
 42    }
 43
 44public:
 45    HashTable(int cap = 16) 
 46        : capacity(cap), size(0), load_factor_threshold(0.75) {
 47        table.resize(capacity);
 48    }
 49    
 50    void insert(const K& key, const V& value) {
 51        if ((double)size / capacity > load_factor_threshold) {
 52            resize();
 53        }
 54        
 55        int index = hash(key);
 56        auto& bucket = table[index];
 57        
 58        // 更新已存在的key
 59        for (auto& entry : bucket) {
 60            if (entry.key == key) {
 61                entry.value = value;
 62                return;
 63            }
 64        }
 65        
 66        // 插入新key
 67        bucket.push_back(Entry(key, value));
 68        size++;
 69    }
 70    
 71    V get(const K& key) const {
 72        int index = hash(key);
 73        const auto& bucket = table[index];
 74        
 75        for (const auto& entry : bucket) {
 76            if (entry.key == key) {
 77                return entry.value;
 78            }
 79        }
 80        
 81        throw std::runtime_error("Key not found");
 82    }
 83    
 84    void remove(const K& key) {
 85        int index = hash(key);
 86        auto& bucket = table[index];
 87        
 88        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
 89            if (it->key == key) {
 90                bucket.erase(it);
 91                size--;
 92                return;
 93            }
 94        }
 95        
 96        throw std::runtime_error("Key not found");
 97    }
 98    
 99    bool contains(const K& key) const {
100        try {
101            get(key);
102            return true;
103        } catch (...) {
104            return false;
105        }
106    }
107    
108    int getSize() const {
109        return size;
110    }
111    
112    void print() const {
113        std::cout << "{";
114        bool first = true;
115        for (const auto& bucket : table) {
116            for (const auto& entry : bucket) {
117                if (!first) std::cout << ", ";
118                std::cout << entry.key << ": " << entry.value;
119                first = false;
120            }
121        }
122        std::cout << "}" << std::endl;
123    }
124};
125
126
127int main() {
128    std::cout << "=== 哈希表演示 ===" << std::endl << std::endl;
129    
130    HashTable<std::string, int> ht(4);
131    
132    std::cout << "插入键值对:" << std::endl;
133    ht.insert("apple", 5);
134    std::cout << "  apple: 5" << std::endl;
135    ht.insert("banana", 3);
136    std::cout << "  banana: 3" << std::endl;
137    ht.insert("orange", 7);
138    std::cout << "  orange: 7" << std::endl;
139    
140    std::cout << "\n哈希表: ";
141    ht.print();
142    std::cout << "大小: " << ht.getSize() << std::endl << std::endl;
143    
144    std::cout << "查找 'apple': " << ht.get("apple") << std::endl;
145    std::cout << "包含 'grape': " << (ht.contains("grape") ? "是" : "否") << std::endl << std::endl;
146    
147    std::cout << "更新 'apple' 为 10" << std::endl;
148    ht.insert("apple", 10);
149    std::cout << "哈希表: ";
150    ht.print();
151    std::cout << std::endl;
152    
153    std::cout << "删除 'banana'" << std::endl;
154    ht.remove("banana");
155    std::cout << "哈希表: ";
156    ht.print();
157    
158    return 0;
159}