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

num ext

1
2
3
4
5
6
7
8
9
10
11

37 6

hash table

24 -1

8
9
10
11
12
13
14
15
-1

overflow table

12
13
14
15

Figure 10-3. After adding 24 to the overflow table

Now, consider how an item may be deleted. There are two cases to consider:

k , say), we can delete it with this:

• If the item to be deleted is in the hash table (at

if (hash[k].next == -1) set hash[k].num to Empty //only item in the list
else { //copy an item from the overflow table to the hash table
h = hash[k].next;
hash[k] = hash[h]; //copy information at location h to location k
return h to the free list //see next
}

h , say) to the free list with this: • We can return a location (

hash[h].next = free;
free = h;

curr , say) and prev is the location of the
item that points to the one to be deleted, we can delete it with this:

• If the item to be deleted is in the overflow table (at

hash[prev].next = hash[curr].next;
return curr to the free list

Now consider how an incoming key might be processed. Suppose free is 9 and the number 52 hashes to location
2 . We search the list starting at 2 for 52 . It is not found, so 52 is stored in the next free location, 9 . Location 6 contains
the last item in the list, so hash[6].next is set to 9 , and hash[9].next is set to -1 .