Java 8的HashMap实现

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;

这些常数是如何使用的？我需要一些明确的例子。 他们如何通过这些常数实现性能提升？

其次

如果你查看JDK中HashMap的源代码，你会发现以下静态内部类：

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;
        }
    }
    //...
}

如何使用？我只是想要该算法的解释。

- Hasnain Ali Bohra

Answer 1

HashMap 包含一定数量的桶。它使用 hashCode 确定将其放入哪个桶中。为简单起见，可以将其想象为模数。

如果我们的 hashCode 是 123456，而我们有 4 个桶，则 123456 % 4 = 0，因此该项将放入第一个桶，即 Bucket 1。

如果我们的 hashCode 函数很好，它应该提供均匀分布，使得所有桶被相对平均地使用。在这种情况下，桶使用链表来存储值。

但是您不能依赖于人们实现良好的哈希函数。人们经常会编写糟糕的哈希函数，从而导致分布不均匀。同时我们也有可能对输入不够幸运。

这个分布越不均匀，我们就越远离O(1)操作，越接近O(n)操作。

HashMap的实现尝试通过将一些桶组织成树而不是链接列表来减轻这种情况，如果桶变得太大。这就是“TREEIFY_THRESHOLD = 8”的作用。如果一个桶包含超过八个项目，则应该成为一棵树。

这棵树是一棵红黑树，可能是因为它提供了一些最坏情况的保证而被选择。首先按哈希码排序。如果哈希码相同，则使用Comparable的compareTo方法（如果对象实现了该接口），否则使用身份哈希码。

如果从映射中删除条目，则存储桶中的条目数可能会减少，以至于不再需要此树结构。这就是UNTREEIFY_THRESHOLD = 6的作用。如果存储桶中的元素数量下降到六个以下，我们可以回到使用链接列表。

最后，有MIN_TREEIFY_CAPACITY = 64。

当哈希映射增大时，它会自动调整大小以拥有更多存储桶。如果我们有一个小HashMap，那么桶变得非常满的可能性就很高，因为我们没有那么多不同的桶来放东西。最好有一个更大的HashMap，有更多的桶，每个桶都不那么满。这个常量基本上是说，如果我们的HashMap非常小，不要开始将桶变成树 - 它应该先调整大小变得更大。

---

为了回答您关于性能提升的问题，这些优化是为了改善最坏情况而添加的。如果您的hashCode函数不是很好，那么您可能只会看到明显的性能提升。

它旨在保护免受糟糕的hashCode实现，并提供基本的保护措施，以防止碰撞攻击，其中恶意行为者可能会试图通过故意选择占用相同桶的输入来减慢系统的速度。

- Michael

---

请问您能帮我理解为什么Java选择8作为树化的阈值，而不是像5或10或其他数字一样的数字吗？另外，在最初使用链表时的原因是什么？当元素数量超过8并且变成树时，为什么不最初使用树而是使用链表呢？ - Vishwas Tyagi

@VishwasTyagi 选择的阈值可能是通过试错确定的。他们可能尝试了很多阈值，并实验确定8是最好的。之所以最初不使用树是因为树会产生额外开销，如果元素数量较少，则不值得产生这种开销。 - Michael

RBT 被使用的另一个主要原因是它的“平衡树”。这样就不会出现倾斜树的情况，从树中获取元素的最坏情况时间复杂度为 O(log(N))。 - Mandar Autade

使用链表的原因是在链表的头部添加一个元素是廉价的，并且保证时间复杂度为O(1)。而将元素添加到其他类型的容器中并不总是具有这样的性能。例如，向一个满数组中添加元素需要先调整数组的大小。向AVL树中添加元素的时间复杂度是O(log n)。 - Aetherus

Answer 2

简单地说（尽可能简单）+更多细节。

这些属性取决于很多内部的东西，最好先了解它们，然后再直接进入它们。

TREEIFY_THRESHOLD -> 当一个单独的桶达到此阈值（且总数超过MIN_TREEIFY_CAPACITY），它将转换为完美平衡的红黑树节点。 为什么？ 因为搜索速度会更快。 以不同的方式思考一下：

  

在具有 Integer.MAX_VALUE 条目的桶/ bin中搜索一个条目最多需要32个步骤。

