Hash tables · 哈希表
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
哈希表:快速查找
- 哈希表(hash table)存储数据的方式,让你能非常快地找到它 —— 通常只需一步。
- 它是一个由槽位(slot)组成的列表。一个哈希函数(hash function)把键转换成槽位编号。
- 你不必搜遍每个元素,而是直接跳到这个键应该在的槽位。
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
哈希函数
- 哈希函数接收一个键,返回一个从
0到size - 1的槽位下标。 - 同一个键总是给出相同的槽位,这样以后才能再找到它。
- 一个简单的做法:把字符编码相加,再取
% size把结果限制在范围内。
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Collisions
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
碰撞
- 两个不同的键可能哈希到同一个槽位。这就是碰撞(collision)。
- 表的槽位有限,所以随着它被填满,碰撞无法避免。
- 当我们想要的槽位已经被占用时,需要一条规则来决定怎么办。
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
线性探测
- 线性探测(linear probing):如果一个槽位满了,就试下一个,再下一个,到末尾就绕回开头。
- 不断地走
(slot + 1) % size,直到找到一个空槽位。 - 下面,
A和F都想要槽位 0,所以F被挤到了槽位 1。
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
查找一个键
- 要查找一个键:先哈希它,然后向前探测,把每个槽位与这个键比较。
- 找到时就停下并返回它的下标。
- 如果走到一个空槽位(或检查了每个槽位),说明这个键不在表里 —— 返回
-1。
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
为什么哈希表很快
- 碰撞很少时,插入和查找大约只要一步 —— 我们称之为
O(1)。 - 随着表被填满,探测会变长,所以保留一些空槽位是明智的。
- 最坏情况下(全部碰撞),它会退化成线性扫描,
O(n)。
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
常见错误
- 哈希函数把键映射到表中的一个索引。
- 两个键可能碰撞到同一个索引——要处理它,例如用链地址法。
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
现在轮到你
- 实现三个部分:哈希函数、带探测的插入,以及查找。
- 每个任务都会用碰撞和绕回的情形来检查你的函数。
- 按检查答案来测试它。
Hashing to a bucket · 哈希到一个桶
A hash function sends each key to a bucket · 桶; clashes chain. · 哈希函数把每个键送到一个桶;冲突时串成链。
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 to · 到 size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · 编写 hash_key(key, size)。把 key 的各个字符编码相加(用 ord(ch)),返回总和 % size,这样结果就是一个从 0 到 size - 1 的槽位。例如:hash_key("AB", 10) 是 (65 + 66) % 10 = 1。空字符串得到 0。
Click Run to see the output here. · 点击“运行”查看此处输出。
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index. · hash_key 已提供。用线性探测编写 insert(table, key):先到这个键的哈希槽位;只要该槽位被占用(不是 None),就走到 (slot + 1) % len(table);把键放进第一个空槽位,并返回它的下标。
Click Run to see the output here. · 点击“运行”查看此处输出。
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an empty · 空的 slot (key not there). Make sure it ends even if the table is full · 充分 — never loop forever. · hash_key 已提供。编写 find(table, key),返回 key 的下标,若不存在则返回 -1。从哈希槽位开始向前探测,逐个比较。遇到空槽位就停止(键不在表里)。要保证即使表是满的也能结束 —— 绝不能死循环。
Click Run to see the output here. · 点击“运行”查看此处输出。