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 (this is because raw Hash Table randomly distributes entries in BUCKETS). Logical coordinates change to:
template<typename T, int (*comparator)(const T&, const T&), std::size_t (*hasher)(const T&)>
class LinkedHashTable {
...
private:
LinkedList<T>* bucketList; // preallocated at CAPACITY size
std::size_t capacity; // size of bucketList
std::size_t size; // number of entries in data structure
DoublyLinkedList<T*> insertionOrder;
};
How are ENTRY items inserted into a linked hash table:
A LINKED HASH MAP implements Associative Array abstract data type using LINKED HASH TABLE above. In order to do so, it needs to derive hash table coordinates specification in a way similar to Hash Map with following C++ structure:
template<typename K, typename V, int (*comparator)(const K&, const K&), std::size_t (*hasher)(const K&)>
class LinkedHashMap {
...
private:
LinkedList<MapEntry<K, V>>* bucketList; // preallocated at CAPACITY size
std::size_t capacity; // size of bucketList
std::size_t size; // number of entries in data structure
DoublyLinkedList<MapEntry<K, V>*> insertionOrder;
};
| Operation | Description |
| clear | Deallocates BUCKETS LIST, clears DOUBLY LINKED LIST, reallocates new BUCKETS LIST and resets SIZE to zero. |
| containsKey | Applies HASHER to ENTRY KEY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any KEY matches |
| containsValue | For each ENTRY in DOUBLY LINKED LIST applies VALUE COMPARATOR to see if any ENTRY VALUE matches |
| get | Applies HASHER to ENTRY KEY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any KEY matches. If it does, returns VALUE of ENTRY. If not, ERROR thrown |
| set | Applies HASHER to ENTRY KEY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any KEY matches. If it does, updates VALUE of existing ENTRY. If not, writes ENTRY (to BUCKET and DOUBLY LINKED LIST) and increments SIZE |
| removeKey | Applies HASHER to ENTRY KEY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any KEY matches. If it does, removes ENTRY (from BUCKET and DOUBLY LINKED LIST) and decrements SIZE. If not, ERROR thrown |
| removeValue | For each ENTRY in DOUBLY LINKED LIST applies VALUE COMPARATOR to see if any VALUE matches. If it does, removes ENTRY (from BUCKET and DOUBLY LINKED LIST) and decrements SIZE. If none match, ERROR thrown |
| isEmpty | Checks if SIZE is zero |
| size | Gets value of SIZE |
For a complete implementation example, check LinkedHashMap class documentation or its GitHub code.
A LINKED HASH SET implements Set abstract data type using LINKED HASH TABLE above. Since linked hash table by itself fits SET requirements, no derivation is needed!
| Operation | Description |
| clear | Deallocates BUCKETS LIST, clears DOUBLY LINKED LIST, reallocates new BUCKETS LIST and resets SIZE to zero. |
| contains | Applies HASHER to ENTRY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any ENTRY matches |
| add | Applies HASHER to ENTRY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any ENTRY matches. If none does, writes ENTRY (to BUCKET and DOUBLY LINKED LIST) and increments SIZE |
| remove | Applies HASHER to ENTRY to detect BUCKET then loops through all ENTRIES inside and applies COMPARATOR to see if any ENTRY matches. If it does, removes ENTRY (to BUCKET and DOUBLY LINKED LIST) and decrements SIZE. If not, ERROR thrown |
| isEmpty | Checks if SIZE is zero |
| size | Gets value of SIZE |
For a complete implementation example, check LinkedHashSet class documentation or its GitHub code.
Same advantages and disadvantages of Hash Table apply, with these differences: