본문 바로가기
Data Structure & Algorithm

해시 테이블 (Hash Table) (3)

Johny-609 2023. 1. 1. 22:10

6. 충돌(Collision) 해결 알고리즘 (좋은 해시 함수 사용하기)

해시 테이블의 가장 큰 문제는 충돌(Collision)이다. 이 문제를 충돌(Collision) 또는 해시 충돌(Hash Collision)이라고 부른다.

 

두 개 이상의 데이터가 동일한 hash address에 저장이 될 경우 충돌이 발생한다.

 

충돌 해결의 전략은 크게 2 가지이다.

  1. 개방 해싱(Open Hashing) 기법: 해시 테이블 저장공간 외의 공간을 활용하는 기법
  2. 폐쇄 해싱(Close Hashing) 기법: 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

 

Chaining 기법은 개방 해싱(Open Hashing) 기법 중 가장 많이 사용되는 기법이다. 충돌이 일어나면 링크드 리스트라는 자료구조를 사용해서 링크드 리스트로 데이터를 추가로 뒤에 연결시켜 저장하는 기법이다.

 

앞서 본 해시 테이블 코드에 Chaining 기법으로 충돌 해결 코드를 추가해보면 다음과 같다.

 

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:	# 데이터가 들어가 있다면
        for index in range(len(hash_table[hash_address])):	# 파이썬에서는 리스트에 append로 데이터를 추가하면 링크드 리스트와 유사한 효과를 낼 수 있다.
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value])	# index_key와 같은 것이 하나도 없다면, hash_table[hash_address]에 지금의 index_key 값을 가진 것을 추가하는 것. 결과적으로 내가 원하는 데이터가 충돌이 되더라도 append의 형태로 리스트 데이터가 테이블 밖 슬롯에 추가된다.
    else:
        hash_table[hash_address] = [[index_key, value]]	# 어드레스가 0이라면 데이터가 없다면 [index_key, value]라는 리스트를 가지고 있는 리스트를 만드는 것. 0번 데이터를 넣은 것이다.

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None	# 링크드 리스트는 있었는데 그 key값에 해당하는 값이 없다는 것. 그래서 None을 리턴
    else:	# 0이면 데이터가 아예 없는 것이니 None으로 끝남
        return None

 

이렇게 된다. 이것을 테스트 해보면,

 

print(hash('David') % 8)
print(hash('Daddario') % 8)

save_data('David', '1201023010')
save_data('Daddario', '3301023010')
print(read_data('David'))

print(hash_table)

 

 

이렇게 값이 나오는 것을 알 수 있다. hash() 함수를 사용하기에 값을 엄밀히 통제할 수는 없고, 위와 같이 충돌이 발생하는 경우를 만들어봤다. 충돌이 발생하더라도 read_data('David')가 '1201023010'으로 잘 출력되는 것을 알 수 있다.

 

만약에 이것을 배열로 했다면 충돌이 얼마나 일어날 지 모르는 상황에서, 최대 충돌 확률 만큼 미리 공간을 잡아놔야 할 것이다. 반면 링크드 리스트는 충돌이 날 때에만 리스트 데이터를 만들면 되기 때문에 많이 사용된다.

 

 

 

Linear Probing 기법은 폐쇄 해싱(Close Hashing) 기법 중 가장 많이 언급되는 기법이다. 충돌이 일어나면 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법인 것이다. 이러한 폐쇄 해싱 기법은 저장 공간 활용도를 높일 수 있다는 장점이 있다.

 

Linear Probing 기법을 코드로 구현하면 다음과 같다.

 

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)	# key를 별도 변수로 넣는 것은 다른 공간에 충돌된 데이터를 넣을 경우, 특정 주소인 hash address를 얻었을 때 이 데이터가 내가 원하는 데이터인지, 아니면 충돌이 되어서 이곳에 저장되어 있는 것인지 알기 위해서이다.
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:	# 데이터가 있다면
        for index in range(hash_address, len(hash_table)):	# 현재 hash_table의 길이는 8이다. hash_address 이후부터 순회를 돌리는 것
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]	# 데이터가 원래 안 들어가 있던 상태이므로 그곳에 key와 value를 저장하는 것
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value	# 지금 이 데이터 주소의 index_key가 동일하다면 hash_table[index]의 [1]이 value가 된다는 것
                return
    else:	# 해당 슬롯에 데이터가 한 번도 들어간 적이 없는 것
        hash_table[hash_address] = [index_key, value]	# hash_table[hash_address]에 그냥 저장

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:	# for문을 계속 돌고 있는데 마지막까지 갔는데 해당 key값을 찾을 수 없다면 None을 리턴. 즉, 해당 데이터값이 한 번도 저장된 적이 없다는 것이다.
                return None
            elif hash_table[index][0] == index_key:	# 내가 원하는 key를 찾았을 때, value를 리턴
                return hash_table[index][1]
    else:
        return None

 

