哈希思想

一句话理解

哈希把键映射成数组下标。

为什么要学

期望 O(1) 查找。

讲解

好的哈希让不同键尽量散开。整数可直接取模，字符串要多项式哈希或 STL。

例子

学号很大，映射到 0..M-1 的桶。

常见错误

• 模数太小冲突多。
• 当精确下标用却没处理冲突。