RKS
BAN USERAn array offers the constant time of O(1) for accessing an element using its ordinal index.
However, rarely do we know the ordinal index of the element that we are searching for. This forces us to search through the entire array to find an element.
Searching through an unsorted array has the complexity of O(n).
If the array is sorted, the complexity decreases to O(log n). However, this is still far from the desired O(1) that we would like to achieve.
An array that uses hashing to compress its indexers space is referred to as a hashtable. A hash function is the one which is used to do this transformation.
So, we can use any hashing function to reduce the indexers space. e.g. if we access the records based on SSN, we can select the hashing fuction to be the last-4 digits.
Now, as we can easily see, this would cause collisions i.e. the multiple elements would be competing for the same position in the hashed array. We can resolve collisions using the following methods:-
1) Linear probing ->
Inserting an element - If the position at the hashed value is occupied, move to the next position and store the value. Continue moving to the next position until a free space is found.
Searching for an element - Find the hashed element position, access that element from the hashtable, continue moving to the next position until the element is found.
This leads to clustering of data and is not a very effective collision resolution strategy.
2) Quadratic probing ->
Inserting an element - If the position at the hashed value is occupied, move to the next position in quadratic multiples e.g. (s - 1^2), (s + 1^2), (s - 2^2), (s + 2^2) and so on. Continue moving to the next position until a free space is found.
Searching for an element - Find the hashed element position, access that element from the hashtable, continue moving to the next position in quadratic multiples as used for inserting the value until the element is found.
This gives a better performance than Linear probing but still leads to clustering.
3) Rehasing -> This strategy is used by .NET framework for collision resolution in System.Collections.Hashtable class.
It uses the following hashing function
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
First H1 is used in the above hashing function, if a collision occurs H2 is tried till Hn.
4) Chaining -> This strategy is used by .NET framework for collision resolution in System.Collections.Generic.Dictionary class.
In this method, we just chain all the elements which are located in the same bucket after applying the hashing function.
These are the several methods using which we can build a Hashtable and achieve collision resolution in it.
Perhaps I don't get the complexity of a problem or I don't understand the actual question but my solution would be the following. Please correct if I am wrong.
Thanks.
- RKS October 31, 2016