[자료구조] Hash Table

Hash

Hash는 입력 데이터를 고정된 길이의 데이터로 변환된 값. 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수. 해시 함수는 키를 해시 테이블의 주소로 변환하는 함수. Python에서는 hash() 내장 함수를 통해 객체의 해시 값을 얻을 수 있음.

Hash Table

Hash Table은 작업 속도가 빠르도록 설계된 데이터 구조.

Array나 Linked List 보다 Hash Table이 많은 양의 데이터에 대해서도 데이터 검색, 추가 및 삭제를 매우 빠르게 수행할 수 있음.
Array나 Linked List의 시간복잡도 O(n), Hash Table의 시간복잡도는 O(1).
Hash Table은 어떤 것이 컬렉션에 있는지 확인하는 것(도서관에서 책을 찾는 것), 고유한 항목을 저장하고 빠르게 찾을 수 있거나 키에 값 연결(예: 전화 번호에 이름 연결).

예를들어, Linked List에서 "Bob"이 있는 노드를 찾을 때까지 한 노드에서 다음 노드로 이동하여 각 노드를 확인해야 하기 때문에 "Bob"이 있는 사람을 찾는 데 시간이 걸림.
Array에서는 "Bob"을 찾는 것은 인덱스를 알면 빠를 수 있지만, "Bob"이라는 이름만 알면 각 요소를 비교해야 해서 시간이 걸림.
Hash Table의 해시 함수라는 것을 사용하여 "Bob"이 저장된 곳으로 바로 이동할 수 있어서 훨씬 빠름.

Hash Table 구축하기

해시 함수는 여러가지 방법으로 만들 수 있음. 일반적으로 해시집합의 인덱스 숫자 중 하나와 같은 숫자로 변환하는 방법.

간단하게 유지하기 위해 목록에 최대 10개의 이름이 있다고 가정하고 배열은 10개 요소의 고정 크기로 가정. Hash Table에서 이러한 각 요소를 bucket라고 함.

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)     # 내장함수 ord(char)로 char의 아스키코드 값을 구함.

    return sum_of_chars % 10          # 10으로 나눈 나머지를 계산. 10으로 나누는 이유는 해시 값을 0에서 9 사이의 범위로 제한하기 위함.

print("'Bob' has hash code:",hash_function('Bob'))

'Bob' has hash code: 5

문자 "B"는 유니코드 66, "o"는 111, 그리고 "b"는 98. 유니코드값의 합은 275이므로 10으로 나누면 5가 반환됨. "Bob"은 인덱스 5에 배열 요소로 저장.
해시 함수가 반환하는 수를 해시 코드라함.
추가로 해시 함수를 사용하여 "Pete", "Jones", "Lisa", "Siri"라는 다른 이름을 저장할 위치 찾기.

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

"Pete"가 있는지 확인하기 위해 배열 요소를 요소별로 확인할 필요가 없기 때문에 해시 함수를 사용하여 올바른 요소로 바로 이동할 수 있음.

def contains(name):
    index = hash_function(name)
    return my_hash_set[index] == name

print("'Pete' is in the Hash Set:",contains('Pete'))

'Pete' is in the Hash Set: True

이 Hash Set에 "Stuart"를 입력해보자.
해시함수를 이용하면 해시코드 3이 반환되는데, 이미 "Lisa"가 있는 인덱스 3에 저장되어야하므로 충돌이 발생한다.
이를 해결하기 위해 같은 butket에 더 많은 원소가 들어가도록 공간을 만드는 chaining 방법을 사용한다. 각 butket을 Linked List나 Array로 구현한다.

def add(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    if value not in bucket:
        bucket.append(value)
        
add('Stuart')
print(my_hash_set)
print('Contains Stuart:',contains('Stuart'))

[[None], ['Jones'], [None], ['Lisa', 'Stuart'], [None], ['Bob'], [None], ['Siri'], ['Pete'], [None]]
Contains Stuart: True