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

Question

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

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

此外，在 C++ 中 java 和 unordered_map 中生成字符串哈希键的方式有什么不同吗？
谢谢。

Answer 1

在散列中插入等table 是 O(1)，因为它相对于 table 中的元素数量是常数（或更准确地说，有界）。

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

Answer 2

根据Java的实现，Hashtable使用key（String或Integer）的hashCode方法。 Hashtable String.hashCode Integer.hashCode

并且 C++ 根据 http://en.cppreference.com/w/cpp/utility/hash 使用 std::hash<std::string> 或 std::hash<int> 并且实现在功能文件中 (/path/to/c++... /include/c+ +/4.8/功能）

Answer 3

It's usually said that inserting and finding a string in a hashtable is O(1). But how is hash key of a string made ? Why it's not O(L), length of string? It's clear for me that why for integers it's O(1), but not for strings.

通常引用的 O(1) 意味着时间不会随着容器中元素的数量而增长。正如您所说，从字符串生成哈希值的时间本身可能不是 O(1) 字符串的长度 - 尽管对于某些实现来说它是：例如 Microsoft 的 C++ std::hash<std::string> 有：

            size_t _Val = 2166136261U;
            size_t _First = 0;
            size_t _Last = _Keyval.size();
            size_t _Stride = 1 + _Last / 10;

            if (_Stride < _Last)
                    _Last -= _Stride;
            for(; _First < _Last; _First += _Stride)
                    _Val = 16777619U * _Val ^ (size_t)_Keyval[_First];
            return (_Val);

_Stride是字符串长度的十分之一，因此固定个相距较远的字符将被合并到哈希值中。这样的哈希函数在字符串的长度上是O(1).

GCC 的 C++ 标准库采用不同的方法：至少在 v4.7.2 中，它通过 _Hash_impl 支持向下调用 class 到 static 非成员函数 _Hash_bytes，它对包含每个字节的 Murmur 哈希进行运算。因此 GCC 的 hash<std::string> 是 O(N) 字符串的长度 .

GCC 在 std::unordered_set 和 std::unordered_map 中使用质数桶也明显体现了 GCC 对碰撞最小化的更高优先级，而 MS 的实现并没有这样做——至少直到 [=63] =];总而言之，MS 的方法将 lighter-weight/faster 用于不易发生冲突且负载系数较低的键，但在其他情况下会更早且更显着地降级。

And is there any difference between how hash keys for strings are produced between hashTable in java and unordered_map in C++?

C++ 标准未指定如何散列字符串 - 它留给了各个编译器实现。因此，不同的编译器会做出不同的妥协——甚至是同一编译器的不同版本。

文档 David Pérez Cabrera 的回答链接解释了 Java 中的 hashCode 函数：

Returns a hash code for this string. The hash code for a String object is computed as

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the i^th character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

字符串的长度显然是 O(N)。

正在快速返回...

It's usually said that inserting and finding a string in a hashtable is O(1).

...a "key" ;-P 洞察力是，在许多问题领域中，已知字符串的实际长度变化不大，或者最坏情况长度的散列仍然是足够快。考虑一个人或公司的名称、街道地址、来自某些源代码的标识符、编程语言关键字、product/book/CD 等名称：您可以预期十亿个密钥需要比存储大约多一百万倍的内存第一千。使用散列 table，对整个数据集的大多数操作预计会花费一百万倍的时间。在 100 年后，这将和今天一样真实。重要的是，如果某些请求与单个键相关，那么执行它所花费的时间应该不会比以前使用一千个键时长很多（假设有足够的 RAM，并忽略 CPU 缓存效果）——当然，如果这是一个长密钥，它可能比短密钥需要更长的时间，如果您有超低延迟或硬实时要求，您可能会在意。但是，尽管数据量增加了一百万倍，但使用随机键的请求的平均吞吐量将保持不变。

仅当您的问题域在密钥大小上存在巨大差异并且密钥散列时间对于您的性能需求很重要，或者您预计平均密钥大小会随着时间的推移而增加（例如，如果密钥是视频流，每隔几年人们就会提高分辨率和帧速率，从而导致密钥大小呈指数增长），您是否需要密切关注散列（和密钥比较）成本。

Answer 4

哈希函数的复杂度永远不会是 O(1)。如果字符串的长度是 n 那么复杂度肯定是 O(n)。但是，如果您计算给定数组中的所有哈希值，则不必进行第二次计算，并且您始终可以通过比较预先计算的哈希值在 O(1) 时间内比较两个字符串。

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

Time complexity of creating hash value of a string in hashtable

java

c++

string

hashtable