CODEWITHSUNDEEP
performancehashhashmaphashtabletime-complexity
Henrik Sommerland
Henrik Sommerland

Reputation: 595

Time complexity for getting the list of keys in a hash table?

In a lot of languages you have the ability to get the list of keys from a hash table. Like the keySet() method for hash maps in java. How can this be obtained from a populated hash map? Isn't the hashfuction irreversible? Do you have too keep the keys in a separate list?

So when i use functions to obtain the list of keyes used in a populated hash table what is the time complexity of that function?

For my particular problem i happen to know the maximum number of entries in the hash table. Does this help?

Upvotes: 2

Views: 2827

Answers (2)

Gene
Gene

Reputation: 47010

In any reasonable implementation, touching all the keys in natural order (not sorted) is O(current size of the table including empty slots).

In an implementation that chains together the entries (e.g. Java as you can observe in the LinkedHashMap iterator code here), the table size is irrelevant. The algorithm is traversing a linked list.

You don't need to know the hash keys because the iterations are touching the data structure directly, not using the keys.

Upvotes: 1

user395760
user395760

Reputation:

Virtually every hash table stores the keys in addition to the values. This is necessary anyway, to resolve hash collisions (in some cases collisions are provably impossible, but this requires enumerating the full key set beforehand so it doesn't apply to general-purpose hash table). That is, the hash table {"foo": 1, "bar": 2} does not look like this:

1
2

but rather like this

("foo", 1)
("bar", 2)

Iterating over the keys is then simply a matter of iterating over the underlying structure of the hash table.

Upvotes: 1

Related Questions