Hash

# Hash Table

hash table은 key값을 input으로 넣어 hash function을 통해 나온 output, hash값를 인덱스화하여 value(데이터)를 저장하는 자료구조입니다. 이때, 데이터가 저장되는 공간을 bucket이라 합니다. 해시테이블은 (key, value)쌍을 저장하는데, 그렇기 때문에 순서가 없다는 특징이 있습니다

[ value ] 

우리가 저장하고자 하는 정보입니다

[ key ]

- value를 구분할 수 있는 고유한 데이터입니다.

- 해시테이블에서 value는 key를 기준으로 관리되기 때문에, key는 고유한 값을 가진다는 특징이 있습니다.(중복되면 안되기 떄문에 사람이름을 key로 쓰는 것은 적절하지 못합니다)

[ hash function ] 

- 임의의 데이터(key)를 특정 값(hash)으로 매핑시키는 함수입니다.

- key 값을 input으로 넣으면 hashing값을 output으로 반환해줍니다 (key의 주소값을 반환한다고 생각하면 됩니다)

- python은 hash라는 내장함수가 있습니다

hash('Hello')
# 8595176075292139795
hash('World')
# -8693978449659715803

- 좋은 해시 함수는 키값을 고르게 분포 시켜야 하며, 빠른 계산을 할 수 있고 충돌을 최소화할 수 있습니다

[ hashing ]

데이터를 빠르게 저장하고 가져오는 기법 중 하나로, 키에 특정 연산(hash function)을 적용하여 테이블의 주소를 계산합니다

 

 

# Hash Collision

해시 충돌은 키 값이 다른데, 해시 함수의 결과값(hash값)이 동일한 경우를 말합니다. (key값은 중복이 될 수없지만, key값의 결과값은 중복될 수 있습니다)  해시 충돌은 해시 자료구조의 성능을 저하시키는 가장 큰 요인이 되기 때문에 해시충돌이 가장 적게 생기도록 구현을 해야합니다 (해시 충돌은 필연적으로 발생할 수 밖에 없기 때문에, 완전히 피할 수는 없습니다)

해시 충돌을 해결하는 방법에는 2가지가 있습니다

[ Chaining ] 

key값을 해시함수에 넣어 나온 해시값을 인덱스화하여 value를 저장하는데, 다른 key도 같은 해시값을 가진다면 두 키가 똑같은 인덱스 값을 가지게됩니다. 이때, value를 저장하는 bucket이 마치 linkedlist처럼 다음 노드를 가리키게 해서 그 노드에 새로운 value를 저장하는 방식입니다. 이 모습이 체인과 같다해서 chaining이라고 합니다.

chaining 방법을 통해서 해시 충돌을 피하게 될 경우, 결국 hash function으로 인덱스의 위치를 찾는데 O(1)의 시간복잡도가 소요된다고 해도 인덱스 값으로 해당 value를 찾는데 리스트를 탐색하는 과정을 거쳐야하므로 O(N)만큼의 시간 복잡도가 더 소요됩니다. 많은 노드들이 연결되어 있을 수록 시간은 더 늘어나게 됩니다. 그래서 최악의 경우 O(N)만큼의 시간복잡도를 갖게 되는 것입니다

 

[ Open Addressing ] 

충돌 발생 시 다른 버킷에 데이터를 저장하는 방식입니다

- 선형탐색 

해시충돌시 n칸을 건너 뛴 다음 버킷에 저장하는 방법입니다. 예를 들어, 위의 그림에서 10번 인덱스에 데이터가 들어 있다면 그 다음 11번째에 데이터를 저장하는 것입니다. 11번에도 데이터가 들어있다면, 12번에 데이터를 저장하게 됩니다.

선형탐색으로 bucket을 찾게 되면, 계산이 단순하다는 장점이 있습니다. 하지만 비어있는 bucket을 찾기위한 검색시간이 많이 소요되며 최악의 경우 시간복잡도가 O(N)까지 늘어날 수 있습니다. 또한, 좋은 해시함수는 키 값을 고르게 분포시킨다고 했었는데 선형탐색의 경우 데이터들이 특정 위치에만 밀집된다(clustering)는 단점이 있습니다. (밀집될수록 해시 충돌의 가능성이 높아집니다)

