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

Question

通常说在哈希表中插入和查找字符串是O(1).但是如何制作字符串的哈希键呢？为什么它不是O(L),字符串的长度？对我来说很明显,为什么整数是O(1),而不是字符串.

请注意,我理解为什么一般来说,插入哈希表是O(1),但我对将哈希插入表之前的步骤感到困惑; 制作哈希值阶段.

在Java中的hashTable与C++中的unordered_map之间如何生成字符串的哈希键之间是否有任何区别？

Answer 1

在哈希表中插入等等是O(1),因为它在表中的元素数量上是恒定的.

在这种情况下,"O(1)"并未声明您可以多快地计算哈希值.如果这种努力以某种方式增长,那就是它的方式.但是,我发现散列对象的"复杂性"(即"适合此应用程序")散列函数的复杂性可能不会比正在散列的对象的"大小"(即字符串示例中的长度)中的线性更差.

Answer 2

通常说在哈希表中插入和查找字符串是 O(1)。但是字符串的哈希键是如何制作的呢？为什么不是 O(L)，字符串的长度？我很清楚为什么整数是 O(1)，而不是字符串。

通常引用的 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支持类向下调用static非成员函数_Hash_bytes，该函数执行合并每个字节的 Murmur 哈希。hash<std::string>因此，GCC 的字符串长度为O(N) 。

• GCC的冲突最小化的高prioritorisation也体现在其使用吊桶的素数的std::unordered_set和std::unordered_map，其中MS的实现没有做-至少直到VS2013 / VC12; 总而言之，对于不易碰撞且负载系数较低的键，MS 的方法将更轻/更快，但否则会更早更显着地降级。

并且在java中的hashTable和C++中的unordered_map之间如何生成字符串的哈希键有什么区别？

C++ 标准没有规定如何对字符串进行散列处理——这取决于各个编译器的实现。因此，不同的编译器会做出不同的妥协——甚至是同一编译器的不同版本。

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

返回此字符串的哈希码。String 对象的哈希码计算如下

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

使用int算术，其中s[i]是字符串的i^{第 th 个}字符，是字符串n的长度，并^表示求幂。（空字符串的哈希值为零。）

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

快速返回...

通常说在哈希表中插入和查找字符串是 O(1)。

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

只有当您有一个密钥大小差异很大的问题域并且密钥散列时间很重要时，才考虑到您的性能需求，或者您期望平均密钥大小随着时间的推移而增加（例如，如果密钥是视频流，并且每隔几个多年来人们一直在提高分辨率和帧速率，从而导致密钥大小呈指数增长），您是否需要密切关注散列（和密钥比较）成本。