1.해쉬 테이블
해쉬 테이블이란
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
라는데 파이썬의 딕셔너리 기능과 같다고 보면 된다.
해쉬는 키를 통해 바로 데이터를 받아올 수 있으므로, 속도가 빠르다.
배열을 다 둘러보지 않고, 키에 대해서 검색하면 바로 값을 조회할 수 있는 자료구조이기 때문이다.
2.해쉬 함수
해쉬 함수는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다.
파이썬에서 hash(object)로 해쉬 함수를 제공하고 있다.
예를 들어 파이썬 콘솔에서 hash("fast") 라고 입력하면
hash("fast")
394819032821
이런식으로 출력이 된다.
이 값들을 이용하여 배열에 넣을 수 있다.
배열의 길이가 7이라면 해쉬함수를 7로 나눈 나머지를 구하는 것이다.
7로 나눈 나머지를 구한다면 무조건 7이내의 숫자가 나오게 되고 그 숫자를 이용해 인덱스의 배열에 넣는것이다.
이 개념을 그대로 이용하여 예제를 작성해 보았다.
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index] = value
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index]
my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))
put함수와 get함수에 있는 index는 둘 모두 해쉬값을 배열의 길이로 나눈 것이다.
그렇게 출력된 index값을 배열로 지정해준다.
위 예제에서 my_dict.put("test",3)을 입력한다면, key인 test는 해쉬함수로 바뀌어서 배열의 길이로 나뉘고, 그 값이 index가 되어 value인 3이 들어가는 배열의 순서가 된다.
my_dict.get("test")를 하면 test를 마찬가지의 과정을 거쳐 index로 바뀌고 바뀐 index를 가지고 value를 찾아낸다.
3.충돌
하지만 이런 방식으로 자료를 관리하면 문제가 생긴다
해쉬의 값이 같거나, 해쉬의 값을 배열의 길이로 나눈 나머지가 같은 경우가 발생 할 수도 있다.
그런 경우에는 같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생한다. 이를 충돌(collision)이 발생했다고 한다.
3-1 체이닝
이런 문제를 링크드 리스트를 사용하여 해결하는 방식이 체이닝이다.
fast 의 해쉬 값과 slow 의 해쉬 값이 동일하게 3이 나왔다고 하면 3번째 인덱스에 fast 와 slow 가 서로 충돌한다.
체이닝은 아래와 같이 둘을 연결해주는 것이다 .
이 개념을 가지고 개선된 딕셔너리를 쓰면 다음과 같다.
class linkedTuple:
def __init__(self):
self.items = list()
def add(self, key, value):
self.items.append((key,value))
def get(self, key):
for k, v in self.items:
if key == k:
return v
class linckedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(linkedTuple())
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key, value)
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
간단히 내가 이해한대로 정리해보자면, linkedDict라는 리스트의 배열안에 linkedTuple이라는 리스트를 넣는 것이다.
그렇다면 index가 중복되어도 그 [index] 안의 list에 value가 저장되는것이다.
값을 찾을때도 index가 중복된다면, 중복된 [index]의 list에서 쪼개지지 않은 key값을 이용해 값을 찾아낸다.
3-2 개방 주소법
충돌을 해결하는 두 번째 방법은 배열의 다음 남는 공간에 넣는 것이다.
fast 의 해쉬 값과 slow 의 해쉬 값이 동일하게 3이 나와서 충돌 할때, items[4] 를 본다. 이미 차 있다면 그 다음 칸인 items[5] 를 본다.
비어 있으면 items[5] 에 slow 의 value 값을 넣는다.
이런 방식을 개방 주소법(Open Addressing) 이라고 한다.