매일 사용하세요! HASH가 무엇인지 아시나요?

HashMap을 사용해 본 적이 있나요? 해시가 무엇인지 진지하게 이해하셨나요? 이 기사에서는 원리 수준에서 해시 알고리즘에 대한 심층적인 연구를 안내합니다.

1. 해싱의 개념

해싱 방법의 주요 아이디어는 노드의 키 코드 값을 기반으로 저장 주소를 결정하는 것입니다. 특정 함수 관계 h(K )(해시 함수라고 함)를 사용하여 해당 함수 값을 계산하고 이 값을 노드의 저장 주소로 해석하고 이 저장 장치에 노드를 저장합니다. 검색할 때에도 동일한 방법으로 주소를 계산한 후 해당 유닛으로 이동하여 원하는 노드를 가져옵니다. 해싱을 통해 노드를 빠르게 검색할 수 있습니다. 해시("해시"라고도 함)는 중요한 저장 방법이자 일반적인 검색 방법입니다.

해시 저장 방식에 따라 구성된 저장 구조를 해시 테이블이라고 합니다. 해시 테이블의 위치를 ​​슬롯이라고 합니다. 해싱 기술의 핵심은 해시 함수입니다. 주어진 동적 조회 테이블 DL에 대해 "이상적인" 해시 함수 h와 해당 해시 테이블 HT가 선택되면 DL의 각 데이터 요소 X에 대해 선택됩니다. 함수 값 h(X.key)는 해시 테이블 HT에서 X의 저장 위치입니다. 데이터 요소 X는 삽입(또는 테이블 생성) 시 이 위치에 배치되고, X를 검색할 때도 이 위치에서 검색됩니다. 해시 함수에 의해 결정된 저장 위치를 ​​해시 주소라고 합니다. 따라서 해싱의 핵심은 해시 함수가 키 코드 값(X.key)과 해시 주소 h(X.key) 간의 대응 관계를 결정하는 것입니다. 이 관계를 통해 조직적인 저장 및 검색이 실현됩니다.

일반적으로 해시 테이블의 저장 공간은 1차원 배열 HT[M]이며, 해시 주소는 배열의 첨자입니다. 해싱 방법을 설계하는 목적은 키 값 K에 대해 특정 해시 함수 h, 0

2. 해시 함수

다음 논의에서는 값이 정수인 키 코드를 다룬다고 가정합니다. 그렇지 않으면 키 코드와 양의 정수 사이에 항상 일대일 대응이 가능합니다. 키 검색을 해당 양의 정수 검색으로 동시에 변환하려면 해시 함수의 값이 0과 M-1 사이에 있다고 가정합니다. 해시 함수를 선택하는 원칙은 다음과 같습니다. 작업은 가능한 한 간단합니다. 함수의 값 범위는 해시 테이블의 범위 내에 있어야 합니다. 즉, 노드를 최대한 균등하게 분산해야 합니다. 키에는 서로 다른 해시 함수 값이 있습니다. 키 길이, 해시 테이블 크기, 키 분포, 레코드 검색 빈도 등 다양한 요소를 고려해야 합니다. 아래에서는 일반적으로 사용되는 몇 가지 해시 함수를 소개합니다.

1. 나머지 나누기 방법

이름에서 알 수 있듯이 나머지 방법은 키 코드 x를 M(종종 해시 테이블의 길이를 취함)으로 나누고 나머지를 해시 주소로 사용하는 것입니다. 나머지 방법은 거의 가장 간단한 해싱 방법이며 해시 함수는 h(x) = x mod M입니다.

2. 곱셈 나머지 반올림 방법

이 방법을 사용하는 경우 먼저 키 코드에 상수 A(0< A < 1)를 곱한 후 제품의 소수 부분을 추출합니다. 그런 다음 이 값에 정수 n을 곱하고 그 결과를 반올림하여 해시 주소로 사용합니다. 해시 함수는 다음과 같습니다. hash (key) = _LOW(n × (A × key % 1)). 그 중 "A × 키 % 1"은 A × 키의 소수 부분을 취한다는 의미입니다. 즉, A × 키 % 1 = A × 키 - _LOW(A × 키), _LOW(X)는 정수 부분을 취한다는 의미입니다. of X

3. 제곱법

