Java Reference
In-Depth Information
Note:
The size of a hash table should be a prime number
n
greater than 2. Then, if you
compress a positive hash code
c
into an index for the table by using
c
%
n
, the indices will be
distributed uniformly between 0 and
n
-
1.
One final detail remains. You saw earlier that the method
hashCode
might return a negative
integer, so you need to be a bit careful. If
c
is negative,
c
n
lies between 1
−
n
and 0. A zero
result is fine, but if
c
%
n
is negative, add
n
to it so that it lies between 1 and
n
−
1.
%
21.11
We now can implement a hash function for the ADT dictionary. The following method computes
the hash index for a given search key whose data type is the generic object type
K
. The data field
hashTable
is the array that serves as the hash table. Realize that
hashTable.length
is the size of
the array, not the number of current entries in the hash table. We assume that this size is a prime
number and that the method
hashCode
returns a hash code consistent with the previous discussion.
private int
getHashIndex(K key)
{
int
hashIndex = key.hashCode() % hashTable.length;
if
(hashIndex < 0)
hashIndex = hashIndex + hashTable.length;
return
hashIndex;
}
// end getHashIndex
Question 2
Question 1 in Segment 21.8 asked you to compute the hash code for the string
Java
. Use that value to calculate what
getHashIndex(
"
Java
"
)
returns when the length of the
hash table is 101.
Question 3
What one-character string, when passed to
getHashIndex
, will cause the
method to return the same value as in the previous question?
21.12
When adding to a dictionary, if your hash function maps a search key into a location in the hash
table that is already in use, you need to find another spot for the search key's value. You have two
fundamental choices:
•
Use another location in the hash table
•
Change the structure of the hash table so that each array location can represent more than
one value
Finding an unused, or open, location in the hash table is called
open addressing
. This choice
sounds simple, but it can lead to several complications. Changing the structure of the hash table
is not as difficult as it might sound and can be a better choice for resolving collisions than using
an open addressing scheme. We will examine both approaches, beginning with several variations
of open addressing.
VideoNote
Resolving collisions
When a collision occurs during the addition of an entry to a hash table, an open addressing scheme
locates an alternate location in the hash table that is available, or open. You then use this location to
reference the new entry.
