java - 在哈希表中创建字符串的哈希值的时间复杂度

Question

通常说在哈希表中插入和查找一个字符串是 O(1)。但是一个字符串的hash key是怎么生成的呢？为什么不考虑 O(L)，字符串长度？
我很清楚为什么整数是 O(1) 而不是字符串。

我明白为什么一般来说，插入哈希表是 O(1)，但我对将哈希插入表之前的步骤感到困惑:生成哈希值。

此外，在 java 中生成字符串哈希键的方式与在 C++ 中生成 unordered_map 之间有什么区别吗？
谢谢。

Answer 1

在哈希表中插入等是 O(1)，因为它相对于表中的元素数量是恒定的(或更准确地说，是有界的)。

本文中的“O(1)”并未说明您可以多快地计算哈希值。如果为此付出的努力以某种方式增长，那就是它的方式。但是，我发现体面的(即“适合此应用程序”)散列函数的复杂性不太可能比被散列对象的“大小”(即我们的字符串示例中的长度)的线性更差。