HASHING - Introduction to Java Programming: Comprehensive Version - page 993

27.12

What is secondary clustering?

27.13

Show the hash table of size 11 after inserting entries with keys 34, 29, 53, 44, 120,
39, 45, and 40, using linear probing.

27.14

Show the hash table of size 11 after inserting entries with keys 34, 29, 53, 44, 120,
39, 45, and 40, using quadratic probing.

27.15

Show the hash table of size 11 after inserting entries with keys 34, 29, 53, 44, 120,
39, 45, and 40, using double hashing with the following functions:

h(k) = k % 11 ;
h'(k) = 7 - k % 7 ;

27.5 Handling Collisions Using Separate Chaining
The separate chaining scheme places all entries with the same hash index in the same
location, rather than finding new locations. Each location in the separate chaining
scheme uses a bucket to hold multiple entries.

Key
Point
separate chaining
implementing bucket

You can implement a bucket using an array, ArrayList , or LinkedList . We will use
LinkedList for demonstration. You can view each cell in the hash table as the reference to
the head of a linked list, and elements in the linked list are chained starting from the head, as
shown in Figure 27.7.

For simplicity, only the keys are
shown, and not the values. Here
N is 11 and index = key % N.

0
1
2
3
4
5
6

key: 44

New element with
key 26 to be inserted

key: 4
key: 16

key: 26

.

key: 28

.
.

7
8

9
10

key: 21

F IGURE 27.7

Separate chaining scheme chains the entries with the same hash index in a

bucket.

27.16

✓ ✓

Show the hash table of size 11 after inserting entries with the keys 34, 29, 53, 44,
120, 39, 45, and 40, using separate chaining.

Check

Point

27.6 Load Factor and Rehashing
The load factor measures how full a hash table is. If the load factor is exceeded,
increase the hash-table size and reload the entries into a new larger hash table. This
is called rehashing.

Key
Point
rehashing
load factor Load factor l ( lambda ) measures how full a hash table is. It is the ratio of the number of

elements to the size of the hash table, that is, l =

n
N , where n denotes the number of elements

and N the number of locations in the hash table.
Note that l is zero if the hash table is empty. For the open addressing scheme, l is between
0 and 1 ; l is 1 if the hash table is full. For the separate chaining scheme, l can be any value.