CODEWITHSUNDEEP
algorithmhashhashmap
m_ocean
m_ocean

Reputation: 355

In hash tables, how can iteration over keys be implemented?

Basically, I wonder what happens or might happen under the hood when I run something like this:

for key in some_hash_map.keys():
    print(key)

Is it just about using a reversed hash function?

Upvotes: 1

Views: 608

Answers (1)

btilly
btilly

Reputation: 46408

A typical hash table can be implemented as an array of buckets, each of which has a linked list of entries.

A hash lookup goes by running the hash function to find the right bucket, then searching the bucket.

Iterating over the keys is implemented by iterating over the buckets, searching each list in turn.

If there are too many buckets, you waste memory and iteration is slow. Too few, and the linked lists get slow. But we can dynamically resize the number of buckets for fixed per key overhead.

If the hash function fails to work well, then a hash will perform terribly.

Upvotes: 3

Related Questions