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

Posted on | In
해시 테이블의 개념과 구조. 해시 테이블의 장단점. 해시 테이블의 충돌 해결 알고리즘. 해시 테이블의 시간 복잡도

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

  • 해시 테이블은 키(Key)에 데이터(Value)를 저장하는 데이터 구조이다.

해시 구조

  • 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라진다.
  • 파이썬의 딕셔너리(Dictionary) 타입이 해시 테이블의 예이다.
  • 보통 배열로 미리 해시 테이블의 사이즈 만큼 생성 후에 사용한다.
    • 파이썬에서는 해시를 별도 구현할 필요 없다.

용어

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

간단한 해시

1. 해시 테이블 생성

1
2
3
4
5
6
# 슬롯 생성
hash_table = list([0 for _ in range(10)])
hash_table
'''
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
'''

2. 간단한 해시 함수

  • 다양한 해시 함수 고안 기법이 있으며, 가장 간단한 방식인 디비전(Division) 방법을 사용해본다.
    • 나누기를 통한 나머지 값을 사용하는 기법이다.
1
2
def hash_func(key):
    return key % 5

3. 저장

  • 데이터에 따라 필요 시 키 생성 방법 정의가 필요하다.
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
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'
data4 = 'Anthor'
## ord(): 문자의 ASCII(아스키)코드 리턴
print (ord(data1[0]), ord(data2[0]), ord(data3[0]))
print (ord(data1[0]), hash_func(ord(data1[0])))
print (ord(data1[0]), ord(data4[0]))
'''
65 68 84
65 0
65 65
'''


# 해시 테이블에 값 저장
## 데이터와 값을 넣으면, 해당 데이터에 대한 키를 찾아내어, 해당 키에 대응하는 해시 주소에 값을 저장하는 예
def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value


storage_data('Andy', '01055553333')
storage_data('Dave', '01044443333')
storage_data('Trump', '01022223333')

4. 열람

1
2
3
4
5
6
7
8
9
10
def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]


get_data('Andy')
'''
'01055553333'
'''

장단점

장점

  • 데이터 저장 및 읽기 속도가 굉장히 빠르다.
    • 검색 속도가 빠르다.
  • 해시는 키에 대한 데이터가 있는 지 중복 확인이 쉽다.

단점

  • 일반적으로 저장 공간이 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우, 충돌을 해결하기 위한 별도 자료구조가 필요하다.

주요 용도

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

구현

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
29
30
31
32
33
hash_table = list([0 for _ 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]


save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
'''
'0102030200'
'''


hash_table
'''
['0102030200', 0, 0, 0, 0, 0, 0, '01033232200']
'''

충돌 해결 알고리즘

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

체이닝(Chaining) 기법

  • 개방 해싱 또는 오픈 해싱 기법 중 하나이다.
    • 해시 테이블 저장 공간 외의 공간을 활용하는 기법이다.
  • 충돌이 일어나면 연결 리스트라는 자료 구조를 사용해서, 연결 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법이다.

구현

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
hash_table = list([0 for _ in range(8)]) # 슬롯 생성


def get_key(data): # 키 생성
    return hash(data)


def hash_function(key): # 해시 함수
    return key % 8


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

    if hash_table[hash_address] != 0: # 값이 있을 경우
        for i in range(len(hash_table[hash_address])):
            if hash_table[hash_address][i][0] == idx_key: # 두개로 쪼개서 하나는 키, 하나는 값
                hash_table[hash_address][i][1] = value # 덮어 씌우고 끝낸다.
                return
        hash_table[hash_address].append([idx_key, value]) # 리스트 타입으로 삽입
    else:
        hash_table[hash_address] = [[idx_key, value]]


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

    if hash_table[hash_address] != 0:
        for i in range(len(hash_table[hash_address])):
            if hash_table[hash_address][i][0] == idx_key:
                return hash_table[hash_address][i][1]
        return
    else:
        return


save_data('Dave', '1201023010')
save_data('Dasdfdfgqata', '3301023010')
read_data('Dave')
'''
'1201023010'
'''


hash_table
'''
[0,
 0,
 0,
 [[399862619351125179, '1201023010'], [2148369322995284107, '3301023010']],
 0,
 0,
 0,
 0]
'''

리니어 프로빙(Linear Probing) 기법

  • 폐쇠 해싱 또는 클로즈 해싱 기법 중 하나이다.
    • 해시 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법이다.
  • 충돌이 일어나면 해당 해시 주소의 다음 주소부터 맨 처음 나오는 빈 공간에 저장하는 기법이다.
    • 저장 공간 활용도를 높이기 위한 기법이다.

구현

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
hash_table = list([0 for _ in range(8)]) # 슬롯 생성


def get_key(data): # 키 생성
    return hash(data)


def hash_function(key): # 해시 함수
    return key % 8


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

    if hash_table[hash_address] != 0: # 값이 있을 경우
        for i in range(hash_address, len(hash_table)): # 다음 주소 부터 탐색
            if hash_table[i] == 0: # 빈 곳을 발견하면
                hash_table[i] = [idx_key, value]
                return
            elif hash_table[i][0] == idx_key: # 키가 동일하면
                hash_table[i][1] = value # 업데이트
                return
    else:
        hash_table[hash_address] = [idx_key, value]


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

    if hash_table[hash_address] != 0: # 값이 있을 경우
        for i in range(hash_address, len(hash_table)):
            if hash_table[i] == 0: # 저장이 안된 경우
                return None
            elif hash_table[i][0] == idx_key:
                return hash_table[i][1]
    else:
        return


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


save_data('dk', '01200123123')
save_data('da', '3333333333')
read_data('dk')
'''
'01200123123'
'''

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

  • 해시 함수를 재정의하거나 해시 테이블 저장 공간을 확대한다.
1
2
3
4
hash_table = list([None for i in range(16)])

def hash_function(key):
    return key % 16

유명한 해시 함수

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

SHA-1

1
2
3
4
5
6
7
8
9
10
import hashlib

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

SHA-256

1
2
3
4
5
6
7
8
9
10
import hashlib

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

시간 복잡도

  • 일반적인 경우(충돌이 없는 경우)는 O(1)이다.
  • 최악의 경우(충돌이 모두 발생하는 경우)는 O(n)이다.
  • 해시 태이블은 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1)이라고 말할 수 있다.

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

  • 배열에서 데이터를 저장하고 검색하면 O(n)이 걸리지만, 그만큼의 데이터 저장 공간을 가진 해시 테이블에 데이터를 저장하고 검색한다면 O(1)이 걸린다.
0%