Part 5: Hashing
Hashing in programming is the one of an efficiency way to store the data into list by each data has own specific address inside. In fact, having own address, we will use hash function to find it (which hash function depends on what we want to be). Advantage of using hashing, it is faster than searching data in normal list or array because hashing has more flexible method of retrieving data.
Hash function is the function to find the address of the data that we can give, which one of the most common function is h(x) = x % size of the table (list) where x is the number that represent the data.
There are four main methods that we can hash the data which are separate chaining, linear probing, quadratic probing, and double hashing.
Separate Chaining
When we get result from our hash function, we will put the data into a list in given index (which is result). If it already has the data in that index of list, we will use linked list (find more: https://www.geeksforgeeks.org/linked-list-set-1-introduction/) to connect the data together which, in the other words, we will have two or more data in that index of list.
Linear Probing
After we get the result from our hash function, we will put the data into a list in given index (as same as in separate chaining). However, if it already has the data in that index of list, we will put the data into next index (next index = index + 1). If the next index that we find still has element inside, we will continue to use a same method until it satisfy.
Quadratic Probing
In this method, it quite similar to the linear probing. The difference of two method is when we find new index in linear probing, we will add one from previous index, nevertheless, in double probing, we will skip the index every quadratic number, for example, 1 (1²), 4 (2²), 9 (3²), 16 (4²), 25 (5²). In fact, this will not separate the data, not grouping together as same as linear probing.
Double Hashing
In this method, if index of list that we find from our hash function already has data, we will use another hash function to find a new index by adding the result from a second hash function to the result of first function (new index = result of first function + result of second function). If new index still has data, we just continue to add the result of second function to our new index until it satisfy.
