Static Hashing


In all search techniques like linear search, binary search and search trees, the time required to search an element is depends on the total number of element in that data structure. In all these search techniquies, as the number of element are increased the time required to search an element also increased linearly.

Hashing is another approach in which time required to search an element doesn't depend on the number of element. Using hashing data structure, an element is searched with constant time complexity. Hashing is an effective way to reduce the number of comparisions to seach an element in a data structure.

Hashing is defined as follows...

Hashing is the process of indexing and retrieving element (data) in a datastructure to provide faster way of finding the element using the hash key.

Here, hash key is a value which provides the index value where tha actual data is likely to store in the datastructure.

In this datastructure, we use a concept called Hash table to store data. All the data values are inserted into the hash table based on the hash key value. Hash key value is used to map the data with index in the hash table. And the hash key is generated for every data using a hash function. That means every entry in the hash table is based on the key value generated using a hash function.

Hash Table is defined as follows...

Hash table is just an array which maps a key (data) into the datastructure with the help of hash function such that insertion, deletion and search operations can be performed with constant time complexity (i.e. O(1)).

Hash tables are used to perform the operations like insertion, deletion and search very quickly in a datastructure. Using hash table concept insertion, deletion and search operations are accoplished in constant time. Generally, every hash table make use of a function, which we'll call the hash function to map the data into the hash table.

A hash function is defined as follows...

Hash function is a function which takes a piece of data (i.e. key) as input and outputs an integer (i.e. hash value) which maps the data to a particular index in the hash table.

Basic concept of hashing and hash table is shown in the following figure...