해시는 레코드의 저장 위치와 해당 키워드 사이에 특정 대응 관계를 설정하여 각 키워드 키가 저장 위치 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이 될 때까지 공석이 있습니다. 아래 표에 나와 있습니다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 0 | 11 | |
12 | 25 |
16 |
67 |
56 | |
위 내용은 데이터 구조에서 해시 테이블(해시 테이블)의 일반적인 충돌 처리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!