Hashing
Introduction
The problem at hands is to speed up searching. Consider the problem of searching an array for a
given value. If the array is not sorted, the search might require examining each and all elements
of the array, which will take O (n) time. If the array is sorted, the binary search algorithm can be
used which will reduce the worse-case runtime complexity to O (log n). However, search can be
made even faster if the index at which that value is located in the array is known in advance.
Suppose we do have that magic function that would tell us the index for a given value. With this
magic function the searching process will be reduced to just one probe, giving us a constant
runtime.
Such a technique is called hashing. Hashing is basically a searching technique which takes O (1)
time. In this searching technique, a special function, called the hash function, will generate a
unique address/index for all data values and the data values will be stored in a special table,
called the hash table, at the index that is generated by the hash function.
The example of a hash function is a book call number. Each book in the library has a unique call
number. A call number is like an address: it tells us where the book is located in the library.
Many academic libraries in the United States, uses Library of Congress Classification for call
numbers. This system uses a combination of letters and numbers to arrange materials by subjects.
Hash Tables
Hash table is a data structure in which key values are mapped to certain array positions
generated by a hash function. It is a collection of items which are stored in such a way as to
make it easy to find them later. Each position of the hash table, often called a slot, can hold an
item and is named by an integer value starting at 0. For example, we will have a slot named 0, a
slot named 1, a slot named 2, and so on. Initially, the hash table contains no items so every slot is
empty. If for any data, ‘d’, the index generated by a hash function is ‘i', then the data ‘d’ will be
stored in index/address ‘i’ of the hash table only. When two or more data values map to the same
memory location or index, then a collision is said to occur which needs to be handled.
Hash Functions
The mapping between an item and the slot where that item belongs in the hash table is called
the hash function. A hash function is a mathematical formula which, when applied to a data
value, produces an integer which can be used as an index for the data value in the hash table. The
main aim of hash function is that elements should be relatively, randomly and uniformly
distributed. It produces a unique set of integers within some suitable range in order to reduce
collisions. Our goal is to create a hash function that minimizes the number of collisions, is easy
to compute, and evenly distributes the items in the hash table. The different hash functions are as
follows:
1. Division Method: It is the simplest method of hashing which divides ‘x’ by ‘m’ and then
uses the remainder obtained. In this case, the hash function is given as:
H (x) = x mod m
Where x is the given data value and m is any integer. This method is fast but extra care
should be taken to select the value of m as chances of collisions will increase with a
smaller value of m. For larger value of m, lager hash table has to be maintained which
will result in memory loss.
2. Mid-Square Method: This is a good hash function which works in two steps:
Square the given data value.
The middle digit of the squared number will serve as the index.
This method somewhat reduces the chances of collisions as the probability of getting the
same middle value of each squared data value will be a little bit less.
3. Folding Method: This method works as follows:
Divide the data values into a number of parts, i.e. divide d into d1, d2, d3… dn,
where each part has the same number of digits except the last part which may
have lesser digits than the other parts.
Add the individual parts and the resulting sum value will serve as the index.
The hash function is given by:
H (d) = d1 + d2 + d3…
As already stated, collisions occur when the hash function maps two different data values to the
same location. Obviously, two records can’t be stored in the same location. Therefore, there are
various collision resolution techniques to solve the problem. These techniques are:
Open Addressing
o Linear Probing
o Quadratic Probing
o Clustering
o Double hashing
o Rehashing
Chaining