1

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?

Lance
  • 75,200
  • 93
  • 289
  • 503
  • Since you're thinking about doing it in Javascript, one thing that comes to mind is maybe allocating a list and a empty object. When adding items, add the key to the list and the values in the object/dictionary where dict[key] = value. We can then iterate in order over the hashtable by looping over the key list and getting the values from the object/dictionary. – driouxg Dec 30 '20 at 20:31
  • I want to implement an ordered object/dictionary, you’re using the built in dictionary to implement it, which is cheating haha – Lance Dec 30 '20 at 21:19

1 Answers1

4

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.

Welbog
  • 59,154
  • 9
  • 110
  • 123
  • I can’t imagine what this means: “You will have a doubly linked list of Nodes, and each one is indexed via the hash table.” How do you go from node to index? Given node has a string key, I pass that into a hash function, how is it going to give me the index? – Lance Dec 30 '20 at 21:16
  • In the conventional way of whatever your hash table's implementation is. It could be as simple as a modulus of the string's hash. Basically, instead of your hash table's value type being your structure's values, it's a Node instead. The key behaves as normal. – Welbog Dec 30 '20 at 21:50
  • https://stackoverflow.com/questions/14645035/sorted-map-implementation – Lance Dec 31 '20 at 02:12