HashMap Java 8 구현

HashMap Java 8 구현

다음 링크 문서에 따르면 Java HashMap 구현

는 지금 이 HashMap(의 HashMap을 사용하다

일단은

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

이러한 상수는 왜 그리고 어떻게 사용됩니까?나는 이것에 대한 몇 가지 명확한 예를 원한다.이를 통해 어떻게 성능을 향상시키고 있습니까?

두 번째로

「」의 .HashMapJDK 、 음음음음 j j j j j j j j j 。

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

어떻게 사용하나요?알고리즘에 대한 설명을 듣고 싶습니다.

HashMap에는 일정 수의 버킷이 포함되어 있습니다. it it를 한다.hashCode어떤 버킷에 넣을지 결정합니다.단순하게 하기 위해 그것을 계수라고 상상하라.

이 있는 , "123456" "4"123456 % 4 = 0 첫버킷인 .

우리의 ★★★★★★★★★★★★★★★★★.hashCode함수는 양호합니다.모든 버킷이 어느 정도 균등하게 사용될 수 있도록 균등한 분포를 제공해야 합니다.이 경우 버킷은 링크된 목록을 사용하여 값을 저장합니다.

하지만 좋은 해시 함수를 구현하기 위해 사람들에게 의존할 수는 없습니다.사람들은 종종 부실한 해시 함수를 쓰기 때문에 불균등한 분포를 초래하게 된다.또한 입력에 운이 없을 수도 있습니다.

이 분포가 적을수록 O(1) 운영에서 더 멀어지고 O(n) 운영으로 더 가까워집니다.

HashMap 구현에서는 버킷이 너무 커질 경우 일부 버킷을 링크 목록이 아닌 트리로 구성함으로써 이 문제를 완화하려고 합니다. 바로 런 this this입니다.TREEIFY_THRESHOLD = 8를 위한 것입니다.버킷에 8개 이상의 항목이 포함되어 있으면 트리가 됩니다.

이 트리는 Red-Black 트리로, 최악의 경우 보증을 제공하기 때문에 선택되었을 가능성이 있습니다.먼저 해시 코드로 정렬됩니다.해시 코드가 같을 경우,compareTo의 of의 Comparable오브젝트가 그 인터페이스를 실장하고 있는 경우는 ID 해시 코드를 실장하고 있지 않은 경우는, ID 해시 코드입니다.

엔트리가 맵에서 삭제되면 버킷 내의 엔트리의 수가 줄어들어 이 트리 구조가 불필요해질 수 있습니다.그게 뭐냐면UNTREEIFY_THRESHOLD = 6를 위한 것입니다.버킷의 요소 수가 6개 미만으로 떨어지면 링크 목록을 다시 사용하는 것이 좋습니다.

마지막으로, 다음과 같은 것이 있습니다.MIN_TREEIFY_CAPACITY = 64.

해시 맵의 크기가 커지면 자동으로 크기가 조정되어 더 많은 버킷이 있게 됩니다.작은 HashMap을 사용하면 데이터를 저장할 수 있는 다양한 버킷이 없기 때문에 매우 꽉 찬 버킷을 얻을 가능성이 매우 높습니다.더 큰 HashMap을 사용하는 것이 훨씬 더 좋습니다. 더 많은 버킷이 가득 차지 않습니다.이 상수는 기본적으로 HashMap이 매우 작을 경우 버킷을 트리로 만들지 않도록 합니다. 대신 크기를 먼저 더 크게 조정해야 합니다.

---

성능 향상에 대한 질문에 답하기 위해 최악의 경우를 개선하기 위해 이러한 최적화가 추가되었습니다.에 의해 하게 향상되는 은, 「」의 경우 입니다.hashCode기능은 그다지 좋지 않았습니다.

일로부터 하기 위한 입니다.hashCode구현 및 충돌 공격에 대한 기본 보호 기능을 제공합니다. 충돌 공격에서는 악덕 행위자가 같은 버킷을 사용하는 입력을 의도적으로 선택하여 시스템 속도를 낮추려고 할 수 있습니다.

간단히 말하면 (내가 할 수 있는 한) + 좀 더 상세하게.

이러한 속성은 직접 이동하기 전에 이해하기 쉬운 많은 내부 사물에 의존합니다.

트리화_단일 버킷이 이 값에 도달했을 때(합계가 이 값을 초과했을 경우)MIN_TREEIFY_CAPACITY)는 완벽하게 균형 잡힌 빨간색/검은색 트리 노드로 변환됩니다. 왜일까요?검색 속도 때문에.다른 방식으로 생각해 보세요.