- 제곱탐색

 N^2칸(1,4,9,16, ...)칸을 건너 뛴 bucket에 데이터를 저장하는 방법으로, 데이터들이 특정 위치에 밀집하는 clustering 문제를 해결한 방법입니다. 하지만, 해시함수를 통해 나온 해시값이 동일하다면 건너뛰는 칸의 갯수도 동일하기 때문에 여전히 O(N)번의 시간복잡도가 소요됩니다

- 이중해시

해시 값에 다른 해시 함수를 한번 더 적용하는 방법으로, 제곱탐색에서도 선형탐색의 단점을 보완하지 못해 나온 방법입니다.

- hashfunction1() : 해시값을 구하는 해시함수

- hashfunction2() : 충돌발생시 이동 폭을 구하는 해시함수

첫번째 해시함수를 통해 구해진 해시 값이 같더라도 이동 폭이 다르기 때문에 clustering문제를 해결할 수있습니다. 이 방법은 bucket을 탐색하는데에 있어서, 규칙성을 완전히 없애버린 방법이라고 할 수 있습니다

 

 

# 코드 구현 (Python)

해쉬 충돌이 발생했을 때, Linked List를 사용하여 chaining 방식으로 해결을 할 것입니다. 그래서 노드 생성 클래스를 만들어 줍니다. 이 노드에는 (key, value)쌍을 이루고 있는 데이터가 저장되게 됩니다.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value

배열 안에 리스트 노드를 만들 수 있는 bucket을 만들어 줍니다. 버킷사이즈는 2의 10제곱수인 1024를 default로 잡아줍니다.

class HashTable:
    def __init__(self, bucketsize=1024):
        self.buckets = [[]] * bucketsize
        self.size = 0
        self.bucketsize = bucketsize

 

 

[ put ]

put은 hash에 데이터를 넣는 기능을 하는 연산입니다.

def put(self, key, value):
    idx = hash(key) % self.bucketsize
    for element in self.buckets[idx]:
        if element.key == key:
            element.value = value
    node = Node(key, value)
    self.buckets[idx].append(node)
    self.size += 1

idx = hash(key) % self.bucketsize   hash(key)값을 인덱스화하여 데이터를 저장하는데 해시값이 bucketsize보다 클 수 있으므로 모듈로 계산해 무조건 인덱스가 버킷사이즈보다 작게 만들어 줍니다
for element in self.buckets[idx]:
    if element.key == key:
        element.value = value      키값은 고유해야하기 때문에, 같은 키 값으로 데이터가 들어온다면 새로운 value값으로 업데이트 되어야 합니다.
node = Node(key, value)             (key, value)쌍의 데이터 노드를 생성해줍니다
self.buckets[idx].append(node)   인덱스 위치의 버킷에 데이터를 저장해줍니다
self.size += 1

[ get ] 

get은 key값으로 value값을 반환받는 연산입니다

def get(self, key):
    idx = hash(key)% self.bucketsize
    for element in self.buckets[idx]:
        if element.key == key:
            return element.value
    return None

idx = hash(key)% self.bucketsize
for element in self.buckets[idx]:  
   if element.key == key:
       return element.value       for문으로 순환하면서 key값과 동일한 노드의 value를 반환합니다
return None

[ delete ] 

get은 인덱스 위치의 해당 데이터를 삭제하는 연산입니다.

def delete(self, key):
    idx = hash(key)% self.bucketsize
    for idx, element in enumerate(self.buckets[idx]):
        if element.key == key:
            self.buckets[idx].remove(element)
            self.size -= 1

idx = hash(key)% self.bucketsize
for idx, element in enumerate(self.buckets[idx]):     **enumerate 아래 설명 참조
   if element.key == key:
        self.buckets[idx].remove(element)
        self.size -= 1

**enumerate

- 반복문을 사용할때 리스트의 순서값, 즉 인덱스의 정보가 필요한 경우가 있는데, 이때 사용합니다. enumerate함수는 리스트의 원소에 순서값을 부여해주는 함수입니다. for문과 함께 자주 사용됩니다.

- 인덱스 번호와 컬렉션의 원소를 tuple형태로 반환합니다.

t = [1, 5, 7, 33, 39, 52]
for p in enumerate(t):
    print(p)
 
# (0, 1)
# (1, 5)
# (2, 7)
# (3, 33)
# (4, 39)
# (5, 52)

 

 

# 전체 코드

전체 코드와 다른 기능 함수들은 깃허브를 참고하시면 됩니다.

GitHub - sonzwon/TIL: Today I Learned