Hash Table Search

Idea

Hash Table Search maps a key via hash function to a slot—trading space for time, achieving near $O(1)$ lookups.

哈希表查找演示

此处可扩展为哈希函数、冲突处理等动画。

• 哈希函数映射
• 冲突处理（开放定址/链地址）
• 查找过程演示

When to use

• Large data, very frequent lookups
• High-performance equality queries

Algorithm

1. Design a hash function $H(x)$ mapping key $x$ to a slot.
2. If empty, not found.
3. If occupied, compare key.
4. On collision, resolve (open addressing, chaining, etc.).

Pseudo-code:

pos = H(x)
if table[pos] == null:
    return -1
elif table[pos].key == x:
    return pos
else:
    // collision handling (e.g., linear probing or chaining)
    ...

Complexity

• Ideal: $O(1)$
• Worst (heavy collisions): $O(n)$
• In practice, near $O(1)$ with good hash & load factor

Exercises

Exercise 1

Hash-table search idea and common collision strategies?

参考答案

思路：哈希映射 + 冲突处理。

步骤：

1. 哈希函数定位
2. 冲突用开放定址、链地址等

答案：哈希定位；开放定址、链地址等。

Exercise 2

Average complexity? When does it degrade to $O(n)$?

参考答案

思路：装填因子与冲突。

步骤：

1. 平均 $O(1)$
2. 哈希差或负载过高导致大量冲突时，最坏 $O(n)$

答案：平均 $O(1)$；冲突严重时退化 $O(n)$。

Past exam

2020·408

哈希查找过程哪两步？冲突处理有哪些？

参考答案

思路：定位 + 处理。

步骤：

1. 哈希函数定位
2. 冲突时开放定址或链地址

答案：定位 + 冲突处理；开放定址、链地址等。

PreviousBinary SearchBinary search basics, algorithm flow, complexity, and practice. NextB-Tree and B+Tree SearchStructures of B-/B+ trees, search process, complexity, and practice.