HashMap Java 8实现

Question

根据以下链接文档:Java HashMap Implementation

我对HashMap(或者更确切地说是增强HashMap)的实现感到困惑.我的疑问是:

首先

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

为什么以及如何使用这些常量？我想要一些明确的例子. 他们如何通过这个获得性能提升？

其次

如果您HashMap在JDK中看到源代码,您将找到以下静态内部类:

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

    final HashMap.TreeNode<K, V> root() {
        HashMap.TreeNode arg0 = this;

        while (true) {
            HashMap.TreeNode arg1 = arg0.parent;
            if (arg0.parent == null) {
                return arg0;
            }

            arg0 = arg1;
        }
    }
    //...
}

怎么用？我只想要解释算法.

Answer 1

HashMap包含一定数量的桶.它用于hashCode确定将这些存储器放入哪个存储桶.为简单起见,将其假设为模数.

如果我们的哈希码是123456并且我们有4个桶,123456 % 4 = 0那么该项目就在第一个桶中,即桶1.

如果我们的哈希码函数是好的,它将提供均匀分布,因此所有桶将在某种程度上同等使用.在这种情况下,存储桶使用链接列表来存储值.

但是你不能依赖人们来实现好的哈希函数.人们经常会写出糟糕的哈希函数,这会导致非均匀分布.

这种分布越不均匀,我们越是从O(1)运算开始,越接近O(n)运算.

Hashmap的实现试图通过在存储桶变得太大的情况下将一些存储桶组织到树而不是链接列表来缓解这种情况.这TREEIFY_THRESHOLD = 8是为了什么.如果一个桶包含八个以上的项目,它应该成为一棵树.

这棵树是红黑树.它首先按哈希码排序.如果散列码相同,它使用compareTo的方法,Comparable如果对象实现该接口,否则身份哈希码.

如果从映射中删除条目,则存储桶中的条目数可能会减少,从而不再需要此树结构.这就是UNTREEIFY_THRESHOLD = 6它的用途.如果存储桶中的元素数量低于6,我们也可以回到使用链接列表.

最后,还有MIN_TREEIFY_CAPACITY = 64.

当哈希映射的大小增加时,它会自动调整自身大小以获得更多存储桶.如果我们有一个小的哈希映射,我们获得非常完整的桶的可能性是相当高的,因为我们没有很多不同的桶来放入内容.拥有更大的哈希映射会更好,更多的桶不够饱满.如果我们的哈希映射非常小,这个常量基本上不会开始将桶变成树 - 它应该首先调整大小.

为了回答有关性能增益的问题,我们添加了这些优化以改善最坏情况.我只是在推测,但如果你的hashCode功能不是很好的话,你可能只会看到明显的性能提升,因为这些优化.

图像是我的(感谢MSPaint).不管怎样你都可以重复使用它们

Answer 2

更简单(尽可能简单)+更多细节.

这些属性取决于许多内部事物,这些内容很难理解 - 在直接转移到它们之前.

TREEIFY_THRESHOLD - >当一个单个铲斗达到此(和总数超过MIN_TREEIFY_CAPACITY),它被转换成一个完全平衡的红色/黑色树节点.为什么？因为搜索速度快.以不同的方式考虑它:

这将需要最多32个步骤,以搜索与桶/箱中的条目,Integer.MAX_VALUE的条目.

下一个主题的一些介绍.为什么箱/桶的数量总是2的幂？至少有两个原因:比模运算更快,负数上的模数将为负.你不能把一个条目放入一个"负面"桶:

 int arrayIndex = hashCode % buckets; // will be negative

 buckets[arrayIndex] = Entry; // obviously will fail

相反,有一个很好的技巧而不是模数:

 (n - 1) & hash // n is the number of bins, hash - is the hash function of the key

这在语义上与模运算相同.它会保留较低的位.当你这样做时,这有一个有趣的结果:

Map<String, String> map = new HashMap<>();

在上面的例子中,根据您的哈希码的最后4位来决定条目的去向.

这是桶的倍增发挥作用的地方.在某些条件下(需要花费大量时间来详细解释),水桶的尺寸增加了一倍.为什么？当铲斗的尺寸加倍时,还会有一个钻头进入游戏.

所以你有16个桶 - 最后4位的哈希码决定了一个条目的位置.您将桶加倍:32个桶 - 最后5个桶决定进入的位置.

因此,此过程称为重新散列.这可能会变慢.那就是(对于那些关心的人),因为HashMap被"开玩笑"为:快速,快速,快速,懒散.还有其他实现 - 搜索暂停hashmap ...

现在UNTREEIFY_THRESHOLD在重新散列后发挥作用.此时,某些条目可能会从此二进制位移到另一些(它们会在(n-1)&hash计算中再添加一位- 因此可能会移动到其他存储区)并且可能会达到此目的UNTREEIFY_THRESHOLD.在这一点上,保持垃圾箱不会得到回报red-black tree node,但作为一个LinkedList替代,就像

 entry.next.next....

MIN_TREEIFY_CAPACITY是将某个存储桶转换为树之前的最小存储桶数.

Answer 3

TreeNode是另一种存储属于单个bin的条目的方法HashMap.在较旧的实现中,bin的条目存储在链表中.在Java 8中,如果bin中的条目数传递了threshold(TREEIFY_THRESHOLD),则它们存储在树结构中而不是原始链表中.这是一个优化.

从实施:

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.