The perfect place for easy learning...

Data Structures

×

Topics List

Place your ad here

Static Hashing

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

Hashing is an another approach in which time required to search an element doesn't depends on the total number of elements. Using hashing data structure, a given 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 hash key.

Here, hash key is a value which provides the index value where the actual data is likely to be stored 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 hash key value generated using 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 are performed with constant time complexity (i.e. O(1)).

Hash tables are used to perform insertion, deletion and search operations very quickly in a datastructure. Using hash table concept, insertion, deletion and search operations are accomplished in constant time complexity. Generally, every hash table makes use of a function called 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 produces an integer (i.e. hash value) as output 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...

Static Hashing

Place your ad here
Place your ad here