哈希表
最后更新
哈希表把元素存放在一个桶数组中。要放入或查找一个键，先用哈希函数处理这个键，再对桶的数量取模，就能以 O(1) 得到桶的下标。点击上方的“播放”，观察每个键如何被哈希到某个桶中存储，以及查找时如何直接跳到正确的桶。
当两个键哈希到同一个桶时，就发生了冲突。这个可视化使用拉链法：每个桶存一个小列表，冲突的键追加到列表中。只要表不太满（负载因子较低），并且哈希函数能把键分散均匀，链就会保持很短，插入、查找和删除的平均复杂度都是 O(1)。
时间复杂度
| 操作 | 平均 | 最坏情况 |
|---|---|---|
| 插入 | O(1) | O(n)（所有键都冲突） |
| 查找 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
| 空间 | O(n) | O(n) |
核心概念
| 术语 | 含义 |
|---|---|
| 哈希函数 | 把键映射为桶的下标 |
| 冲突 | 两个键落在同一个桶中 |
| 拉链法 | 每个桶存一个由冲突条目组成的列表 |
| 开放寻址法 | 另一种方案：探测下一个空位 |
| 负载因子 | 条目数 / 桶数，决定何时扩容 |
示例演算
用 hash(k) = k % 7 把键 20、34、9、13 插入一个有 7 个桶的表：
| 步骤 | 结构 | 操作 |
|---|---|---|
插入 20 | 桶 6：[20] | 20 % 7 = 6，桶 6 为空，存入 20 |
插入 34 | 桶 6：[20, 34] | 34 % 7 = 6，与 20 冲突，把 34 追加到链上 |
插入 9 | 桶 2：[9] | 9 % 7 = 2，桶 2 为空，存入 9 |
插入 13 | 桶 6：[20, 34, 13] | 13 % 7 = 6，发生冲突，把 13 追加到桶 6 的链上 |
查找 34 | 桶 6：[20, 34, 13] | 34 % 7 = 6，扫描链：20 不是，34 匹配，找到了 |
什么时候使用哈希表
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
需要按键进行平均 O(1) 的插入、查找和删除 | 需要让键保持有序，应使用平衡 BST |
| 键没有有用的顺序，只需判断是否精确存在 | 需要范围查询或查找最接近的键 |
| 能为桶和较低的负载因子付出一些额外内存 | 内存极其紧张，每个字节都要计较 |
| 你的键类型有好的哈希函数 | 最坏情况下的延迟必须有上限，冲突会让它变成 O(n) |
Hash Table 代码
简洁、可运行的 Hash Table 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Hash Table 的 Python 代码
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Hash Table 的 JavaScript 代码
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Hash Table 的 Java 代码
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Hash Table 的 C++ 代码
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Hash Table 的 C 代码
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}哈希表常见问题
什么是哈希冲突？怎么解决？
当两个不同的键哈希到同一个桶时，就发生了冲突。两种常见的解决方法是拉链法（每个桶存一个列表，冲突的键追加进去，也就是这里演示的方法）和开放寻址法（在数组中探测下一个空位）。两者都能保证查找正确，区别在于内存布局和高负载下的性能。
哈希表的时间复杂度是多少？
当哈希函数能把键均匀分布、负载因子保持较低时，插入、查找和删除的平均复杂度都是
O(1)。最坏情况下（所有键都冲突到同一个桶），它们会退化为 O(n)，所以好的哈希函数和扩容很重要。什么是负载因子？
负载因子等于已存条目数除以桶数。它越大，链就越长，操作也越慢，所以大多数哈希表会在它超过某个阈值（如 0.75）时扩容，即重新哈希到一个更大的数组中。
什么时候该用哈希表而不是二叉搜索树？
如果只需要精确匹配的查找，希望平均速度达到
O(1)，并且不要求顺序，就用哈希表。如果需要键有序、范围查询，或查找前驱和后继，就用平衡二叉搜索树，这些是哈希表无法高效完成的。BST 能保证 O(log n) 的操作，而哈希表放弃了这种保证，换来更快的平均性能。拉链法和开放寻址法有什么区别？
拉链法把冲突的键存在每个桶自己的列表中，所以一个桶可以容纳很多条目，表永远不会真正被填满。开放寻址法把所有内容都放在数组本身里，冲突时探测下一个空位，这对缓存很友好，但随着负载因子接近 1，性能会急剧下降，删除也需要小心处理。拉链法能容忍更高的负载因子，开放寻址法的内存使用更紧凑。
为什么不能指望哈希表按插入顺序或排序顺序保存键？
哈希函数会刻意把键分散到各个桶中，避免扎堆，所以迭代顺序反映的是桶的布局，而不是插入顺序或排序顺序。如果需要顺序，请使用有序映射或树，或者按插入顺序保存的映射（例如 Python 的
dict 会保留插入顺序，但这是语言层面的保证，并不是哈希表固有的特性）。除非语言明确承诺，否则永远不要假设迭代顺序和插入键的顺序一致。相关资源
更多可视化
