计算散列的速度有多快？

-1

它是在O（1）或O（n）还是在两者之间完成的？计算一个非常大的对象和一个小对象的散列是否有缺点？如果重要，我使用Python。计算散列的速度有多快？

2017-06-16 Vic

取决于散列函数的实现。 – zerocool

一个插件：与较大的对象相比，较小的对象碰撞的可能性较高？ – Vic

那么，我的回应仍然是一样的，碰撞是依赖于算法的。您可能有一个长度为100个字符的字符串，另一个长度为1个字符。现在，如果你的散列函数只考虑了字符串的第一个字符，你就会有很多冲突。 – zerocool

一般来说，对于“小”项目计算散列将是O（1），对于“大”项目（其中“N”表示项目的键的大小）计算散列将是O（N）。小的和大的精确的分界线是变化的，但是通常在寄存器的大小附近（例如，32位机器上的32位，64位机器上的64位）的某处。这也可以取决于输入类型 - 例如，寄存器大小上的整数类型全部散列且具有恒定的复杂性，但字符串需要的时间与字节大小成正比，直至单个字符（即，两个字符字符串大约是单个字符串的两倍）。

一旦你计算出散列表，访问散列表的过程就会有恒定的复杂度，但在最坏的情况下可能和O（N）一样坏（但这是一个不同的“N” - 项数插入表中，而不是个别密钥的大小）。

来源

2017-06-16 22:25:13

渐近复杂性可能不是用于讨论小输入大小运行时间的最合适的工具，因为它在技术上只关心当我们接近无穷大时发生的情况。另外，难道你不能说从N = 1开始它就像O（N/32）或O（N/64）（= O（N））一样吗？也许更重要的是，复杂性将完全取决于你如何实际计算哈希 - 我不认为有一条规则说明你可能只做O（1）每字节的工作来计算哈希。 – Dukeling

谢谢。在一个相关的说明中，这是否意味着一个字符的字符串占用64位，而一个两个字符的字符串占用128位？（假设是一个64位机器） – Vic

@Vic：不 - 通常一个字符会占用一到四个字节的东西，但是比这更大的东西将会非常少见。 –

大部分时间你的散列将在O（1）的访问中进行计算。但是，如果它是一个非常糟糕的散列，每个值都具有相同的散列值，那么最坏的情况就是O（n）。

与哈希关联的对象越多，就相当于碰撞的次数越多。

来源

2017-06-16 22:24:23

真正的答案取决于。你没有指定你感兴趣的散列函数。当我们谈论像SHA256这样的密码散列时，复杂度是O（n）。当我们正在谈论使用电话号码的后两位数字的散列函数时，它将是O（1）。哈希表中使用的哈希函数往往会针对速度进行优化，因此更接近O（1）。

有关散列表的进一步参考，请参阅Time Complexity上的python维基页面。

来源

2017-06-18 19:33:49

计算散列的速度有多快？

回答

相关问题