Notes - Imperative Programming HT23, Hash tables
Flashcards
What is the universe $U$ when discussing hash tables?
The set of all possible keys for the hash table.
When the universe of possible keys $U$ is small, what’s the name of the technique where every possible element has a space?
Direct addressing.
Storing every possible key in a hash table in a universe of keys $U$ would take $O( \vert U \vert )$ space but lookups can be done in $O(1)$ time. Considering only a subset $K$ of the keys means this can be reduced to $O( \vert K \vert )$ space, despite still only taking $O(1)$ time. What’s the catch?
This is $O(1)$ average-case, but $O( \vert K \vert )$ worst case.
What’s the name for an ideal hash function, one that uniformly distributes the keys into buckets?
An independent uniform hash function.
What data structure is used to resolve collisions in a hash table via chaining?
A doubly-linked list.
What’s open addressing in the context of hash tables?
A technique for minimising collisions that stores all data in the hash table at the first location available.