Java의 HashMap 충돌 해결

Question

그래서 stackoverflow 및 다른 웹 사이트에서 읽은 것에서. Java는 해시 충돌 해결을 위해 연결된 목록을 사용합니다.

이것은 삽입, 가져 오기 및 제거의 최악의 시나리오에 대한 O (n) 복잡성을 보장합니다.

Java가 삽입, 가져 오기 및 제거의 최악의 시나리오에 대한 O (log n) 복잡성을 보장하기 위해 자체 균형 조정 BST (AVL, 빨강 검정 등)를 사용하지 않는 이유는 무엇입니까?

Answer 1

대개의 경우 버킷에는 매우 적은 수의 항목이 있습니다. 종종 0 또는 1이다. 이 경우 간단한 해시 버킷 구조가 O (1)을 보장 할 수 있습니다. O (log n) BST는 일부 차선의 경우에서 시간을 단축 할 수 있지만, 성능 이득은 좋지 않은 경우 무시할 수 있으며 최악의 경우는 음수입니다. 또한 상당한 메모리 오버 헤드가 있습니다. Java 8은 연결된 목록이 더 이상 최적이 아니고 BST로 변환되는시기를 감지하기 위해 노력합니다. 그러나이 동작이 자주 발생하면 해시 및 HashMap이 잘못 사용되고 있다는 표시입니다.

JDK의 소스 코드를 읽을 때 많은 구현 정보가 있습니다. 여기에 오라클의 java.util.HashMap에의 상단에서 간단한 발췌입니다 :

/* 
* 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의 #는 getNode 및 HashMap.Node의 구현을 보면, 우리는 각 버킷은 매우 간단한 링크 된 list--로 시작하는 것을 볼 수있다 실제로는 이중 링크리스트 인 java.util.LinkedList보다 간단합니다.

댓글에 따라 특정 크기로 커지면 트리로 변환됩니다. HashMap.TreeNode에서 무슨 일이 벌어지고 있는지 정확하게 말하기는 어렵습니다. 왜냐하면 그 코드가 정확히 자기 설명 적 (self-descriptive)이 아니기 때문입니다. 그러나 그것은 단순한 붉은 검정색 BST 인 것처럼 보입니다.

Answer 2

Java 8 않습니다, 링크 된 체인이 충분히 커지면.

그러나 요소 수가 적 으면 상당한 메모리 및 성능 오버 헤드가 추가됩니다. 연결된 목록은 매우 적은 수의 요소에 대해 실제로 매우 효율적입니다. 이는 99 %의 상황에서 해시 양동이에 대해 정확히 예상되는 요소입니다. 또한 정확하게 이진 트리를 정렬해야하는 방법을 정의하는 것은 명백하지 않으며, 요소가 Comparable 인 경우 특수한 경우에 사용되지 않는 해시 코드 비트별로 정렬해야합니다.