Hash Tables
Tags: computerscience, algorithms, datastructures, csharp
Published: 2019-11-11 03:27:47

## Resources

1. [Hash table overview](https://www.interviewcake.com/concept/java/hash-map)
1. [Hashing explanation](https://www.interviewcake.com/concept/java/hashing)
1. [Hash table explanation](https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm)
1. [Hash table overview + implementation](https://brilliant.org/wiki/hash-tables/)
1. [In depth explanation](https://craftinginterpreters.com/hash-tables.html) - **warning** this one is a _long_ read (~60 mins). But there is too much good, approachable, info in there to not mention it. 

Takeaways:

* A **hash table** is essentially an array of buckets.
* Each bucket contains a key value pair (KVP).
* When inserting a KVP into a hash table, the key is hashed and modulo'd by the max size/capacity of the array. The resulting integer is the index of the array the KVP should be inserted at.
* Hashing of keys can be done using a variety of hashing functions*. 
* No **hashing function** is perfect and **collisions** do happen.
* Collisions are when we try to insert a KVP at a bucket that is not empty. This can happen when the same hash is generated for different keys. When the generated hash is the same, the resulting indexes are the same.
* There are two ways to perform **collision resolution**: **Separate Chaining** and **Open Addressing** (also known as **Closed Hashing**). 
* Separate Chaining means that each bucket in our array is a Linked List. When a collision occurs the KVP gets added to the Linked List. This means multiple KVPs can reside at the same index.
* Open Addressing uses a technique called **probing** to find the next available index to insert a KVP at. The order you search for an available bucket is the **probe sequence**. One type of probe sequence is **linear probing** - where we just increment the index by 1 until we find a free bucket in the array.
* One thing that determines how likely collisions are is the **Load Factor** of a hash table's underlying array. Load factor is: Number of KVPs/Number of Buckets.
* More robust hash table implementations will resize the underlying array when the Load Factor has reached a certain point. In my implementations I resize the arrays when the Load Factor reaches 0.75.
* Searching, Inserting, and Deleting are all worst case `O(n)` (linear), but for each the amortized time is `O(1)` (constant). This is because collisions should be rare (if you use a good hashing function and keep the Load Factor below a certain threshold).
* Space for hash tables is `O(n)`.

*The most common hashing functions I came across were: __DJB2__, __FNV-1a__, and __Murmur__. [FNV-1a is pretty simple](https://craftinginterpreters.com/hash-tables.html#hashing-strings), [as is DJB2](https://brilliant.org/wiki/hash-tables/). As it turns out [FNV-1a and Murmur are probably the _best_ hashing functions to rely on](https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed). I personally like FNV-1a for how simple, yet effective, it is.

Below is the finished implementation of two Hash Tables (with test code). One is implemented using separate chaining and the other open addressing:

{% gist https://gist.github.com/jbolton209/1abe2c7fb356f07d37afd9903a5adf66 %}

As always, if you found any errors in this post please let me know!