使用 TreeNode 而不是链表的 Java 8 hashmap 实现

Question

根据这篇文章:

http://coding-geek.com/how-does-a-hashmap-work-in-java/

java 8 hashmaps 使用树节点而不是链表(如在 java 7 中)作为数组的元素。

TreeNodes有一个特殊的性质，当元素个数少的时候，就相当于链表；如果元素个数多，就相当于红黑树。 (因为涉及红黑树的操作是 log(n))。

但是，这是否要求键是可比较的或存在键的某种排序？

这是在 java 8 hashmap 中强制执行的吗？如果键是可比较的(存在键的顺序)，它会只使用红黑树吗？

Answer 1

Will it only use red black trees if the keys are Comparable (ordering of keys exist)?

不，当 HashMap 较小时，所有冲突都将作为 LinkedList 解决。看源码:

/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st, TREEIFY_THRESHOLD = 8
    treeifyBin(tab, hash);
    break;

treeifyBin() 方法将在达到阈值时将所有碰撞转换为 TreeMap 。

However, doesn't this require the key to be Comparable or some ordering of the keys to exist?

您可以将任何键放入 hashmap。根据java doc , null 是一个有效的键，因为 null 不是 Comparable，所以键不必是 Comparable。如果键不是Comparable，它将被put作为LinkedList(如果数组已经转换为树，则通过内表)。