Hashing as a Dictionary Implementation - Data Structures and Abstractions with Java - page 545

Notice that λ is zero when the dictionary—and hence the hash table—is empty. The maximum

's
maximum value is 1 when the hash table is full. In that case, each entry in the dictionary uses one
location in the hash table. Notice that the number of locations in the available state does not affect
λ

value of λ depends on the type of collision resolution you use. For open addressing schemes, λ

. For separate chaining, the number of entries in the dictionary can exceed the size of the hash
table, so λ has no maximum value.

Note: The load factor
The load factor

is a measure of the cost of collision resolution. It is the ratio of the number
of entries in the dictionary to the size of the hash table.

λ

λ is never negative. For open address-

ing, λ does not exceed 1. For separate chaining, λ has no maximum value. As you will see,

restricting the size of λ improves the performance of hashing.

Question 1 When λ is 0.5 with open addressing, how many locations in the hash table
contain dictionary entries?

Question 2 With separate chaining, does λ indicate how many buckets in the hash table
are not empty? Explain.

The Cost of Open Addressing
22.3

Recall that all open addressing schemes use one location in the hash table per entry in the diction-
ary. The dictionary operations getValue , remove , and add each require a search of the probe
sequence indicated by both the search key and the collision resolution scheme in effect. Analyzing
the efficiency of these searches is sufficient.
For each open addressing scheme that we considered earlier, we will state the number of com-
parisons necessary to locate a search key in the hash table. We will express these numbers in terms
of the load factor . The derivations of these numbers are messy at best and in some cases difficult,

so we omit them. Interpreting the results, however, is straightforward. Recall that for open address-
ing,

λ

λ ranges from 0, when the table is empty, to 1 when it is full.

22.4

Linear probing. When you use linear probing, more collisions will likely occur as the hash table
fills. After a collision, you search a probe sequence that forms a cluster. If you add a new entry, the
cluster grows in size. So you would expect the probe sequences to grow and, therefore, require lon-
ger search times. In fact, the average number of comparisons needed to search the probe sequence
for a given search key is about

- ½

1
---

1

for an unsuccessful search and

® 1 + ------------------- ¾

2

¯ ¿

( 1 - λ )

- ½

1
---

1

for a successful search

® 1 + ----------------- ¾

( 1 - λ )

¯ ¿