# Iterable hash table

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?

• What about using a linked-list for that? Jan 21 at 12:25

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.