[Python 코테 입문] 3. 해시(Hash)

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션3. 해시(Hash)

3-1. 해시테이블 개념

(1) 해시테이블(Hash Table)

해시테이블(Hash Table)

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 삼아 데이터의 키(key)와 값(value)을 함께 저장하는 자료구조

이때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.

• 장점

Direct-address Table보다 메모리 효율성이 좋다.

• 단점

키 개수보다 해시테이블의 크기가 작기 때문에 해시 충돌 문제가 발생한다.

 

(2) Direct-address Table

Direct-address Table

가장 간단한 형태의 해시테이블

키의 전체 개수와 동일한 크기의 Bucket을 가진 해시테이블

• 장점

키 개수와 해시테이블 크기가 동일하기 때문에 해시 충돌 문제가 발생하지 않는다.

• 단점

전체 키 중에서 실제 사용되는 키의 개수가 적을 경우 메모리 효율성이 크게 떨어진다.

 

(예시) 다음 수열에서 각 숫자의 빈도수를 구하시오.

array = [55236, 55238, 55239, 55240, 55236, 55236, 55238, ..., 55240]

 

3-2. 해시 충돌

(1) 해시 충돌(Hash Collision)

해시 충돌(Hash Collision)

해시 함수는 대개 해시값의 개수보다 더 많은 수의 키값을 해시값으로 변환한다.

이때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌(Hash Collision)이 발생하게 된다.

 

아래 예시는 이름-전화번호를 매핑하기 위한 해시함수를 개념적으로 나타낸 것이다.

위의 해시 함수는 'Daniel'과 'Bill'을 모두 '04'로 매핑해 해시 충돌을 일으키고 있다.

 

3-3. 해시 충돌 해결 1 : Chaining

(1) Separate Chaining

해시 충돌을 해결하기 위해 먼저 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 방법을 생각해볼 수 있다.

해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식(연결리스트)으로 구현한다.

 

(2) 해시테이블의 시간복잡도

해시테이블의 탐색, 삽입, 삭제의 시간복잡도는 평균적으로 O(1)을 갖는다.

단, 충돌이 빈번하게 일어나면 최악의 경우 O(n)의 시간복잡도로 수렴할 수 있다. (Chaining으로 해시 충돌 해결 시 연결리스트로 구현하기 때문이다.)
(참고) 연결리스트 탐색의 시간복잡도는 O(n)이다.

https://moominie.tistory.com/53

[Python 코테 입문] 2. 배열, 연결리스트, deque

 

3-4. 해시 충돌 해결 2 : Open Addressing

(1) Open Addressing

Open Addressing은 Chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다.

해시함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 Open Addressing이라고 한다.

해시 충돌이 빈번하게 생길 수 있다.

 

 

1) 선형탐사 (Linear Probing)

최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면 해당 해시값에서 고정폭(예 : 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 엑세스한다.

여기에도 데이터가 있으면 또 다시 고정폭을 옮겨 엑세스한다.

 

2) 제곱탐사 (Quadratic Probing)

최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면 해당 해시값에서 폭의 제곱수만큼 옮겨 다음 해시값에 해당하는 버킷에 엑세스한다.

여기에도 데이터가 있으면 그 폭이 제곱수로 늘어난다.

예컨대 임의의 키값에 해당하는 데이터에 엑세스할 때 충돌이 일어나면 1²칸을 옮긴다. 여기에서도 충돌이 일어나면 이번에는 2²칸, 그 다음에는 3²칸을 옮기는 식이다.

 

3) 이중해싱 (Double Hashing)

탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법이다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.

 

3-5. dictionary 자료구조

(1) dictionary 개념

dictionary 객체는 key, value를 한 쌍으로 가지는 자료구조다.

 

(2) dictionary 함수

1. dict() : dictionary 객체를 생성하는 생성자

sH = dict();

sH = {}

 

2. sH 딕셔너리의 key 탐색

sH = {'a': 3, 'b': 5, 'c': 2}
for key in sH:
	print(key)

a, b, c

 

3. sH 딕셔너리의 value 탐색

sH = {'a': 3, 'b': 5, 'c': 2}
for val in sH.values():
	print(val)

3, 5, 2

 

4. sH 딕셔너리의 key, value 동시 탐색

sH = {'a': 3, 'b': 5, 'c': 2}
for key, val in sH.items():
	print(key, val)

a 3

b 5

c 2

 

5. key in sH : sH 딕셔너리에 key가 있는지 확인해서 있으면 True, 없으면 False를 반환한다. 

시간복잡도는 O(1)이다.

sH = {'a': 3, 'b': 5, 'c': 2}
p1 = 'a' in sH;
p2 = 'e' in sH;
print(p1, p2)

True, False

 

6. del(sH[key]) : sH에서 key에 해당하는 데이터를 삭제한다.

sH = {'a': 3, 'b': 5, 'c': 2}
del sH['a']
print(sH)

{'b': 5, 'c': 2}

 

7. len(sH) : sH의 키의 개수를 구한다.

시간복잡도는 O(1)이다.

sH = {'a': 3, 'b': 5, 'c': 2}
print(len(sH))

3