Hash 충돌 해결 방법 소결

충돌
대상 Hash 의 전 제 는 equals()와 hashCode()두 가지 방법 을 실현 하 는 것 이라는 것 을 알 고 있 습 니 다.그러면 HashCode()의 역할 은 대상 이 유일한 hash 값 을 되 돌려 주 는 것 을 보장 하 는 것 입 니 다.그러나 두 대상 의 계산 값 이 같 을 때 충돌 이 발생 합 니 다.충돌 을 어떻게 처리 하 는 지 소개 하 겠 습 니 다.물론 그 전 제 는 일치 성 hash 입 니 다.
1.주소 법 열기
개방 적 인 법 집행 에는 Hi=(H(key)+di)MOD m i=1,2,...,k(k<=m-1)공식 이 있다.
그 중에서 m 는 해시 표 의 시계 길이 이다.di 는 충돌 이 발생 할 때의 증분 시퀀스 입 니 다.만약 di 값 이 1,2,3,m-1 일 수 있다 면 선형 탐지 재 산열 이 라 고 합 니 다.
di 가 1 을 취하 면 충돌 할 때마다 1 개의 위 치 를 뒤로 이동 합 니 다.di 의 수치 가 1,-1,2,-2,4,4,9,9,16,-16,...k*k,-k*k(k<=m/2)일 수 있 으 면 2 차 탐지 재 산열 이 라 고 합 니 다.
만약 di 수치 가 가짜 랜 덤 수열 일 수 있 습 니 다.위조 랜 덤 탐지 재 산열.
2.재 해시 법
충돌 이 발생 했 을 때 충돌 이 없 을 때 까지 두 번 째,세 번 째,해시 함수 로 주 소 를 계산 합 니 다.단점:계산 시간 증가.
예 를 들 어 위 에서 처음으로 성 이니셜 에 따라 하 쉬 를 진행 하 는데 충돌 이 생기 면 성 이니셜 두 번 째 에 따라 하 쉬 를 진행 하고 충돌,세 번 째 는 충돌 하지 않 을 때 까지 할 수 있다.
3.체인 주소 법(지퍼 법)
모든 키 워드 를 동의어 로 기록 하 는 것 을 같은 선형 링크 에 저장 합 니 다.다음 과 같다.

그래서 이런 방법 은 통안 통 이 라 고 비슷 하 게 볼 수 있다.
4.공공 넘 침 구역 만 들 기
해시 함수 의 값 영역 이[0,m-1]이 라 고 가정 하면 벡터 HashTable[0.m-1]을 기본 표 로 하고 저장 공간 벡터 OverTable[0.v]를 설치 하여 충돌 이 발생 한 기록 을 저장 합 니 다.
지퍼 법의 장단 점:
장점:
① 지퍼 법 은 충돌 처리 가 간단 하고 퇴적 현상 이 없다.즉,동의어 가 아 닌 경우 충돌 이 발생 하지 않 기 때문에 평균 적 으로 길이 가 짧다.
② 지퍼 법 에서 각 링크 의 결산 공간 은 동태 적 으로 신청 한 것 이기 때문에 표를 만 들 기 전에 표 의 길 이 를 확정 하지 못 하 는 상황 에 더욱 적합 하 다.
③ 개방 주소 법 은 충돌 을 줄 이기 위해 인 자 를 채 워 야 한다.α비교적 작 기 때문에 결점 규모 가 비교적 클 때 많은 공간 을 낭비 할 수 있다.지퍼α≥1.그리고 결점 이 비교적 클 때 지퍼 법 에 추 가 된 지침 역 은 무시 할 수 있 기 때문에 공간 을 절약 할 수 있다.
④ 지퍼 로 구 성 된 산 목록 에서 결점 을 삭제 하 는 작업 은 쉽게 이 루어 진다.링크 에 해당 하 는 결산 점 을 간단하게 삭제 하면 된다.열 린 주소 법 구조의 산 목록 에 대해 서 는 삭 제 된 노드 의 공간 을 간단하게 비 워 서 는 안 됩 니 다.그렇지 않 으 면 그 후에 산 목록 을 작성 하 는 동의어 노드 의 검색 경 로 를 차단 할 것 입 니 다.이 는 각종 오픈 주소 법 에서 빈 주소 셀(즉 오픈 주소)이 검색 에 실패 한 조건 이기 때문이다.따라서 충돌 을 열 린 주소 법 으로 처리 하 는 산열 표 에서 삭제 작업 을 수행 하고 삭 제 된 노드 에 만 삭제 표 시 를 할 수 있 으 며 노드 를 진정 으로 삭제 할 수 없습니다.
단점:
지침 은 추가 공간 이 필요 하기 때문에 결점 규모 가 시간 에 비해 개방 주소 법 은 공간 을 절약 할 수 있다.만약 에 절 약 된 지침 공간 을 산 목록 의 규 모 를 확대 하면 장 착 인 자 를 작 게 할 수 있다.이것 은 개방 주소 법의 충돌 을 감소 시 켜 평균 검색 속 도 를 높 일 수 있다.
자바 의 hashmap 어떻게 hash 충돌 처리
핵심 적 개념
map 는 entry 의 집합 입 니 다.key,value 는 entry 입 니 다.
도해

자바 가 hash 충돌 을 처리 할 때 링크 를 사 용 했 습 니 다.
그림 의 0 에서 10 번 사각형 은 바로 entry(키 값 쌍)입 니 다.hashcode 의 충돌 이 발생 하면 4 번 사각형 처럼 뒤로 추가 하기 시작 합 니 다.4 번 사각형 의 next 속성 을 주의 하 세 요.그 속성 은 null 이 아니 라 사각형 을 가리 키 고 있 습 니 다.
이상 의 Hash 충돌 을 신속하게 해결 하 는 방법 소결 은 바로 편집장 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 에 게 참고 가 되 고 저희 도 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.