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

an integer value called a hash code , then compresses the hash code into an index to the
hash table .

4.

A collision occurs when two keys are mapped to the same index in a hash table. Gener-
ally, there are two ways for handling collisions: open addressing and separate chaining .

5.

Open addressing is the process of finding an open location in the hash table in the event
of collision. Open addressing has several variations: linear probing , quadratic probing ,
and double hashing .

6.

The separate chaining scheme places all entries with the same hash index into the
same location, rather than finding new locations. Each location in the separate chaining
scheme is called a bucket . A bucket is a container that holds multiple entries.

Q UIZ

Answer the quiz for this chapter online at www.cs.armstrong.edu/liang/intro10e/quiz.html .

P ROGRAMMING E XERCISES
**27.1

( Implement MyMap using open addressing with linear probing ) Create a new con-
crete class that implements MyMap using open addressing with linear probing.
For simplicity, use f(key) = key % size as the hash function, where size is
the hash-table size. Initially, the hash-table size is 4 . The table size is doubled
whenever the load factor exceeds the threshold ( 0.5 ).

**27.2

( Implement MyMap using open addressing with quadratic probing ) Create a new
concrete class that implements MyMap using open addressing with quadratic
probing. For simplicity, use f(key) = key % size as the hash function, where
size is the hash-table size. Initially, the hash-table size is 4 . The table size is
doubled whenever the load factor exceeds the threshold ( 0.5 ).

**27.3

( Implement MyMap using open addressing with double hashing ) Create a new
concrete class that implements MyMap using open addressing with double hash-
ing. For simplicity, use f(key) = key % size as the hash function, where
size is the hash-table size. Initially, the hash-table size is 4 . The table size is
doubled whenever the load factor exceeds the threshold ( 0.5 ).

**27.4

( Modify MyHashMap with duplicate keys ) Modify MyHashMap to allow dupli-
cate keys for entries. You need to modify the implementation for the put(key,
value) method. Also add a new method named getAll(key) that returns a set
of values that match the key in the map.

**27.5

( Implement MyHashSet using MyHashMap ) Implement MyHashSet using
MyHashMap . Note that you can create entries with ( key, key ), rather than ( key,
value ).

**27.6

( Animate linear probing ) Write a program that animates linear probing, as shown
in Figure 27.3. You can change the initial size of the hash-table in the program.
Assume the load-factor threshold is 0.75 .

**27.7

( Animate separate chaining ) Write a program that animates MyHashMap , as
shown in Figure 27.8. You can change the initial size of the table. Assume the
load-factor threshold is 0.75 .