HashMapJava8实现

TreeNode是另一种存储属于 HashMap的单个 bin 的条目的方法。在较早的实现中，bin 的条目存储在一个链表中。在 Java8中，如果 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.

HashMap包含一定数量的桶。它使用 hashCode来确定将这些文件放入哪个桶中。为了简单起见，把它想象成一个模。

If our hashcode is 123456 and we have 4 buckets, 123456 % 4 = 0 so the item goes in the first bucket, Bucket 1.

如果我们的 hashCode函数是好的，它应该提供一个均匀的分布，以便所有的桶将被使用有些平等。在这种情况下，bucket 使用链表来存储值。

But you can't rely on people to implement good hash functions. People will often write poor hash functions which will result in a non-even distribution. It's also possible that we could just get unlucky with our inputs.

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

HashMap 的实现试图通过将一些桶组织到树中而不是在桶变得过大时使用链表来缓解这种情况。这就是 TREEIFY_THRESHOLD = 8的作用。如果一个桶包含八个以上的项目，它应该成为一棵树。

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

If entries are removed from the map, the number of entries in the bucket might reduce such that this tree structure is no longer necessary. That's what the UNTREEIFY_THRESHOLD = 6 is for. If the number of elements in a bucket drops below six, we might as well go back to using a linked list.

Finally, there is the MIN_TREEIFY_CAPACITY = 64.

当散列映射的大小增长时，它会自动调整自己的大小以便拥有更多的存储桶。如果我们有一个小的 HashMap，我们得到非常满的桶的可能性是相当高的，因为我们没有那么多不同的桶来放东西。最好有一个更大的 HashMap，带有更多不那么满的桶。这个常量基本上是说，如果我们的 HashMap 非常小，就不要开始将桶制作成树——它应该首先调整大小，使其更大。

To answer your question about the performance gain, these optimisations were added to improve the worst case. You would probably only see a noticeable performance improvement because of these optimisations if your hashCode function was not very good.

它旨在防止坏的 hashCode实现，并提供基本的 碰撞攻击保护，在这种情况下，坏的参与者可能通过故意选择占用相同桶的输入来试图减慢系统的速度。

您需要对它进行可视化: 假设有一个 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
/   \   /  \

树遍历比 LinkedList 更快{ O (logn)} ，随着 n 的增长，差异变得更加显著。

更简单的说(尽可能的简单) + 更多的细节。

这些属性依赖于很多内部的东西，这些东西在直接转移到它们之前非常容易理解。

TREEIFY_THRESHOLD -> when a 单身 bucket reaches this (and the total number exceeds MIN_TREEIFY_CAPACITY), it is transformed into a 完美平衡的红/黑树节点. Why? Because of search speed. Think about it in a different way:

它将使用 最多32步在带有 Integer.MAX_VALUE条目的 bucket/bin 中搜索条目。

Some intro for the next topic. 为什么垃圾桶的数量总是2的幂次方? At least two reasons: faster than modulo operation and modulo on negative numbers will be negative. And you can't put an Entry into a "negative" bucket:

 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<>();

 entry.next.next....