[자료구조] 해시테이블(Hash Table)이란?

Posted on | In
중요한 자료구조인 해시 테이블, 해시 함수(요구 조건과 기본 해시함수, 좋은 해시함수), 해시 성능, 해시 충돌(충돌 방지 방법)

해시테이블(Hash Table)이란?

image

  • 해시는 딕셔너리 코드와 관련되어 활용되는 개념이다.
  • 해시테이블은 키를 활용하여 값에 직접 접근이 가능한 구조이다.
  • 해싱의 목적은 앞에서 배웠던 정렬 알고리즘들과는 다르게 검색이다.
    • 즉, 해시테이블은 검색 알고리즘의 역할도 한다.
    • 장점은 데이터 양에 영향을 덜 받으며 성능이 빠르다는 점이다.(키를 통해 값을 검색한다.)
  • 파이썬의 딕셔너리는 내부적으로 해시테이블 구조로 구현되어있다.
    • 해시테이블은 검색을 위한 역할도 하고, 딕셔너리를 위한 자료구조의 역할도 한다.
  • 해시 함수, 해시 테이블, 해시 충돌, 해시를 활용했을 때의 성능에 대해 알아볼 것이다.
    • 해시는 해시 함수를 통해 나온 값이다.
    • 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블 형태의 자료구조이다.
    • 해시 함수는 여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭시키는 역할을 한다.
    • 해싱은 쉽게 말해서 다 흩으려놓고, 키와 매칭되는 값을 검색하는 과정이다.

간단한 예시

  • 아래와 같이 키와 값이 정렬되지 않은 형태로 있는 경우, 색상에 해당하는 코드를 찾는 상황일 때,
    • 반복문과 조건문을 활용한다면 선형시간 성능(O(N))을 나타낸다.
    • 색상이 알파벳 순서대로 이미 정렬되어 있다면 이진검색을 할 수 있을 것이고, 성능은 로그를 따른다(O(logN))
1
2
3
4
5
6
7
8
# 슈도코드
[("aqua", "#00FFFF"), ("beige", "#F5F5DC"), ("chartreuse", "#7FFF00")]

for i in range(0, len(dictionary)):
  1)알파벳순서대로 정렬되어있음
  2)알파벳찾기(예를 들어, "beige"를 찾아보겠다.)
  3)이진검색 알고리즘 활용
  4)로그시간 성능이 나온다.

해시함수

image

  • 해시함수는 키를 해시테이블 내의 버킷(해시값)으로 매핑시킨다.
  • 해시함수의 입력값의 형태는 다양하고, 출력값의 형태는 숫자이다.

해시함수의 요구조건

  • 해시함수는 입력값이 같다면, 동일한 출력값을 받아야한다.
  • 입출력값이 일정하지 안다면 적절한 해시함수가 아니다.
    • 해시함수는 특정 범위 안의 숫자를 반환해야한다.
  • 하나의 해시함수가 입력 데이터 별로 다른 숫자와 매핑된다면, 그것은 완벽한 해시함수이다.
    • 해시함수가 입력데이터에 따라 다른 숫자를 반환하게 되면 해시충돌을 최소화하는 것이다.

기본 해시함수

  • 해시함수는 보통 문자열 입력값에 정수형 출력값을 반환한다.
  • 정수형에서 문자열로 변환하기 위해서, 해시함수는 문자열에 해당하는 개별적인 단어를 활용한다.
    • 아래 예제는 파이썬에서 .encode()메소드를 활용해서 문자열에서 바이트 코드로 인코드하는 것이다.
    • 인코딩된 후, 정수형은 각 단어를 나타낸다.
1
2
3
4
5
6
7
8
9
10
11
12
# 인코딩 예제
bytes_representation = "hello".encode()

for byte in bytes_representation:
    print(byte)
'''
104
101
108
108
111
'''
  • 여러개의 정수를 더하는 방법으로 하나의 문자열로 변환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 정수값의 합 반환
bytes_representation = "hello".encode()

sum = 0
for byte in bytes_representation:
    sum += byte

print(sum)


