데이터 구조에서 해시 테이블(해시 테이블)의 일반적인 충돌 처리

해시는 레코드의 저장 위치와 해당 키워드 사이에 특정 대응 관계를 설정하여 각 키워드 키가 저장 위치 f(키)에 해당하고 키워드와 저장 위치 간의 상호 대응을 설정하는 것입니다. 관계 f를 해시 함수(hash function)라고 합니다. 이 기사의 편집자는 주로 해시 함수의 충돌 처리 문제에 대해 이야기합니다.

충돌 횟수에 따라 키 코드 비교 횟수가 달라집니다. 충돌이 적게 발생하면 검색 효율성이 높아집니다. 낮추다. 따라서 충돌 횟수에 영향을 미치는 요소는 검색 효율성에 영향을 미치는 요소입니다. 다음 세 가지 요소가 충돌 횟수에 영향을 미칩니다.

2. 충돌 처리 방법

3.

해시 테이블의 채우기 요소는 다음과 같이 정의됩니다. α = 테이블에 채워진 요소 수 / 해시 테이블의 길이

α는 해시 테이블의 채우기 정도에 대한 부호 요소입니다. 테이블 길이는 고정된 값이므로 α는 "테이블에 채워지는 요소 수"에 비례합니다. 따라서 α가 클수록 테이블에 채워지는 요소가 많아지고 충돌 가능성이 작아집니다. α, 테이블에 채우는 요소 수가 적을수록 충돌이 발생할 가능성이 줄어듭니다.

사실 해시 테이블의 평균 검색 길이는 채우기 요소 α의 함수이지만 충돌을 처리하는 방법에 따라 기능도 다릅니다.

해시 충돌을 해결하는 방법은 일반적으로 다음과 같습니다.

NO.1 개방형 주소 지정 방법

소위 개방형 주소 지정 방법은 일단 충돌이 발생하면 해시 테이블이 큰 한 다음 빈 해시 주소를 검색하는 것입니다. 충분하면 해시 주소를 항상 찾을 수 있으며 레코드가 저장됩니다.

공식: f(key)=(f(key)+di)%m(di=1,2,3….m-1)

예를 들어 키워드 세트는 {12, 67, 56, 16 , 25, 37, 22, 29, 15, 47, 48, 34}, 테이블 길이는 12입니다. 해시 함수 f(key) = 키 mod 12.

처음 5개 숫자 {12, 67, 56, 16, 25}를 계산하면 모두 충돌 없는 해시 주소이며 키 = 37을 계산하면 f(37) = 1인 것으로 확인됩니다. 이번에는 25의 위치와 충돌합니다. 따라서 위 공식 f(37) = (f(37) + 1) mod 12 =2를 적용합니다. 따라서 37은 인덱스 2의 위치에 저장됩니다. 다음 22, 29, 15, 47은 충돌이 없어 정상적으로 입금됩니다. 48에서 우리는 f(48) = 0으로 계산했는데 이는 12의 0 위치와 충돌합니다. 상관없습니다. f(48) = (f(48) + 1) mod 12 = 1이며 이제 충돌합니다. 25. 입장을 가지고 갈등을 빚는다. 따라서 f(48) = (f(48) + 2) mod 12 = 2, 여전히 충돌이 있습니다... f(48) = (f(48) + 6) mod 12 = 6이 될 때까지 공석이 있습니다. 아래 표에 나와 있습니다.

일련번호키워드

NO.2 재해시 방법

해시 테이블의 경우 여러 해쉬 함수를 미리 준비할 수 있습니다.

공식: fi(key)=RHi(key)(i=1,2,3...,k)

여기서 RHi는 다른 해시 함수입니다. 나머지 남기기, 접기, 사각형 찾기를 제외한 모든 기능을 사용할 수 있습니다. 해시 주소 충돌이 발생할 때마다 다른 해시 함수가 계산에 사용됩니다.

이 방법을 사용하면 키워드 집계를 방지할 수 있지만 그에 따라 계산 시간도 늘어납니다.

NO.3 체인 주소 방식(zipper 방식)

키워드가 포함된 모든 레코드를 동의어로 단일 연결 리스트에 저장하는 이런 종류의 테이블을 동의어라고 합니다. 하위 테이블의 경우 모든 동의어 하위 테이블 앞의 포인터만 해시 테이블에 저장됩니다. 키워드 세트 {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}에 대해 이전과 동일한 나머지로 12를 사용하고 나누기와 나머지 방법을 수행하여 구조를 얻습니다. 아래에.

NO.4 공개 오버플로 영역 설정

이 방법은 모든 충돌하는 키워드에 대한 주소를 다시 찾는 것입니다. 저장을 위한 공통 오버플로 영역을 만듭니다.

이전 예시의 경우 이전 키워드 위치와 충돌하는 키워드 37, 48, 34가 있으므로 오버플로 테이블에 저장합니다. 아래 그림과 같습니다.

검색 시에는 해시 함수를 통해 주어진 값의 해시 주소를 계산한 후 기본 테이블의 해당 위치와 먼저 비교하게 됩니다. 동일하면 검색이 성공하고, 동일하지 않으면 오버플로 테이블에서 순차 검색이 수행됩니다. 기본 테이블에 비해 충돌하는 데이터가 거의 없다면 공용 오버플로 영역의 구조는 검색 성능에 있어 여전히 매우 높습니다.

【추천 강좌: C++ 관련 강좌】

0	1	2	3	4	5	6	7	8	9	1 0	11
12	25			16			67	56

위 내용은 데이터 구조에서 해시 테이블(해시 테이블)의 일반적인 충돌 처리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!