1. Takes a key / value pair as input 2. Key goes through the hash function and returns an index 3. The pair is stored at that index hash function 1 { key: value }
function is irreversible. One cannot take the index and find the key. It only works one way. • A hash table is deterministic system. One gets the same result from the same input every time. • A hash table is very efficient. The time complexity in big O notation is O(1).
to return the same result. This is called a collision. • Collisions are stored in a nested array. This method is called seperate chaining. • This is also why the time complexity worst case is O(n), n being the number of inputs.
included in most programming languages. This article is for a better understanding on how they work than a tutorial on how to implement one yourself. • In the following code example, we will implement an simple hash function. There are multiple ways to write them.