Hashing and Hash Tables

• Hashing maps data to a fixed-size value, called a hash code or hash value, and is used for fast data access, insertion, and deletion.
• Hashing is the foundation of hash tables, which allows for average-case constant time (O(1)) operations.

Hash Functions

• A hash function takes a key and returns an index in the hash table.
• A good hash function must be deterministic (same input yields the same output), efficient (fast to compute), uniform (distributes keys evenly), and minimizes collisions.

Collisions

• A collision occurs when two different keys hash to the same index.

Collision Resolution Strategies

• Chaining (Separate Chaining): Each bucket stores a linked list of entries and is easy to implement. The table size doesn't limit the number of elements, but can be slower if many items hash to the same index.
• Open Addressing: Finds the next available slot in the table itself.
• Linear Probing: Checks the next index = ((i + k) % tableSize) until a free spot is found.
  • i is the index the key was originally hashed to.
  • k is the number of collisions for that key, which is also the current step number in the probing process.
• Quadratic Probing: Checks the index = (i + c1 * k + c2 * k²) % tableSize until a free spot is found.
  • i is the original index from the hash function.
  • k is the number of collisions for that key, which is also your current step number in the probing process.
  • c1 and c2 are constants (commonly c1 = 0, c2 = 1).
• Double Hashing: Uses a second hash function to determine the step size, index = (i + k * h2(key)) % tableSize.
  • h2 is the second hash function and k is the number of collisions so far.

Load Factor

• Load Factor (a) = number of elements / table size.
• It measures how full the table is; as it approaches 1, collision chances increase.
• Rehashing is common practice when 'a' exceeds a threshold (e.g., 0.7).
  • Rehashing involves creating a new table, typically doubling the original size to the nearest prime number, and re-inserting all elements using the new table and hash function to maintain efficiency.

Picking a Table Size

• Using key % size when the size is not prime can lead to clustering.
  • Clustering: Keys hash to nearby locations, forming large blocks and slowing search, insert, and delete operations.
  • With tableSize = 10, keys like 10, 20, 30 all hash to 0, creating non-uniform distribution.
  • With quadratic probing, non-prime sizes can cause repeated or skipped indices.
• Using a prime number for the table size minimizes modular arithmetic patterns, ensuring a more uniform spread of keys.

Picking a Collision Resolution Strategy

• Chaining (Separate Chaining): Each bucket holds a list of entries, is easy to implement, and handles high load factors but requires extra memory.
• Open Addressing: All entries are stored in the table itself.
  • Linear Probing probes the next slot: (i + k) % tableSize which is simple but causes primary clustering and performance degradation.
  • Quadratic Probing probes using: (i + c1 * k + c2 * k^2) % tableSize which reduces primary clustering and has better spread but has secondary clustering and more complex deletions.
    • Deleting an item in open addressing can break the probe sequence for other keys, leading to incorrect searches.
      • Simply marking a slot as empty can cause searches for later-inserted keys to stop too early.
      • To fix this, deleted slots are marked with a tombstone that indicates the slot was occupied but is now deleted, signaling to continue probing.
      • Tombstones preserve probe sequence integrity but add complexity by distinguishing between empty, tombstone, and occupied slots.
  • Double Hashing probes using a second hash function: (i + k * h2(key)) % tableSize, which minimizes clustering and provides unique probe sequences but requires two good hash functions and is more complex.

Performance

• Chaining has high extra space, low clustering risk, unlimited load factor limit and Easy deletion handling
• Linear Probing has None extra space, High clustering risk, ~0.7 max load factor limit and Tricky (tombstones) deletion handling
• Quadratic Probing has None extra space, Medium clustering risk, ~0.5-0.7 load factor limit and Tricky (tombstones) deletion handling
• Double Hashing has None extra space, Low clustering risk, ~0.7 load factor limit and Tricky (tombstones) deletion handling

Runtime of Hash Map Operations

• Search average/best case: O(1), worst case: O(n)
• Insert average/best case: O(1), worst case: O(n)
• Delete average/best case: O(1), worst case: O(n)
• In ideal scenarios, hash tables provide constant-time operations.

Applications of Hashing

• Dictionaries/Maps (e.g., unordered_map in C++)
• Database indexing
• Caching (e.g., using hash values as keys)
• Symbol tables in compilers
• Password storage (cryptographic hashing)