Python中的内部hash()函数的复杂性

2024-03-29 14:09:30 发布

您现在位置:Python中文网/ 问答频道 /正文

我知道哈希表查找的平均情况是O(1),但这是否包括计算给定输入的哈希值本身所需的时间?我试着在google上寻找答案,阅读了所有需要的文档,但是在Python中找不到内部hash()函数的实现。一些网站声明计算哈希值需要一个固定的时间量,有些网站说它是O(k),其中{}是输入的长度。如果你能帮我找到正确的答案,我会很高兴的。提前感谢:)


Tags: 函数答案文档声明网站google时间情况
2条回答

我做了一个小测试来验证这个假设。结果似乎并不取决于输入的长度。在

import datetime

x = ['a','aa','aaaaaaaaaaaaaaaaaaaaaaaaaaaa','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa']
for i in range(len(x)):

    for j in range(len(x)):
        print "Checking for: " + x[i] + " " + x[j]
        a = datetime.datetime.now()

        h = hash((x[i],x[j])) 
        b = datetime.datetime.now()
        c = b - a
        print "Time taken : " + str(c.microseconds) 

结果

^{pr2}$

它完全取决于被散列的类型。以下是CPython 2.7.13中的一些简单测试,这不是唯一的选择:

>>> pprint.pprint([(i, timeit.timeit('hash(n)', setup='n="a"*{}'.format(6400*i), number=1)) for i in range(16)])
[(0, 1.9073486328125e-06),
 (1, 1.6927719116210938e-05),
 (2, 3.314018249511719e-05),
 (3, 4.887580871582031e-05),
 (4, 6.4849853515625e-05),
 (5, 8.106231689453125e-05),
 (6, 9.679794311523438e-05),
 (7, 0.00011301040649414062),
 (8, 0.00012993812561035156),
 (9, 0.00014495849609375),
 (10, 0.00016188621520996094),
 (11, 0.0001780986785888672),
 (12, 0.00019288063049316406),
 (13, 0.0002090930938720703),
 (14, 0.000225067138671875),
 (15, 0.00024199485778808594)]
>>> pprint.pprint([(i, timeit.timeit('hash(n)', setup='n="a"*{}'.format(6400*i))) for i in range(16)])
[(0, 0.09920382499694824),
 (1, 0.09032988548278809),
 (2, 0.09069585800170898),
 (3, 0.09006309509277344),
 (4, 0.09059309959411621),
 (5, 0.09033513069152832),
 (6, 0.09037399291992188),
 (7, 0.09031510353088379),
 (8, 0.09110498428344727),
 (9, 0.09074902534484863),
 (10, 0.0909719467163086),
 (11, 0.09081602096557617),
 (12, 0.09112405776977539),
 (13, 0.09091711044311523),
 (14, 0.09103798866271973),
 (15, 0.09085893630981445)]

请注意,对新创建的字符串进行哈希处理的方式是O(n),但是每个字符串都在缓存其哈希,以便在重复时将其摊销为常量时间(number=1000000是{}的默认值)。在

^{pr2}$

long也是O(n),其中n是数字的宽度,因此是数量的对数。粒度是^{},通常是2**30,专门用于直接用作较小整数的散列。在

其他对象将有自己的行为,例如tuples将粗略地合计其内容的哈希时间。在

相关问题 更多 >