TIL103. Algorithm : Hash Tables

📌 이 포스팅에서는 Hash Tables에 대해 정리하였습니다.

🌈 Hash Tables

🔥 Hash Tables 이란?

🔥 Hash Tables vs Arrays

🔥 Hash Collisions

1. Hash Tables 이란?

🤔 사전이 알파벳 순으로 되어 있지 않다면 어떻게될까?

✔️ 사전이 알파벳 순으로 되어 있지 않다면, 내가 원하는 단어의 뜻을 알기 위해 처음부터 순차적으로 확인해야 한다. 하나하나 모두 확인해야하는 이 과정은 단순 탐색과 같고, 시간 복잡도는 O(N)이다.

✔️ 다행스럽게도 사전은 알파벳순으로 되어있기 때문에 이진 탐색이 가능하다. 이 경우에 시간 복잡도는 O(logN)이다.

✔️ 이번에는 사전이 아니라, 마트에서 계산원을 하고 있다고 생각해보자. 물품별로 가격이 적혀있는 장부가 있을 때, 단순 탐색은 O(N)이고, 이진탐색을하면 O(logN)의 시간복잡도가 필요하다.

✔️ 1초에 품목 10개를 읽을 수 있다고 가정하면, 판매중인 물건 1개의 값을 알아내는데 아래와 같은 시간이 필요하다.

✔️ 따라서 O(logN)의 시간 복잡도를 가지는 이진 탐색 또한 이러한 상황에서는 효율적인 방식이 아니다. 10000개의 품목을 판매 중이라면 계산원이 1개의 물품의 가격만을 확인하는데에도 최대 2초의 시간을 소요되기 때문이다.

✔️ 이에 더 효율적인 방식의 자료구조가 필요하다. 이를 가능하게하는 것이 해쉬다. 해쉬가 얼마나 빠른지는 뒤에서 살펴보겠다.

🤔 Hash Tables의 특징

✔️ 해쉬 테이블은 키(key)에 값을(value)를 저장하는 데이터 구조로 키(key) 값을 마치 index처럼 상용하여 값(value)을 읽을 수 있기 때문에 빠르다.

✔️ 이미 python에서는 dictionary라는 데이터 타입이 이를 지원하고 있다. 즉, python에서는 해쉬 테이블을 별도 구현할 필요 없이 딕셔너리를 사용할 수 있고, 딕셔너리 내부적으로 해쉬 테이블의 구조를 갖고 있다.

✔️ 해쉬의 대표적인 장점으로는 데이터를 Create/Read 하는 속도가 빠르고, 이미 Key가 존재하는지 중복을 처리하기가 쉽다.

✔️ 단점으로는 충분한 저장 공간을 확보해두어야하기 때문에 비교적 저장 공간이 많이 필요하고, 여러 Key에 해당하는 주소가 동일할 경우 충돌을 막기 위한 방편이 필요하다. 이는 추후 다뤄보겠다.

✔️ 이에 해쉬 테이블의 주 용도는 CRUD가 빈번한 경우, 검색이 자주 일어나는 경우, 캐쉬를 구현할 때 활용된다.

✔️ 예를 들어, 스마트폰의 주소록은 해쉬로 개념과 동일하다. 사람을 주소록에서 검색하면, 전화번호, 주소, email 등을 모두 빠르게 확인할 수 있다.

✔️ 뿐만아니라 앞에서 정리한 Domain과 IP Address의 관계도 이러한 해쉬로 이뤄져있다.

🤔 해쉬 테이블 관련 용어

✔️ hash : 임의에 값을 고정 길이로 변환하는 것

✔️ hash table : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

✔️ hash function : Key에 대해 산술 연산을 적용해 해쉬 값으로 변환해주는 함수

✔️ hash value : Key를 해싱 함수에 대입하여 반환되는 것을 해쉬 값이라하고, 이를 기반으로 테이블에서 해당 Key에 대한 데이터 위치를 탐색

✔️ slot : 한개의 데이터를 저장할 수 있는 공간

2. Hash Tables vs Arrays

🤔 hash의 시간복잡도는 어떻게 될까?

✔️ 해쉬는 key값을 통해 value를 바로 읽어올 수 있기 때문에 장부의 품목이 무한대로 늘어난다해도 O(1)의 시간 복잡도를 가진다.

✔️ 사실, O(1)이라는 시간복잡도는 Key값을 해쉬 함수에 넣었을 때, 충돌이 발생되지 않을 때(반환되는 해쉬 값이 중복이 없을 때)에 해당된다. 이에 대해서는 아래서 다시 얘기해보도록 하자.

🤔 간단 해쉬 테이블 구현하기

✔️ 10자리의 간단한 해쉬 테이블은 배열을 사용하여 아래처럼 만들어 볼 수 있다.

# 빈 해쉬 테이블 만들기
hash_table = list([0 for i in range(10)])
print(hash_table) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

✔️ 간단 해쉬 테이블 구현이기 때문에 division 방식으로 해쉬 함수가 아래처럼 존재한다고 가정해보자.

# 간단 해쉬 함수
# Division 방식 : 나누기를 통한 나머지 값을 사용하는 기법
def hash_func(key):
    return key % 5  # 👈 어떤 key값이 들어오면, 이를 5로 나눈 나머지를 반환해요!

