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:

- program: instances LinkedHashTable with HASH/COMPARATORs, optionally signaling expected CAPACITY
- HashTable: a BUCKET LIST is allocated with CAPACITY + a DOUBLY LINKED LIST
- program: uses above object to write ENTRY
- HashTable: HASHER is applied to ENTRY to get BUCKET to write to
- HashTable: COMPARATOR is applied to every ENTRY in BUCKET and writes (to BUCKET and DOUBLY LINKED LIST) only if none match

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:

- elements can be iterated in predictable insertion order, thanks to Doubly Linked List it maintains
- higher memory consumption, because it needs to maintain a Doubly Linked List
- slower performance in insertions/deletions because they need to be mirrored in Doubly Linked List
- much slower performance in random deletions due to linked list's drawbacks