algorithm - 完美哈希时间复杂度

Question

一个完美的散列会在 0(1) 次内删除插入和搜索吗？如果是这样，那么为什么计算机科学家不一直使用完美散列，否则时间复杂度是多少？

Answer 1

Would a perfect hash have delete insert and search in 0(1) time?

是的，因为您只会得到单元素桶。所以有多少元素就有多少桶。

If so then why don't computer scientists use perfect hashing all the time if not what would be the time complexity?

其中一个原因是理论上的。完美的散列函数是单射的，定义这样的函数即使不是不可能也可能很困难。

考虑以下简单结构:

{
  int x;
  int y;
}

基本上，您希望您的 hash() 函数为 x 和 y 的每个可能值提供唯一的结果，这可能是不可能的。基本上对于像 x + y、x * y、x ^ y 这样的普通输入，您总是可以创建另一个会给出相同结果的输入.

另一方面，这是可能的(如 |N^2| = |N| = aleph-null)- 参见 Cantor pairing function .

另一个原因是实用 - 你的返回函数必须有一个返回类型。返回类型需要能够存储所有可能的注入(inject)结果——因此对于两个 32 位值的散列，它需要 64 位，对于三个 3 * 32 等(比较上面提到的配对函数有效地乘以参数)