개념 정의
해시테이블
hashTable
hashTable은 { key : value } 로 구성되고 hash 기법을 이용해 데이터의 저장, 조회, 삭제의 속도를 높히는 자료구조이다. 즉 추상 데이터 구조라고 할 수 있다.(21.4.6.) 솔직히 추상자료형이라고 하기엔...글쎄다. 해시테이블은 자료를 저장해두고 탐색하는 것에 초점을 두고 있기 때문에, 그 세부구현이 훨씬 중요하다. 추상자료형은 사용자가 내부 구현을 모르더라도 해당 메소드를 사용하기 위해 존재하지만, 해시테이블은 언어마다 자료형이 다르고, 구현되는 내용이 다르기 때문에, 추상자료형이 중요하다고는 말할 수 없을 거 같다.
(자바에는 hashTable 클래스가 존재하지만, 해시테이블은 일반적으로 자바의 hashTable 클래스를 지칭하지 않는다.)
hashSet(21. 4. 6.추가)
집합을 구현하는 대표적인 자료구조이다. 파이썬에서는 set 자료형으로 사용한다.
- 해시값을 인덱스로 하여 배열(Bucket)에 자료를 저장하는 자료구조이다.
- 자료를 저장하는 인덱스는 index = hash_value % bucket_size로 정한다.
- 자료의 중복을 허용하지 않으며, 빠르게 자료를 탐색할 수 있다.
해시테이블과의 차이는 해시테이블은 key:value 로 key를 해싱해 인덱스로 삼고 value를 저장하지만, 해시셋은 value 자체를 key로 삼아 해싱하고, 그 인덱스에 바로 값을 저장한다. 그래서 값의 중복을 허용하지 않는다.
hashMap
hashMap은 hashTable 자료구조 및 hash 기법, hash function 등을 구체화 시켜 실제 코드로 사용할 수 있게 만든 클래스 및 인터페이스이다.
파이썬에서는 dictionary를 사용한다.
hash
는 key 값을 hash function 을 통해 특정 값으로 변환 시키는 기법이다. 이 특정 값은 hash table의 인덱스가 된다. (추가 21.4.6.) 이 해시 value가 곧 바로 인덱스가 되지는 않는다. 내가 사용하려는 해시 테이블의 bucket size가 있을 것이고, 이 bucket size를 기준으로 해시 value를 인덱스로 재생산해야 한다. 보통 modular(나머지) 함수를 사용해서 이 인덱스를 산출해 낸다.
hash function
hash funciton은 key 값을 받아 특정 output으로 만들어주는 함수이다. hash table은 이 output을 인덱스로 삼아 이 인덱스에 해당하는 bucket에 value를 넣는다.
시간 성능
(21. 4. 6.)추가 이 해시 함수의 성능은 해시테이블의 성능에 매우 중요한 영향을 미친다. 왜냐하면 해시테이블의 주요 작업인 데이터 set과 데이터 get을 작동시킬 때 마다 해시 함수가 동작하기 때문이다. 이 해시 함수의 시간이 오래걸린다면 그와 비례해서 해시테이블 전체의 성능이 떨어지게 될 것이다.
충돌 성능
해시 함수가 충분히 value를 배분해주지 못한다면 값의 클러스터링이 일어나게 되고, 이는 해시충돌 가능성을 매우 높힌다. 해시 충돌은 해시 테이블의 성능 저하에 지대한 영향을 미치게 되므로 이는 최대한 회피해야 하는 요인에 속한다.
생각
나는 어떤 용어를 사용하든지 그 용어의 정의가 매우 중요하다고 생각한다.
하지만 많은 블로그 들을 보면 hashmap, hash table을 혼용해서 사용하고 마치 그 둘이 같은 개념이라고 적어두는 곳이 많은 것 같다.
해시테이블을 효율적으로 구성하기 위해서는 해시 함수를 이용해 key 값을 해싱해야 하고, 해싱값으로 적절한 인덱스를 구성해야 한다. 그리고 인덱스가 겹치는 해시 충돌에 대해 적절하게 대처해야 해시테이블 자료구조를 구현할 수 있다.
테이블의 데이터가 늘어나다 보면 해시충돌이 발생하게 된다. key 값은 무한하게 많을 수 있는데, 인덱스로 지정할 수 있는 공간(bucket)은 한정되어있기 때문이다. 비둘기집의 원리라고도 한다.
비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.
by wekipedia
해시 충돌
해시 테이블은 해시 충돌이 발생했을 때의 문제를 크게 분리연결법(chaining) 과 개방주소법(open addressing) 두 가지로 해결하고 있다.
(21.4.6. 추가) 파이썬의 경우 개방 주소법, 자바의 경우 분리 연결법을 사용한다. 파이썬 공식문서에는 chaining의 노드를 만들어내는 오버헤드가 커서 개방주소법을 사용한다고 한다.
분리연결법
분리연결법은 해시 충돌이 발생했을 때 해당 해시 충돌이 발생한 인덱스 버킷에서 연결리스트를 구성해 추가적인 공간을 확보하는 방법이다.
예를 들어, 아래 그림을 보면,
출처 : https://mangkyu.tistory.com/102(망나니개발자)
"john smith" 와 "sandra dee" 가 같은 버킷값을 가져 해시 충돌을 발생시키고 있다. 그러면 기존에 들어있던 john smith 값에서 "Sandra dee" 값을 포인팅하게 만들어서 연결 리스트를 구성하게 된다.
이 방식은 복잡하지 않고, 테이블 구조를 변형하거나 알고리즘적으로 접근할 필요가 없기 때문에 만들기가 쉽다. 하지만 해시 충돌이 빈번하게 발생한다면 연결리스트가 계속 만들어지기 때문에, 해시 테이블의 장점(조회의 시간복잡도가 빠름)을 잃게 될 확률이 많다.
개방주소법
개방주소법은 분리연결법(폐쇄주소법)과 대조적으로 해시충돌이 발생했을 때 추가적인 메모리를 사용하지 않고 해시 테이블 내부의 비어있는 공간을 이용한다.
linear probing, quadratic probing, double hashing probing 세 가지 기법이 대표 적인데,
linear probing
현재의 인덱스로부터 고정 폭 만큼 다음 인덱스로 이동
장점 : 간단한 구조
단점 : 클러스터링에 가장 취약
클러스터링 : 데이터가 특정 주소값으로 군집화 되는 것
quadratic probing
현재의 인덱스로부터 제곱수만큼 다음 인덱스로 이동
1을 이동해보고 존재하면 4, 9 씩 계속 다음 인덱스로 이동
double hashing probing
해시 값을 한 번 더 해싱해서 나온 인덱스를 사용
장점 : 클러스터링에 가장 강력
단점 : 연산 시간이 오래 걸림
개방주소법은 테이블의 값들이 삭제될 경우에 문제가 발생할 수 있다. 해시충돌이 여러번 발생하여 여러번의 probing 을 걸쳐 데이터가 저장되어있는데, 중간의 값이 삭제되는 경우가 있을 수 있다. 그러면 데이터를 조회할 때 중간에 데이터가 끊어진 부분이 있으므로 정확한 조회가 불가능해진다. (각 데이터가 다음 데이터를 포인팅하기 때문에)
이를 예방하기 위해서 dummy data를 중간에 넣게 되고, 주기적인 refreshing 과정이 필요하다.
해시는 데이터가 전체의 80%를 차지하게 되면 해시충돌이 너무 빈번하게 발생하게 되어 효율이 많 떨어지게 된다.
(21. 4. 6.) 추가 실제로 분리연결법을 사용하는 것은 효율적이지 않을 수가 있는데, 왜냐하면 현대의 메모리는 충분히 커서 해시충돌이 잘 일어나지 않을 뿐만 아니라, 일어나더라도 다음 노드의 저장하는 것으로 발생하는 오버헤드는 거의 없기 때문이다.
코드 구현(21. 4. 6. 추가)
class HashTable:
def __init__(self, hash_func = None, bucket_size=15):
self.hash_func = hash_func
self.bucket_size = bucket_size
self.hashTable = [[i, None, None, None] for i in range(bucket_size)]
def set(self, key, value):
hash_result = self.hash_func(key)
object = self.hashTable[hash_result % self.bucket_size]
if object[1] is None:
object[1] = key
object[2] = value
else:
if object[1] == key:
print("already key")
return False
else:
new_node = [hash_result % self.bucket_size, key, value, None]
while object[3] is not None:
object = object[3]
object[3] = new_node
def get(self, key):
hash_result = self.hash_func(key)
object = self.hashTable[hash_result % self.bucket_size]
if object[1] == key:
return object[2]
else:
if object[3] is not None:
while object[3] is not None:
object = object[3]
if object[3] is None:
print("no key")
return False
elif object[1] == key:
return object[2]
else:
print("no key")
return False