An Example of Hash Coding

Suppose you are creating a list of objects sequentially and you need to avoid listing duplicates. One possible way to do this is simply to check the list created so far to make sure the currrently tested item has not appeared previously. However, for a list of N items, this would require N(N −1)/2 operations. We can avoid the large cost by using hash coding:

0. Decide on a way to associate a label with each item whose prior presence on the list can be easily checked (i.e., by O(1) operations regardless of the length of the list).

1. Put the first item on the list and mark its label to be on the list.

(At this point, only 1 item is associated with the particular label; so it is easy to put the reverse identification of label ⟹ the item.)

2. Pick the next item and test if its label is already on the list. You do this by looking up item(s) associated with the same label and examining it (them) only (not the whole list).

(If there are multiple items with the same label, you can set up an auxiliary pointer tree which starts from the item most recently associated with the label and points in a chainlike manner toward the oldest such item.)

• If yes, discard the item and repeat 2.

• If no, put the item on the list and mark its label to be on the list. Then repeat 2.

(Either set up the reverse identification label ⟹ to the item if there is only one item with this label, or continue with the pointer tree if there are now more than one such item.)

3. Stop when an appropriate stopping criterion is satisfied (a predetermined size of the list or no more items left due to the item creation/search algorithm in most cases).