Linked Hash Table

A linked hash table is a combination of a hash table and a linked list. Nodes are arranged in buckets but also have a doubly linked list running through them.

One can use the hash table structure for fast hash based lookups, and the linked list for effirient traversal.

Hash Table Traversal

There's no way to know which buckets are empty, and which ones are not, so all buckets must be traversed. This means traversal is Θ(n + m).

In practice this is only relevant if the hash table is initialized with a very large capacity. After the first rehashing the number of buckets can be considered linearly proportional to the number of items, and traversal is Θ(n).

Adding a linked list

If one wants to avoid the overhead due to empty buckets one can let a linked list run through all nodes. Whenever a node is added to the hash table, it's appended to this list.

This effectively trades some memory (additional next / prev pointers) for improved speed.

Since the overlay list structure is doubly linked, append and remove are constant time operations, so it does not affect the complexity of other operations.

The LinkedHashMap in the Java API is an example of this technique.