0. Hash Colision

해시함수가 모든 입력에 대해 항상 다른 해시값을 부여할 수 있다면 이상적인 상황이다.
하지만 모든 데이터에 대해 알고 있지 않다면 이렇게 완벽한 해시 함수를 작성하는 것은 불가능하다.

해시 충돌(hash colision)은 키(key)가 들어갈 자리(bucket)이 없는 경우에 발생하는 개념이다.

위와 같이 B와 C라는 키값이 해시함수를 통과하면 4라는 동일한 hash 값을 부여받게 된다. 이것이 해시 충돌이다.

한편, 해시테이블의 가장 중요한 목적은 해시 충돌을 최소화 시키는 해시함수를 만드는데 있다.

해시충돌이 벌어지는 상황을 파이썬 코드로 구현해본다.

# 길이가 5인 리스트 생성
hashtable = [None] * 5
print(hashtable)
# [None, None, None, None, None]

# 해시함수
def hash_function(key):
    return key % len(hashtable)
 
print(hash_function(10)) 
print(hash_function(20)) 
print(hash_function(31)) 

#
0
0
1

# 해시테이블에 데이터를 삽입
def insert_hash(hashtable, key, value):
    hash_key = hash_function(key)
    hashtable[hash_key] = value 

insert_hash(hashtable, 10, 'A')   # 해시함수로 계산되어 0번째 인덱스에 A가 삽입됨
print(hashtable)
# ['A', None, None, None, None]

insert_hash(hashtable, 23, 'B')   # 3번째 인덱스에 B가 삽입됨
print(hashtable)
# ['A', None, None, 'B', None]

# 현재 0번째 인덱스에 A, 3번째 인덱스에 B가 저장되어있음
# 아래와 같이 해시함수를 통해 계산된 0번째 인덱스에 'Collision' 값을 삽입할 경우, 충돌이 발생한다.
# 그리고 'A'값은 'Collision'으로 대체(충돌)된다.
insert_hash(hashtable, 20, 'Collision')
print(hashtable)
# ['Collision', None, None, 'B', None]

해시 충돌로 인해 발생하는 문제를 해결하는데 가장 대표적인 두가지 방법을 알아본다.
먼저, Chaining(체이닝) 방법이다.

1. Chaining

체이닝은 해시 테이블에서 동일한 해시값에 대해 충돌이 일어날 때, 그 위치에 있던 버킷에 다음 키값을 연결하는 방법이다.
즉, 체이닝은 연결리스트 자료구조를 활용하여 bucket에서 연결될 수 있는 entry에 제한을 두지 않고 체인 형태로 연결하는 것이다.

체이닝 과정

• 키의 해시값을 계산한다.
• 해시값에 해당하는 리스트 인덱스를 구한다.
• 같은 해시값을 가진 키가 있다면(충돌) 리스트로 연결한다.

연결리스트 형태로 이어지기 때문에 특정 해시값에 대해 충돌하더라도, 체이닝을 통해 값을 찾을 수 있게된다.

체이닝 과정을 파이썬 코드로 구현해본다.

# 2차원 리스트 생성
chain_hash_table = [[] for _ in range(10)]
print(chain_hash_table)
# [[], [], [], [], [], [], [], [], [], []]

# 해시함수 및 해시 값 확인
def chain_hash_func(key):
    return key % len(chain_hash_table)

print(chain_hash_func(10))
print(chain_hash_func(21))
print(chain_hash_func(39))
#
0
1
9

# extend 방식으로 체이닝하는 함수
def chain_insert_func(chain_hash_table, key, value):
    hash = chain_hash_func(key)
    chain_hash_table[hash].extend(value)

chain_insert_func(chain_hash_table, 10, 'A')
chain_insert_func(chain_hash_table, 25, 'B')
print(chain_hash_table)
# [['A'], [], [], [], [], ['B'], [], [], [], []]

# 20(key)에 해당하는 해시가 중복된 해시더라도 체이닝을 통해 리스트가 연결되어 값이 추가된다.
chain_insert_func(chain_hash_table, 20, 'C')
print(chain_hash_table)
# [['A', 'C'], [], [], [], [], ['B'], [], [], [], []]

2. Open Addressing

오픈 어드레싱은 하나의 bucket에 하나의 entry만 들어갈 수 있는 형태이다.
이 방법은 해시 충돌이 발생했을 때, 비어있는 배열 슬롯이 발견될 때까지 array의 위치를 검색한다.
즉, 배열의 빈 공간을 탐사(proving)하면서 해시 충돌을 피하는 방식이다.

체이닝과 달리 open addressing방법은 저장공간이 정해져있다.

4. Python Dictionary

파이썬의 자료형 중 해시테이블로 구현된 자료형은 딕셔너리다.
또한, 파이썬은 내부적으로 오픈 어드레싱 방식을 활용하여 해시 충돌을 해결한다.

오픈 어드레싱을 활용할 때 빈 공간이 없는 경우, 시간이 오래 걸릴 수 있다.
이러한 이유로 파이썬에서는 로드팩터(load factor)를 작게 설정하여 성능 저하 문제를 해결한다.

3. Load Factor

로드팩터(load factor)는 해시 테이블이 얼마나 가득 찼는지를 측정하는 지표다.

load factor = (해시테이블에 입력된 키 갯수 / 해시테이블의 전체 인덱스 갯수)

• 로드팩터 값에 따라 해시함수 재작성여부, 해시테이블 크기조정여부가 결정된다.
• 로드팩터값을 통해 해시테이블의 성능 정도를 파악할 수 있다.
• 오픈 어드레싱 방식을 사용하면 로드 팩터는 1정도 나온다.
• 체이닝 방식을 사용하면 로드 팩터 <= 1 (오픈 어드레싱보다 좋은 성능)을 보인다.
• 로드팩터를 낮추면 해시테이블의 성능은 올라간다.

로드팩터 예시

• 로드팩터가 0.75에 도달하면 기존 용량을 2배 증가하도록 설정한다.
• 해시테이블의 초기용량이 10이라고 가정할 때, $10*0.75=7.5$
• 결과적으로 기존 용량(10)에서 증가된 용량(20)이 된다.
• 용량이 증가될 때, 기존 데이터들을 해시함수에 다시 넣어 해시테이블을 재정렬한다.

Created on Dec 1, 2021

• 글 작성