정수 나누기는 일반적으로 곱셈보다 느리게 실행되므로 의식적으로 나머지 연산의 사용을 피하면 해시 알고리즘의 실행 시간이 향상될 수 있습니다. square-middle 방법의 구체적인 구현은 먼저 키 코드의 제곱 값을 찾아 유사한 숫자 간의 차이를 확장한 다음 테이블 길이에 따라 중간 숫자(종종 이진 비트)를 해시 함수로 취하는 것입니다. 값. 제품의 중간 숫자는 승수의 각 숫자와 관련되어 있으므로 결과 해시 주소가 더 균일합니다.

4. 수치 분석 방법

키워드 집합의 각 키워드는 s자리(u1, u2, …, us)로 구성되어 있다고 가정하고, 전체 키워드 집합을 분석하고, 균등하게 분포된 여러 개를 추출합니다. 비트 또는 그 조합을 주소로 사용합니다. 디지털 분석 방법은 데이터 요소 키워드 중 상대적으로 균일한 값을 갖는 일부 디지털 비트를 해시 주소로 취하는 방법이다. 즉, 키워드의 자릿수가 많은 경우 키워드의 비트를 분석하여 불균등하게 분포된 비트를 해시 값으로 버릴 수 있습니다. 키워드 값을 모두 알고 있는 경우에만 적합합니다. 분포를 분석하면 키워드 값 범위가 더 작은 키워드 값 범위로 변환됩니다.

예: 데이터 요소 수 n=80, 해시 길이 m=100으로 해시 테이블을 구성합니다. 일반성을 잃지 않고 여기서는 분석을 위해 8개의 키워드만 제공합니다. 8개의 키워드는 다음과 같습니다. 1394220

위 8개 키워드를 분석한 결과, 키워드의 왼쪽부터 1, 2, 3, 6번째 숫자의 값이 상대적으로 밀집되어 있어 나머지 4, 5번째, 7번째, 8비트 값은 상대적으로 짝수이고, 그 중 2개를 해시 주소로 선택할 수 있다. 마지막 두 자리가 해시 주소로 선택되었다고 가정하면 이 8개 키워드의 해시 주소는 2, 75, 28, 34, 15, 38, 62, 20입니다.

이 방법은 다음과 같은 경우에 적합합니다. 모든 키워드의 각 숫자에서 다양한 숫자의 발생 빈도를 미리 예측할 수 있습니다.

5. 베이스 변환 방법

키 코드 값을 다른 베이스의 숫자로 처리한 후 원래 베이스의 숫자로 변환한 후 그 중 몇 개를 해시 주소로 선택합니다. 예제 해시(80127429)=(80127429)13=8137+0136+1135+2134+7133+4132+2*131+9=(502432641)10 가운데 세 자리를 해시값으로 하면 Hash가 됩니다. (80127429) =432 좋은 해시 함수를 얻으려면 먼저 베이스를 변경한 다음 접거나 제곱하는 등 여러 가지 방법을 조합하여 사용할 수 있습니다. 해시가 균일한 한 마음대로 함께 모을 수 있습니다.

6. 접는 방법

때때로 키 코드에 자릿수가 많아 제곱법을 사용하여 계산하기가 너무 복잡하면 키 코드를 같은 자릿수로 여러 부분으로 나눌 수 있습니다. 마지막 부분의 자릿수는 다를 수 있음) 그런 다음 이러한 부분의 중첩 합계(캐리 삭제)를 해시 주소로 사용합니다. 이 방법을 접기 방법이라고 합니다. 는 다음과 같이 나누어집니다.

이동 중첩: 나누어진 부분의 낮은 비트를 정렬하고 추가합니다.

• 테두리 중첩: 구분선을 따라 한쪽 끝에서 앞뒤로 접은 다음 정렬하고 추가합니다.
3. 충돌 해결 전략

해시 함수의 목표는 충돌을 최소화하는 것이지만 실제로 충돌은 피할 수 없습니다. 그러므로 우리는 갈등 해결 전략을 살펴보아야 합니다. 충돌 해결 기술은 개방형 해싱(지퍼링, 별도 체인이라고도 함)과 폐쇄형 해싱(폐쇄형 해싱, 개방형 주소 지정이라고도 함)의 두 가지 범주로 나눌 수 있습니다. 이 두 가지 방법의 차이점은 개방형 해싱 방법은 충돌 키를 기본 해시 테이블 외부에 저장하는 반면, 폐쇄형 해싱 방법은 충돌 키를 테이블의 다른 슬롯에 저장한다는 것입니다.