# 해시함수 생성
def my_hashing_func(str, list_size):
    bytes_representation = str.encode()    
    sum = 0
    for byte in bytes_representation:
        sum += byte

    print('sum:', sum)
    print('list_size', list_size)
    print('sum%list_size:', sum % list_size)
    return sum % list_size
  • 위의 해시함수를 활용하여 추가학습을 진행한다.
    • 먼저 5개의 빈 슬롯이 들어가는 리스트를 초기화한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 위의 my_hashing_func이라는 해시함수를 활용하여 아래처럼 값을 확인할 수 있다.
my_list = [None] * 5

my_list[my_hashing_func("aqua", len(my_list))] = "#00FFFF" # 리스트에 값을 입력

print(my_list[my_hashing_func("aqua", len(my_list))]) # 리스트에 있는 값을 출력

print(my_list)
'''
sum: 424
list_size 5
sum%list_size: 4
sum: 424
list_size 5
sum%list_size: 4
#00FFFF
[None, None, None, None, '#00FFFF']
'''

해시 성능

  • 해시테이블 자체는 충돌을 해결해주지 않는다.
  • O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.
    • 상수 시간(O(1))은 해시테이블의 사이즈에 관계없이 동일한 양의 계산을 다룬다.
    • 해시충돌로 인해 모든 bucket의 value를 찾아야하는 경우(반복문)도 있다.
  • 만약 해시테이블이 하나의 요소를 갖고 있다면, 해시테이블 인덱스 갯수와 관계없이 프로그램 수행시간이 비슷하다.
    • 검색, 삽입, 삭제 무엇을 하든지 해시함수는 키를 통해 저장된 값에 연관된 인덱스를 반환한다.(즉, 키와 인덱스가 매칭되어야 한다.)

해시 충돌

  • 지금까지 해시 함수가 항상 다른 입력을 다른 인덱스에 매핑한다는 가정하에 알아보았다.
  • 그러나 가능한 모든 데이터를 알고있지 않으면 완벽한 해시함수를 작성하는 것은 불가능하다.
  • 해시충돌은 키가 들어갈 자리(버킷)가 없는 경우 발생한다.

image

  • 위의 경우 키 B와 C가 같은 경우가 해시함수를 통해 계산된 상태에서 버킷 4와 충돌이 발생했다.
  • 충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적이다.

충돌 방지 방법

체이닝(Chaining)

image

  • 체이닝은 위 그림처럼 리스트를 활용하여 해시함수에서 매핑된 후, bucket에서 연결될 수 있는 entry에 제한을 두지 않는 체인 형태로 연결하는 것이다.
  • 해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키 값을 뒤이어 연결한다.
  • 데이터의 형태는 위 그림처럼 연결리스트의 형태를 갖는다.

체이닝의 원리

  • 키의 해시값을 계산한다.
  • 해시값을 이용해 리스트의 인덱스를 구한다.

  • 같은 해시값이 있다면 리스트로 연결한다.

  • 충돌을 줄이기 위해, 각 리스트에 대해 연결한다.
  • 따라서 특정 해시값에 대해 충돌이 발생해도, 체이닝을 통해 값을 찾을 수 있다.

image

  • 위 그림은 체이닝으로 충돌상황을 재현하고 해결하는 모습이다.
  • 체이닝은 연결리스트의 원리를 사용하기 때문에 해시값이 같은 노드를 연결하는 모습을 나타낸다.
  • 해시값이 인덱스 역할을 하며, 위 그림에서는 나누기방법을 사용한 것인데, 나누기 방법은 쉽기 때문에 많이 사용되는 기본적인 해시함수로서 키값이 정수로 가정된다.

체이닝 예시코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 리스트안에 중첩되는 리스트를 만들어서 연결개념으로 해시테이블을 생성

chain_hash_table = [[] for _ in range(10)] # 10의 길이로 테스트 진행(0~9, 총 10개의 인덱스)
print(chain_hash_table)
# 해시함수는 위와 동일하게 테스트할 수 있다.

def chain_hash_func(key):
    return key % len(chain_hash_table)
 
print(chain_hash_func(10)) 
print(chain_hash_func(20)) 
print(chain_hash_func(25)) 
# append를 활용해서 키-값 쌍을 해시테이블에 삽입한다.

