Computer Science

A hash function is a procedure which takes a large amount of data as input and returns a number or code. This code or number is normally used as an index in an array or table.

A hash table is a data structure which uses a hash function to map the identifier or key to the index of a free a slot within the data table. For example, suppose we had a large list of people's names with a telephone number for each. The hash function examines the name of each person, and converts it into a numerical value. This value will be the index or key that gives the location of the data in the hash table. When the program receives a request for the phone number of a person, the hash function is applied to their name and the resulting value used to locate their phone number within the hash table.

It is tricky to develop a perfect hashing algorithm. A good algorithm uniformly distributes values across the hash table, can produce all of the available locations and minimises collisions (where two different values, when hashed, produce the same hash value).

When a collision occurs whilst a value is being hashed, the data is normally placed in the next available location or in a separate overflow area. Regardless, when the data is searched, the search algorithm can check these two locations if the value sought is not found in the expected location. In any case, the process of retrieving information this way is quicker than searching through all or most of the records to find the value.

There is a built-in hashtable class in C#. Check that you can instantiate a hashtable and add to and retrieve data from it.