[데이터구조 & 알고리즘] Hash Tables 및 Dictionaries 개요
Dictionary : collection or data structure of key/value pair.
- search
- insert
- delete
- O(1)
Dictionary로부터 Hash Table을 만들려면 Dictionary의 키/값 쌍이 배열의 어떤 인덱스에 들어갈 지 결정해야 한다.
그 뒤 배열에 인덱스에 맞게 넣어준다.
Hash function should be
- fast to compute (컴퓨팅이 빨라야 함)
- avoid collisions(충돌/중복을 막아야 함) : djb2
To avoid Collisions
-Chaining
Linked List를 만들고 포인터가 가르키게 한다.
새 키/값 쌍은 제일 앞에 위치한다.
여기서 n은 요소의 수, m은 배열의 길이이다.
알파가 1보다 작으면 검색에는 O(1)만큼 든다.
- Linked List를 사용하지 않고 싶은 경우 -> open addressing
Linear Probing
충돌할 경우 충돌되는 인덱스의 비어있는 오른쪽 인덱스에 충돌되는 키/값 쌍을 삽입한다.
단점 : 아래와 같이 쫘르륵 있는 경우 맨 첫번째 인덱스와 충돌할 시 오른쪽으로 한 인덱스씩 전부 검사해야 한다.
Double Hasing
리니어 프로빙의 단점을 해결
오른쪽의 인덱스를 검사하는 대신 특정 숫자만큼 오른쪽의 인덱스를 검사한다.
더블 해싱에서는 충돌 시마다 각기 다른 인덱스 시퀀스를 사용하여 검사한다.
인덱스 : [key를 해싱함수에 넣은 값] % 8(배열의 길이)
특정 키에 고를 값 : (인덱스 + c) % 8
c를 고르는 법
조건 gcd(c,m) = 1 , gcd - 최대공약수 , m - 배열의 길이 , 이 조건이 있어야 배열 전체에 겹치지 않고 다 골라짐
(m: 배열의 길이)가 소수이고 c가 배열의 길이보다 낮은 양수면 최대공약수는 항상 1이다.
key에 해싱함수2를 적용 후 (m-1)로 나눈 나머지 -> 이러면 범위는 [0, m-2]
그 값에 1을 더하면 범위는 [1, m-1]이 된다. 이 값을 c로 설정한다.
h2(key)란?
해싱함수1의 입력에 [key + 문자열'd'] 또는 그대로.
해싱함수1은 파이썬의 기본 해싱함수를 기준으로 하는데 다른 것도 되는지 확인해보자.
파이썬의 해싱함수는 djb2를 기준으로 한다.
더블 해싱 시 검색 및 삽입에서 평균 이만큼 시도한다.
알파는 현재 있는 요소/전체 배열 수 -> 해시 테이블이 얼마나 가득 찼는지를 나타낸다.
알파가 2/3보다 크면 배열의 크기를 키운다. (새 배열을 만들어 옮김)
배열 리사이징이 시간이 걸려도 삽입과 검색에 효율적이다.