Database Reference
In-Depth Information
The technique has two main disadvantages:
Additional space is required for the linked lists. However, since
linked lists are dynamic structures, this is not significant.
Linked lists cannot be accessed randomly; they are sequential
access structures.
A2.3.3 Rehashing
Rehashing is another open addressing strategy that significantly reduces clustering. The
technique involves the application of a second hash function to resolve any collision that
might have occurred from the first hash function. In principle, rehashing can continue to
other levels until collision is resolved. However, in practice, if you have to hash more than
twice to resolve collision, you probably need to change your hash function(s).
The main advantage of rehashing is that it tends to produce an even spread of key
values over the address space. One significant disadvantage is that records may be moved
some distance from their home address, thus violating the locality principle.
A2.4 Hashing in Java
You can develop and implement hash functions in just about any programming language.
However, as usual, Java provides you with some nice features that facilitate this. In
particular, there are three Java classes that you should be familiar with — the Hashtable,
HashMap, and the TreeMap classes. These classes reside in the java.util package.
The Hashtable class implements a hash-table that maps keys to values. A key can
be any valid object. Each instance of Hashtable class has two properties that affect its
performance: the initial capacity and load factor . The capacity is the number of buckets
in the hash table, and the initial capacity is simply the capacity at the time the hash table
is created. A bucket is simply a holding area for key values that have the same address
(similar to a chain); the bucket is searched sequentially. The load factor is a measure of
how full the hash table is allowed to get before its capacity is automatically increased. The
conventional wisdom is 0.75. Figure A2-8 provides the UML diagrams for the class.
 
Search WWH ::




Custom Search