hash - 计算哈希值有多快？

Question

它是在 O(1) 或 O(n) 还是介于两者之间的时间内完成的？计算一个非常大的对象的哈希值与计算一个小对象的哈希值相比有什么缺点吗？如果重要的话，我正在使用 Python。

Answer 1

一般来说，对于“小”项，计算哈希值的时间复杂度为 O(1)；对于“大”项，计算哈希值的时间复杂度为 O(N)(其中“N”表示项的键的大小)。小和大之间的精确分界线有所不同，但通常位于寄存器大小附近的某个位置(例如，32 位机器上为 32 位，64 位机器上为 64 位)。这也可能取决于输入类型——例如，整数类型取决于寄存器大小，所有散列都具有恒定的复杂性，但字符串所花费的时间与字节大小成正比，一直到单个字符(即两个字符)字符串大约花费单个字符串时间的两倍)。

计算完哈希后，访问哈希表的复杂性预计会恒定，但在最坏的情况下可能会像 O(N) 一样糟糕(但这是一个不同的“N”——插入的项目数表中的大小，而不是单个 key 的大小)。