Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Separate Chaining

Figure gif shows a hash table that uses separate chaining  to resolve collisions. The hash table is implemented as an array of linked lists. To insert an item into the table, it is appended to one of the linked lists. The linked list to it is appended is determined by hashing that item.

   figure10945
Figure: Hash table using separate chaining.

Figure gif illustrates an example in which there are M=16 linked lists. The twelve character strings "ett"-"tolv" have been inserted into the table using the hashed values and in the order given in Table gif. Notice that in this example since M=16, the linked list is selected by the least significant four bits of the hashed value given in Table gif. In effect, it is only the last letter of a string which determines the linked list in which that string appears.




next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.