使用TreeNode而不是linkedlist实现Java 8 hashmap

Question

根据这篇文章:

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

java 8 hashmaps使用treenode而不是链表(如在java 7中)作为数组的元素.

如果元素的数量很小,则TreeNodes具有充当链表的特殊属性,如果存在大量元素,则表现为红黑树.(因为涉及红黑树的操作是log(n)).

但是,这不是要求密钥是可比较的还是密钥的某些排序存在？

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

Answer 1

如果键是可比较的（存在键的排序），它是否只使用红黑树？

不，当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()当达到阈值时，方法会将所有碰撞转换为树形图。

但是，这是否不需要键是可比较的或键存在某种顺序？

您可以将任何键放入哈希图。根据java文档，null是一个有效的密钥，并且由于null不是Comparable，所以密钥不必是Comparable。如果键不是，Comparable则为（如果数组已转换为树put，LinkedList则通过内部表）。