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

num ext

1
2
3
4
5
6
7
8
9
10
11

hash table

7
8
9
10
11
12
13
14
15
-1

overflow table

12
13
14
15

Figure 10-2. Link items in overflow table to form “free list”

Suppose 37 hashes to location 2 . This is empty, so 37 is stored in hash[2].num . If another number ( 24 , say)
hashes to 2 , it must be stored in the overflow table. First we must get a location from the “free list.” This can be done
with the following:

f = free;
free = hash[free].next;
return f;

Here, 6 is returned, and free is set to 7 . The number 24 is stored in location 6 , and hash[2].next is set to 6 . At this
stage, we have free = 7 , with the tables having the values shown in Figure 10-3 .