산 목록 (해시 해시 해시) 초기

1. 머리말 
       해시 표 (Hash Table) 는 효율 적 인 데이터 구조 로 서 중요 한 역할 을 하고 있다. 해시 표 의 가장 큰 장점 은 데이터 의 저장 과 찾기 소모 시간 을 크게 줄 이 고 거의 상수 시간 으로 볼 수 있다 는 것 이다.대 가 는 비교적 많은 메모 리 를 소모 하 는 것 에 불과 하 다.그러나 현재 메모리 가 점점 많아 지 는 상황 에서 공간 으로 시간 을 바 꾸 는 것 은 가치 가 있다.또 인 코딩 이 쉬 운 것 도 특징 이다. 
       해시 표 는 산 목록 이 라 고도 부 르 는데 '산 열 열기' 와 '산 열 닫 기' 로 나 뉜 다.다수의 사람들 이 동적 저장 구 조 를 사용 하 는 것 을 피 하 는 것 을 감안 하면 본 고의 '해시 표' 는 '폐 산열' 만 가리킨다.
2. 기초 조작 
2.1 기본 원리 
       우 리 는 아래 표 시 된 범위 가 비교적 큰 배열 을 사용 하여 요 소 를 저장 합 니 다.하나의 함수 (해시 함수, 해시 함수 라 고도 함) 를 설계 하여 모든 요소 의 키 워드 를 하나의 함수 값 (즉, 배열 아래 표) 과 대응 하 게 할 수 있 습 니 다. 그래서 이 배열 유닛 으로 이 요 소 를 저장 합 니 다.또한 키워드 에 따라 모든 요소 로 '분류' 한 다음 에 이 요 소 를 해당 하 는 '클래스' 에 저장 하 는 것 으로 간단하게 이해 할 수 있다. 
그러나 각 요소 의 키워드 와 함수 값 이 일일이 대응 하 는 것 을 보장 할 수 없 기 때문에 서로 다른 요소 에 대해 똑 같은 함수 값 을 계산 할 가능성 이 높다. 그러면 '충돌' 이 생 긴 다. 다시 말 하면 서로 다른 요 소 를 똑 같은 '클래스' 로 나 누 는 것 이다.뒤에 우 리 는 충돌 을 해결 하 는 간편 한 방법 을 볼 수 있 을 것 이다. 
전체적으로 말 하면 '직접 주소 지정' 과 '충돌 해결' 은 하 쉬 표 의 두 가지 특징 이다. 
2.2 함수 구조 
       구조 함수 의 상용 방법 (다음은 간결 함 을 서술 하기 위해 h (k) 를 설정 하여 키 워드 를 k 로 표시 하 는 요소 에 대응 하 는 함수 값): 
a) 나머지 나 누 기: 
       적당 한 정수 p 를 선택 하여 h (k) = k mod p 를 선택 하 십시오. 여기 서 p 는 비교적 큰 소 수 를 선택 하면 효과 가 좋 습 니 다.그리고 이 법 은 실현 되 기 쉬 워 가장 많이 사용 되 는 방법 이다. 
b) 숫자 선택 방법: 
       만약 에 키워드 의 자릿수 가 비교적 많 고 긴 정형 범 위 를 초과 하여 직접 연산 할 수 없다 면 그 중에서 숫자 분포 가 비교적 고 른 몇 개의 위 치 를 선택 하여 구 성 된 새로운 값 을 키워드 로 하거나 함수 값 으로 직접 할 수 있다. 
2.3 충돌 처리 
       선형 재 산열 기술 은 실현 하기 쉽 고 목적 을 잘 달성 할 수 있다.배열 요소 의 개 수 를 S 로 만 들 면 h (k) 가 요 소 를 저 장 했 을 때 순서대로 탐색 (h (k) + i) mod S, i = 1, 2, 3....................................................... 
