There are two methods of creating multiple storage locations for the same address in the hash table. One solution involves a matrix, while the other uses dynamic linked lists.

To implement the hash table as a matrix, an estimate of the maximum number of collisions at any one address must be made. The second dimension is sized accordingly. Suppose that number is estimated as 5:

Item[][] table = new Item[15000][5];

This method has some major drawbacks. The size of this data structure has suddenly increased by a factor of five. The above table will have 75,000 cells, many of which will be empty. Also, what happens if a location must deal with more than 5 collisions?

A dynamic solution, referred to as chaining, is much better. The linked lists will only grow when values are stored in that location in the hash table. In this version, the hash table will be an array of object references.

ListNode[] hashTable = new ListNode[MAX];

The order of the values in the linked lists is unimportant. If the hashing scheme is a good one, the number of collisions will be minimal.