如何检查元组键是否在 O(1) 时间的字典中？

Question

我正在尝试在 Python 中实现散列 table/hash 映射。

假设我像这样使用元组作为键：

hashTable = {}
node = [1, 2, 3]

print(hashTable[tuple(node)]) # throws an error
hashTable[tuple(node)] = True
print(hashTable[tuple(node)]) # prints TRUE

我想在添加元素之前检查元素是否存在于 hashTable 中。我尝试用所有 False 值初始化字典。

hashTable = {}
for i in range(1000):
    hashTable[i] = False

因此，这将创建一个大小为 1000 的散列 table，每个槽都设置为 FALSE。但是如果我尝试检查哈希表中是否存在不存在的元素：

print(hashTable[tuple(node)])

我得到了和以前一样的错误。

如何做到这一点？我认为这可以用 in 遍历字典，但这不会破坏首先使用散列 table 的全部目的吗？

Answer 1

您可以使用 in 运算符来确定字典中的成员资格：

例如

if tuple(node) in hashTable:
     x = hashTable[tuple(node)]
     ...

Answer 2

访问密钥与检查密钥是否存在类似，但不一定相同。要检查某个键是否在字典中，请通过 in 运算符使用 dict.__contains__。要检查它是否丢失，请使用 not in 运算符：

key = tuple(node)
if key not in hashTable:
    hashTable[key] = value

也就是说，一种完全有效的检查收容的方法是尝试访问：

key = tuple(node)
try:
    # attempt to use hashTable[key]
except KeyError:
    # Do something with missing key

当需要两条路径时这样做的好处是您只需要访问字典一次而不是两次。

尽量避免一遍又一遍地调用 tuple(node)：它不是免费的。如果可以，将 node 生成为 tuple，这样做。如果不是，则执行一次转换并使用转换后的值。

Answer 3

您可以尝试获取密钥，如果它不在词典中，return 一个默认值可能是 None:

x = hashTable.get(node, default=None)

如何检查元组键是否在 O(1) 时间的字典中？

How to check if a tuple key is in a dict with O(1) time?

python

dictionary

hashtable