Answer:
Linear probing and quadratic probing are collision resolution techniques used in hash tables to handle collisions that may arise when multiple keys are being mapped to the same location in the hash table.
Linear probing involves searching for the next available slot in the hash table, starting from the current slot where collision occurred, in a sequential manner until an empty slot is found. This means that keys that collide will be placed in the next available slot, which may or may not be close to the original slot, leading to clusters of data in the hash table. Linear probing has a relatively simple implementation and requires less memory usage compared to other collision resolution techniques, but it can also lead to slower search times due to clusters of data that may form, causing longer search times.
Quadratic probing, on the other hand, involves searching for the next available slot in the hash table by using a quadratic equation to calculate the offset from the current slot where the collision occurred. This means that keys that collide will be placed in slots that are further apart compared to linear probing, resulting in less clustering of data in the hash table. Quadratic probing can lead to faster search times but has a more complex implementation and requires more memory usage compared to linear probing.
One example of linear probing is when adding keys to a hash table with a size of 10:
Key 18 maps to index 8. Since this slot is empty, key 18 is inserted in index 8.
Key 22 maps to index 2. Since this slot is empty, key 22 is inserted in index 2.
Key 30 maps to index 0. Since this slot is empty, key 30 is inserted in index 0.
Key 32 maps to index 2. Since this slot is already occupied, we search for the next available slot starting from index 3. Since index 3 is empty, key 32 is inserted in index 3.
Key 35 maps to index 5. Since this slot is empty, key 35 is inserted in index 5.
One example of quadratic probing is when adding keys to a hash table with a size of 10:
Key 18 maps to index 8. Since this slot is empty, key 18 is inserted in index 8.
Key 22 maps to index 2. Since this slot is empty, key 22 is inserted in index 2.
Key 30 maps to index 0. Since this slot is empty, key 30 is inserted in index 0.
Step-by-step explanation: