Java hashtable with seperate chaining collision resolution?

Question

I have created a program using the built in java.util.hashtable but now I need to resolve collisions using separate chaining. Is it possible with this implementation of a hashtable? Is there one out there already implemented that uses separate chaining?

Answer 1

Looking at the source of the Hashtable implementation, it looks like it already uses separate chaining. If you look at the Entry<K,V> class starting at line 901, you'll see that it has a reference to another Entry named next. If you then look at the put() method, on line 420 the next reference is populated via the constructor to be whatever element was previously stored in that bucket.

Note that you shouldn't generally be concerned about implementation details such as these. The Java Collections Framework is probably one of the most widely used frameworks in Java, and as such you should assume that the authors have tuned the performance to be as good as it's going to get.

One other thing I'd like to point out is that the Hashtable class has been mostly replaced by the HashMap class (which also uses separate chaining, see here). The main difference between the two is that all of the methods in Hashtable are synchronized, whereas in HashMap they are not. This leads to better performance in situations where you are running in a single threaded environment (possibly the reason for this question?).

If you do need a thread-safe map implementation, then you should consider either wrapping a normal HashMap in a call to Collections.synchronizedMap(), or using a ConcurrentHashMap.