hash - 完美哈希函数的大 O 是多少？

Question

可能发生冲突的常规哈希函数在恒定时间内运行：O(1)。但是完美哈希函数的时间复杂度是多少？是1吗？

Answer 1

如果哈希函数旨在用于访问哈希表，那么完美哈希函数和常规哈希函数在复杂性方面没有区别，因为它们都可能在表中产生冲突。原因是与哈希表中的元素关联的索引是哈希除以表的长度（通常是素数）的余数。这就是为什么散列到不同值的两个元素如果它们的余数模（所述）素数对于它们两者相同，则会发生冲突。这意味着访问表的时间复杂度O(1)在这两种情况下都是如此。

Note also that the computation of the hash usually depends on the size of the input. For instance, if the elements to be hashed are strings, good hashes take all their characters into account. Therefore, for the complexity to remain O(1), one has to limit the size (or length) of the inputs. Again, this applies to both perfect and regular hashes.