2.4 연산 지원 
       해시 표 가 지원 하 는 연산 은 주로 초기 화 (Makenull), 해시 편지 수치 연산 (h (x), 요소 삽입 (insert), 요소 찾기 (member) 가 있 습 니 다.삽 입 된 요소 의 키 워드 를 x, A 로 저장 하 는 배열 로 설정 합 니 다.초기 화 는 비교적 쉽다. 예 를 들 어:

const empty=maxlongint; //                      
p=9997; //       
procedure makenull;  
var i:integer;  
begin  
for i:=0 to p-1 do  
A[i]:=empty;  
End; 

 해시 편지 수치의 연산 은 함수 에 따라 달라 집 니 다. 예 를 들 어 나머지 를 제외 한 예 입 니 다. 

function h(x:longint):Integer;  
begin  
h:= x mod p;  
end;   

우 리 는 삽입 과 찾기 는 먼저 이 요소 에 대한 포 지 셔 닝 이 필요 하 다 는 것 을 알 게 되 었 습 니 다. 즉, 이 요소 가 존재 한다 면 어느 위치 에 저장 해 야 하 는 지 알 게 되 었 기 때문에 포 지 셔 닝 함수 locate 를 추가 합 니 다. 

function locate(x:longint):integer;  
var orig,i:integer;  
begin  
orig:=h(x);  
i:=0;  
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do  
inc(i);  
//         ，            ，         
//      ，         
locate:=(orig+i) mod S;  
end;   

요소 삽입 

procedure insert(x:longint);  
var posi:integer;  
begin  
posi:=locate(x); //          
if A[posi]=empty then A[posi]:=x  
else error; //error        ，           
end;   

요소 가 표 에 있 는 지 찾 습 니 다. 

procedure member(x:longint):boolean;  
var posi:integer;  
begin  
posi:=locate(x);  
if A[posi]=x then member:=true  
else member:=false;  
end;   

이것 이 바로 해시 표 에 세 워 진 상용 기본 연산 이다.
초보적인 결론: 
       데이터 규모 가 하 쉬 표 의 상계 나 하계 에 가 까 울 때 하 쉬 표 는 효율 적 인 특징 을 나타 내지 못 하고 심지어 일반 알고리즘 보다 못 하 다.그러나 규모 가 중앙 에 있다 면 효율 적 인 특징 을 충분히 나 타 낼 수 있다.실험 에 따 르 면 원소 가 해시 표 의 90% 를 가득 채 웠 을 때 효율 이 현저히 떨 어 지기 시작 했다.이것 은 우리 에 게 해시 표를 사용 하 는 것 이 확실 하 다 면 가능 한 한 배열 을 크게 열 어야 하지만 가장 큰 배열 을 조작 하 는 데 도 시간 이 걸 리 고 균형 점 을 찾 아야 한 다 는 것 을 알려 주 었 다.보통 그것 의 용량 은 적어도 문제 의 최대 수요 의 120% 이 고 효과 가 비교적 좋다 (이것 은 경험 일 뿐 엄격 한 증명 이 없다). 
4. 예 를 들다 
4.1 응용의 간단 한 원칙 
       해시 시 계 는 언제 적용 하기에 적합 합 니까?이 문 제 를 해결 하 는 것 을 발견 하면 '어떤 요소 가 이미 알 고 있 는 집합 에 있 습 니까?' 라 고 자주 물 어 봐 야 합 니 다. 즉, 효율 적 인 데이터 저장 과 검색 이 필요 하 다 면 해시 표를 사용 하 는 것 이 가장 좋 습 니 다!그렇다면 해시 표를 응용 하 는 과정 에서 주의해 야 할 것 은 무엇 일 까? 
해시 함수 의 디자인 은 매우 중요 하 다.좋 지 않 은 해시 함 수 는 많은 충돌 을 일 으 키 는 상황 을 말한다. 앞의 예 에서 알 수 있 듯 이 충돌 을 해결 하 는 데 많은 시간 을 낭비 할 수 있 기 때문에 우리 의 목 표 는 충돌 을 피 하 는 것 이다.앞에서 언급 한 바 와 같이 '제 여 법' 을 사용 할 때 h (k) = k mod p 는 p 가 가장 좋 은 소수 이다.충돌 을 피하 기 위해 서다.왜 일 까요?p = 1000 을 가정 하면 해시 함수 분류의 기준 은 실제 적 으로 마지막 세 자릿수 로 분류 되 는데 이렇게 하면 최대 1000 가지 가 되 고 충돌 이 많 을 것 이다.일반적으로 p 의 약수 가 많 을 수록 충돌 할 확률 이 높다. 
간단 한 증명: p 는 비교적 많은 약수 가 있 는 숫자 라 고 가정 하고 데이터 에 q 만족 gcd (p, q) = d > 1 이 존재 한다. 즉, p = a * d, q = b * d 가 있 으 면 q mod p = q – p * [q div p] = q – p * [b div a] 가 있다. ① 그 중에서 [b div a] 의 수치 범 위 는 [0, b] 의 정 수 를 초과 하지 않 는 다.즉, [b div a] 의 값 은 b + 1 가지 만 가능 하고 p 는 미리 정 해진 숫자 이다.따라서 ① 식 의 수 치 는 b + 1 가지 만 가능 하 다.이렇게 하면 mod 연산 후의 나머지 수 는 [0, p - 1] 안에 있 지만 그의 수 치 는 ① 가 져 올 수 있 는 값 에 국한 된다.나머지 분포 가 고 르 지 않 아 졌 다 는 얘 기다.쉽게 알 수 있 듯 이 p 의 약수 가 많 을 수록 이런 나머지 분포 가 고 르 지 않 은 상황 이 발생 할 수록 빈번 하고 충돌 할 확률 이 높다.소수 의 약 수 는 가장 적 기 때문에 우 리 는 큰 소 수 를 선택한다.소 수 는 우리 의 유능 한 조수 라 는 것 을 기억 해라. 
       한편 저 충 돌 률 만 추구 하 는 것 도 좋 지 않다.이론 적 으로 거의 완벽 하고 충돌 이 거의 없 는 함 수 를 설계 할 수 있다.그러나 이렇게 하 는 것 은 분명히 가치 가 없다. 왜냐하면 이런 함수 디자인 은 시간 을 낭비 하고 인 코딩 이 반드시 복잡 하기 때문이다. 이렇게 많은 정력 을 들 여 함 수 를 설계 하 는 것 보다 충돌 이 많 지만 인 코딩 이 간단 한 함 수 를 사용 하 는 것 이 낫다.따라서 함 수 는 인 코딩 하기 쉽 고 실현 하기 쉽다. 
       다시 말하자면, 좋 은 해시 함 수 를 설계 하 는 것 이 매우 관건 적 이다.한편, '좋다' 는 기준 은 바로 비교적 낮은 충돌 율 과 실현 하기 쉽다 는 것 이다. 
       또 해시 표를 사용 하 는 것 은 앞의 기본 조작 을 기억 하면 변 함 없 는 변화 에 대응 할 수 있 는 것 이 아니다.어떤 때 는 제목 의 요구 에 따라 하 쉬 표 의 구 조 를 개선 해 야 한다.종종 간단 한 개선 이 큰 편 의 를 가 져 올 수 있다. 
이런 것들 은 일반적인 원칙 일 뿐 진정 으로 시험 문 제 를 만 났 을 때 실제 상황 이 천변만화 하기 때문에 구체 적 인 문 제 를 구체 적 으로 분석 해 야 한다.