散列如何对 python 集工作

Question

我完全熟悉哈希表和哈希的工作原理，但我试图完全理解O(1)是如何完全来自的。

set1 = {'s','t'}
print('x' in set1)
print('s' in set1)
set2 = {'s'}
print('s' in set2)

我被告知要检查是否's'在 set1 中，if 将检查 的哈希值的内存分配's'，并检查它是否在O(1)中的 set1 中并返回布尔值。因此两个 O(1) 操作，但我的问题是：散列实际上如何深入工作。我的意思是，当您 hash 时's'，该散列是否有类似的东西set1，set2并且您正在检查是否set1为set1或set2，或者每个集合是否具有不同的散列's'并且您正在检查's'每个不同集合的散列。

Answer 1

Pythondict本质上是一个哈希表。本质上，键通过哈希函数转换为表位置；由于多个键可能具有相同的值，因此必须有某种机制来检测冲突（多个键具有相同的值）并向下移动一系列备用条目，直到找到正确的键。

对于dict关键单元格，当找到时，它与一个值关联。为一个set没有值：键要么属于该集合，要么不属于该集合。

因此，散列行为允许在恒定时间内消除大多数可能的值（假设冲突并不频繁出现问题，并且 Python 会在发生冲突时小心地重新分配存储）。