In open addressing, how are collisions typically resolved?

Correct option is A

Open addressing is a collision-resolution technique used in hash tables in which all elements are stored directly within the hash table itself. When two or more keys produce the same hash index, a collision occurs.
Instead of creating an external linked list or separate storage, open addressing resolves the collision by probing other positions in the same hash table until an available slot is found.
For example, suppose the hash function gives:
h(k) = 3
for two different keys. If position 3 is already occupied, the algorithm searches for another available position according to a probing strategy.
Common probing techniques include:
1. Linear Probing
​$$h_i(k)=(h(k)+i)\bmod m$$​​
2. Quadratic Probing
​$$h_i(k)=(h(k)+i^2)\bmod m$$​​
3. Double Hashing
​$$h_i(k)=(h_1(k)+i\cdot h_2(k))\bmod m$$​​
Thus, collisions are resolved by probing for an available slot within the hash table.
Information Booster
1. Open addressing: Every key is stored directly in the hash table.
2. Collision: Occurs when two different keys map to the same hash-table index.
3. Linear probing: Checks consecutive slots until an empty slot is found.
4. Quadratic probing: Uses quadratic increments to determine the next position.
5. Double hashing: Uses a second hash function to calculate the probing step.
Additional Knowledge
Why the Other Options Are Incorrect?
· (b) Creating a linked list → This is the approach used in separate chaining, not open addressing.
· (c) Rehashing the entire table → Rehashing may be performed when the table becomes too full, but it is not the standard collision-resolution mechanism of open addressing.
· (d) Separate array → Open addressing stores the colliding element within the same hash table, rather than using a separate array.
The key distinction to remember is:
​$$\boxed{\text{Open Addressing} \rightarrow \text{Probing}}$$​​
whereas:
​$$\boxed{\text{Separate Chaining} \rightarrow \text{Linked List/Bucket}}$$​​