在存储桶中的条目对象从阈值开始减少后,JDK 8中的hashmap是否会再次自行调整大小.

Question

我遇到了一个博客,其中在JDK8中给出了hashmap的更改和性能改进.

从JDK 1.8开始,HashMap引入了一种改进的策略来处理高冲突率.由于糟糕的散列函数(例如总是返回相同存储桶的位置),可以将HashMap转换为链接列表,即将get()方法转换为在O(n)而不是O(1)中执行,并且有人可以利用这一事实,一旦某个阈值被破坏,Java现在在内部将链表重新替换为二进制true.这确保了性能或命令O(log(n)),即使在散列函数没有正确分配密钥的最坏情况下也是如此.

在JDK 8中,我们都知道无论何时达到阈值,链表都会将自身重新调整为二叉树.我想知道当节点变得小于阈值数时,二叉树是否会将自身重新调整为链表.

有人在接受采访时向我询问,不,因为每次数字发生变化时都不会重新调整尺寸.我对吗？

博客供参考:

1. http://javarevisited.blogspot.com/2014/07/java-optimization-empty-arraylist-and-Hashmap-cost-less-memory-jdk-17040-update.html
2. http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Answer 1

这是HashMap来源评论的一部分:

 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  

再往下看,我看到了这个:

/**
 * 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;

所以问题的答案是"是和否".当大小降至相同阈值以下时,它不会自行调整大小,但是当它低于不同阈值时会调整大小.

我不明白你为什么会在面试中被问到这个问题 - 你申请的公司是否真的希望你记住Java库的源代码？