How is collision resolved in hashing?

Collision in hashing is resolved through various methods, including:

1. Separate Chaining: In this method, each bucket in the hash table contains a linked list. When a collision occurs, the collided elements are stored in the same bucket as a linked list.

2. Open Addressing: In this method, when a collision occurs, the hash function is re-evaluated with a different algorithm to find the next available empty slot in the hash table. This process continues until an empty slot is found.

- Linear Probing: In linear probing, the next available slot is searched sequentially until an empty slot is found.
- Quadratic Probing: In quadratic probing, the next available slot is searched using a quadratic function until an empty slot is found.
- Double Hashing: In double hashing, a second hash function is used to calculate the step size for searching the next available slot.

3. Robin Hood Hashing: This method aims to minimize the variance in the lengths of the linked lists by swapping elements between buckets to achieve a more balanced distribution.

4. Cuckoo Hashing: In cuckoo hashing, multiple hash functions are used, and if a collision occurs, the element is moved to the alternate hash location. This process continues until a cycle is detected or a maximum number of rehashing attempts is reached.

These methods help to efficiently handle collisions and ensure that the hash table can store and retrieve elements effectively.