1. 분리된 연결 리스트 방식

(1) 지퍼 방식

해시 테이블의 각 슬롯을 연결 리스트의 선두로 정의하는 간단한 형태입니다. 특정 슬롯에 해시된 모든 레코드는 해당 슬롯에 대한 연결 목록에 저장됩니다. 그림 9-5는 각 슬롯이 레코드와 연결된 목록의 나머지 부분에 대한 포인터를 저장하는 개방형 해시 테이블을 보여줍니다. 이 7개의 숫자는 11개의 슬롯이 있는 해시 테이블에 저장되며 사용되는 해시 함수는 h(K) = K mod 11입니다. 숫자의 삽입 순서는 77, 7, 110, 95, 14, 75, 62입니다. 슬롯 0에 2개의 값이 해시되고, 슬롯 3에 1개의 값이 해시되고, 슬롯 7에 3개의 값이 해시되고, 슬롯 9에 1개의 값이 해시됩니다.

2. 폐쇄형 해싱 방식(개방 주소 방식)

폐쇄형 해싱 방식은 모든 레코드를 해시 테이블에 직접 저장합니다. 각 레코드 키 키에는 해시 함수, 즉 h(key)로 계산된 기본 위치가 있습니다. 키를 삽입해야 하고 다른 레코드가 이미 R의 기본 위치를 차지하고 있는 경우(충돌 발생) R은 테이블의 다른 주소에 저장되며 충돌 해결 정책에 따라 그것이 어떤 주소인지 결정됩니다.

