Chaining vs. Open Addressing

Once there is a collision, instead of probing for an open (unoccupied) position, you traverse the auxiliary data structure referenced by the table element at index = key.hashCode() % M. Once you have determined that an item is not present, you can insert it in the auxiliary data structure.

To delete an item, you simply remove it from the auxiliary data structure. In contrast to open addressing, removing an item actually deletes it, so it will not be part of future search chains.

Another contrast to open addressing is that during search, only items that have the same value for key.hashCode() % M will be examined. In open addressing, search chains can overlap, so a search chain may include items in the table that have different starting index values.

With chaining, you can store more elements in the table than its capacity allows (which is not the case for open addressing). This eliminates the need for rehashing. On the other hand, it can result in load factors $\alpha > 1$ which means higher chances of collisions.