이렇게 된다. 이것을 테스트 해보면,

 

print(hash('dk') % 8)
print(hash('da') % 8)
print(hash('dc') % 8)

save_data('dk', '01200123123')
save_data('da', '3333333333')
print(read_data('dk'))
print(read_data('dc'))	# 'dc'는 값이 저장되지 않아서 None이 나옴

 

'dk', 'da', 'dc'가 서로 충돌하게 했을 때, 이렇게 출력된다.

 

 

충돌이 되더라도, 'dk'의 데이터가 잘 출력되는 것을 알 수 있다. 'dc'는 데이터를 저장하는 절차를 진행하지 않았기 때문에 정상적으로 None이 출력된다.

 

 

 

한편, 빈번한 충돌을 개선하는 방법은 해시 함수를 재정의하거나, 해시 테이블 저장 공간을 확대하는 것이 있다.

 

hash_table = list([None for i in range(16)])

def hash_function(key):
    return key % 16

 

위 코드에서처럼 해시 테이블의 슬롯을 늘려주는 것이다.

 

참고로, 파이썬의 hash() 함수는 실행할 때마다 값이 달라질 수 있다. 반면, SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)은 어떤 데이터도 유일한 고정된 크기의 값으로 리턴해주므로, 해시 함수로 유용하게 활용할 수 있다.

 

SHA를 사용하려면 파이썬에서 hashlib라는 라이브러리를 import 해줘야 한다.

 

import hashlib

data = 'test'.encode()	# 인코딩을 하는 것은 바이트로 바꾸는 것이다.
hash_object = hashlib.sha1()	# sha1 해시 알고리즘을 사용하고 싶다면, hash_object를 하나 만들어야 한다.
hash_object.update(data)	# 만든 hash_object에 인코딩 한 데이터를 update 한다.
# hash_object.updata(b'test') 로 기입해도 된다. b는 바이트를 의미함
hex_dig = hash_object.hexdigest()	# 몇 진수로 다시 추출할 것인지 쓰는 것이다. 보통은 16진수로 많이 추출한다.
print(hex_dig)

 

 

이런 값이 몇 번을 출력해도 동일하게 나온다. 'test'라는 값의 해시 값이 이런 것이다. SHA의 일반 hash()와 큰 차이점이라고 할 수 있다. 이 해시값은 문자열이 같을 경우 항상 동일한 해시값이 나오고, 문자열이 한 글자이든, 십만 글자이든 이 정도로 고정된 길이의 해시값을 추출할 수 있다.

 

이것보다 조금 더 보안이 잘 되어 있는 함수가 SHA-256이다. 고정된 길이가 조금 더 늘어난다.

 

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()	# SHA-256 사용
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print(hex_dig)

 

 

이 데이터를 가지고 원래 데이터가 무엇인지 추론할 수 없다. 보안적인 측면에서 훌륭한 것이다. 블록체인의 해시값 원리와 같다고 할 수 있다.

 

앞서 알아본 Linear Probing 기법을 적용한 해시 테이블 코드에 키 생성 함수를 sha256 해시 알고리즘을 사용해보면 아래와 같다.

 

import hashlib

hash_table = list([0 for i in range(8)])

def get_key(data):
        hash_object = hashlib.sha256()
        hash_object.update(data.encode())
        hex_dig = hash_object.hexdigest()
        return int(hex_dig, 16)	# hex_dig는 문자열이기 때문에, 문자열을 가지고 나머지를 구할 수 없다. 그래서 이 부분을 숫자로 만들어주는 것이다. 16진수의 문자열을 10진수(정수)로 만들어줄 때 이렇게 기입한다.

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

 

 

7. 시간 복잡도

  • 일반적인 경우인 Collision이 없는 경우는 O(1)
  • 최악의 경우인 Collision이 모두 발생하는 경우는 O(n)

해시 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1) 이라고 말할 수 있다.

 

검색에서 해시 테이블의 사용 예

  • 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
  • 16개의 데이터 저장공간을 가진 위의 해시 테이블에 데이터를 저장하고, 검색할 때 O(1)

배열의 사이즈에 따라 저장하고 검색할 때 다 순회를 해야 하기 때문에 O(n)인데 반해, 해시 테이블의 경우 해시 함수를 통해서 특정 위치에 저장한 해당 데이터를 바로 찾을 수 있기 때문에 O(1)이다. 그래서 해시 테이블이 배열보다 저장과 검색에 있어서는 훨씬 더 개선된 자료구조이다.

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료

'Data Structure & Algorithm' 카테고리의 다른 글

트리 (Tree) (2)  (0) 2023.01.03
트리 (Tree)  (0) 2023.01.02
해시 테이블 (Hash Table) (2)  (0) 2022.12.08
해시 테이블 (Hash Table)  (0) 2022.12.07
링크드 리스트 (Linked List) (3)  (0) 2022.12.06

'Data Structure & Algorithm' Related Articles

티스토리툴바