In java Hashtable uses which resolution technique internally?

Question

After reading posts , I am confused in java Hashtable internally uses separate chaining or Linked List or open close addressing for handling hashtable collisions.

Can someone tell me hashtable uses which techquie internally?

You can always look at the source code; [here's one copy I found with a quick search](http://www.docjar.com/html/api/java/util/Hashtable.java.html) (it's JDK 7, though). There's a `src.jar` or `src.zip` in the JDK's `lib` directory (only OpenJDK for v11+). — T.J. Crowder, Oct 19 '18 at 06:45
Generally speaking Hashtable is a legacy API replaced by HashMap in Java 1.2. — Peter Lawrey, Oct 19 '18 at 06:46
@T.J. Crowder thank you , I found a single bucket stores multiple entries, which must be searched sequentially. Does it mean It uses Linked List ? M I correct? — kavya, Oct 19 '18 at 06:54
@kavya - Buckets where each bucket is a singly-linked list, yes. — T.J. Crowder, Oct 19 '18 at 07:01

score 0 · Answer 1 · answered Oct 19 '18 at 07:35

If you look at the source (there are some online sources, or there's a src.jar or src.zip in the lib directory of the JDK—I think with JDK 11+ it's only in the OpenJDK, not Oracle's), you can see that Hashtable is implemented as an array of buckets, and each bucket is a singly-linked list.

The data is stored here:

/**
 * The hash table data.
 */
private transient Entry<?,?>[] table;

Then if we look at get:

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

We can see that the hashCode of the key is used to select the bucket, and then it's a linear search within that bucket for the entry.

Note that Hashtable is largely a legacy class, superceded by HashMap as of Java 1.2. OpenJDK's HashMap starts out working largely the way Hashtable does, but if the buckets get too large, it switches to using buckets containing TreeMap-like structures instead (they're faster to look things up in when the bucket is overfilled).

In java Hashtable uses which resolution technique internally?

1 Answers1