def chain_insert_func(chain_hash_table, key, value):
    hash_key = chain_hash_func(key)
    chain_hash_table[hash_key].extend(value)
    
chain_insert_func(chain_hash_table, 10, 'A')
print (chain_hash_table)

chain_insert_func(chain_hash_table, 25, 'B') # 5번째 인덱스에 B가 삽입된다.
print (chain_hash_table)

# 아래 결과값과 같이 중첩되는 결과값이 있더라도 값이 대체(충돌)되는 것이 아니다.
# 리스트 메소드 개념(list.append)이 활용되어 값을 이어 붙인다.('A' -> 'C')
chain_insert_func(chain_hash_table, 20, 'C')    
print (chain_hash_table)

오픈 어드레싱(Open addressing)

  • 오픈 어드레싱은 하나의 버킷에 하나의 입력값만 들어갈 수 있는 형태이다.
  • 다른 로직의 함수를 활용하기 때문에 오픈 어드레스라고 한다.
    • 비어있는 배열 슬롯이 발견될 때까지 배열의 위치를 검색하여 해시 충돌을 해결한다.
    • 충돌이 일어나는 경우, 탐사(Probing)를 진행하면서 빈 공간을 찾아야 해결된다.
    • 체이닝과 다르게 저장공간이 정해져있다.
  • 체이닝의 경우 연결리스트를 활용하고, 오픈 어드레싱은 내부적으로 공간이 어느정도 정해진 배열을 활용하여 설계되어 있다.
    • 파이썬 딕셔너리의 경우, 내부적으로 오픈 어드레싱 방식을 활용한다.
  • 파이썬에서 오픈어드레싱을 활용하는 경우 빈 공간이 없는 경우 시간이 오래 걸릴 수 있다.
    • 때문에 로드팩터를 작게 설정하여 성능 저하 문제를 해결한다.

로드 팩터(Load Factor)

image

  • 위 공식처럼 로드 팩터 비율에 따라 해시함수 재작성 여부, 해시테이블 크기조정여부가 결정된다.
    • 로드 팩터값을 통해 해시 테이블의 성능 정도를 파악할 수 있다.
  • 해시 테이블에 저장된 항목 수(해시 테이블에 입력된 키 갯수)를 슬롯 수(해시 테이블 전체 인덱스 갯수)로 나눈 값이다.
    • 오픈 어드레싱을 사용하면 최대 로드 팩터는 1 정도 나온다.
    • 체이닝을 사용하면 로드 팩터는 오픈 어드레싱보다 좋은 성능을 보일 수 있다.
  • 로드 팩터를 낮추면 해시에 대한 성능이 올라간다.

해시 테이블에 대한 다양한 실생활 사례

  • 해시 테이블은 무언가를 찾을 수 있도록 한 사물에서 다른 사물로 매핑해야 하는 경우 적합하다.
    • 전화번호부(사람의 이름을 전화번호에 매핑)
    • DNS 확인(웹 주소를 IP 주소에 매핑)
    • 학생 기록(고유한 학생 ID가 학생 정보에 매핑)
    • 도서관 시스템(책의 고유 식별자가 자세한 책 정보에 매핑)

좋은 해시함수란?

  • 해시함수를 어떻게 구현하는지에 따라 해시의 성능이 결정된다.

계산 과정

  • 키와 값의 계산 과정이 쉬워야 한다.

충돌

  • 충돌을 피할 수 있어야 한다.

계산 과정이 쉬운 경우

  • 체이닝이 제대로 활용된다면 반복작업 없이 해시의 검색 알고리즘을 활용하여 O(1)의 검색시간을 확보할 수 있다.
  • 해시값은 해시되는 데이터에 의해 완전히 결정된다.
  • 해시함수는 모든 입력 데이터를 사용해야한다.

충돌을 피할 수 있는 경우

  • 해시함수는 가능한 해시값의 전체 집합에 데이터를 균일하게 배포한다.
  • 해시함수는 유사한 문자열에 대해 다른 해시값을 생성한다.

해시를 사용할 때 주의점

  • 키 데이터 타입에 맞는 좋은 해시함수가 있는 지 확인한다.
  • 적절한 해시 테이블 크기를 사용한다.

참조

0%