HashMap은 언제 어떻게 링크 된 목록의 버킷을 Red Black Trees로 변환합니까?

Question

자바 8 기능을 사용하여 버킷의 항목 집합 수가 증가 할 때 hashmaps가 연결된 목록 대신 빨간색 검정색 트리를 사용한다는 사실을 알게되었습니다.

그러나 이것은 키가 Comparable이거나 키의 순서가 존재할 필요가 없으며 어떻게 작동합니까? 이 전환은 실제로 어떻게 발생합니까?

Answer 1

가 단일 버킷 적어도 8 항목 (TREEIFY_THRESHOLD)가 있으며 버킷의 총 수는 하나의 버킷에 완벽하게 균형 레드 - 블랙 트리 노드으로 변환되도록 한 다음 더 다음 64 (MIN_TREEIFY_CAPACITY)이면 .

엔트리 (UNTREEIFY_THRESHOLD == 6)를 제거 할 때 발생하는 축소 현상 (원하는 경우)도 있습니다.

당신은 키가 Comparable해야한다는 정확한지 -하지만 그들은 (경우에 그들은 같은 hashCode을)하는 경우 그것은 항상 필요하지 않습니다, 그것은 좋지만, 경우에 그들은이 사용되지 않습니다

static int tieBreakOrder(Object a, Object b) { 
     int d; 
     if (a == null || b == null || 
      (d = a.getClass().getName(). 
      compareTo(b.getClass().getName())) == 0) 
      d = (System.identityHashCode(a) <= System.identityHashCode(b) ? 
       -1 : 1); 
     return d; 
} 

그래서 String으로 클래스 이름은 비교를 위해 사용되며, 그 역시 실패 할 경우, 다음 System.identityHashCode는 가 및 바로 왼쪽 결정 (Marsaglia XOR-Shift 키 알고리즘)을 사용한다.

언제 이런 일이 일어나는지 - 크기가 변경되면 호출됩니다. HashMap의 크기를 조정해야 할 때 몇 가지 일이 발생합니다. 버킷 수가 2 배 증가하면 (항목이 이동하는 위치를 고려하여 하나 이상의 비트가 고려 됨) 특정 버킷이 트리로 변환됩니다. 이 과정은 (정말로 당신이 정말로 신경 쓰는다면) 꽤 느리다. 어떤 사람들은 Java HashMap이 "sloooooooow, 그 다음 빠르다 빠르다, 그 다음 sloooooo 다, 그리고 그것은 빠르다 빠르기 때문에 말한다"(나는 조롱으로 이것을 본다. PauselessHashMap 구현입니다.

두 가지 흥미로운 점이 있습니다. 먼저이 어떤 크기를 조절을 피할 것, 즉 :

new HashMap<>(256); // choosing the size 

(심지어 대략 추정 할 것입니다) 처음에 Map의 정확한 크기를 선택합니다.

두 번째 이유는 BTREE ... 인 이유는 데이터베이스 인덱스를 생각하면 ... Tree으로 변환하는 것이 중요합니다. INTEGER.MAX_VALUE 항목 (이론적으로)이있는 완벽한 트리에서 항목을 찾으려면 몇 단계가 필요합니다. 오직 32까지.