[파이썬으로 배우는 자료구조] 해시(Hash)

728x90

해시(Hash)란?

일반적으로 말하는 해시/해쉬(Hash)는 해시 테이블(Hash Table)로 Key와 Value를 매핑해서 데이터를 저장하는 자료구조입니다. 파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조입니다! 쉽게 이해하기 위해서 관련 용어를 먼저 설명한 뒤에 특징을 살펴보도록 하겠습니다.

용어

키(Key) - 고유의 값으로 해시 함수의 Input. 다양한 길이의 값이 될 수 있다.
해시 테이블 (Hash Table) 또는 해시 맵(Hash Map) - Key와 Value를 매핑해서 데이터를 저장하는 자료구조
해시 함수(Hash Function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수. 다양한 길이의 키를 고정된 길이의 해시로 변환시키므로 저장소를 효율적으로 운영할 수 있게 해준다.
해시(Hash) - 해시 함수의 output으로 해시 값과 매칭되어 버킷에 저장된다.
해시 값(Hash Value) 또는 해시 주소(Hash Address) - 키에 해시 함수를 적용하여 얻는 해시 값
버킷(Bucket) - 한 개의 데이터를 저장할 수 있는 공간

위 그림으로 설명을 하자면, 다양한 길이를 갖고 있는 Key 값에 해시 함수를 적용시키면 00, 01, 02 등과 같이 고정된 길이의 데이터로 변환이 됩니다. 이렇게 변환된 데이터가 해시 값이고, 버킷에는 키와 매핑된 원래 데이터를 저장하게 됩니다. 결과적으로는 변환된 키값과 버킷에 매핑되어 있는 데이터를 해시라 하고 이러한 자료구조를 해시 테이블이라고 하는 것입니다.

해시의 특징

연산의 평균 시간복잡도가 O(1)로 데이터 저장 및 읽기 처리 속도가 매우 빠릅니다. 배열의 인덱스와 같이 해시 함수를 통해 얻은 키값으로 그 위치를 찾아주면 되는 것입니다. 위 그림으로 예를 들면 John Smith라는 키의 데이터를 찾는다고 하면 먼저 해시 함수를 통해 해시 값을 얻고 그 해시 값을 인덱스로 사용하여 찾아주면 됩니다.

하지만 해시라고 해서 무조건 O(1)의 시간 복잡도를 갖는 것은 아닙니다. worst case인 경우 O(n)의 시간복잡도를 갖습니다. 그 이유는 바로 충돌(Collision) 때문입니다. 그렇다면 충돌이란 무엇일까요?

충돌(Collision) - 여러 개의 키값이 해시 함수를 통해 같은 해시 값을 갖는 경우

만약 해시 테이블에 데이터를 저장한다고 합시다. Rdav라는 키값을 가진 데이터를 저장하기 위해 해시 함수를 적용시켰는데 해시 값으로 기존에 존재하는 값이랑 중복되는 값이 나와버리게 되었습니다. 해시 함수라고 해서 꼭 전부 다른 해시 값을 산출해내는 것은 아닐 수도 있으니까요! 이런 경우는 어떻게 해결해야 할까요?

해시 충돌 해결

Chaining

Chaining은 충돌이 발생할 시 버킷에 연결리스트 자료구조를 통해 데이터를 연결하여 충돌을 해결하는 방법입니다.

Open Addressing

Open Addressing 방법은 충돌이 발생하면 빈 버킷을 찾아 데이터를 저장하는 방법으로 대표적으로 선형 탐색 방법이 있습니다.

선형 탐색(Linear Probing) - 충돌이 발생하면 해당 위치부터 순차적으로 버킷을 하나하나씩 탐색

해시 값 02로 충돌이 발생해서 다음 버킷을 탐색했는데 빈 버킷이므로 해당 위치에 데이터를 저장하게 됩니다. 선형 탐색 이외에 제곱 탐색, 이중 해시 방법이 있습니다.

제곱 탐색(Quadratic Probing) - 충돌이 발생하면 해당 위치부터 제곱만큼 떨어진 다음 버킷을 탐색 (1, 4, 9, 16,... )
이중 해시(Double Hashing) - 충돌이 발생하면 다른 해시 함수를 한번 더 적용

해시 구현

코드

hash_table = [0 for _ in range(100)]

def hash_function(key):
    # 파이썬 내장함수 hash 사용
    return hash(key) % 100

def set_data(key, value):
    hash_value = hash_function(key)
    hash_table[hash_value] = value

def get_data(key):
    hash_value = hash_function(key)
    return hash_table[hash_value]

set_data('Rdav', 2022)
set_data('hello', 77)
print(get_data('Rdav'))
print(get_data('hello'))

실행 결과