Hash tables
Python for A-Level CS Lesson 13 2:40 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A hash table is a list of slots, and the trick is that you never look for anything.
哈希表是一排槽，而它的窍门在于：你从来不去"找"任何东西。
You compute where it belongs.
你把它的位置算出来。
Give it the key cat and a function answers with a slot number, so you go straight to the slot and look there.
给它键 "cat"，一个函数回答一个槽号， 于是你直接去那个槽，在那里看。
The alternative is what the last few lessons did: test every slot in turn until you find it.
另一条路就是前几课做的事：一个一个槽地试，直到找到为止。
One of those gets slower as the table grows; the other does not.
其中一条会随着表变大而变慢；另一条不会。
Here is the simplest hash function the syllabus asks for.
这是考纲要求的最简单的哈希函数。
Add up the character codes of the key — c is ninety-nine, a is ninety-seven, t is one hundred and sixteen, which comes to three hundred and twelve.
把键里每个字符的编码加起来—— c 是 99，a 是 97，t 是 116，加起来是 312。
Then take the remainder after dividing by the table's size, and three hundred and twelve leaves two.
然后除以表的大小取余数，312 除以 5 余 2。
That last step is the whole reason the answer is always inside the table.
最后那一步，正是答案永远落在表内部的全部理由。
Two different keys can hash to the same number, and with a small table that is not unlucky, it is inevitable.
两个不同的键可以哈希到同一个数字， 而在一个小表里，这不是运气不好，是必然。
Here A hashes to slot zero and goes in.
这里 A 哈希到槽 0，放了进去。
Now F, which also wants slot zero — but zero is taken.
现在轮到 F，它也想要槽 0——但 0 已经被占了。
Linear probing says: try the next one.
线性探测说：试下一个。
Slot one is free, so F lands there.
槽 1 是空的，所以 F 落在那里。
And the remainder in that line is what wraps back to the start once you reach the end of the table.
而那一行里的取模，正是走到表尾时把你绕回开头的东西。
Finding a key walks exactly the same path.
查找一个键走的正是同一条路。
Start where the hash says, then step forward.
从哈希指出的位置开始，然后往前走。
If a slot holds the key you want, return its index.
如果某个槽里就是你要的键，返回它的下标。
And here is the part students get wrong: an empty slot means stop.
而这里是学生最容易错的地方：遇到空槽就要停。
Probing put F right after A with no gap, so a gap proves the key was never inserted — return minus one.
探测把 F 紧挨着 A 放下，中间没有空隙， 所以一个空隙就证明这个键从来没有被插入过——返回 -1。
So how fast is it?
那它到底有多快？
With space to spare, both inserting and finding take about one step, and that is what order one means — the cost does not depend on how many items are stored.
在还有余地的时候，插入和查找都大约只要一步， 这就是"O(1)"的意思——代价不取决于存了多少个元素。
But as it fills up, every probe gets longer, and in the worst case, where everything collides, you are back to scanning the lot.
但随着它被填满，每一次探测都变得更长， 而在最坏的情况下，也就是所有东西都冲突时， 你又回到了把整张表扫一遍。
Keep some slots free and the speed stays.
留一些空槽，速度就还在。
Four things to take with you.
带走四点。
One: a hash function turns a key into a slot number.
第一：哈希函数把一个键变成一个槽号。
Two: two keys can collide on the same slot.
第二：两个键可能冲突在同一个槽上。
Three: linear probing tries the next slot, wrapping around at the end.
第三：线性探测去试下一个槽，走到末尾就绕回开头。
Four: with room to spare, a lookup is about one step.
第四：在还有余地时，一次查找大约只要一步。
Now write the hash function, the insert and the find.
现在把哈希函数、插入和查找都写出来。