Iterable hash tables

[OnionKnight]

Just a thing that's been bugging me lately. I've read a considerable amount of theory on as well as implemented hash tables and for pretty much every implementation of them in different languages as well as similar data types (C++ std::map) you are able to iterate the keys and values, or even get an array of the keys and values. I'm wondering how this is done as I have only seen hash tables in the form of a large array where you hash a key into an index for that array. Iterating such an implementation would require brute force unless you add some additional information that can tell you about the location of things.

[cyberfish]

You could keep a linked list of occupied indexes.

Insertion = O(1)
Deletion = O(n)
Iterating = O(n)

Depending on your usage scenario and how saturated the hash table is, it may or may not be faster than "brute force".

[CornedBee]

Iterating such an implementation would require brute force

Huh? If you have a bucket hash table, you simply iterate over the buckets in sequence. I don't see what the problem is.

Nobody ever guaranteed any specific order in the iteration of hash tables.

[Cactus_Hugger]

You could keep a sorted linked list of occupied indexes.

Insertion = log(n)
Deletion = log(n)
Iterating = n

Insertion/Deletion into a sorted linked list is O(n). Binary search, which I'm assuming you're suggesting, requires random access into the container.

You can always look into your STL's implementation and see how it works, if it has them, of std::hash_map or std::hash_set. (MinGW keeps these in an "ext" folder on my machine, but they're in STLPort too.) Additionally, TR1 has unordered_set/map, not sure how much these differ. None of these are standard, yet, I think. Read The Manual, as always.

[cyberfish]

Ah, my bad. Must have been drunk.

Thanks for the correction.
Post above editted. (There is no point in using a sorted list then)

[OnionKnight]

Huh? If you have a bucket hash table, you simply iterate over the buckets in sequence. I don't see what the problem is.

Nobody ever guaranteed any specific order in the iteration of hash tables.

I wasn't thinking of order. But I usually envision hash tables to be sparse and that iterating over the whole array would take a lot of time. But I suppose you're right, if you keep your array sized in accommodation to the hash table's load you're not really wasting much time going over lots of empty buckets, and it is just O(n).