Hash Table for Customer Details

Untitled

Linear Probe Resolution Method :

Quadratic Probing

Quadratic probing is an open-addressing scheme where we look for the i2‘th slot in the i’th iteration if the given hash value x collides in the hash table.

Features

Pseudo code

  1. Generate a hash key for a entry
  2. If the place pointed by hash key is empty, Insert a data at that position
  3. Else, Loop until we get a empty position
  4. If, there is no empty location print hash table full
  1. Generate a hash key for given key
  2. If the location pointed by hash key is empty, return -1
  3. If that location contains desired key, return position
  4. else, loop until we get desired key
  5. If the key is not found return -1
  1. Loop(until last position)
  2. If the position contains data, print data
  3. else, print no hash entry
  4. end loop

Time complexity

Advantages :

Disadvantages :

Chaining

In hashing there is a hash function that maps keys to some values. But these hashing function may lead to collision that is two or more keys are mapped to same value. Chain hashing avoids collision. The idea is to make each cell of hash table point to a linked list of records that have same hash function value.

Let’s create a hash function, such that our hash table has ‘N’ number of buckets.

To insert a node into the hash table, we need to find the hash index for the given key. And it could be calculated using the hash function.

Example: hash Index = key % noOfBucketsInsert: Move to the bucket corresponds to the above calculated hash index and insert the new node at the end of the list. Delete: To delete a node from hash table, calculate the hash index for the key, move to the bucket corresponds to the calculated hash index, search the list in the current bucket to find and remove the node with the given key (if found).

Untitled

Time Complexity:

Auxiliary Space: O(1), since no extra space has been taken.

Chaining in Hashing with Linked List (Extra)

Chaining in hashing is a technique used to resolve collisions in hash tables. It involves creating a linked list for each bucket in the hash table, and inserting elements into the linked list if a collision occurs. This technique can be used to store and access data efficiently, as it reduces the number of collisions and improves the performance of hash tables.

Advantages

Chaining in hashing has several advantages, including:

Disadvantages

Chaining in hashing also has some disadvantages, including:

Double Hashing

Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing uses the idea of applying a second hash function to key when a collision occurs.

Double hashing can be done using : (hash1(key) + i * hash2(key)) % TABLE_SIZE Here hash1() and hash2() are hash functions and TABLE_SIZE is size of hash table. (We repeat by increasing i when collision occurs)

First hash function is typically hash1(key) = key % TABLE_SIZEA popular second hash function is : hash2(key) = PRIME – (key % PRIME) where PRIME is a prime smaller than the TABLE_SIZE.A good second Hash function is:

Untitled

Advantages of Double hashing

Conclusion (when to use where)

In general, you should use probing when the number of collisions is expected to be low and when the keys are evenly distributed throughout the hash table. You should use separate chaining when the number of collisions is expected to be high or when the keys are not evenly distributed. It is also worth noting that other collision resolution methods, such as open addressing, exist and may be more suitable for certain applications.

Applications Of Hash Tables