Hashing Techniques in Data Structures

Hashing Technique

• Hashing in data structures maps data items to specific locations (buckets) in a hash table.
• This enables efficient data storage and retrieval.
• Hashing is a well-known technique for searching elements within a set of data.
• It's highly efficient for storing, retrieving, and handling data by converting keys into specific locations.

Hash Tables

• A hash table uses an array data structure for storing data items.
• The hash function calculates a unique integer value (hash value) from a data item or key.
• This hash value corresponds to an index in the hash table where the data is stored..
• Data items are inserted into the hash table based on their hash values.

Hash Value

• A hash key value is a special value used as an index for a data item.
• It determines where a data item should be stored in the hash table.
• The hash key value is generated using a hash function.

Hash Function

• The hash function converts a range of key values into a range of indexes.
• It's crucial for the efficiency of hashing by distributing data evenly throughout the hash table.
• A good hash function minimizes collisions (when two keys produce the same hash value).
• It's essential that hash function's mathematical or bitwise operations are efficient to compute.

Hash Table

• A hash table (or hash map) is a data structure that holds key-value pairs for easy access later.
• It's a collection of items enabling fast retrieval of data stored based on keys.

Collision Resolution Techniques

• Collisions occur when two keys produce the same hash value.
• Techniques handle collisions:
  • Linear Probing: Finds the next available slot sequentially.
  • Quadratic Probing: Uses a quadratic function to find slots reduce clustering.
  • Double Hashing: Uses a second hash function to calculate the next probing step.
  • Chaining: Stores elements that hash to the same index in a linked list.

Open Addressing

• In open addressing, if a collision occurs, the hash table tries alternative slots until an empty slot is found.

Quadratic Probing

• If a slot calculated by a hash function is full, quadratic probing tries the next slot based on a quadratic equation until a free slot is found.

Separate Chaining

• Separate chaining manages collisions by storing elements with the same hash index in a linked list at that index.

Load Factor

• The load factor (á) represents the utilization of the hash table.
• It's calculated by dividing the number of occupied table elements by the table size.
• Ideally, the load factor should be below a certain threshold (e.g., 0.75) to maintain good performance and avoid severe collisions, especially in open addressing methods.

Rehashing

• Rehashing involves increasing the table size when it becomes too full.
• This improves efficiency by distributing data more evenly to minimize collisions and improve search and insertion times in the hash table.