[자료구조] 해시 테이블(Hash Table)

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인,

연관 배열 추상 자료형(ADT)을 구현하는 자료구조다.

 

 

해시(Hash)

 

해시 함수란 임의 크기 데이터를 고정 크기 값으로

매핑하는 데 사용할 수 있는 함수를 말한다.

 

ABC -> A1

1234BC -> CB

AF32B -> D5

 

이처럼 3글자, 5글자, 6글자이지만 해시 함수를 통과함으로써 2바이트의 고정 크기 값으로 매핑된다.

 

이처럼 해시 테이블을 인덱싱 하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라 한다.

 

해싱은 정보를 빠르게 저장하고 검색하기 위해 사용하는 기법 중 하나이고

 

심볼 테이블 등의 자료구조를 구현하기에도 적합하다.

 

이외에도 체크섬(Checksum), 손실 압축, 무작위화 함수(Randomization Function), 암호와도 관련이 깊다.

 

하지만 5글자, 6글자로 이루어진 값을 2바이트로 고정하려니

 

여러 개 매핑하다 보면 중복("충돌"이라 표현함)되는 값도 있기 마련이다.

 

이러한 문제는 "생일 문제"를 통해 이해할 수 있다.

 

생일의 가짓수는 365개로 얼핏 생각하면 생일이 같은 2명이 존재할 확률은 무척 낮아 보인다.

 

하지만 23명만 모여도 이러한 확률은 50퍼센트 이상으로 늘어난다.

 

 

import random
 
TRIALS = 100000 # 10만 번 실험
same_birthdays = 0 # 생일이 같은 실험의 수
 
# 10만 번 실험 진행
for _ in range(TRIALS):
    birthdays = []
    # 23명이 모여ㅆ을 때, 생일이 같을 경우 same_birthdays += 1
    for i in range(23):
        birthday = random.randinit(1,365)
        if birthday in birthdays:
        same_birthdays += 1
        break
    birthdays.append(birthday)
 
# 전체 10만 번 실험 중 생일이 같은 실험의 확률
print(f'{same_birthdays / TRIALS * 100}%')

 

이 코드의 결과 값은 50.708%이다.

 

 

로드 팩터(Load Factor)

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

 

로드 팩터의 비율에 따라서 해시 함수를 재작성할지, 해시 테이블의 크기를 조정해야 할지를 결정한다.

 

또한 이 값은 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용된다.

 

자바 10에서는 해시 맵의 디폴트 로드 팩터를 0.75로 정했으며 '시간과 공간 비용의 적절한 절충안'이라 설명한다.

 

일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하게 되며,

 

자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다.

 

 

충돌(Collision)

 

아무리 좋은 해시 함수여도 충돌은 발생하게 된다.

 

충돌이 발생할 경우 

 

1) 개별 체이닝

 

2) 오픈 어드레싱

 

이 두 방식 중 하나로 처리하게 된다.

 

 

1) 개별 체이닝(Separate Chaining)

 

 

해시에 따라 값을 넣어주게 되는데

 

만약 1번 공간처럼 중복된 해시가 있을 경우

 

개별 체이닝에서는 그다음 오는 값을 연결 리스트로 연결한다.

 

 

2) 오픈 어드레싱(Open Addressing)

 

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

 

사실상 무한정 저장할 수 있는 체이닝 방식과 달리,

 

이 방식은 전체 슬롯의 개수 이상은 저장할 수 없다.

 

해시가 중복될 경우 빈 공간을 찾아 저장되므로

 

모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

 

오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우엔 삽입할 수 없으므로

 

일정 이상 채워지면

 

(일정 로드 팩터 비율을 넘어서게 되면)

 

그로스 팩터(Growth Factor)의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후

 

여기에 새롭게 복사하는 리해싱(Rehashing) 작업이 일어난다.

 

 

해시 테이블로 구현된 파이썬의 자료형을 제시하라.

 

답은 딕셔너리이다.

 

파이썬에서는 충돌 시 오픈 어드레싱 방식으로 중복된 값을 처리한다.

 

체이닝 방식을 선택하지 않은 이유는

 

malloc으로 메모리를 할당하는 오버헤드가 높기 때문.

 

즉,

 

연결 리스트를 만들기 위해 추가로 메모리를 할당하는 작업은 상당히 느린 작업이라 택하지 않았다고 한다.

 

Chaining vs Linear probing(오픈 어드레싱의 한 방식)

 

루비나 파이썬 같은 모던 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신,

 

로드 팩터를 작게 잡아 성능 저하 문제를 해결한다.

 

c++, 자바, 고 등의 언어는 개별 체이닝을 사용한다.