Untitled Quiz

Study Notes

Advanced Data Structure - Hashing

Hashing is a technique used to store and retrieve data.
Hashing uses a hash function to compute an index into an array called a hash table.
Common types of Hashing techniques include:
- Open Addressing
  - Linear Probing
  - Quadratic Probing
  - Double Hashing
- Separate Chaining
Hash function:
- A function that takes a key (input) and returns a hash value (index).
- A crucial element of hashing, dictates data placement in the hash table.
- Typically utilizes the modulo operator (%) to map the key to an index, often with a hash table size (e.g., 8).
Open Addressing:
- If a collision (multiple keys produce the same hash value) occurs, a probing strategy (finding an empty slot) is employed to avoid collisions.
  - Linear Probing
    - Simple.
    - Probe consecutive slots from the original hash value until an empty slot.
    - Can encounter clustering problems (consecutive occupied slots making searching inefficient). -Quadratic Probing
    - Employs a quadratic function to calculate the next slot for probing.
    - Less prone to clustering than Linear Probing.
  - Double Hashing
    - A collision resolution method that involves both a primary hash function and a secondary hash function
    - More complex.
    - Produces relatively even distribution within the hash table when correctly designed, making collision resolution more robust.
Separate Chaining:
- Handles collisions by storing the elements that hash to the same index in a linked list.
- A collision does not cause re-probing.
- Each slot in the hash table functions as a head of the linked list when there is more than one element with the same hash value.
- Typically easier to implement and maintain than open addressing.
Example values:
- Example input: 26, 30, 70, 45, 13
- Example hash table size: 8
- Example probing sequence for 70: 6,5,4...
Key takeaway: Different probing techniques in open addressing and separation chaining determine handling methods for hash collisions.