[TAVE/파이썬 알고리즘 인터뷰] Ch11 | 해시 테이블 - 개념 정리

참고 자료: 파이썬 알고리즘 인터뷰

📌해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료이다.

👉🏻대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이다.

 

해시

---

📌해시 함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수

📌해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

• ABC → A1
• 1234BC → CB
• AF32B → D5

👉🏻위의 각각 3글자, 6글자. 5글자인 문자열을 모두 2바이트의 고정 크기 값으로 매핑했다. 여기서 화살표 역할을 하는 함수가 해시 함수이다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용한다.

 

생일 문제

---

 

💡 여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률은 얼마나 될까?

👉🏻비둘기집 원리에 따르면 생일의 가짓수는 365개이므로 사람이 366명 이상 모여야 할 것 같다. 하지만 통계상 23명만 모여도 확률이 50%가 넘고 57명이 모이면 99%가 넘어간다. 이를 파이썬 코드로 증명해보자!

import random

TRIALS = 100000 #10만번 실험
same_birthdays = 0 #생일이 같은 실험의 수

#10만 번 실험 진행
for _ in range(TRIALS):
    birthdays = []
    #23명이 모였을 때, 생일이 같을 경우 same_birthday += 1
    for i in range(23):
        birthday = random.randint(1, 365)
        if birthday in birthdays:
            same_birthdays += 1
            break
        birthdays.append(birthday)

# 전체 10만 번 실험 중 생일이 같은 실험의 확률
print(f'{same_birthdays / TRIALS * 100}')

👉🏻3번 실행하니 3번 모두 50%가 넘었다.

👉🏻이는 충돌이 쉽게 일어난다는 것을 보여주며 때문에 충돌을 최소화하는 일이 중요하다!

 

비둘기집 원리

---

 

📌n개 아이템을 m개 컨테이너에 넣을 때, n > m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어있다는 원리를 말한다.

👉🏻비둘기집 원리에 다르면 9개의 공간에 10개의 아이템이 들어오면 반드시 1번 이상은 충돌이 발생한다. 좋은 해시 함수라면 이러한 충돌을 최소화하는 것이 중요하다.

 

로드 팩터

---

 

📌해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다.

$$load factor = \frac{n}{k}$$

👉🏻로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정한다. 또한 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용한다.

 

해시 함수

---

👉🏻해싱의 나눗셈 방식을 살펴보자

$$h(x) = x mod m$$

• h(x): 입력값 x의 해시 함수를 통해 생성된 결과
• m: 해시 테이블의 크기

 

충돌

---

👉🏻아무리 좋은 해시 함수여도 충돌은 발생한다. 위 그림에서도 A와 C는 해시 값이 2로 같은 값이 되어 충돌이 발생했다. 이렇게 충돌이 발생했을 때 어떻게 처리할지 살펴보자!

 

개별 체이닝

---

키	값	해시	충돌 여부
A	15	2	충돌
B	47	1
C	17	2	충돌
D	7	4

👉🏻이 표를 개별 체이닝 방식으로 구현하면 다음과 같다.

👉🏻충돌이 발생한 A와 C는 A의 다음 아이템이 C인 형태로 서로 연결 리스트로 연결되었다.

• 키의 해시 값을 계산한다.
• 해시 값을 이용해 배열의 인덱스를 구한다.
• 같은 인덱스가 있다면 연결 리스트로 연결한다.

👉🏻잘 구현할 경우 탐색은 O(1)이지만 최악의 경우 모든 해시 충돌이 발생한다면 O(n)이 된다.

 

오픈 어드레싱

---

📌충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다.

👉🏻무한정 저장할 수 있는 체이닝 방식과 달리 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하므로 모든 원소가 반드시 자기 해시 값과 일치하는 주소에 저장된다는 보장은 없다.

 

📌선형 탐사 방식: 충돌이 발생하면  해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 오픈 어드레싱 방식 중 가장 간단한 방식이다.

👉🏻선형 탐사 방식의 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상을 클러스터링이라고 한다. 클러스터들이 점점 커지며 인근의 클러스터들과 서로 합쳐지면 다른 위치에는 데이터가 거의 없게 된다. 이러한 현상은 탐사 시간을 오래 걸리게 하고, 전체적으로 해싱 효율을 떨어뜨린다.

 

📌리해싱: 오픈 어드레싱 방식을 사용했을 때 버킷 사이즈보다 커지면, 즉 기준이 되는 로드 펙터 비율을 넘어서면 그로스 펙터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사한다.

 

언어별 해시 테이블 구현 방식

---

👉🏻파이썬에서는 딕셔너리가 오픈 어드레싱 방식을 사용해 해시 테이블로 구현되어 있다.

💡오픈 어드레싱을 선택한 이유는 무엇일까?

• 체이닝을 사용하면 연결 리스트를 만들어야 하는데 이는 추가 메모리 할당이 필요하고 느린 작업이기 때문이다.
• 체이닝에 비해 성능이 좋다. 

👉🏻그러나 오픈 어드레싱은 로드 팩터 1 이상을 저장할 수 없다. 빈 공간을 탐사하는 선형 탐사 방식은 공간이 찰수록 탐사에 오랜 시간이 걸리고 공간이 가득 차면 더이상 빈 공간을 찾을 수 없기 때문이다. 때문에 로드 팩터를 작게 잡아 성능 저하 문제를 해결하고 있다.