시발 내용 반이 짤렸네 디씨좆병신


HashMap은 모든 키를 분산시키기 위해 포인터 배열 (테이블 []이라고 가정)을 사용한다. 키가 추가되면 배열의 첨자 <별칭> i는 해시 알고리즘에 의해 계산된 다음 가 사용된다. 테이블 [i]에 삽입되면 같은 i에 계산된 두 개의 다른 키가 존재하면 collision(충돌이라고 불린다)이라고 하는 테이블 [i]에 연결된 목록을 형성한다. 테이블 []의 크기가 2와 같이 작다면 10개의 키를 넣으려고 하면 충돌이 자주 발생하므로 O(1) 검색 알고리즘이 연결된 목록에 통과가 되고 그것은 해시 테이블의 결함 인 O (n)이 된다. (Hash Collision DoS) 따라서 해시 테이블의 크기와 용량은 매우 중요함. 일반적으로 해시 테이블 컨테이너는 삽입할 데이터가 있을 때 용량이 설정한 기준을 초과하는지 여부를 확인하는데 이를 초과하는 경우 해시 테이블의 크기를 늘려야 하지만 이 경우 해시 테이블 전체가 사용가능하므로 다시 계산해야 한다. 이것은 재진입 (rehash)이라고 불리우며 비용이 상당히 크다.


해쉬 알고리즘은 키 mod 테이블의 크기 (즉, 배열의 길이)를 단순히 사용한다고 가정한다. 맨 위는 해시 테이블의 크기가 2인 오래된 해시 테이블이다. 따라서 테이블 [1]에서 mod 2 충돌 후 key = 3, 7, 5가 된다. 다음 세 단계는 해시 테이블 크기를 4로 변경 한 다음 모든 re-rehash 프로세스이다.






두 개의 스레드가 있다고 가정한다.


Thread1의 e는 key (3)를 가리키고 key (7)를 가리키고 있기 때문에 스레드 2가 다시 해쉬 된 후에 스레드 2의 연결 목록을 가리킨다. 이로써 연결된 목록의 순서가 바뀌었음을 알 수 있다.



먼저 newTalbe [i] = e를 실행한다. 그러면 (e = next)로 e가 key(7)를 가리키도록 만든다. next = e.next의 다음 사이클은 key (3)를 가리킨다.




스레드가 정상적으로 작동하면 key (7)를 끄고 newTable [i]의 첫 번째에 넣은 다음 e와 next를 아래로 이동한다. Lin 링크가 나타난다.

E.next = newTable [i] key (3) .next가 key (7)를 가리키도록 한다.


참고 : 이 시점에서 key (7) .next는 이미 key (3)을 가리키고 순환 목록이 나타난다.


따라서 스레드가 HashTable.get(11)을 호출하면 무한반복이 일어난다.



Http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457


썬은 아무 문제가 없다고 쌩을 깠다고 한다.