Data Structures and Algorithms
In this project, the objective was to study and implement various hashing algorithms to efficiently store and retrieve data in a hash table. Hashing algorithms are widely used in computer science to provide fast access to data by mapping keys to array indices.
Linear probing is a technique where, if a collision occurs (i.e., two keys hash to the same index), the algorithm searches for the next available slot in the hash table sequentially. Quadratic probing, on the other hand, uses a quadratic function to determine the next available slot for collision resolution.
Linked list hashing handles collisions by creating a linked list at each index of the hash table. If multiple keys hash to the same index, they are stored as nodes in the linked list, providing a chain-like structure for collision resolution.
Cuckoo hashing is a different approach that uses two separate hash functions to compute two different indices for each key. If a collision occurs at one index, the key is "kicked out" to its alternate index. This process continues until either an empty slot is found or a maximum number of "kicks" is reached.
This project taught me different hashing algorithms and their benefits. Understanding pros and cons of each helps choosing one for application. Personally understanding how to avoid clustering was a challenge. I wonder what other hashing algorithms are still undiscovered.
You can browse full analysis here: