Amir Omidi Amir Omidi - 11 months ago 84
Java Question

Java's HashMap collision resolution

So from what I've read on stackoverflow and other websites. Java uses linkedlists for hash collision resolution.

This would guarantee a O(n) complexity for worst case scenarios of inserting, getting and, removing.

Why does Java not use a self balancing BST (Like AVL, Red Black, etc...) to guarantee a O(log n) complexity for worst case scenarios of inserting, getting, and, removing?

Answer Source

There are a lot of implementation details available when reading the source code for the JDK. Here's a brief excerpt from the top of Oracle's java.util.HashMap:

 * Implementation notes.
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.
 * [...]

Looking at the implementations of HashMap#getNode and HashMap.Node, we can see that each bucket starts as a very simple linked list--simpler than java.util.LinkedList, which is actually a doubly-linked list.

Per the comment, when a list grows to a certain size, it's converted to a tree. It's hard to tell exactly what's going on in HashMap.TreeNode because the code isn't exactly self-descriptive, but it appears to be a simple red-black BST.