A Simple Hash Function and Handling Collisions (Hash Table)
Hash Function
A function that converts a string (an arbitrary size) to a number (of a fixed size) can be described as a hash function. An important thing about hash functions is there is no backward (after you convert it to hash indices you can not come back to the string i.e. back to key).
Example: Image below shows using a hash function to convert keys to hashes(later we are going to use these numbers as an array index).
Why even use a hash function?
It is easier to search any item using a hashed key than searching with the original value (ideally constant time).
A simple hash example
So in our hash function, we are going to use a method charCodeAt() that returns an integer between 0 and 65535 representing the UTF-16 code unit at the given index.
Our Hash function looks like this.
So, in our simple hash function, what we basically do is iterate through each character of our given string, convert each string using charCodeAt() function and do some maths operation as shown in-line 7 in the above image(we are using modulo ‘%’ because we want our array length to be within the desired limit). If you notice, we are using prime numbers because they minimize collisions. (for further detail you can research about it, it's a complex topic)
In the above example, we see we are getting the same hash value for two different keys(i.e. ‘another one’ & ‘TET’) that's called collision.
Collisions are inevitable, but there are many strategies for dealing with collisions such as Separate Chaining, Linear Probing, etc.
To deal with our above example we will be working with separate chaining.
Separate Chaining
Here we store different pieces of data at the same spot using another nested data structure. (In the above image we put Martha and Janet in an array which will form a nested array, we can also use linked list )
Our Hash Table (Using Separate Chaining)
In our above Hashtable class, we see there was a collision in our array at index 57, so we nested the array. For better performance, we tried to diversify the element index(in hash function) using prime numbers.
We were able to achieve the big ‘O’ of O(1) in the best case for our set and get methods. The worse case depends upon how diverse the indexes will be for each element, it can be from O(1) to O(n).
