Does java use open addressing or chaining to implementing Hashtable?
Is one method or the other required by some specification/certification?
Asked
Active
Viewed 932 times
2
-
13What's easier than checking the source? http://www.docjar.com/html/api/java/util/Hashtable.java.html – MByD Aug 04 '11 at 18:17
-
2Java probably doesn't require either. Individual implementations likely do whatever they think works best, as things like that are implementation details. – Aug 04 '11 at 18:18
-
3You should also look at HashMap, LinkedHashMap and ConcurrentHashMap which are all subtly different. I would suggest you not use the old Hashtable class unless you have to. – Peter Lawrey Aug 04 '11 at 18:21
-
See [How do HashTables deal with collisions?](http://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions/4981071#4981071) – Paŭlo Ebermann Aug 05 '11 at 02:18
3 Answers
2
If you look at the Javadoc for Hashtable, you'll notice that it doesn't specify which hash scheme it uses. This means that any compliant Java implementation could implement this object however it sees fit, as long as it obeys the complexity guarantees specified in the interface. A compliant implementation could use chaining, quadratic hashing, Robin hood hashing, dynamic perfect hashing, Cuckoo hashing, etc. as long as the guarantees specified in the interface were met.
From a client perspective, you shouldn't need to worry about this, though.
templatetypedef
- 362,284
- 104
- 897
- 1,065
1
Both java.util.HashMap and java.util.Hashtable use some sort of chaining, at least in the implementation used in the Sun/Oracle JRE and the OpenJDK one.
Paŭlo Ebermann
- 73,284
- 20
- 146
- 210
aka
- 2,723
- 1
- 14
- 10
