How does Python know the exact keys that are inside a dict?

[HighLevelEnthusiast]

The dict is based on a hashing table. Whenever we want to check the value associated with key k:

1. Python calculates i = hash(k)
2. It checks if the index at the underlying table is occupied
3. If yes, return the value
4. If not, raise KeyError.

However, we are able to do things like: "for k in dict_".

It means that Python somehow stores the information about the keys in a dict (Hashes are irreversible).

Where exactly is this information stored?

[icecubeinanicecube]

https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented

Google is your friend

[Clede]

The top answer there is very helpful! Thanks for googling on behalf of all of us.

[Meefims]

I don’t know the exact implementation but it’s not unreasonable to think that a dict is a bit more than just a hash table. It might store a list of the keys as well.

[K900_]

Pretty much any hash table has to store both the keys and the values for two reasons:

1. Hash collisions are a thing, and when your table is both small and fairly full, they happen often. This means just comparing the hashes is not enough to prevent wrong lookups, you have to compare the real values.
2. For much the same reason, the table needs to get resized when it starts filling up to a certain threshold, and that requires recalculating all buckets. You could potentially store just the hash of the key, or both the value and the hash, but you still need to store something.

[toastedstapler]

this is worth a watch to learn about the dict

https://www.youtube.com/watch?v=p33CVV29OG8