Introduction and applications of Hashing

Hashing
In linear and binary search, we need to perform several operations to find a particular target data. Operations are done with search, index calculation, target comparison with the data on that index and modifying the index in case the target is not found. Ideally, we expect to find the target in lesser steps. There is a way to achieve this we should get the address where the data is stored. Hashing is the technique of finding the address where the data is located with the help of a key and by the use of mathematical function called hash function.

Components of hashing
Hashing has four major components:
1. Hash Table
2. Hash Functions
3. Collisions
4. Collision Resolution Techniques

Hash Table
A hash table is a data structure that stores and uses keys, their associated values. It uses Hash function for mapping keys with their respective values. It is an array [0 to n-1] of size n. Insertion, deletion and search operations in hashing can be performed with constant time complexity (i.e. O(1)). The problem with direct addressing is that if the universe U is large, then the table T to store Size |U| is not possible considering the limited memory available on the computer. One way in this case is to use a hash table. With direct addressing, an element with the key k is stored in slot k. With hashing, this element will be stored in in the slot h(k) i.e. we use hash function h to map their respective key values.

Hash Function
The hash function is used to map the key to the index of the hash table. Given a set of elements, a hash function that maps each item to a unique slot is known as an ideal hash function. Given a set of elements, unfortunately there is no systematic way to construct an exhaustive hash function. Our goal is to create a hash function that minimizes numbers. of collisions, which is easy to calculate, and evenly distributes the elements in the hash table.

Collison
In hashing techniques, collison is a condition when the hash value of two keys becomes the same. Suppose we want to add a new Record with key k in a hashtable, but index address H(k) is already occupied by another record. This situation is known as a collision.

Conflict resolution techniques
The process of finding alternate locations is known as collision resolution.
There are several methods of collision resolution:

• Direct Chain: Linked List Implementation
• Different Chains
• Open Addressing: Array-Based Implementation
• Linear Probe (Linear Search)
• Quadratic Detection (Non-Linear Search)
• Double hashing (use two hash functions)

Hashing applications

• Hash tables are used by the compiler to keep track of the variables declared in the source code. The data structure is known as symbol table.
• Another application is game programs. As the program look through different lines of play, it monitors positions that it has experienced by computing a hash function on the basis of position
• Hashing is also used in online spelling checkers.