데이터 구조 해시 테이블(해시 테이블)이란 무엇입니까? 구체적인 작업은 무엇입니까?

1. 해시 테이블이란 무엇입니까

해시 테이블이 무엇인지 알고 싶다면 먼저 해시 함수를 이해해야 합니다

해시 함수:

논의된 이진 정렬 트리와 이진 균형 트리를 비교해 보세요. 이전 블로그 Red-black tree B B+ tree에서는 검색이 루트 노드부터 시작하여 해당 노드에서 데이터나 인덱스를 꺼내어 검색 값과 비교합니다. 그럼 H라는 함수가 있는 걸까요? 이 함수와 검색 키워드 키를 바탕으로 일일이 비교하지 않고 검색값의 위치를 ​​바로 알아낼 수 있는 것입니다. 이런 방식으로 키의 위치를 ​​미리 '알' 수 있고, 데이터를 직접 찾아 효율성을 높일 수 있다.

즉, 주소 인덱스 = H(키)

직설적으로 말하면 해시 함수는 키를 기반으로 주소가 저장되어야 할 위치를 계산하고, 해시 테이블은 해시 함수를 기반으로 구축된 조회 테이블입니다.

이 , 해시 함수 구성 방법

이전 경험을 토대로 일반적으로 사용되는 해시 함수의 구성 방법은 다음과 같습니다.

직접 사용자 정의 방법

해시 함수는 키워드(키) = a*key+b인 H와 같은 선형 함수

이 구성 방법은 비교적 간단하고 획일적이지만 주소 크기 = 키워드 세트인 경우에 한해 한계가 크다

사용 예 :

중국 인구 분포의 나이를 10을 가장 작은 단위로 계산해야 한다고 가정해 보겠습니다. 올해는 2018년이므로 10세 미만은 2008~2018년에 분포하고, 20세 미만은 1998~2008년에 분포합니다... 2018년이 2018~2008년의 직접 데이터를 나타낸다고 가정하면 키워드는 다음과 같습니다. 2018, 2008, 1998...

그러면 해시 함수 H(key)=(2018-key)/10=201-key/10을 구성할 수 있습니다.

그러면 해시 테이블은 다음과 같이 구성됩니다

인덱스 키 연령 인원수(가정자료)

0 2018 0-10 200W

1 2008 10-20 250W

2 1998 20-30 253W

3 1988 30-40 300W

......

숫자 분석 방법
키워드 집합의 각 키워드 키가 s자리 숫자(k1, k2,..., knk1, k2,..., kn)로 구성된다고 가정하고 키에 포함된 전체 데이터를 분석하고, 균등하게 분포된 여러 숫자 또는 그 조합을 추출하여 전체를 구성합니다.

사용 예

ID 번호가 규칙적이라는 것을 알고 이제 학급의 학생들의 ID 번호를 저장하려고 합니다. 이 클래스의 학생들이 모두 태어났다고 가정합니다. 같은 지역, 같은 연도에 ID 카드의 첫 번째 숫자가 동일하면 다음과 같은 다른 비트를 가로채서 저장할 수 있습니다. 5개의 다른 비트가 있다고 가정하면 이 5개의 비트를 사용하여 주소를 나타낼 수 있습니다.

H(key)=key%100000

이 방법은 일반적으로 숫자에 일정한 패턴이 있어야 하고, 숫자의 분포를 알아야 합니다. 위의 예를 통해 우리는 사전에 학생들이 같은 해, 같은 지역에서 태어났다는 것을 알고 있습니다.

제곱의 방법

키워드의 각 자리에 특정 숫자가 자주 등장한다면, 먼저 키워드의 제곱 값을 구하고, 제곱으로 그 차이를 확장한 후, 가운데 숫자를 최종 저장 주소로 삼으면 됩니다.

사용 예

예를 들어 key=1234 1234^2=1522756, 해시 주소로 227을 사용

예를 들어, key=4321 4321^2=18671041, 해시 주소로 671을 사용

