在哈希表中创建字符串的哈希值的时间复杂性 [英] Time complexity of creating hash value of a string in hashtable

问题描述

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

我确实理解为什么在一般情况下，插入哈希表是O(1)，但我对插入哈希表之前的步骤感到困惑：生成哈希值。

在Java中生成字符串的散列键的方式与在C++中生成unordered_map的方式有什么不同吗？ 谢谢。

推荐答案

在哈希表中插入EQUTE是O(1)，因为它在表中的元素数中是常量。

这个上下文中的"O(1)"并没有声明计算散列的速度有多快。如果这方面的努力在某种程度上有所增长，那就是它的方式。然而，我发现一个像样的(即"适合此应用程序")散列函数的复杂性不太可能在散列对象的"大小"(即我们的字符串示例中的长度)中比线性的要差。

这篇关于在哈希表中创建字符串的哈希值的时间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！