5

I found following code in Java HashMap source code:

/**
 * 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. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

My doubt is this:

Q0. How these three variables together determine treeifying and untreeifying?

However the question above could be abstract as there might involve a lot of subtle facts that needs to be addressed in the answer to make it complete overall. As these are subtle facts and could possibly be overlooked in the answer, I tried to list them down in three separate questions below. You may answer Q0 or preferably Q1, Q2 and Q3.

I understood as follows:

We start with linked list for collision resolution. Once we insert a key which is to be hashed to the bucket already containing 8 (TREEIFY_THRESHOLD) keys and if there are already 64 (MIN_TREEIFY_CAPACITY) keys in HashMap, linked list of that bucket is converted to balanced tree. If we delete a key from the bucket containing 6 keys in a balanced tree, then it is converted back to the linked list.

Q1. Is above understanding correct?

Q2. I didnt get why

UNTREEIFY_THRESHOLD should be at most 6 to mesh with shrinkage detection under removal.

Q3. I didnt get why

MIN_TREEIFY_CAPACITY should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts between resizing and treeification thresholds.

MsA
  • 2,599
  • 3
  • 22
  • 47
  • 1
    Related: [HashMap Java 8 implementation](https://stackoverflow.com/questions/43911369/hashmap-java-8-implementation) – Slaw Mar 11 '20 at 15:29
  • 1
    I really dont get why this question got closed. I could have very well asked "how these three variables together determine treeifying and untreeifying" to make it SOUND more focused on one problem. But that would be very abstract, if you consider what all aspects might have involved. I tried to think a bit more in a depth and asked questions specific to those aspects to help answerers better form answers. Answering each of those three questions pointwise will help better answer "how these three variables together determine treeifying and untreeifying". – MsA Mar 13 '20 at 08:30
  • I have edited the question to state single question. But I guess I cant help, but keep the rest three. Answerer may answer the Q0 or more specific ones Q1 to Q3. – MsA Mar 13 '20 at 08:39
  • You basically got it right with the exception that treeification and resizing happen _after_ insertion thus "already containing 8" would be "now containing 8" (after insertion) etc. As for the threshold definitions: I'm not sure about the exact numbers but assume the values where very similar: adding a new node might result in untreeifying a just treeified node because it also triggered a resize and thus nodes got split. – Thomas Mar 13 '20 at 09:06
  • Didnt get "As for the threshold definitions..." I guess Q2 and Q3 are still unanswered and am still unsure about `MIN_TREEIFY_CAPACITY` – MsA Mar 13 '20 at 13:14

0 Answers0