从哈希集中添加和检索字符串的时间复杂度是多少

Question

假设我们将一组长字符串添加到哈希集中，然后测试该哈希集中是否已经存在一些字符串。添加和检索操作的时间复杂度是否恒定？还是取决于字符串的长度？

例如，如果我们有三个字符串。

s1 = 'abcdefghijklmn'
s2 = 'dalkfdboijaskjd'
s3 = 'abcdefghijklmn'

然后我们做：

pool = set()
pool.add(s1)
pool.add(s2)
print s3 in pool # => True
print 'zzzzzzzzzz' in pool # => False

上述操作的时间复杂度是否会成为字符串长度的因素？

另一个问题是，如果我们对一个元组进行散列怎么办？像（1,2,3,4,5,6,7,8,9）之类的东西？

感谢您的帮助！

Answer 1

Wiki是您的朋友

https://wiki.python.org/moin/TimeComplexity

对于上面的操作，对于set，它们似乎都是O（1）

Answer 2

严格来说，它取决于哈希集的实现以及您使用它的方式（在特殊情况下，可能会有一些聪明的做法可以优化某些时间），但是总的来说，是的，您应该期望它将需要O（n）时间来对键进行哈希处理以进行插入或查找，其中n是键的大小。通常，将哈希集假定为O（1），但是有一个隐式假设，即密钥的大小固定，并且对其进行哈希处理是O（1）操作（换句话说，假设密钥大小可以忽略）比较集合中的项目数）。

优化真正的大数据块的存储和检索是数据库的原因。 ：）

Answer 3

平均情况为O（1）。但是，最坏的情况是O（n），其中n是集合中元素的数量。这种情况是由哈希冲突引起的。你可以在这里了解更多https://www.geeksforgeeks.org/internal-working-of-set-in-python/

Answer 4

回答类似问题的最好方法之一就是深入研究实现：）

尽管有optimization magic标头中描述的某些setobject.c，但adding an object into a set重用了曾经调用过hash()（调用，字符串是不可变的）或calls the type's hash implementation的字符串的散列。

对于Unicode /字节对象，我们最终通过here到_Py_HashBytes，这似乎对小字符串进行了优化，否则它使用编译时配置的哈希函数，所有这些自然都为O（n ）-ish。但是同样，每个字符串对象似乎只发生一次。

对于元组，可以找到_Py_HashBytes –显然是简化的非缓存xxHash。

但是，一旦计算出哈希，here。

EDIT：一个快速但不太科学的基准：

the time complexity for sets should be around O(1)

输出

import time


def make_string(c, n):
    return c * n


def make_tuple(el, n):
    return (el,) * n


def hashtest(gen, n):
    # First compute how long generation alone takes
    gen_time = time.perf_counter()
    for x in range(n):
        gen()
    gen_time = time.perf_counter() - gen_time

    # Then compute how long hashing and generation takes
    hash_and_gen_time = time.perf_counter()
    for x in range(n):
        hash(gen())
    hash_and_gen_time = time.perf_counter() - hash_and_gen_time

    # Return the two
    return (hash_and_gen_time, gen_time)


for gen in (make_string, make_tuple):
    for obj_length in (10000, 20000, 40000):
        t = f"{gen.__name__} x {obj_length}"
        # Using `b'hello'.decode()` here to avoid any cached hash shenanigans
        hash_and_gen_time, gen_time = hashtest(
            lambda: gen(b"hello".decode(), obj_length), 10000
        )
        hash_time = hash_and_gen_time - gen_time
        print(t, hash_time, obj_length / hash_time)

基本上说哈希序列是字符串或元组，是线性时间，但是哈希字符串比哈希元组快很多。