哈希的直觉

哈希函数就是一条固定的规则，能把任何键都变成一个数字。比如把名字里每个字的编码加起来，再对表格长度取个余，落在 $0$ 到 $n-1$ 之间，正好当下标用。规则是固定的，所以同一个键每次都算出同一个位置，存进去、再取出来才对得上。

#include <iostream>
#include <string>
using namespace std;
const int N = 100;
int hashKey(string s) {
    int h = 0;
    for (char c : s) h = (h + c) % N;   // 相加再取余
    return h;
}
int main() {
    cout << hashKey("cat") << endl;  // 落在 0~99 的某个位置
    return 0;
}

小纸条问：这样算出来的数字，可能撞车吗？会的——不同的键完全可能算出同一个位置，这叫"冲突"。因为位置只有 N 个，键却可能有无数个，挤到一起在所难免。别指望哈希能做到人人不同，重点是遇到撞车怎么收场，下一节讲。