Search code examples
data-structureslinked-listhashmaphashtable

How do you implement an ordered hashtable?

I am searching for how to implement an ordered hash table but not finding anything.

I would like to create a hash table which you can iterate over and that gives you the elements based on the order in which you defined or inserted the keys. How do you do this generally, in a performant way? How is this implemented? If a language must be chosen for an example, I am thinking about doing this in JavaScript. I know for example JavaScript objects ("hash maps") are ordered hash maps, but I have no idea how they are implemented. I would like to learn how to implement the same thing from scratch for a custom programming language.

The example is, say you are listing the native script version of a language name, like "עִברִית" for "Hebrew", as the key, and you want to create a map of the native language to the english language, but you want them to stay in the order defined. How do you implement that?

Solution

  • The general, performant solution to this problem is combining a linked list with a hash table. You will have a doubly linked list of Nodes, and each one is indexed via the hash table. You can look things up in either direction in constant time. Broadly, the operations are implemented as follows,

    1. Insert - O(1)* - Insert a Node to the end of the linked list, and reference that Node via its key via the hash map.
    2. Retrieve by key - O(1)* - Using the hash table, find the corresponding Node and return its value.
    3. Delete by key - O(1)* - Using the hash table, find the corresponding Node and remove it by removing its neighbour's references to it.
    4. Traverse - O(n) - Traverse the linked list. n in this case is the number of Nodes, not the full capacity of the hash table.

    * The actual insert/retrieve/delete times are subject to the worst-case of the hash table's implementation. Typically this is O(n) worst case, O(1) average.

    (An alternative to this is to store a "next key" in each Node instead of a direct pointer to the next node. The runtimes are the same, but traversal needs to involve the hash table whereas in the direct pointer implementation it can be bypassed.)

    So if you want to implement this on your own, you'll need a hash table and some Nodes to use within it.