Hashing Techniques in Data Structures

Open Addressing, Closed Hashing

• Linear Probing: Used in closed hashing. Calculates the next hash index by incrementing the original index.
• Collision Handling: If a key's hash index is already occupied, the next available slot along the index array is used.
• Example: For a hash table size of 10, if key 38 maps to index 8 and it's taken, probing moves to index 9, and so on.
• Collision Formula: (key + i) % length, where 'i' is the probe number. This formula shows how to calculate a new index when collision occurs.

Quadratic Probing

• Collision Resolution: Calculates the next hash index by incrementing the original index. If occupied, it tries the next index using a quadratic formula instead of a linear one.
• Formula: (key + i * i) % size of table.
• Example Application: Handles collisions more efficiently in hash tables compared to linear probing.

Double Hashing

• Collision Resolution: Uses a secondary hash function to calculate the step size between collision probes.
• Formula: h(key) = key % tableSize, g(key) = 1 + [(key/tableSize) % (tableSize - 1)]
• Key Functions: It uses two independent hashing functions: one calculates the initial index and one determines the step size for probing.
• Example Usage: Handles collisions by using sequences determined by a step size formula.

General Hashing

• Hash Function: Computes an index from a key.
• Hash Table: A data structure used to store data efficiently.
• Collision: The situation when multiple keys generate the same index in a hash table.
• Load Factor: The ratio of the number of keys in a hash table to the size of the table (number of slots).
• Types: Closed and open addressing.
• Possible Order Keys: Can check if an order of keys in a hash table is feasible after insertion.
• Hash Types: Linear, Quadratic, Double Hashing (techniques for managing collisions in a hash table).