어떻게 hash 충돌 을 해결 합 니까?

1)충돌 은 어떻게 발생 합 니까?
앞에서 언급 한 바 와 같이 해시 함 수 는 키 워드 를 어떻게 주소 로 만 드 는 규칙 을 말 합 니 다.이곳 의 키 워드 는 범위 가 매우 넓 고 무한 집합 으로 볼 수 있 습 니 다.무한 집합 의 원 데이터 가 주소 로 만 들 때 중복 되 지 않도록 어떻게 보장 합 니까?규칙 자체 가 이 목적 을 실현 할 수 없다.예 를 들 어,여전히 학급 학우 들 을 비유 하 는데,현재 아래 와 같은 학우 데이터 가 있다.
장삼,이사,왕 오,조 강,오 로....
만약 에 우리 가 주소 지정 규칙 이 성씨 의 성 을 가 진 이니셜 을 알파벳 의 상대 적 인 위치 에서 주소 로 한다 면 다음 과 같은 해시 표 가 생 길 것 이다.
위치.
자모
성명.
0
a
1
b
2
c
...
10   
L    
이사
...
22
W
왕 오 로
..
25 
Z 
장삼
우 리 는 회색 배경 이 표 시 된 두 줄 안에 키워드 왕 오,오 로 가 같은 위치 로 편집 되 었 고 키워드 장 삼,조 강도 같은 위치 로 편집 되 었 다 는 것 을 알 게 되 었 다.선생님 께 서 다시 번 호 를 가지 고 장 삼 을 찾 아 오 세 요.자리 에 두 사람 이 있 습 니 다."너희 둘 은 누가 장 삼 이 니?"
2)충돌 문 제 를 어떻게 해결 할 것 인가
충돌 을 피 할 수 없 는 이상 충돌 을 어떻게 해결 할 것 인 가 는 분명 추가 적 인 절차 가 필요 하 다.이러한 절 차 를 통 해 더 많은 규칙 을 제정 하여 키워드 집합 을 관리 합 니 다.일반적인 방법 은 다음 과 같 습 니 다.
a)오픈 주소 법
개방 적 인 법 집행 에는 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 수치 가 가짜 랜 덤 수열 일 수 있 습 니 다.위조 랜 덤 탐지 재 산열.여전히 학생 번 호 를 예 로 들 면,
현재 두 명의 학우 가 있 는데,이사,오용 이다.이사 와 오용 은 사전에 이미 서열 을 정 했 는데,지금 새로 온 학우 가 있 는데,이름 은 왕 오 라 고 하 는데,이 를 편제 한다
10..
....
22
..
..
25
이사..
....
오용
..
..
25
조 강 미래 전에
10..
..
22
23
25
이사..
오용
왕 오
 
(a)선형 탐측 재 산열 은 조 강 에 대해 주 소 를 편집 하고 di=1
10...
20
22
..
25
이사..
왕 오
오용
(b)2 차 탐지 재 산열,그리고 di=-2
1...
10...
22
..
25
왕 오..
이사..
오용
(c)위 랜 덤 탐지 재 산열,위 랜 덤 서열 은 5,3,2 이다.
b)재 해시 법
충돌 이 발생 했 을 때 충돌 이 없 을 때 까지 두 번 째,세 번 째,해시 함수 로 주 소 를 계산 합 니 다.단점:계산 시간 증가.
예 를 들 어 위 에서 처음으로 성 이니셜 에 따라 하 쉬 를 진행 하 는데 충돌 이 생기 면 성 이니셜 두 번 째 에 따라 하 쉬 를 진행 하고 충돌,세 번 째 는 충돌 하지 않 을 때 까지 할 수 있다.
c)체인 주소 법
모든 키 워드 를 동의어 로 기록 하 는 것 을 같은 선형 링크 에 저장 합 니 다.다음 과 같다.

그래서 이런 방법 은 통안 통 이 라 고 비슷 하 게 볼 수 있다.
d)공공 넘 침 구역 만 들 기
해시 함수 의 값 영역 이[0,m-1]이 라 고 가정 하면 벡터 HashTable[0.m-1]을 기본 표 로 하고 저장 공간 벡터 OverTable[0.v]를 설치 하여 충돌 이 발생 한 기록 을 저장 합 니 다.
이상 의 방법 을 통 해 기본적으로 hash 알고리즘 충돌 문 제 를 해결 할 수 있 습 니 다.
주:hash 를 간단하게 소개 한 이 유 는 lzw 알고리즘 을 잘 배우 기 위해 서 입 니 다.lzw 알고리즘 을 배 우 는 것 은 gif 파일 구 조 를 잘 연구 하기 위해 서 입 니 다.마지막 으로 저 는 gif 파일 이 어떻게 구성 되 고 이런 유형의 파일 을 어떻게 효율적으로 조작 하 는 지 상세 하 게 논술 하 겠 습 니 다.
이상 이 바로 본문의 전체 내용 입 니 다.여러분 께 참고 가 될 수 있 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.