이 방법이 적합합니다. 미리 알 수 없는 데이터이고 데이터 길이가 긴 경우 작은 경우

접는 방법
숫자의 자릿수가 많으면 숫자를 여러 부분으로 나누어 중첩 합을 해시 주소로 사용할 수 있습니다
사용 예
예를 들어 key=123 456 789
61524에 저장할 수 있고, 마지막 세 자리를 취하면 위치는 524입니다.
이 방법은 숫자가 많고 데이터 분포를 미리 알 수 없는 상황에 적합합니다.

나머지 방법을 자주 사용합니다.
H(key) = key MOD p(p물론 p를 어떻게 선택하느냐가 핵심 문제입니다.

사용 예

예를 들어, 3 6 9를 저장하면 p는 3이 될 수 없습니다.

왜냐하면 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p는 m보다 크지 않은 소수이거나 20을 포함하지 않음 다음 소인수 조합은 주소의 중복(충돌)을 줄일 수 있습니다

예를 들어 키 = 7, 39, 18, 24, 33, 21일 때 테이블 길이 m을 9로, p를 다음과 같이 취합니다. 7, 다음과 같이 저장합니다

난수 방식
H(key) =Random(key)
키워드의 랜덤 함수 값을 해시 주소로 사용

해시 함수 설계 시 고려 사항

1. 해시 주소를 계산하는 데 필요한 시간(즉, 해시 함수 자체가 너무 복잡하면 안 됩니다)
2. 테이블 길이
4. 키워드 분포가 균등한지, 따라야 할 규칙이 있나요?
5. 위의 조건이 충족되면 충돌을 최소화하도록 설계되었습니다.

3. 해시 충돌

즉, 키 값이 다릅니다. ​​동일한 주소를 생성합니다. H(key1) = H(key2)

예를 들어 위에서 언급한 대로 3 6 9를 저장하면 p는 3을
3 MOD 3 == 6 MOD 3 == 9 MOD 3
At로 취합니다. 이번에는 3 6 9 모두 해시 충돌이 있습니다

해시 충돌 해결 솔루션

해시 함수가 아무리 영리하게 설계되었더라도 항상 해시 충돌을 일으키는 특수 키가 있을 것입니다. 특히 동적 조회 테이블의 경우 더욱 그렇습니다.

해시 함수에는 다음과 같은 충돌 해결 방법이 있습니다.

1. 개방형 사용자 정의 방법

2. 체인 주소 방법

3. 충돌하는 데이터를 저장합니다. 이 방법은 데이터가 적고 충돌이 적은 상황에 적합합니다.

4. 재해시 방법

여러 가지 해시 함수를 준비하세요. 첫 번째 해쉬 함수 사용 시 충돌이 발생하면 두 번째 해쉬 함수도 사용하세요.. 집중하세요. 오픈 커스터마이징 방식과 체인 주소 방식

오픈 커스터마이징 방식

먼저 H(key)의 해시 함수가 있습니다

H(key1) = H(keyi)

그러면 keyi 저장 위치 Hi = ( H( key)+di)MODmHi=(H(key)+di)MODmm은 테이블 길이입니다.

참고

increment di는 다음 특성(완전성)을 가져야 합니다. 생성된 Hi(주소)는 동일하지 않습니다. 그리고 생성된 s(m-1) Hi는 해시 테이블의 모든 주소를 포함할 수 있습니다.

* 제곱 감지 중에 테이블 길이 m은 4j+3의 소수여야 합니다(제곱 감지 테이블 길이는 제한됨)

* 무작위 탐지 m과 di가 공통 인수가 없는 경우(di의 무작위 탐지에는 제한이 있음)

세 가지 개방형 주소 지정 방법에 대한 충돌 해결 솔루션의 예

일련의 데이터가 있습니다 19 01 23 14 55 68 11 86 37 테이블 길이 11에 저장됩니다. 배열에서 H(키) = 키 MOD 11

그러면 위의 세 가지 충돌 해결 방법에 따라 저장 프로세스는 다음과 같습니다.

(테이블 설명: 데이터를 앞에서부터 끝까지 삽입합니다. 삽입 위치가 이미 점유된 경우 충돌이 발생합니다. 충돌이 있으면 새 줄을 시작하고 주소를 사용할 수 있을 때까지 계속해서 새 줄을 시작합니다. 최상위 데이터(가장 많이 "점유된" 데이터이기 때문)

선형 감지 후 해싱

di=1을 취합니다. 즉, 충돌이 계속 발생하면 그 위치에 저장됩니다. , 뒤로 계속

제곱 감지 후 해싱

해시에서 무작위 감지(이중 감지 후 해싱)

충돌 후

H(key)'=(H( key)+di)MOD m 이 예에서는
H(key)=key MOD 11 di=key MOD 10 +1
을 사용하면 다음과 같은 결과가 나타납니다.

체인 주소 방식

해시 충돌이 발생한 후 저장된 데이터 뒤에 포인터를 추가하여 충돌하는 데이터를 가리킵니다.
위의 예에서 , 체인을 사용하십시오. 주소 규칙은 다음과 같습니다.

4. 해시 테이블 검색 과정

테이블 생성 프로세스와 일치하며 개방형 주소 지정 방법을 사용하여 충돌을 처리한다고 가정하면 검색 프로세스는 다음과 같습니다.

주어진 키에 대해 해시 주소 인덱스 = H(키 )

배열 arr[index]의 값이 비어 있으면 검색에 실패합니다

배열 arr[index] == 키이면 검색에 성공합니다 #🎜 🎜#

그렇지 않으면 충돌 해결 방법을 사용하여 arr[index]==key 또는 arr[index]==null

#🎜🎜 #어떤 함수를 사용하더라도 로딩 인자가 클수록, 평균 검색 길이가 클수록 로딩 인자 α는 작아지는 것을 알 수 있죠? 아니요, 테이블 길이가 100이면 하나의 데이터만 저장되는 것처럼 α는 작지만 공간 활용도는 높지 않습니다. 이는 시간과 공간의 균형입니다. 일반적으로 α=0.75는 시간과 공간을 가장 효율적으로 종합적으로 활용하는 것으로 간주됩니다.

위의 표는 특히 유용합니다. 이제 10개의 데이터가 있고 충돌을 해결하기 위해 체인 주소 방법을 사용하고 평균 검색 길이

가 필요하다고 가정합니다. 그러면 1+α/2 가 있습니다.

α

즉 n/m

m>10/2

m>5 즉, 체인 주소 방법을 사용하여 평균 검색 길이가 5

내 블로그에서 이전에 다양한 트리의 평균 검색 길이에 대해 논의한 적이 있습니다. 이는 모두 데이터 n을 저장하는 기능을 기반으로 합니다. 해시 테이블은 다릅니다. 즉, 데이터 n이 증가하면 테이블 길이 m을 늘려 로드 팩터를 변경하지 않고 ASL을 유지하도록 할 수 있습니다.

그러면 해시 테이블의 구조는 다음과 같아야 합니다.

5. 해시 테이블 삭제 #🎜 🎜#

먼저 체인 주소 방식은 요소를 직접 삭제할 수 있지만 개방형 주소 지정 방식은 이전의 이중 감지 및 해싱을 예로 들어 요소 1을 삭제하면 해당 요소가 삭제됩니다. position 공백으로 두면 23을 찾을 수 없습니다. 올바른 접근 방식은 -1과 같이 존재하지 않는 데이터를 삭제하기 전에 삽입하는 것입니다.

관련 질문이 더 필요하시면 PHP 중국어 웹사이트를 방문하세요:

PHP 실용 동영상 튜토리얼

위 내용은 데이터 구조 해시 테이블(해시 테이블)이란 무엇입니까? 구체적인 작업은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!