✔️ 해쉬 테이블에 값을 저장하는 함수는 아래 처럼 작성할 수 있다. key값이 string이기 때문에 ord로 숫자로 변환 후, index값을 구하기 위해 해쉬 함수에 넣는다.

def storage_data(data, value): # 👈 키와 저장할 데이터를 받음
    key = ord(data[0]) # 👈 키를 해쉬함수에 넣어 연산하기 위해 숫자로 변환
    hash_address = hash_func(key) # 👈 해쉬 함수 작동하여 해쉬값(해쉬주소) 얻음
    hash_table[hash_address] = value # 👈 해쉬 주소를 index로하여 데이터를 테이블에 저장
storage_data('Jaewon', '010-1234-5678')
storage_data('Haezin', '010-4444-9999')
storage_data('Ginsu', '010-8989-1212')
# 해쉬 테이블 저장 후 해쉬 테이블 상태 확인
print(hash_table)
# [0, '010-8989-1212', '010-4444-9999', 0, '010-1234-5678', 0, 0, 0, 0, 0]

✔️ 해쉬 테이블에 값을 저장했으니, 이를 읽어올 수 있는 함수도 아래 처럼 만들 수 있다.

# 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수
def get_data(data):
    key = ord(data[0]) # 👈 데이터에서 Key를 추출
    hash_address = hash_func(key) # 👈 key를 해쉬 함수에 넣어 해쉬 주소를 얻음
    return hash_table[hash_address] # 👈 해쉬 주소를 통해 배열에서 데이터를 반환
print(get_data('Jaewon')) # 010-1234-5678
print(get_data('Haezin')) # 010-4444-9999
print(get_data('Ginsu')) # 010-8989-1212

🤔 해쉬, 배열, 연결 리스트의 시간 복잡도는 어떻게 될까?

✔️ 사실 해쉬 테이블의 시간복잡도는 평균적으로 가지는 해쉬의 시간복잡도와 최악의 경우의 시간 복잡도가 존재한다.

✔️ 간단 해쉬 테이블의 예시를 통해 충돌이 어떻게 발생하는지 살펴보도록 하겠다.

✔️ 예를 들어, key값이 'Jeawon'과 'Jisu'가 있다면, 둘다 'J'를 ord 함수로 처리하기 때문에 74를 반환받는다. 이를 해쉬 함수에 넣어 5로 나눈 몫은 서로 동일하기 때문에 덮어씌어지는 충돌 문제가 발생한다.

✔️ 충돌을 해결하기 위한 방법으로 Open Hashing방식의 Chaining 기법 또는 Close Hashing 방식의 Linear Probing 기법을 사용하는데, 이럴 경우, 해당하는 key값을 찾기 위해 다시 반복이 필요하기 때문에 O(N)의 시간복잡도를 가진다.

✔️ 따라서 해쉬, 배열, 연결 리스트의 시간복잡도는 아래와 같다.

3. Hash Collisions

🤔 Close Hashing 기법

✔️ 해쉬 충돌을 해결하는 방법으로 Close Hashing 기법으로 대표적인 기술은 Chaining이다.

✔️ Chaining은 해쉬 테이블 공간 외의 새로운 공간을 마련하여 충돌이 발생 시 연결 리스트 자료 구조를 사용해 데이터를 저장하는 기법이다.

✔️ 또한 Chaining 기법은 데이터를 식별할 수 있는 key값을 함께 저장하여 이를 식별하는데, 단점으로는 공간이 많이 필요하다.

# 해쉬 테이블
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) # 👈 index_key라는 별도의 변수에 key값을 저장
    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:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value])
    else: # hash_table[hash_address] == 0 👈 없을 때
        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(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None
# 해쉬주소 중복 발생 <- 할때마다 변함
print(hash('Jaewon')%8) # 3
print(hash('Haezin')%8) # 2
print(hash('AaLa')%8)  # 3
# 저장
save_data('Jaewon', '01011112222')
save_data('Haezin', '01088889999')
save_data('AaLa', '01033331234')
print(hash_table)
# [0, 0, [[-3231082452735185358, '01088889999'], [630994963842225842, '01033331234']], [[-6162502635708335149, '01011112222']], 0, 0, 0, 0]
# 조회
print(read_data('Jaewon')) # 01011112222
print(read_data('Haezin')) # 01088889999

🤔 Open Hashing

✔️ Linear Probing 기법은 Open Hashing의 한 기술로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 대표적인 방식이다.

✔️ 또한 Linear Probing 기법은 충돌 발생 시, hash adress의 다음 adress부터 맨 처음 나오는 빈 공간에 저장하는 방식이기 때문에 저장공간 활용도가 높다.

# 해쉬 테이블
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(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
    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
# 해쉬주소 중복 발생 <- 할때마다 변함
print(hash('Jaewon')%8) # 0
print(hash('Haezin')%8) # 0
print(hash('AaLa')%8)  # 7
# 저장
save_data('Jaewon', '01011112222')
save_data('Haezin', '01088889999')
save_data('AaLa', '01033331234')
print(hash_table)
# [[3214169218863054112, '01011112222'], [-291548128366538008, '01088889999'], 0, 0, 0, 0, 0, [-143120377966334057, '01033331234']]
# 조회
print(read_data('Jaewon')) # 01011112222
print(read_data('Haezin')) # 01088889999