Hash tables are used for efficient searches of arrays when a linear search may take too long, or the maintenance of the sorting required for a binary search is too much processing.
A hash table is an array in which elements are placed according to the result of a certain "hash algorithm" applied to them. Many/most of the hash table's element numbers (subscripts) are exactly the same as the results of that certain “hash algorithm”.
So, for example, if the hash algorithm applied to the data element “Hello” evaluates to 7, then “Hello” will be held at the 7th subscript position [7] of the hash table array.
If more than one data item from the original array evaluates to the same value (then preferably another hash algorithm that yields more possible numbers should be used, or else) one of several “tie-breaking” approaches needs to be utilized. The approach suggested by the IBO is simply searching for the next free space and putting the data item there.
So when you are searching for a specific data item in a hash table array, you first re-perform the exact same hash algorithm that was used in the hash table's creation (for example, the most common for Strings is modulo division performed on the ASCII sum of the String's chars by the size of the array, to yield in that case remainders of 0 - size-of-the-array). Then you'd look at that index to see if the item you are searching for is there. If it is, voila! If it's not (in which case there must have been a tie), you would revert at that stage to the slower linear search beginning to the right of that index until you find it – it should be close.
Here are the core parts of a standard hashing algorithm.
int total = 0;
for(int i = 0; i < stringToAdd.length(); i++){
total += stringToAdd.charAt(i);
}
int hashValue = total % 10; //Hopefully, and usually, this will be an element number which is available.
//But if not, the tie-breaking part of the algorithm below will do the trick.
while (!hashTable[hashValue].equals(“”)){ //The case where that element number is already occupied.
hashValue++; //Keep on looking to the right.
if(hashValue > hashTable.length){ //If you go over then end of the array...
hashValue = 0; //...go back to the beginning
}
hashTable[hashValue] = stringToAdd; //Place your content in the free element you have found
But for a more complete hash tables program, refer to the app and code here in Java Revolution.
Terms:
Hashing: applying a certain algorithm on a piece of data resulting in a numeric value, which when the hashing is applied again, will yield the same value.
Hash calculation (or algorithm): the steps taken to come up with the hash value. This can be simple, as with adding up ASCII values of characters and modules dividing by the array length, or it could be much more complex.
Hash table: an array which is created by placing element according to a certain hash calculation.
Hash total: the total value of the ACSII values of a record, as used in the simplest of hash algorithms.
Hash value: the final value which will correspond with a specific element number of the hash table array.
Pointer: The temporary element number kept track of through either adding to or searching through a hash table array.
Below is an animated demonstration of how hashing works:
But make sure to look at the code image itself for complete comments of how the Java solution works.
(Flash file original: _Flash/Hash-Tables.swf)
