Hash
Table of contents
해시 (Hash)
용어
-
해싱(Hashing)
- Key 값에 산술연산을 적용하여 특정 항목의 테이블 주소(해시값)를 구하는 과정
-
해시 함수(Hash Function)
- 해싱을 할 때 사용하는 산술 연산 함수(알고리즘)
- 고정된 길이의 데이터로 매핑하는 함수
- 중복없이 해시값을 고르게 만들어내는 함수가 좋은 함수 - 충돌이 일어나지 않을수록 좋음
-
해시 충돌(Hash Collision)
- 다른 내용의 데이터가 같은 해시값을 가질 때 일어남
- 해싱 과정에서 Input이 무한할 때 Output이 유한하기에 해시 충돌은 반드시 발생 (비둘기집 원리)
해시 테이블
정의
- 연관 배열에서의 Key값으로 고유한 index를 생성하여 버킷 또는 슬롯이라는 저장소(배열)에 (Key, Value)로 데이터를 저장하는 자료구조
- 파이썬 dictionary, 자바 Map이 해시테이블의 대표적인 예
특징
- 기본 연산으로 search, insert, delete
- 순차적으로 데이터 저장 X
- 수정 가능하다 (=mutable)
장점
- 많은 데이터를 유한한 개수의 해시값으로 매핑하면서 작은 크기의 캐시메모리로 프로세스 관리 가능
- 해당 색인(해시값)만 알면 해시테이블의 데이터에 접근 가능
단점
- 주소가 동일할 경우 충돌(Collision)을 해결하기 위한 별도의 자료구조 필요
시간복잡도
- 평균: O(1)
- 최악: O(n) = 연결 리스트 탐색 시간 복잡도
해시 함수
나눗셈법(Division Method)
정의
- 해시 함수를 적용하고자 하는 값을 테이블 크기(N)으로 나눈 나머지 해시값으로 사용하는 방법
- h(k) = k mod N
- 이때 N은 소수를 사용하는 것이 좋음
- 가장 기본적이고 많이 쓰이는 방법
코드
def hash_func(self,key):
return key % self.size
</br>
폴딩방법(Folding Method)
정의
- 레코드 키값을 여러부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 해시값으로 사용하는 방법
종류
- 이동 폴딩(Shift Folding)
- 해시 테이블 크기의 자릿수로 키 분해
- 분해된 키들을 더한다
- 더한 값이 테이블 크기를 초과하면 초과한 자릿수를 버린다
- 경계 폴딩(Boundary Folding)
- 해시 테이블 크기의 자릿수로 키 분해
- 나누어진 각 부분의 경계 부분 값을 역으로 정렬
- 분해된 키들을 더한다
- 더한 값이 테이블 크기를 초과하면 초과한 자릿수를 버린다
</br>
중간제곱 방법(Mid Square Method)
정의
-
중간 제곱 방법은 키값을 제곱한 결과값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법
-
제곱한 값의 중간 비트들은 대개 키의 모든 값과 관련이 있음
-
서로 다른 키값은 서로 다른 중간 제곱 함수값을 가짐
</br>
자릿수 분석 방법(계수 분석법, 숫자 분석법)
정의
- 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방법
예제
- 테이블 크기: 1000
- 홈 주소: 0 ~ 999(3자리)
| 키 레코드 | 홈 주소 |
|---|---|
| 012-452-0236 | 426 |
| 012-153-0530 | 150 |
| 015-342-0935 | 395 |
| 012-752-1032 | 702 |
| 012-852-0470 | 840 |
- 결과: 4, 8, 10열을 홈 주소로 선택
- 왼쪽 3자리 숫자는 거의 동일하므로 제거
- 5, 6, 7, 9열 역시 비슷한 숫자가 많으므로 무시
- 비교적 고른 분포인 4, 8, 10열을 선택하여 홈 주소로 사용
</br>
기수 변환 방법
정의
-
키 값의 진수를 다른 진수로 간주하여 주소 크기를 초과한 높은 자릿수를 절단하고, 이를 다시 주소 범위에 맞게 조정하여 해시값으로 사용하는 방법
- 해시 테이블 크기 = 1000
- 키 값 B2538(10)을 16진수로 간주해 10진수로 다시 계산
- (1 * 16^5) + (3 * 16^4) + (2 * 16^3) + (5 * 16^2) + (4 * 16^1) + (8 * 16^0) = 1254728(10)
- 해시 테이블의 크기가 1000이므로 해시값은 728이다
해시 충돌
개방 주소법(Open Addressing)
정의
- 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방법
특징
- 삭제의 경우 충돌에 의해 저장된 데이터가 검색되지 않을 수 있다.
- 삭제한 위치에 더미노드를 삽입(다음 위치까지 연결 해 주는 역할)한다.
-
더미 노드의 개수가 일정 이상이 되었을 경우, 주기적으로 새로운 배열을 만들어 다시 해시 해줘야 성능이 유지 가능하다.
- 종류로 선형 조사법, 이차 조사법 등 이 존재한다.
</br>
선형 조사법(linear probing)
정의
- 해시테이블을 선형, 순차적으로 탐색하여 비어있는 공간이 나올 때까지 탐사하는 방법이다.
원리
-
ex) h(k) = k % 7
- 해쉬 키값이 [2,9,16,23]이 나오면 h(k)는 모두 2이다.
- 배열 T
- 2 % 7 = 2 => T[2]
- 9 % 7 = 2 => T[2+1] 탐색 후 비어있으면 => T[3]
- 16 % 7 = 2 => T[2+1+1] 탐색 후 비어있으면 => T[4] - 비어있지 않으므로 T[2+1+1+1] 탐색 후 비어있으면 => T[5]
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| ☑ | ☑ | E85H | ☑ |
특징
- 만약, 조사를 시작했던 위치로 다시 돌아오게 되면 테이블이 가득 찬 것이다.
장점
- 구조가 간단하고 캐시의 효울이 높다.
단점
- 최악의 경우, 해시테이블 전체를 검색해야 하는 상황이 발생한다.
- 데이터의 클러스터링에 가장 취약
- 군집화(clustering) 문제가 발생할 수 있다.
</br>
2차탐사 방법(Quadratic Probing)
정의
- 원래 저장할 위치로부터 조금 더 멀리 떨어진 영역을 찾는 방법으로 해쉬 키 값에 충돌 횟수의 제곱한 수를 더한 값에 저장한다.
원리
-
ex) h(k) = k % 7
- 해쉬 키값이 [2,9,16]이 나오면 h(k)는 모두 2이다.
- 배열 T
- 2 % 7 = 2 => T[2]
- 9 % 7 = 2 => T[2+1^2] = T[3]
- 16 % 7 = 2 => T[2+2^2] = T[6]
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| ☑ | ☑ | ☑ |
</br>
체이닝 방법(Chaining)
정의
- 동일한 해시 값(Hash Value)을 갖는 Key들을 다른 버킷에 넣는 것이 아닌 동일한 버킷에 연결리스트 형식으로 연결하는 방법이다.
단점
- 하나의 해시 값에 여러 엔트리가 몰릴 수 있다. 이렇게 되면 배열, 리스트와 같은 선형적인 구조를 갖는 것과 마찬가지이므로 탐색 시 최악의 경우 O(N)의 시간복잡도를 갖게되어 탐색이 빠르다는 해시 테이블의 장점이 퇴색된다.
해결법
- 버킷의 크기 동적으로 늘리기
- 비선형적 구조로 entry 저장하기
- 트리 -> log(n)