# Hash Tables

Hash tables are a corner stone of data structures for most problems, they are useful when there are unique keys with given values

Last updated

Hash tables are a corner stone of data structures for most problems, they are useful when there are unique keys with given values

Last updated

Runtime analysis

Insert: $O(1)$

Search: $O(1)$

Delete: $O(1)$

Update: $O(1)$

Take note…

Do we need a custom hashing function?

Techniques

Anagram hashing

This technique is particularly when trying to detect all anagrams and store them in buckets of same anagrams

Multiplicative hash with prime numbers (3 onwards)

Assign each character a prime number and calculate the hash

Hash will be unique per anagram

Does not scale well if more than 52 characters possible or $n > 5000$

Fingerprint hash tables/arrays over hash tables

I would recommend using these over hash tables where possible as they can represent the same information while reducing the complexity of the code

Duplicate checking using bitmasks

This is a slight optimization over using hash tables/sets if the only thing that needs to be done is duplicate detection

Not feasible if the numbers can be very large as size grows by powers of 2

Multiplicative hashing

Pairing with another data structure

Often used to improve performance at the cost of using more space to store the hash table

Use Linked Lists to optimize to quickly delete/insert nodes in a certain order

Hash table has pointers to the nodes of the linked list

Types of hashing

Chaining (linked list per bucket)

Open addressing (probing for a blank spot if current bucket is filled)

$h(k) = \lfloor m(\phi \times k - \lfloor \phi \times k \rfloor) \rfloor$

Where $k$ is the key to hash, $\phi$ is the golden ratio = $\sqrt{5} - \frac{1}{2}$