Open Hashing Methods Comparison

A comparison between Linear Probing, Quadratic Probing and Double Hashing.

Hashing is a technique used for storing and retrieving information quickly. It is used to perform optimal searches. It is done for faster access to elements. The efficiency of mapping depends on the efficiency of the hash function used.

Hash functions are used to map each key to a different address space, but practically it is not possible to create such a hash function and the problem is called collision.

Collision is the condition where two records are stored in the same location. or we can say that it is a situation that occurs when two distinct pieces of data have the same hash value

The process of finding an alternate location is called collision resolution. Even though hash tables have collision problems, they are more efficient in many cases compared to all other data structures, like search trees. There are a number of collision resolution techniques, and the most popular are direct chaining and open addressing.

1. Direct Chaining- An array of linked list application.

• Separate Chaining — Collision resolution by chaining combines linked representation with hash table. When two or more records hash to the same location, the records are constituted into a list called chain.

2. Open Addressing- Array-based implementation. In open addressing all keys are stored in the hash table itself. This approach is also known as closed hashing. This procedure is based on probing. A collision is resolved by probing.

• Linear Probing (linear search).
• Quadratic Probing (nonlinear search).
• Double Hashing (use two hash functions).

Comparison between different Open Addressing Methods:

Linear Probing : In linear probing, we search the hash table sequentially, starting from the original hash location. If a location is occupied, we check the next location. The function for rehashing is the following:

rehash(key) = (n + 1)% tablesize

Quadratic Probing : In quadratic probing, we start from the original hash location i. If a location is occupied, we check the locations (i + 12), (i +22 ), (i + 32), (i + 42).

The function for rehashing is the following:

rehash(key) = (n + k2)% tablesize

Double Hashing : It is a computer programming technique used in conjunction with open-addressing in hash tables to resolve hash collisions. In double hashing, the interval between probes is computed by another hash function. Double hashing reduces clustering in a better way than linear and quadric probing.

Overview (Comparison Chart)-