Iterable hash table

Question

I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered_map, which should be a hash table implementation (it's actually not) and wondered that even if I implement the hash table, how could I make it iterable?

Let's say I'm implementing the hash table with a contiguous array in which I store the elements. When needed I resize the array and copy the elements over.

Since the positions of the elements are determined by the hash function, I cannot guarantee that each position is filled, but also, when iterating over each position in the contiguous array I don't know if it is filled by an actual element or it's just the default value there.

The only solution I thought of is to have a separate contiguous array of boolean values which determine which slots are filled and which are not, but I don't really like this solution.

Do you know of any other solutions of how to solve this issue, while still retaining the O(1) element access?

Answer 1

gnasher729's solution is often a good one, from a pragmatic perspective. It achieves linear time iteration as long as you ensure that the load factor of the hash table is bounded below by a constant.

Another alternative is to maintain a doubly-linked list of all of the hash slots. In other words, each hash slot also has a "next" and "prev" pointer, which for filled slots points to the next and previous filled hash slot. You can update this doubly linked list in $O(1)$ time whenever you insert or delete an entry into the hashtable. Then, this list makes it easy to do linear-time iteration over all elements of the hash table. In practice this is probably less desirable, because it significantly increases the space requirements, but it is another option.

Answer 2

In most implementations slots must be clearly recognisable as either "never used", "previously used but not used anymore" or "used, containing a hash value". So you just iterate over the stored hash values and use those that are neither "never used" nor "not used anymore".

Execution time is linear in the number of slots. If the number of slots is vastly greater than the number of used slots, it may be time to reduce the size of the hash table.