1

From HashMap docs we can read:

Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

I know that if the key implements Comparable interface, on many hash collision, the bucket can transform from List to TreeSet.

Is it possible to set the capacity, or check when it will transform?

ByeBye
  • 6,650
  • 5
  • 30
  • 63
  • 2
    Where did u get the `TreeSet` from? Also you are saying lots of things into one sentence that are kind of wrong – Eugene Dec 05 '18 at 18:35
  • From implementation notes of `HashMap` -> not really `TreeSet` but `TreeNodes` which are behaves similar to our `TreeSet`. – ByeBye Dec 05 '18 at 18:38
  • 2
    `TreeNode` has nothing to do with `TreeSet` – Eugene Dec 05 '18 at 18:43

2 Answers2

5

It's not a List, but a LinkedList

It's not a TreeSet, but a perfectly balanced red black tree

It does not has Comparable, but implements

It does nto depend if you are implementing Comparable or not - a bucked will still be transformed from a LinkedList to a red black tree. Comparable just makes it a bit easier to decide if an entry is red or black, that is move to left or right.

When moving to a tree, the decision is taken on both how many entries exist overall and how many entries exist in that particular bucket.

A lot more to read In my other answer if you really want.

Choosing the correct capacity is non-trivial as it seems for a HashMap, a lot more to read here

Eugene
  • 117,005
  • 15
  • 201
  • 306
1

In openjdk it does so when a bucket is larger than static final int TREEIFY_THRESHOLD = 8

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.

Also you must exceed static final int MIN_TREEIFY_CAPACITY = 64

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.

Source: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Might be different for other implementations. You can not modify this (without using reflection).

Also it is not a tree set but a red-black tree

leonardkraemer
  • 6,573
  • 1
  • 31
  • 54