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

在哈希表中插入等是O（1），因为它在表中元素的数量方面是恒定的（或者更确切地说，是有界的）。

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

通常说在哈希表中插入和查找字符串是 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);

是字符串长度的十分之一，因此在哈希值中将包含相距很远的固定数量的字符。这样的哈希函数在字符串的长度上是 O（1）。_Stride

GCC的C++标准库采用了不同的方法：至少在v4.7.2中，它通过支持类向下调用非成员函数_Hash_bytes，该函数执行包含每个字节的Murmur哈希。因此，GCC 在字符串的长度上是 O（N）。_Hash_implstatichash<std::string>

• GCC对碰撞最小化的更高优先级也很明显，因为它使用和的桶的质数，而MS的实现没有这样做 - 至少在VS2013 / VC12之前;总而言之，对于不易发生碰撞的按键，MS的方法将更轻/更快，并且负载系数较低，但性能会更早，否则会更显着地降级。std::unordered_setstd::unordered_map

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

字符串的哈希方式不是由C++标准指定 - 它留给各个编译器实现。因此，不同的编译器会做出不同的妥协 - 甚至是同一编译器的不同版本。

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

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

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

使用算术，其中是字符串的第 ^th 个字符，是字符串的长度，并指示幂。（空字符串的哈希值为零。ints[i]in^

这显然是字符串长度的O（N）。

快速返回...

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

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

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