Hashtable. How it works?

Question

Now, I'm trying to understand how to construct the Hashtable.

The most interesting - as objects are added to the Hashtable?

I have read in a book that:

at first step: Calculated hashCode() object.

Next, we determine the position of this object in the Hashtable: obj.hashCode() % Hashtable.length.

For example, add more elements to the Hashtable:

Hashtable<String, String> hm=new Hashtable<String, String>(100);

        hm.put("Lee","Lee");
        hm.put("lee","lee");
        hm.put("eel","eel");

Define a bucket into which is placed the object:

    System.out.println("Lee".hashCode() % 100);
    System.out.println("lee".hashCode() % 100);
    System.out.println("eel".hashCode() % 100);

If I understand the algorithm, the objects must be placed in the table as follows:

eel /*because,"eel".hashCode() % 100=0*/, 
lee /*because, "lee".hashCode() % 100=20*/, 
Lee /*because, "Lee".hashCode() % 100=68*/

but what we see as a result?

System.out.println(hm);

{Lee=Lee, lee=lee, eel=eel} 

Please, tell me, where did I go wrong?

Answer 1

The iteration order of Hashtable (as well as HashMap) elements is not guaranteed (implementation dependent), so IMHO there is not much point trying to build a theory on it. It may even change between different Java versions (it did change from Java5 to Java6).

Btw Hashtable is obsolete, it is recommended to use (and analyse) HashMap instead.

Your description sounds OK to me as a basic hash map implementation. However, the actual implementation of HashMap is quite a bit more sophisticated than that, at least since Java4. E.g. the size of the hash table is always a power of two (which would be quite a bad decision for a basic hashtable like you describe), and hash values got from the key objects are rehashed internally to achieve a more even distribution over the actual size of the table. For more details on this, see the following issues of the Java Specialist Newsletter:

• HashMap requires a better hashCode()
• Follow-up to JDK 1.4 HashMap hashCode() mystery

Answer 2

A Hashtable is a mapping from keys to values. It is this mapping that is shown when you print a Hashtable.

The story about .hashCode and .equals is a rough description of how it manages to keep track of the key/value pairs internally.

A few remarks on your question though:

• The capacity that you set to 100 in your example, does not represent the number of buckets to store objects in. It represents the number of objects the Hashtable has capacity for, with a load factor of .75.

• The number of buckets may vary during runtime. If you keep adding objects for a long time, the load factor will be increased, and the buckets may be reallocated and the objects "rehashed".

From the docs:

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

Answer 3

The concept of hashtable is to add the objects into the table acording to some hash function (takes object and returns an index).

Your description of a hashtable is just one of many (many...), and I'd be surprised if it was implemented in Java the same way you read.

Answer 4

As previously mentioned Hashtable is implementation dependent and I would reccomend to read about the Hashtable in general, to get the idea of how they work and then after understanding how it works to read about specific implementation in Java or other language.

Wikipedia has quite a good article on this topic, so I suggest read this first.