Hashing Questions
The different types of open addressing in hashing are:
1. Linear Probing: In linear probing, if a collision occurs, the next available slot in the hash table is searched sequentially until an empty slot is found.
2. Quadratic Probing: In quadratic probing, if a collision occurs, the next slot to be checked is determined by adding a quadratic function of the form f(i) = i^2 to the original hash value.
3. Double Hashing: In double hashing, if a collision occurs, a second hash function is used to determine the next slot to be checked. The second hash function is typically of the form f(i) = i * hash2(key), where hash2(key) is another hash function.
4. Cuckoo Hashing: In cuckoo hashing, multiple hash functions are used to determine multiple possible slots for a key. If a collision occurs, the key is moved to one of its alternative slots, displacing the existing key. This process continues until all keys are placed without any further collisions.
5. Robin Hood Hashing: In Robin Hood hashing, keys are stored in a hash table, and if a collision occurs, the key with the smallest probe distance (the number of slots it is away from its ideal position) is moved closer to its ideal position, displacing the existing key. This process continues until all keys are placed without any further collisions.