For Strings, Hashtables work pretty much as you would expect if you are
familiar with hashing. The only catch is remembering to import java.util.Hashtable
(with a small t in table). Here is how you use a Hashtable:
import java.util.Hashtable;
...
// create a new Hashtable
Hashtable h = new Hashtable(149 /*
capacity */, 0.75f /*
loadfactor */);
// add some key/value pairs to the Hashtable
h.put("WA","Washington");
h.put("NY","New
York");
h.put("RI","Rhode
Island");
h.put("BC","British
Columbia");
// look up a key in the Hashtable
String key = "NY";
String stateName = (String) h.get(key);
System.out.println(stateName); //
prints "New York"
// enumerate all the contents of the hashtable
Enumeration keys = h.keys();
while( keys.hasMoreElements() )
{
key = (String)keys.nextElement();
stateName = (String)h.get(key);
System.out.println(key + "
" + stateName);
// prints lines of the form NY New York
// in effectively random order.
} // end while
Some fine points:
-
Hashtables work fastest if the capacity is a prime number. Round your capacity
up to prime number. You are only using 4 bytes per additional entry.
Here are some primes just larger than various powers of two that would be good
choices.
11 |
17 |
37 |
67 |
131 |
257 |
521 |
1031 |
2053 |
4099 |
8209 |
16411 |
32771 |
65537 |
131101 |
262147 |
524309 |
1048583 |
2097169 |
4194319 |
8388617 |
-
You cannot have elements with duplicate keys. If you add a new element
that duplicates the key of an existing element, it will replace it.
-
If you specified a capacity of 101 and a load factor of .75f, then the
initial table could hold 75 elements.
-
Hashtables will automatically grow when you add too many elements. However,
growing requires copying, rehashing and rechaining, quite an involved process.
That is why you want an accurate estimate for the initial capacity.
-
A load factor of .75f means that the table will be expanded when it gets
three quarters full. Hashing works faster when the table is not full. A
value of .25f would use more RAM but would work faster. A value of 1.0f
would use minimal RAM but would run slowly.
-
If two key hash to the same hashCode, or to the same hashCode modulus the
size of the table, all still works. It just takes a little longer to look
up that key, since get() has to chase
a chain of clashing keys to find the match. Keys are matched with the equals()
method, not ==, or simply by comparing hashCodes.
-
The source code for Hashtable is very short. It takes an order of magnitude
more English to describe how it works than does the Java code itself. I
suggest you peruse it if you are in the least curious how it works inside.
Hashing is something every programmer should understand. You might
also study String.hashCode().
-
Hashtables use generic objects or both keys and values. You need to cast
these back to Strings, or whatever you are using.
-
If you want to use something other than Strings as your keys, make sure
you implement an equals() and hashCode()
method for those key objects to override the default Object
equals() and hashCode()
methods. The default equals() method
just checks that the two objects are one in the same (using ==), not that
they consist of the same bit patterns.
-
There are two methods for enumerating the Hashtable, keys()
which gives you the keys, and elements()
which gives you the values. You could step through both enumerations simultaneously
instead of using get() as I showed.
See primes.