Hashing - Advanced Topics in Java: Core Concepts in Data Structures - page 293

num ext

1
2
3
4
5
6
7
8
9
10
11

hash table

overflow table

12
13
14
15

Figure 10-1. Array implementation of chaining

Here, hash[1..5] is the hash table, and hash[6..15] is the overflow table.
Suppose key hashes to location k in the hash table:

hash[k].num is empty ( 0 , say), we set it to key and set hash[k].next to −1 , say, to indicate a
null pointer.

• If

hash[k].num is not 0 , we must search the list starting at k for key . If it is not found, we put it
in the next free location ( f , say) in the overflow table and link it to the list starting at hash[k] .
One way to link it is as follows:

• If

hash[f].next = hash[k].next;
hash[k].next = f;

L is the location of the last • Another way to link the new key is to add it at the end of the list. If

node in the list, this could be done with the following:

hash[L].next = f;
hash[f].next = -1; //this is now the last node

If we have to cater for deletions, we will have to decide what to do with deleted locations. One possibility is to
keep a list of all available locations in the overflow table. When one is needed to store a key, it is retrieved from the list.
When an item is deleted, its location is returned to the list.
Initially, we can link all the items in the overflow table as shown in Figure 10-2 and let the variable free point to
the first item in the list; here, free = 6. Item 6 points to item 7, which points to item 8, and so on, with item 15 at the
end of the list.