🧩Intro to Algorithms Unit 6 – Hash Tables and Hash Functions

What Are Hash Tables?

• Data structures that store key-value pairs enabling efficient insertion, deletion, and lookup operations
• Utilize a hash function to compute an index into an array of buckets or slots from which the desired value can be found
• Provide fast average case time complexity for search, insert, and delete operations
• Useful when speed is critical and data needs to be quickly accessed based on a key
• Consist of two main components:
  • Array that holds the data
  • Hash function that maps keys to array indices
• Facilitate the implementation of associative arrays or dictionaries
• Suitable for scenarios involving large amounts of data and frequent key-based operations

Hash Functions Explained

• Algorithm that maps data of arbitrary size to fixed-size values computing an index into the array
• Take a key as input and return an integer representing the index in the array for storing or retrieving the corresponding value
• Aim to distribute the keys evenly across the array to minimize collisions (multiple keys mapping to the same index)
• Deterministic produce the same output for a given input enabling the retrieval of values based on their keys
• Should be efficient to compute and uniformly distribute keys across the array
• Examples of commonly used hash functions:
  • Division method: $hash(key) = key \bmod m$, where $m$ is the size of the array
  • Multiplication method: $hash(key) = \lfloor m(kA \bmod 1) \rfloor$, where $A$ is a constant between 0 and 1
• Choice of hash function depends on the type and distribution of the keys

Key Components of Hash Tables

• Array (also known as the bucket array) stores the key-value pairs
  • Each element in the array is called a bucket or slot
  • Size of the array determines the capacity of the hash table
• Hash function maps keys to array indices
  • Takes a key as input and returns an integer representing the index
  • Crucial for the performance and distribution of key-value pairs
• Collision resolution mechanism handles cases where multiple keys map to the same array index
  • Techniques include chaining (linked lists) and open addressing (probing)
  • Ensures that all key-value pairs can be stored and retrieved correctly
• Key-value pairs the data stored in the hash table
  • Key uniquely identifies an entry
  • Value is the associated data retrieved based on the key
• Load factor ratio of the number of stored elements to the size of the array
  • Indicates how full the hash table is and affects performance
  • Typically kept below a certain threshold (e.g., 0.75) to maintain efficiency

Common Hash Table Operations

• Insertion: Adding a new key-value pair to the hash table
  • Compute the index using the hash function
  • If the index is empty, store the key-value pair
  • If the index is occupied (collision), use the collision resolution technique to find an alternative location
• Search: Retrieving the value associated with a given key
  • Compute the index using the hash function
  • If the key matches the stored key at the computed index, return the corresponding value
  • If the key doesn't match or the index is empty, the key is not found
• Deletion: Removing a key-value pair from the hash table
  • Compute the index using the hash function
  • If the key matches the stored key at the computed index, remove the key-value pair
  • If the key doesn't match or the index is empty, the key is not found
• Resizing: Increasing or decreasing the size of the array when the load factor exceeds a threshold
  • Create a new array with the desired size
  • Rehash all the existing key-value pairs and insert them into the new array
  • Update the reference to the new array
• Iteration: Traversing all the key-value pairs stored in the hash table
  • Iterate over each bucket in the array
  • For each bucket, access the stored key-value pairs
  • Process the key-value pairs as needed

Collision Resolution Techniques

• Chaining: Each array element is a linked list of key-value pairs that hash to the same index
  • Colliding keys are stored in the same linked list
  • Insertion appends the new key-value pair to the linked list
  • Search traverses the linked list to find the matching key
  • Deletion removes the key-value pair from the linked list
  • Allows multiple key-value pairs to be stored at the same index
• Open Addressing: Colliding keys are stored in alternative locations within the array itself
  • Linear Probing: Linearly search for the next empty slot starting from the collided index
    • $index = (hash(key) + i) \bmod m$, where $i$ is the number of attempts
  • Quadratic Probing: Use quadratic function to determine the next slot
    • $index = (hash(key) + c_1i + c_2i^2) \bmod m$, where $c_1$ and $c_2$ are constants
  • Double Hashing: Use a secondary hash function to calculate the step size for probing
    • $index = (hash_1(key) + i \cdot hash_2(key)) \bmod m$
• Comparison:
  • Chaining handles collisions more efficiently and allows for higher load factors
  • Open addressing avoids the overhead of linked lists and may have better cache performance
  • Choice depends on the expected load factor, key distribution, and performance requirements

Time Complexity Analysis

• Average case assumes uniform distribution of keys and depends on the load factor ($\alpha$)
  • Insertion: $O(1)$ on average, $O(n)$ in the worst case
  • Search: $O(1)$ on average, $O(n)$ in the worst case
  • Deletion: $O(1)$ on average, $O(n)$ in the worst case
• Worst case occurs when all keys map to the same index (clustering)
  • Insertion: $O(n)$ due to potential need for resizing and rehashing
  • Search: $O(n)$ as all elements in the same bucket need to be searched
  • Deletion: $O(n)$ as the key needs to be searched and removed from a large cluster
• Factors affecting performance:
  • Load factor ($\alpha$): Ratio of stored elements to the array size
    • Higher load factor leads to increased collisions and slower operations
  • Hash function distribution: Uniform distribution minimizes clustering and improves performance
  • Collision resolution technique: Chaining and open addressing have different trade-offs
• Resizing: $O(n)$ time complexity as all key-value pairs need to be rehashed and inserted into the new array

Real-World Applications

• Database indexing: Hash tables are used to create indexes on columns for fast data retrieval
• Caching: Web browsers and content delivery networks (CDNs) use hash tables for efficient caching of web pages and resources
• Symbol tables: Compilers and interpreters use hash tables to store and look up identifiers, variables, and symbols
• Unique data representation: Hash tables can be used to store unique elements and quickly check for their existence (e.g., tracking visited nodes in graph algorithms)
• Counting frequencies: Hash tables can count the frequency of elements in a dataset (e.g., word count in a document)
• Associative arrays: Programming languages often provide hash table implementations for key-value storage and retrieval (e.g., dictionaries in Python, maps in C++)
• Cryptographic hash functions: Used in digital signatures, password storage, and blockchain technologies to ensure data integrity and security

Pros and Cons of Hash Tables

Pros:

• Fast average case time complexity for search, insertion, and deletion operations: $O(1)$
• Efficient for large datasets and frequent key-based operations
• Flexible and versatile can be used to implement various data structures and algorithms
• Provide constant-time lookups on average, making them suitable for real-time applications
• Enable fast retrieval of values based on unique keys

Cons:

• Worst-case time complexity can be $O(n)$ if all keys map to the same index or the hash function is not well-distributed
• Inefficient for scenarios with many collisions or a high load factor
• Do not maintain any order among the elements stored based on key-value pairs
• Resizing can be costly when the hash table needs to grow or shrink dynamically
• Memory overhead due to the array size and potential for wasted space if the load factor is low
• Not suitable for range queries or sorting as the elements are not stored in a sorted order
• Choosing an appropriate hash function and handling collisions effectively can be challenging