Java에서 HashMap을 사용하여 해시 충돌 문제를 해결하는 방법

1. 해시 알고리즘과 해시 테이블

해시 충돌을 이해하려면 먼저 해시 알고리즘과 해시 테이블을 이해하세요

• 해시 알고리즘은 해시 알고리즘을 통해 임의의 길이의 입력을 고정 길이의 출력으로 변환하는 것입니다. 출력 결과는 해시값입니다

• 해시 테이블은 키를 통해 메모리 저장 위치에 직접 접근하는 데이터 구조입니다. 테이블의 특정 위치에 키를 매핑하면 해당 위치에서 데이터를 얻을 수 있으므로 데이터 검색 속도가 빨라집니다

2. 해시 충돌

해시 충돌은 해시 알고리즘으로 인해 발생하며 계산되는 데이터는 무제한입니다. , 계산된 결과의 범위는 제한되어 있습니다. 예, 항상 다른 데이터가 있고 계산 후 얻은 값은 동일하며 이 경우 소위 해시 충돌이 발생합니다

3. 해시 충돌을 해결하는 네 가지 방법

개방형 주소 지정 방법은 선형 감지라고도 합니다. 충돌이 발생한 위치에서 시작하여 특정 순서에 따라 해시 테이블에서 빈 위치를 찾은 다음 충돌하는 요소를 여기에 저장하는 방법입니다. Java에서 ThreadLocal은 해시 충돌을 해결하기 위해 선형 감지 방법을 사용합니다

그림에 표시된 것처럼 key=hobby를 추가하면 key=name이 해시 테이블의 인덱스 1에 저장됩니다. 계산된 인덱스도 1이면 이때 해시 충돌이 발생하며, 충돌하는 키를 저장하기 위해 빈 위치를 찾는 방법입니다.

체인 주소 지정 방법은 간단합니다. 이해하는 것은 HashMap

과 같은 Hash 충돌이 있는 키를 저장하기 위해 단방향 연결 목록을 사용하는 것입니다. 그림에서 볼 수 있듯이 충돌하는 키는 단방향 연결 목록 형태로 직접 저장됩니다.

그런 다음 해시 방식은 특정 해시 함수를 통해 키를 계산하는 것입니다. 충돌이 발생하면 다른 해시 함수를 사용하여 더 이상 충돌이 발생하지 않을 때까지 계속 계산할 수 있습니다. 성능에 약간의 영향을 미칩니다

공개 제거 영역을 설정하는 것은 해시 테이블을 기본으로 나누는 것입니다. 테이블과 혜택 테이블의 두 부분이 있습니다. 충돌하는 요소는 혜택 테이블에 배치됩니다.

4. JDK1.8 버전

JDK1.8 버전의 HashMap은 체인 주소 지정 방식과 레드를 사용합니다. 블랙 트리는 해시 충돌 문제를 해결하는 데 사용됩니다. 레드-블랙 트리는 긴 문자열로 인해 증가하는 시간 복잡도 문제를 최적화하는 데 사용됩니다. 연결된 목록의 길이가 8보다 크거나 같고 해시 테이블의 용량이 64보다 큰 경우 연결된 목록 요소에 추가하면 연결된 목록의 변환이 트리거됩니다. 레드-블랙 트리에 나열

위 내용은 Java에서 HashMap을 사용하여 해시 충돌 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!