下一个主题的介绍。 为什么桶/箱的数量总是2的幂次方？ 至少有两个原因：比模运算更快，负数上的模运算会得到负数。并且您不能将Entry放入“负”存储桶中：

 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位。这就是为什么扩大桶的作用发挥了作用。在某些条件下（需要花费很长时间才能精确解释），桶的大小会加倍。为什么？当桶的大小加倍时，会有一个更多的位进入计算。因此，这个过程被称为重新散列。这可能会变慢。这就是HashMap被“玩笑”称为：“快、快、快、慢”的原因。还有其他的实现方式-搜索...现在，在重新散列之后，UNTREEIFY_THRESHOLD起到作用。此时，一些条目可能从这些容器移动到其他容器（它们向(n-1)&hash计算添加了一个位，因此可能会移动到其他桶），并且可能达到这个UNTREEIFY_THRESHOLD。这时，将bin保留为red-black tree node不划算，而是应该改为LinkedList，比如...

 entry.next.next....

MIN_TREEIFY_CAPACITY是指在将某个桶转换为树之前，必须具备的最小桶数。

- Eugene

Answer 3

TreeNode是一种替代方式，用于存储HashMap的单个bin中属于条目。在旧版实现中，bin的条目存储在链表中。在Java 8中，如果一个bin中的条目数量超过了阈值(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.

- Eran

---

并不是完全正确的。如果它们通过了TREEIFY_THRESHOLD AND总桶数至少为MIN_TREEIFY_CAPACITY。我已经在我的答案中尝试解释了这一点... - Eugene

Answer 4

您需要将其可视化：假设存在一个Class Key，仅覆盖hashCode()函数以始终返回相同的值。

public class Key implements Comparable<Key>{

  private String name;

  public Key (String name){
    this.name = name;
  }

  @Override
  public int hashCode(){
    return 1;
  }

  public String keyName(){
    return this.name;
  }

  public int compareTo(Key key){
    //returns a +ve or -ve integer 
  }

}

然后在其他地方，我要向HashMap中插入9个实例为该类的键。

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

    Key key1 = new Key("key1");
    map.put(key1, "one");

    Key key2 = new Key("key2");
    map.put(key2, "two");
    Key key3 = new Key("key3");
    map.put(key3, "three");
    Key key4 = new Key("key4");
    map.put(key4, "four");
    Key key5 = new Key("key5");
    map.put(key5, "five");
    Key key6 = new Key("key6");
    map.put(key6, "six");
    Key key7 = new Key("key7");
    map.put(key7, "seven");
    Key key8 = new Key("key8");
    map.put(key8, "eight");

//Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry 

    Key key9 = new Key("key9");
    map.put(key9, "nine");

  threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g.

                  key1
                 /    \
               key2   key3
              /   \   /  \

树的遍历速度比链表快，时间复杂度为 {O(log n)}，而链表的时间复杂度为{O(n)}。随着n的增长，这种差异变得越来越明显。

- rentedrainbow

---

它无法构建高效的树，因为除了哈希码以外，它没有比较键的方法，而这些哈希码全部相同，并且它们的equals方法也不能帮助排序。 - user253751

@immibis它们的哈希码不一定相同。它们很可能是不同的。如果类实现了它，它还将使用Comparable中的compareTo。identityHashCode是它使用的另一种机制。 - Michael

@Michael 在这个例子中，所有的哈希码都必须相同，并且该类没有实现Comparable接口。使用identityHashCode将无法找到正确的节点。 - user253751

@immibis 哦，是的，我只是匆匆看了一下，但你说得对。因此，由于“Key”没有实现“Comparable”，将使用“identityHashCode” :) - Michael

@EmonMishra 很遗憾，仅仅可视化是不够的，我已经在我的回答中尝试解决了这个问题。 - Eugene

static final int MIN_TREEIFY_CAPACITY = 64;, where does this variable comes into picture. As per above answer, buckets would not be converted to tree, unless number of buckets has reached static final int MIN_TREEIFY_CAPACITY = 64; - Nisarg Patil

Answer 5

HashMap实现的变化是通过JEP-180添加的。目的是：

通过使用平衡树而不是链表来存储映射条目，改善java.util.HashMap在高哈希冲突条件下的性能。在LinkedHashMap类中实现相同的改进。

然而，纯粹的性能并不是唯一的收益。如果哈希映射用于存储用户输入，这也将防止HashDoS攻击，因为用于在桶中存储数据的红黑树在最坏情况下的插入复杂度为O(log n)。在满足某些条件后使用该树-请参见Eugene's answer。

- Anton Krosnev

Answer 6

为了理解哈希表的内部实现，您需要了解哈希算法。 哈希算法最简单的形式是，在对变量/对象的属性应用任何公式/算法后，为其分配一个唯一的代码的方法。

真正的哈希函数必须遵循这个规则 - “当在相同或相等的对象上应用函数时，哈希函数应该每次返回相同的哈希码。换句话说，两个相等的对象必须始终产生相同的哈希码。”

- Java Cloud Techno

---

这并没有回答问题。 - Stephen C