Data Structures: Linked Hash Tables

What is a linked hash table?

A linked hash table is an extension of Hash Table data structure where ENTRIES are also saved in a Doubly Linked List to allow predictable iteration by insertion order.

How does it work?

Linked hash table can be used to implement many abstract data types, but let us take its Associative Array implementation as an example to understand how it works:

Operation Description
clear Deallocates BUCKETS and BUCKETS LIST, resets SIZE to zero.
containsKey Applies hash function to KEY to get an INDEX, gets BUCKET @ INDEX, loops through all ENTRIES inside and applies comparator function to see if any ENTRY key matches
containsValue Loops through all BUCKETS, loops through all ENTRIES inside each BUCKET and applies comparator function to see if any ENTRY value matches
get Applies hash function to KEY to get an INDEX, gets BUCKET @ INDEX, loops through all ENTRIES inside, applies comparator function to see if ENTRY key matches then returns matching ENTRY
set Applies hash function to KEY to get an INDEX, gets BUCKET @ INDEX, loops through all ENTRIES inside, applies comparator function to see if ENTRY key matches then changes matching ENTRY value (if found) or adds a new ENTRY (if not), also incrementing SIZE
If ENTRY didn't exist previously, it is added to doubly linked list tail.
removeKey Applies hash function to KEY to get an INDEX, gets BUCKET @ INDEX, loops through all ENTRIES inside, applies comparator function to see if ENTRY key matches then deletes it, also decrementing SIZE
If ENTRY was found and deleted, it also removed from doubly linked list by making its left node point to next node.
removeValue Loops through all BUCKETS, loops through all ENTRIES inside each BUCKET, applies comparator function to see if any ENTRY value matches then deletes it, also decrementing SIZE
For each ENTRY found and deleted, it also removed from doubly linked list by making its left node point to next node.
isEmpty Checks if SIZE is zero
size Gets value of SIZE (number of elements in structure)

Same advantages and disadvantages of Hash Table apply, with these differences:


Share