Introduction to Hashing
Hashing is the process of converting an input item (key) into a fixed-size value, typically an integer index, using a hash function. This index is then used to place or locate the item in a data structure, most commonly a hash table (hash map or dictionary).
Key Concepts
- Hash Function: A function that maps keys to indices. A good hash function should be fast to compute and distribute keys uniformly across the available indices.
- Hash Table: A data structure that uses a hash function to map keys to values for efficient lookups.
- Collisions: Occur when two different keys map to the same index.
- Collision Resolution: Strategies to handle collisions, such as: * Separate Chaining: Each index points to a linked list (or other structure) containing all keys that hash to that index. * Open Addressing (Probing): If an index is occupied, probe for the next available slot (linear probing, quadratic probing, double hashing).
Common Operations & Complexity (Average Case for Hash Tables)
- Insertion: O(1)
- Deletion: O(1)
- Search: O(1)
- (Worst Case for all can be O(n) if collisions are poorly handled or hash function is bad)
Use Cases
- Implementing dictionaries/hash maps.
- Database indexing.
- Caching.
- Checking for duplicates.