Java 8 HashTable vs HashMap Collision Handling

Question

I want some clarification about the differences between hashtable and hashmap in Java 8.

HashTable to my knowledge functions similarly to a HashMap but is threadsafe, and doesn't allow null keys or values. I am aware that Java 8 updates the HashMap class so that when there's a collision, rather than create a linked list of items with the same hash code in the bucket, it creates a tree.

Is this also the case with hashtable? And is the tree the default storage method even before a collision? (As in, when the first item to fit into a bucket is placed there, it's just a tree root with no branches.)

Also, how does java ensure that a hashtable is threadsafe? Does it create a que when two threads try to concurrently access a piece of data?

On thread-safety, from the javadoc for Hashtable: "Unlike the new collection implementations, {@code Hashtable} is synchronized.". — Not a JD, Mar 28 '19 at 19:43
Doesn't look like it: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/Hashtable.java — shmosel, Mar 28 '19 at 19:47

score 3 · Answer 1 · answered Mar 28 '19 at 19:51

Is this also the case with hashtable?

No.

And is the tree the default storage method even before a collision? (As in, when the first item to fit into a bucket is placed there, it's just a tree root with no branches.)

No. The HashMap class has a constant named TREEIFY_THRESHOLD (value 8).

Javadoc says "The bin count threshold for using a tree rather than list for a bin. Bins are converted to trees when adding an element to a bin with at least this many nodes".

Also, how does java ensure that a hashtable is threadsafe?

The javadoc of Hashtable explicit says: "Unlike the new collection implementations, Hashtable is synchronized".

Does it create a que when two threads try to concurrently access a piece of data?

No.

John Vint · Accepted Answer · 2019-03-28T19:55:28.703

1

This answer is going to be very specific to the current implementation found in the JDK so keep that in mind.

I am aware that Java 8 updates the HashMap class so that when there's a collision, rather than create a linked list of items with the same hash code in the bucket, it creates a tree.

Is this also the case with hashtable?

No. The Hashtable is only ever going to be a table of linked lists. Java devs didn't update the Hashtable for this use case. This should also make it more clear that you probably shouldn't be using Hashtable anyway.

And is the tree the default storage method even before a collision?

Again this is in Java 8, as of today, but, no it's not the default behavior. Once the bucket entry hits 8 linked elements the HashMap turns that linked list into a binary tree.

Also, how does java ensure that a hashtable is threadsafe? Does it create a que when two threads try to concurrently access a piece of data?

By making every method synchronized, meaning, each thread will queue up on the method while another thread is currently accessing any method of the Hashtable. This causes quite a few issues if you want to do things like atomic puts, or atomic computes.

If you wanted a thread safe map HashMap, always use ConcurrentHashMap, never Hashtable.

edited Mar 28 '19 at 19:55

answered Mar 28 '19 at 19:50

John Vint

39,695
7
78
108

1

Minor point of content: To most people, "queue up" means to stand in line and be served first-come-first-served, but that is [not the case for synchronized](https://stackoverflow.com/q/3940164/5221149), so using the word "queue" is misleading. – Andreas Mar 28 '19 at 20:11
That's a reasonable point, but I use queue in the same way the `AbstractQueueSynchronizer` does, which supports both fair and unfair lock acquisitions. – John Vint Mar 28 '19 at 20:18
if it's not first come first serve, then how do monitors determine which threads get prioritized? – Marwa Roshan Mar 28 '19 at 20:28
1

They don't. That's part of the problem with unfair lock acquisitions forced upon you by the `synchronized` keyword. If you want fair in-order acquisition enforced, you would want to use `new ReentrantLock(true)` where `true` defines the lock to be "fair". – John Vint Mar 28 '19 at 20:32
1

The caveat though is that unfair lock acquisition usually performs better than fair. So, there should be a technical reason why you need fair locks. – John Vint Mar 28 '19 at 20:33
so does the monitor just arbitrarily choose which thread gets access to the data next? – Marwa Roshan Mar 28 '19 at 21:14
You may as well assume it does. – John Vint Mar 28 '19 at 22:45
@JohnVint [... and there are 64 entries](https://stackoverflow.com/questions/47921663/when-and-how-does-hashmap-convert-the-bucket-from-linked-list-to-red-black-trees) – Eugene Mar 28 '19 at 23:13

score 0 · Answer 3 · answered Mar 28 '19 at 19:49

From Hashtable's Java Docs:

In the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially

So the answer for the first question is "No". It does not create any tree.

As to threadsafe mechanism, Hashtable uses simple synchronization on each read\write method. If you're concerned about performance and thread safety, you'd better look at ConcurrentHashMap.

Java 8 HashTable vs HashMap Collision Handling

3 Answers3