닫힌 해시 테이블 충돌 해결의 기본 아이디어는 충돌이 발생할 때 특정 방법을 사용하여 키 K에 대한 해시 주소 시퀀스 d0, d1, d2,...di,...dm-1을 생성하는 것입니다. . 그 중 d0=h(K)를 K의 기본 주소 홈 위치라고 하며, 모든 di(0

프로브를 형성하는 다양한 방법은 갈등을 해결하는 다양한 방법으로 이어집니다. 다음은 몇 가지 일반적인 건설 방법입니다.

(1) 선형 탐지 방법

은 해시 테이블을 링 테이블로 간주합니다. 기본 주소 d(예: h(K)=d)에서 충돌이 발생하면 다음 주소 단위가 순차적으로 검색됩니다. +1 , d+2,...,M-1,0,1,...,d-1 빈 주소를 찾거나 키 코드가 있는 노드를 찾을 때까지. 물론, 프로빙 시퀀스를 따라 검색한 후 d번지로 돌아오면 삽입 연산을 하든, 검색 연산을 하든 실패를 의미한다. 단순 선형 프로브의 프로브 함수는 다음과 같습니다. p(K,i) = i

예 9.7 키 코드 세트는 (26, 36, 41, 38, 44, 15, 68, 12, 06, 51, 25)이고 해시 테이블의 길이는 M = 15인 것으로 알려져 있으며 선형을 사용합니다. 충돌을 해결하고 키의 해시 테이블 세트를 구성하는 탐색 방법입니다. n=11이므로 나머지 방법을 사용하여 해시 함수를 구성하고 M보다 작은 가장 큰 소수 P=13을 선택합니다. 그러면 해시 함수는 h(key) = key%13입니다. 각 노드를 순서대로 삽입합니다: 26: h(26) = 0, 36: h(36) = 10, 41: h(41) = 2, 38: h(38) = 12, 44: h(44) = 5 . 15가 삽입되면 해당 해시 주소는 2입니다. 2는 이미 키 코드 41을 가진 요소에 의해 점유되어 있으므로 프로브가 필요합니다. 순차 프로빙 방식에 따르면 3은 개방형 자유 주소임이 분명하므로 유닛 3에 배치할 수 있다. 마찬가지로 68과 12는 각각 단위 4와 13에 배치될 수 있습니다.

(2) 2차 탐색 방법

2차 탐색 방법의 기본 아이디어는 다음과 같습니다. 생성된 후속 해시 주소는 연속적이지 않지만 점프됩니다. 집계를 줄이기 위해 후속 데이터 요소를 위한 공간을 남겨 둡니다. 2차 탐지 방법의 탐지 순서는 12, -12, 22, -22,... 등이다. 즉, 충돌이 발생하면 동의어가 첫 번째 주소의 양쪽 끝에서 앞뒤로 해싱된다. 다음 열린 주소를 찾는 공식은 다음과 같습니다.

(3) 무작위 프로빙 방법

이상적인 프로빙 기능은 프로빙 시퀀스에서 방문하지 않은 슬롯에서 다음 위치를 무작위로 선택해야 합니다. 즉, 프로브 시퀀스는 해시 테이블 위치의 무작위 순열이어야 합니다. 그러나 키를 검색할 때 동일한 프로브 시퀀스를 설정할 수 없기 때문에 실제로 프로브 시퀀스에서 위치를 무작위로 선택할 수 없습니다. 그러나 의사 무작위 조사와 같은 작업을 수행할 수 있습니다. 의사 무작위 프로브에서 프로브 시퀀스의 i번째 슬롯은 (h(K) + ri) mod M입니다. 여기서 ri는 1과 M - 1 사이의 "무작위" 숫자 시퀀스입니다. 모든 삽입과 검색은 동일한 "임의" 숫자를 사용합니다. 프로브 함수는 p(K,i) = perm[i - 1]입니다. 여기서 perm은 1부터 M - 1까지의 값의 무작위 시퀀스를 포함하는 길이 M - 1의 배열입니다.

예:

예를 들어 알려진 해시 테이블 길이가 m=11이고 해시 함수는 다음과 같습니다. H(키) = 키 % 11, 그러면 H(47) = 3, H(26) = 4, H(60) )=5, 다음 키워드가 69라고 가정하면 H(69)=3, 이는 47과 충돌합니다. 선형 감지와 해싱을 사용하여 충돌을 처리하는 경우 다음 해시 주소는 H1=(3 + 1)% 11 = 4입니다. 여전히 충돌이 있는 경우 다음 해시 주소는 H2=(3 + 2)% 11입니다. = 5. , 여전히 충돌이 있습니다. H3 = (3 + 3)% 11 = 6으로 다음 해시 주소를 계속 찾으십시오. 이때 더 이상 충돌이 없습니다. 단위 5에 69를 채우십시오. 그림 8.26(a)을 참조하십시오. ). 충돌을 처리하기 위해 2차 감지 및 해싱을 사용하는 경우 다음 해시 주소는 H1=(3 + 12)% 11 = 4입니다. 여전히 충돌이 있으면 다음 해시 주소 H2=(3 - 12)% 11 =를 찾으십시오. 2. 현재로서는 충돌이 없습니다. 69를 장치 2에 채우십시오. 그림 8.26 (b)를 참조하십시오. 의사 난수 탐지와 해싱을 사용하여 충돌을 처리하고 의사 난수 시퀀스가 ​​2, 5, 9,…..인 경우 다음 해시 주소는 H1 = (3 + 2)% 11 = 5, 여전히 충돌이 있는 경우 H2 = (3 + 5)% 11 = 8로 다음 해시 주소를 찾습니다. 이때 더 이상 충돌이 없습니다. 유닛 8에 69를 채웁니다. 그림 8.26 (c)를 참조하세요.

(4)이중 해시 감지 방법

의사 무작위 프로빙과 2차 프로빙 모두 기본 집계 문제, 즉 기본 주소가 다른 키 코드와 프로빙 시퀀스의 특정 세그먼트가 겹치는 문제를 제거할 수 있습니다. 그러나 두 키가 동일한 기본 주소로 해시되는 경우 두 방법을 모두 사용하여 동일한 프로브 시퀀스를 얻을 수 있으며 집계가 계속 발생합니다. 의사 랜덤 프로빙과 2차 프로빙에 의해 생성된 프로빙 시퀀스는 원래 키 값의 함수가 아니라 기본 주소의 함수일 뿐이기 때문입니다. 이 문제를 보조 클러스터링이라고 합니다.

2차 집계를 방지하려면 프로브 시퀀스를 기본 위치의 함수가 아닌 원래 키 값의 함수로 만들어야 합니다. 이중 해시 검출 방법은 두 번째 해시 함수를 상수로 사용하고, 매번 상수항을 건너뛰고 선형 검출을 수행하는 방식입니다.

위 내용은 매일 사용하세요! HASH가 무엇인지 아시나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!