Hash table

From DocForge

A hash table is an extremely fast data structure which, like a map, allows for quick access to data by searching through its keys.

The principle of the hash table is that it indexes items based on their hash value - an imperfectly unique number which can be used to sort the data. For instance, hypothesize that in Java you have some data, say a bunch of Images. Rather than index each Image and manipulate each Image in memory individually (which would be prohibitively slow) it is easier to assign a key value - in this case a String - to each Image. The way in which Java hashes a String is the sum of each character in the String to the 31st power.

The hash table would take each Image and create a pointer to that Image, and then key that pointer with the String. A hash table usually uses an array of data structures within which each key/value pair is stored. To use the hash value of the key (the String) to determine which location in the Array in which the key value pair belongs, a simple equation finds a location in the Array (hash value % (mod) length of array).

To find the value again, it's a simple matter of finding the hash value of the key and then retrieving the data structure at that location in the Array, and then searching through that data structure for the data. The principle is that by distributing all the data across so many data structures each data structure should have (in the best-case scenario) only one item in it at any given time (though obviously collisions will occur, it's still significantly faster than exhaustively searching any other kind of data structure, even a Binary Search Tree.) To avoid collisions, it is best to ensure that the length of the Array in the Hash Table is at least 1.5 times greater than the number of items that will be stored there.

The Big O notation of any accesses to a Hash Table is said to be O(1).