Integer를 사용하여 버킷/빈 내에서 엔트리를 검색하려면 최대 32단계를 수행해야 합니다.MAX_VALUE 엔트리

다음 토픽은 어떤 도입부입니다.빈/버킷 수가 항상 2의 거듭제곱인 이유는 무엇입니까?최소 두 가지 이유: 모듈로 연산보다 빠름과 음수에서의 모듈로는 음수입니다.또한 엔트리를 "negative" 버킷에 넣을 수 없습니다.

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

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

대신 modulo 대신 사용되는 좋은 방법이 있습니다.

 (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비트는 엔트리의 위치를 결정합니다.버킷을 2배로 만듭니다.32개의 버킷 - 5개의 마지막 비트가 엔트리의 위치를 결정합니다.

이러한 과정을 재해시라고 합니다.느려질 수도 있어요.이는 HashMap이 고속, 고속, 고속, 슬로우라는 "장난"을 치기 때문에 (관심 있는 사람들을 위해) 그렇습니다.다른 구현이 있습니다. 일시 중지 없는 해시 맵 검색...

지금 트리화 해제_HAXMERT는 재해시 후 활성화됩니다.이 시점에서 일부 엔트리는 이 빈에서 다른 엔트리로 이동할 수 있습니다(이 엔트리에 의해 1비트가 추가됩니다).(n-1)&hash계산 - 다른 버킷으로 이동할 수 있으며, 여기에 도달할 수 있습니다.UNTREEIFY_THRESHOLD이 시점에서, 통을 보관하는 것은 효과가 없습니다.red-black tree node단,LinkedList대신, 예를 들면

 entry.next.next....

MIN_TREIFY_CAPACITY는 특정 버킷이 트리로 변환될 때까지의 최소 버킷 수입니다.

TreeNode의 단일 bin에 속하는 엔트리를 저장하는 대체 방법입니다.HashMap. 이전 구현에서는 빈 엔트리가 링크 목록에 저장되었습니다.Java 8에서는 빈의 엔트리 수가 임계값을 넘었을 경우(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.

항상 같은 값을 반환하기 위해 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 
  }

}

그리고 다른 곳에서 해시맵에 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(n)}보다 {O(log n)} 빠르며 n이 커질수록 차이가 더 커집니다.

HashMap 구현의 변경은 JEP-180에서 추가되었습니다.목적은 다음과 같습니다.

java.util의 성능을 향상시킵니다.높은 해시 충돌 조건 하에서 맵엔트리를 저장하기 위해 링크 리스트가 아닌 균형 트리를 사용하는 해시 맵엔트리를 저장합니다.Linked Hash Map 클래스에서 동일한 개선 기능 구현

그러나 순수한 성능만이 유일한 이득은 아닙니다.또한 버킷에 데이터를 저장하기 위해 사용되는 빨간색-검은색 트리는 O(log n)의 삽입 복잡도가 가장 낮기 때문에 해시 맵이 사용자 입력을 저장하기 위해 사용되는 경우 HashDoS 공격을 방지할 수 있습니다.트리는 특정 기준을 충족한 후에 사용됩니다. 유진의 답변을 참조하십시오.

해시맵의 내부 실장을 이해하려면 해시를 이해해야 합니다.해싱은 변수/개체의 속성에 공식/알고리즘을 적용한 후 변수/개체에 고유한 코드를 할당하는 방법입니다.

진정한 해시 함수는 이 규칙을 따라야 합니다.

"해시 함수는 함수가 동일하거나 동일한 객체에 적용될 때마다 동일한 해시 코드를 반환해야 합니다.즉, 동일한 두 개체가 동일한 해시 코드를 일관되게 생성해야 합니다."

언급URL : https://stackoverflow.com/questions/43911369/hashmap-java-8-implementation