[데이터 구조] Hash 표, Hash 함수 및 충돌 해결

1. Hash 표
해시 표 (Hash table, 산 목록 이 라 고도 함) 는 key 에 따라 직접 방문 하 는 데이터 구조 입 니 다.키 를 표 의 한 위치 에 비 추어 기록 에 접근 함으로써 검색 속 도 를 빠르게 하 는 것 이다.이 매 핑 함 수 는 해시 함수 라 고 하 는데 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.
데이터 에 있 는 모든 요소 의 키워드 K 를 독립 변수 로 하고 해시 함수 H (k) 를 통 해 함수 값 을 계산 하 며 이 함수 값 을 연속 저장 공간의 단원 주소 로 함수 값 에 대응 하 는 단원 에 저장 합 니 다.
해시 표 는 키 값 쌍 을 저장 합 니 다. 찾 는 시간 복잡 도 는 요소 의 수량 과 무관 합 니 다. 해시 표 는 요 소 를 찾 을 때 해시 코드 값 을 계산 하여 요소 의 위 치 를 찾 아 요 소 를 직접 방문 합 니 다. 따라서 해시 표 가 찾 는 시간 복잡 도 는 O (1) 입 니 다.
2. 해시 표 의 구조 방법
2.1 직접 주소 법
키워드 나 키워드 의 한 선형 편지 수 치 를 해시 주소 로 합 니 다. 즉 H (Key) = Key 또는 H (Key) = a * Key + b (a, b 는 정수) 라 는 해시 함수 도 자체 함수 라 고 합 니 다. H (Key) 의 해시 주소 에 값 이 있 으 면 H (Key) 를 찾 을 때 까지 다음 위 치 를 찾 습 니 다.주소 집합 크기 는 키워드 집합 크기 와 같 습 니 다.
2.2 디지털 분석 법
한 팀 의 데 이 터 를 분석 하면 예 를 들 어 한 팀 의 직원 들 의 생년월일 등 이다. 이때 우 리 는 생년월일 의 몇 자리 숫자 가 모두 같 기 때문에 충돌 할 확률 이 매우 크다 는 것 을 알 게 되 었 다. 그러나 우 리 는 생년월일 의 몇 자리 가 달 과 구체 적 인 날 짜 를 나타 내 는 숫자 차이 가 매우 크다 는 것 을 알 게 되 었 다. 만약 에 뒤의 몇 자리 숫자 를 이용 하여 해시 주 소 를 구성 하면충돌 확률 이 현저히 낮 아 집 니 다. 따라서 디지털 분석 법 은 숫자의 규칙 을 찾 아 가능 한 한 이 데 이 터 를 이용 하여 충돌 확률 이 낮은 해시 주 소 를 구성 하 는 것 입 니 다. 이 방법 은 전체 키워드 의 모든 숫자 에 나타 나 는 빈 도 를 미리 예측 할 수 있 습 니 다.
2.3 제곱 취 중 법
키워드 의 제곱 값 의 중간 몇 자 리 를 저장 주소 (해시 주소) 로 합 니 다.'키워드 의 제곱 값' 을 구 하 는 목적 은 '차 이 를 확대 하 는 것' 이 고 제곱 값 의 중간 에 여러분 은 전체 키워드 에서 여러분 의 영향 을 받 을 수 있 습 니 다.　
이 법 은 키워드 중의 모든 숫자 가 반복 되 어 빈도 가 높 은 현상 이 나타난다.
2.4 접 는 법
키 워드 를 여러 부분 으로 나 눈 다음 중첩 과 해시 주 소 를 가 져 옵 니 다.두 가지 중첩 처리 방법: 위치 이동 중첩: 분 단 된 몇 부분의 낮은 위 치 를 정렬 합 니 다.간 계 중첩: 한 끝 에서 분할 계 를 따라 왔 다 갔다 접 은 다음 정렬 합 니 다.이 방법 은 키워드 의 숫자 자리 수가 특히 많다.　
2.5 난수 법
해시 함 수 를 H (key) = Random (key) 로 설정 합 니 다. Random 은 가짜 랜 덤 함수 입 니 다. 길이 가 다른 키워드 구조 해시 함수 에 적합 합 니 다.
2.6 잔여 법
키 워드 를 취 하 는 것 은 산열 표 의 길이 m 보다 크 지 않 은 수 p 에 의 해 제 거 된 후 얻 은 나머지 는 산열 주소 이다. 즉, 해시 함 수 는 H (key) = key MOD p (p ≤ m) 이 고 그 중에서 m 는 표 의 길이 이 며 p 는 m 보다 크 지 않 은 소수 이다.
3. 해시 표 충돌 해결 방법
해시 표 처리 충돌 은 주로 개방 주소 법, 재 산열 법, 체인 주소 법 (지퍼 법) 과 공공 넘 침 구역 을 구축 하 는 네 가지 방법 이 있다.구조 적 성능 이 좋 은 해시 함 수 를 통 해 충돌 을 줄 일 수 있 지만 충돌 을 완전히 피 할 수 없 기 때문에 충돌 을 해결 하 는 것 은 하 쉬 법의 또 다른 관건 적 인 문제 이다.'충돌 처리' 의 실제 의 미 는 충돌 이 발생 하 는 키 워드 를 위해 다음 해시 주 소 를 찾 는 것 이다.
3.1 오픈 주소 법
충돌 이 발생 하면 다음 빈 해시 주 소 를 찾 아 보 세 요. 흩 어 진 목록 이 충분 하면 빈 해시 주 소 를 찾 아 기록 을 저장 합 니 다.
3.1.1 선형 탐지
충돌 이 발생 했 을 때 빈 단원 을 찾 거나 전체 표를 찾 을 때 까지 표 의 다음 단원 을 순서대로 봅 니 다.
공식:

fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)

3.1.2 2 차 탐사 법
충돌 이 발생 했 을 때 표 의 좌우 에서 점프 식 탐 사 를 하여 쌍방 향 으로 가능 한 빈 위 치 를 찾 았 다.
공식:

fi(key) = (f(key)+di) MOD m (di = 12, -12, 22, -22,……, q2, -q2, q <= m/2)

3.1.3 랜 덤 탐지 법
충돌 할 때 변위 량 di 에 대해 무 작위 함수 로 계산 할 수 있 습 니 다. 우 리 는 무 작위 탐지 법 이 라 고 부 릅 니 다.
공식:

fi(key) = (f(key)+di) MOD m (di       )

선형 탐측 재 산열 은 '2 차 집적', 즉 동의어 의 충돌 을 처리 할 때 비 동의어 의 충돌 을 초래 하기 쉽다.선형 탐지 재 산열 의 장점 은 해시 가 불만 을 표시 하면 충돌 하지 않 는 해시 주 소 를 찾 을 수 있 고, 2 차 탐지 재 산열 과 위 랜 덤 탐지 재 산열 은 반드시 그렇지 않다 는 것 이다.
3.2 체인 주소 법
모든 해시 주소 와 같은 기록 을 같은 링크 에 연결 합 니 다.각 링크 의 결산 공간 은 동태 적 으로 신청 한 것 이기 때문에 표를 만 들 기 전에 표 의 길 이 를 확정 할 수 없 는 상황 에 더욱 적합 하 다.충돌 처리 가 간단 하고 퇴적 현상 이 없다. 즉, 동의어 가 아 닌 단 어 는 충돌 이 발생 하지 않 기 때문에 평균 검색 길이 가 비교적 짧다.
3.3 재 해시 법
이런 방법 은 여러 개의 서로 다른 해시 함 수 를 동시에 구성 하 는 것 이다.

Hi=RH1（key），i=1，2,3，…,n.

해시 주소 Hi = RH1 (key) 이 충돌 할 때 Hi = RH2 (key) 를 계산 합 니 다. 충돌 이 발생 하지 않 을 때 까지.이런 방법 은 모임 이 생기 기 는 쉽 지 않 지만 계산 시간 을 늘 렸 다.
3.4 공공 유출 구역 구축
이러한 방법의 기본 사상 은 해시 표를 기본 표 와 넘 치 는 표 두 부분 으로 나 누 어 기본 표 와 충돌 하 는 요소 가 있 으 면 일률적으로 넘 치 는 표를 작성 하 는 것 이다. (주의: 이 방법 에서 요 소 를 두 개의 표 로 나 누 어 저장 하 는 것 이다)