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

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)?

感谢您的帮助！

==================================

我知道有像 this one 这样的资源在讨论为什么散列是常数时间和冲突问题。然而，他们通常假设密钥的长度可以忽略不计。本题问的是当key长度不能忽略时，hashing是否还有常数时间。比如我们要判断一个长度为K的key是否在集合中N次，时间复杂度是O(N)还是O(N*K)。

Answer 1

Wiki 是你的朋友

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

上面的操作似乎都是 O(1) for a set

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 described in the header of setobject.c, adding an object into a set reuses hashes from strings where hash() has already been once called (recall, strings are immutable), or calls the type's hash implementation。

For Unicode/bytes objects, we end up via here to _Py_HashBytes, 貌似对小字符串有优化，不然就是用编译时配置的hash函数，自然有点O(n)-ish。但是同样，这似乎每个字符串对象只发生一次。

对于元组，可以找到散列实现 here – 显然是一个简化的、非缓存的 xxHash。

但是，一旦计算出哈希，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)

产出

make_string x 10000 0.23490356100000004 42570.66158311665
make_string x 20000 0.47143921999999994 42423.284172241765
make_string x 40000 0.942087403 42458.905482254915
make_tuple x 10000 0.45578034300000025 21940.393335480014
make_tuple x 20000 0.9328520900000008 21439.62608263008
make_tuple x 40000 1.8562772150000004 21548.505620158674

基本上说哈希序列，无论是字符串还是元组，都是线性时间，但哈希字符串比哈希元组快得多。

编辑 2：这证明字符串和字节串缓存它们的哈希值：

import time
s = ('x' * 500_000_000)
t0 = time.perf_counter()
a = hash(s)
t1 = time.perf_counter()
print(t1 - t0)
t0 = time.perf_counter()
b = hash(s)
t2 = time.perf_counter()
assert a == b
print(t2 - t0)

产出

0.26157095399999997
1.201999999977943e-06

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

What is the time complexity of adding and retrieving strings from hashset

python

hash

hashset