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

I'm trying to implement a hash table/hash map in Python.

Say I'm using tuples as keys like this:

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

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

I want to check if elements exist in the hashTable before adding it. I have tried initializing the dictionary with all False values.

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

So this creates a hash table of size 1000 with every slot set to FALSE. But if I try to check if a non-existent element is in the hashTable:

print(hashTable[tuple(node)])

I get the same error as before.

How does one go about doing this? I think this would work iterating through the dict with in but doesn't that defeat the whole purpose of using a hash table in the first place?

CodePudding user response：

Accessing a key is similar to, but not necessarily the same as checking if it exists. To check if a key is in a dictionary, use dict.__contains__ via the in operator. To check if it is missing, use the not in operator:

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

That being said, a totally valid way to check for containment can be by attempting access:

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

The advantage of doing it this way when both paths are needed is that you only need to access the dictionary once rather than twice.

Try to avoid calling tuple(node) over and over: it's not free. If you can, generate node as a tuple, do so. If not, perform the conversion once and use the converted value.

CodePudding user response：

You can use the in operator to determine membership in a dictionary:

e.g.

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

CodePudding user response：

You can try to get the key and in case it is not in de dictionary yet, return a default value as may be None:

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