Hash Table
Hash Table
key를 이용하여 value에 직접 접근이 가능한 자료구조
key를 통해 value을 검색하기 위한 목적으로 만들어졌으며, 데이터 양에 영향을 덜 받으며 빠르다
*python의 dictionary가 해시테이블 구조로 생성된 collection 자료형이다.
Hash Table 구성
key : 고유한 값이며, 해시함수의 input. 해시함수를 통과해 hash로 바뀐다.
*hash로 바꾸는 이유 : 기본적으로 컴퓨터가 숫자 형태로 데이터를 받아들이기도 하고, 길이가 긴 형태의 key값도 hash로 바꾸어 공간의 효율성을 추구할 수 있다.
해시함수(Hash Function) : key를 hash로 바꾸는 방법을 정의하고 있으며, 이때 일어나는 연산을 모듈러 연산이라고 한다.
Hash : 해시 함수를 거쳐서 나온 결과이며, 저장소(bucket)에서 value와 매칭되어 저장된다. bucket의 인덱스로 사용하기도 한다.
Value : 저장소(bucket)에 저장되는 값으로 키를 통해 저장, 삭제, 검색, 접근이 가능하다.
비유를 하자면,
한 학급의 학생들 이름으로 된 파일을 만들어 거기에 학생들의 시험 점수를 저장할 수도 있지만, 효율성을 위해 각 학생들에게 번호를 부여해서 정리한다고 하자. 이때 학생 이름은 key가 되고 부여한 번호는 hash, 점수는 value라고 할 수 있다. 번호를 부여하는 방법은 생일을 기준으로 하며, 태어난 월 + 태어난 일 = 각자의 번호 라고 하자. 이러한 일련의 방법을 해시 함수, 일어나는 연산을 모듈러 연산이라고 할 수 있다. 이 때, 두 사람의 번호가 같게 부여되는 경우, 이것을 해시충돌이라 한다.
dictionary는 해시테이블의 구조를 차용한 collection 자료형이다.
# 형태 : dict = { key : value }
Result = { 'Ji eun' : 93, 'Min Ji' : 75}
# key로 빠르게 value를 검색할 수 있다
print(Result['Ji eun']) # 결과 : 93
# 값 추가도 간편하다
Result['Yong sun'] = 100
위와 같이 해시테이블 구조에서 value에 접근하기 위해서는 key값을 알아야 한다.
성능
해시테이블은 해시 충돌이 일어나지 않는 상황에서 O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.
해시 함수를 통해 해당 key값과 매치되는 hash(index), value를 빠르게 찾을 수 있기 때문.
해시 충돌(Hash Collision)
서로 다른 key들이 해시 함수를 거쳤을 때 같은 결과값이 나오는 경우, 즉 여러개의 key가 하나의 hash와 매치되는 상황을 말한다.
hash table은 이것을 최소화 하는 방향으로 생성되어야 한다.
해시 충돌이 일어날 때 최악의 경우 빈 bucket을 찾아야 하기 때문에 O(n)의 시간복잡도를 가질 수 있다.
해시 충돌을 방지하는 방법
1. Chaning
해시 충돌이 일어나는 bucket안에서 연결 리스트 구조를 사용하여 저장하는 방법
위 예시에서 지은과 민수의 hash가 같기 때문에 먼저 입력된 지은의 값 뒤에 민수의 값을 연결하여 저장하였다.
이렇게 하면 bucket의 길이를 늘이지 않고도 효율적으로 정보를 저장할 수 있으며, 상대적으로 적은 메모리를 사용한다.
chaning 방식을 python으로 구현하면 아래와 같다. (연결리스트를 사용한 것은 아니지만, python의 list구조는 길이가 변할 수 있으므로 list를 사용하여 구현할 수 있다.)
hash_table = [[] for i in range(5)]
# []*5 의 결과는 [] 이다
# hash function : key값을 5로 나누었을 때 나머지를 hash로 반환
def hash_func(key):
return key % 5
def chain_insert(hash_table, key, value):
hash = hash_func(key)
hash_table[hash].extend(value)
chain_insert(hash_table, 7, 'A')
chain_insert(hash_table, 8, 'B')
chain_insert(hash_table, 12, 'C')
print (hash_table) # 결과 : [[], [], ['A', 'C'], ['B'], []]
2. Open Addressing
충돌이 발생했을 때, 비어있는 bucket을 찾을 때까지 탐색하여 빈 bucket에 value를 저장한다.
저장공간이 처음에 정해져 변하지 않으며, 빈 공간이 없는 경우 시간이 오래 걸릴 수 있다.
이때 Load Factor (= (hash table에 들어갈 데이터 개수) / (bucket 길이) ) 를 작게 설정하면 효과적으로 충돌을 방지할 수 있다. (체이닝을 사용하면 load factor를 1 이하로 유지하여 성능 좋은 해시 테이블을 구성할 수 있다)
해시를 사용할 때는 좋은 해시 함수(계산이 간단하고, 충돌을 피할 수 있는)를 사용하여 성능을 높일 수 있다.
*계산이 간단한 경우 예시 : chaning 을 사용하여 모든 과정(검색, 입력, 삭제)에 대해 O(1)의 시간 복잡도를 가지는 경우
*충돌을 피할 수 있는 경우 예시 : 유사한 문자열에 대해 다른 해시를 생성하는 경우
적절한 해시테이블 크기를 설정하는 것도 중요하다.