24 Data Structures and Algorithms using Java State the diffe

24. Data Structures and Algorithms using Java*

State the difference between an open addressing and a non-open addressing collision algorithm.

Solution

Open Addressing

Non-open addressing

If the location where the has key is pointing is already occupied then different probing techniques are applied to search for empty cells.

Instead of seeking for empty cells, if the location is not free, then a linked list is added to that position and items are placed in that list at the given index.

Since different techniques are used to find an empty cell, the collision resolution is bit more complex than non-open addressing.

When collision occurs, a linked list is added to that place if it not already there, otherwise item is added to that linked list.

Unlike non-open addressing, no extra data structures are needed thus, it has less space complexity

Space complexity is more than open addressing.

Same hashing key is not allowed for different values.

Same hashing key for different items are allowed since in a linked list, multiple items can be added.

Finding a value using a hash key maps to a location in a cluster, if the value is not at that location it continues to next cells. If it finds an empty cell, that means the cluster has completed and search is unsuccessful.

Finding a value using a hash key maps to a linked list in which the item is searched.

When a key is deleted, it leaves an empty cell. After that the location is filled with special key otherwise it creates problem in Find operation since empty cells indicates the end of a cluster.

In delete operation, the value is deleted from the list. No other task is needed. So it is much easier than open addressing.