(자료구조) 해쉬테이블

TIL/Data Structures and Algorithms

(자료구조) 해쉬테이블

parksisi 2021. 1. 22. 09:50

1. 해쉬테이블 소개

- 엄청난 룩업 속도를 자랑한다.

- 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시맵, 딕셔너리 등이다.

- 해쉬테이블의 값 룩업은 평균적으로 O(1)이다.

- 원래 해쉬의 뜻은 임의 값을 어떤 고정된 길이의 값으로 변환하는 것을 말한다

- 해쉬함수가 유효하려면 딱 한가지 기준을 충족해야한다. 해쉬 함수는 동일한 문자열을 해쉬 함수에 적용할 때마다 항상 동일한 숫자로 변환해야한다.

2. 해쉬 구조

- Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조

Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

- 키 -> 해쉬함수 -> 해시주소

- 용어 정리

해쉬: 임의 값을 고정 길이로 변환하는 것
해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음 (데이터 -> 키 -> 해쉬함수 -> 해시주소)

3. 해쉬테이블 룩업 예제

- 위에서 해쉬테이블의 값 룩업은 O(1) 상수 시간이 걸린다고 했다. 예를 통해 확인해보자

- 먼저 해시 함수는 곱셈 해시 함수를 사용할 예정이다.

A=1
B=2
C=3
D=4
E=5

위의 코드에 따르면 BAD는 214 로 변환된다. 곱셈 해시함수를 사용하기로 했으니 2*1*4 = 8 이 될 것이다.

- 유의어 사전을 만들 예정이다. 해시테이블로 아래과 같이 표현할 수 있다.

example = {}

- 배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이루어진 셀 묶음에 저장한다. 각 셀마다 주소가 있다. 예를 들면 아래와 같다.

- 항목을 추가해보자.

example["bad"] = "evil"

해시 테이블이 데이터를 어떻게 저장하는지 보자. 먼저 컴퓨터는 키에 해시 함수를 적용한다.

BAD = 2*1*4 = 8

키 "bad"는 8로 해싱되므로 컴퓨터는 값 "evil"을 다음과 같이 셀 8에 넣는다.

다른 값을 추가해보자

example["cab"] = "taxi"

CAB = 3*1*2 = 6 이므로 6번째 셀에 저장한다.

해시 테이블은 이제 다음과 같아졌다.

{"bad" => "evil", "cab" => "taxi"}

- 이제 해시 테이블에서 값을 어떻게 룩업하는지 알아보자. 키 "bad"의 값을 룩업한다고 하면 컴퓨터는 간단히 두 단계를 실행한다.

1. 컴퓨터는 룩업하고 있는 키를 해싱한다. BAD=2*1*4=8

2. 결과가 8이므로 셀 8을 찾아가서 저장된 값인 "evil"을 반환한다.

즉 해시 테이블은 값을 룩업하는데 O(1) 상수시간이 걸리는 것을 알 수 있다. 배열보다 훨씬 효율적으로 값을 찾는 것이다. 배열에서 해당 항목의 값을 룩업하려면 항목을 찾을 때까지 각 셀을 순회하며 검색해야 한다. 정렬되지 않은 배열에서는 최대 O(N)이 걸리며 정렬된 배열에서는 최대 O(logN)이 걸린다. 하지만 해시테이블에서는 상수시간 만큼 걸리니 훨씬 효율적인 것을 알 수 있다.

4. 해쉬 테이블 장단점

- 장점

데이터 저장/읽기 속도가 굉장히 빠르다
키에 대한 데이터가 있는지 중복 확인하는 것이 쉽다

- 단점

저장공간이 더 많이 필요
- 예를들어 해쉬함수가 %5 였다고 하고, 데이터가 Andy, Dave, Trump라 한다면, 해쉬주소는 0, 3, 4 인데(해쉬테이블배열의 인덱스번호) 불필요한 1,2도 생성해야된다.
주소가 동일하면 충돌 해결하기 위한 별도 자료구조 필요

- 주요 용도

검색이 많이 필요한 경우
저장, 삭제 읽기가 빈번한 경우
캐쉬 구현시(중복 확인이 편하기때문)

5. 해쉬테이블 만들기 예제 (파이썬)

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):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
    
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

5. 해시 테이블의 효율성을 결정하는 요인

- 해시 테이블에 얼마나 많은 데이터를 저장하는가

- 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가

- 어떤 해시 함수를 사용하는가

항상 1과 9사이의 값만 반환하는 해시 함수를 쓰고 있다고 가정하자. 먄약 해시테이블의 크기가 16이라면 해당 해시함수를 사용할 경우 10과 16 사이의 셀은 낭비된다. 따라서 좋은 해시함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수이다.

- 데이터와 셀 간 정상적인 부하율은 0.7이다(원소 7개 / 셀 10개)

6. 충돌해결 알고리즘

6.1. Chaining 기법 (링크드리스트 활용)

개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
링크드리스트로 저장할 때 아래와 같이 키 값도 같이 저장한다.

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: # 저 위의 hash_table 만들때 초기값이 0이었다. 만약 0이 아니라면 이미 값이 들어가 있다는 뜻이다.
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key: # hash_table[hash_address]에는 또 [index_key, value]의 형태로 값이 들어가있다. chaining은 링크드리스트로 계속 붙여 나가는 것이기 때문에 여러 값이 들어가 있을수도 있다. index의 0번째값은 index_key값이 된다.
                hash_table[hash_address][index][1] = value # 만약 똑같은 index_key가 있다면 value값을 덮어씌운다.
                return
        hash_table[hash_address].append([index_key, value]) # 만약 같은 index_key값이 없다면 새로 링크드리스트 어펜드한다. 
    else:
        hash_table[hash_address] = [[index_key, value]]  # hash_table[hash_address]가 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
    else:
        return None

6.2. Linear Probing 기법

폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
- 저장공간 활용도를 높이기 위한 기법

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:    # 순회도중 0값, 즉 초기값을 만난다면 거기엔 값이 한번도 저장이 안됐다는 것이기에
                hash_table[index] = [index_key, value]  # 여기에 값을 넣는다.
                return
            elif hash_table[index][0] == index_key:  # 그런데 만약 index_key값이 있다면, 그건 현재의 value를 업데이트 하겠다는 것이기에
                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

6.3. 빈번한 충돌을 개선하는 기법

해쉬 테이블은 최대한 충돌을 피해야한다. 충돌 회피 기법 로직을 타면 느려질 수 밖에 없어서이다
해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대. 만약 5개의 값만 저장할 해시 테이블이 필요할 때, 셀이 5개만 있다면 충돌이 일어나기 쉽지만 100개의 셀이 있다면 충돌 가능성은 현저히 줄어든다.
위의 해시 테이블의 셀 개수를 아래와 같이 늘려준다면 충돌가능성이 줄어든다. 하지만 메모리 공간을 더 차지한다는 단점이 있다.

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

def hash_function(key): 
	return key % 16

참고: 해쉬 함수와 키 생성 함수

파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
- 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

SHA-1

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig)

SHA-256

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig)

Linear Probing에 SHA-256적용

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)

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. 시간 복잡도

일반적인 경우(충돌 없는 경우)는 O(1)
최악의 경우(충돌 모두 발생하는 경우) O(n)
해쉬테이블의 경우 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라 할 수 잇다
검색에서 해쉬 테이블의 사용 예
- 16개의 배열에 데이터를 저장하고 검색할 때 O(n)
- 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고 검색할 때 O(1)

** 패스트캠퍼스의 '알고리즘/기술면접 완전 정복 올인원 패키지' 강의를 듣고 작성한 글입니다