C/C++/자료구조

내가 정리하는 자료구조 04 - 해쉬 테이블

대표적인 데이터 구조6: 해쉬 테이블 (Hash Table)

1. 해쉬 구조

  • Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
    • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
    • 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
    • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
      • 배열을 Hash Table을 만드는데 사용하지만, 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위해 해쉬테이블의 공간을 늘림으로인해서 배열보단 많은 저장공간이 필요할 수 있기 때문
    • 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

2. 알아둘 용어

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

3. 간단한 해쉬 예

3.1. hash table 만들기

1
2
hash_table = list([i for i in range(10)])
hash_table
결과
1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3.2. 이번엔 초간단 해쉬 함수를 만들어보자.

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

3.3. 해쉬 테이블에 저장해보겠다.

- 데이터에 따라 필요시 key 생성 방법 정의가 필요함

1
2
3
4
5
6
7
8
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]))
결과
1
2
3
65 68 84
65 0
65 65
  • 3.3.2. 해쉬 테이블에 값 저장 예
    • data:value 와 같이 data 와 value를 넣으면, 해당 data에 대한 key를 찾아서, 해당 key에 대응하는 해쉬주소에 value를 저장하는 예
1
2
3
4
def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

3.4. 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수도 만들어보자.

1
2
3
4
storage_data('Andy', '01055553333')
storage_data('Dave', '01044443333')
storage_data('Trump', '01022223333')
# storage_data('Anthor', '01046723456')

3.5. 실제 데이터를 저장하고, 읽어보겠다.

1
2
3
4
def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]
1
get_data('Andy')
결과
1
'01046723456'

4. 자료 구조 해쉬 테이블의 장단점과 주요 용도

  • 장점
    • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
    • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
  • 단점
    • 일반적으로 저장공간이 좀더 많이 필요하다.
    • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
  • 주요 용도
    • 검색이 많이 필요한 경우
    • 저장, 삭제, 읽기가 빈번한 경우
    • 캐쉬 구현시 (중복 확인이 쉽기 때문)

5. 프로그래밍 연습

연습1: 리스트 변수를 활용해서 해쉬 테이블 구현해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data)
  • 밑에서 사용되는 hash함수는 python을 새로 시작할 때마다 출력되는 값이 변화되므로 주의하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]
1
2
3
save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
결과
1
'0102030200'
1
hash_table
결과
1
[0, 0, '01033232200', 0, 0, 0, '0102030200', 0]

6. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

해쉬 테이블의 가장 큰 문제는 충돌(Collision)의 경우이다.
이 문제를 충돌(Collision) 또는 해쉬 충돌(Hash Collision)이라고 부릅니다.

6.1. Chaining 기법

  • 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
  • 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
연습2: 연습1의 해쉬 테이블 코드에 Chaining 기법으로 충돌해결 코드를 추가해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
hash_table = list([0 for i range(8)])

def get_key(data):
    return hash(data)

def hashing_function(key):
    return key % 8

def save_data(data, value):
    key=get(data)
    hash_address=hashing_function(key)
    if hash_table[hash_address] != 0:
        hash_table[hash_address]=value
    else:
        prev_value = hash_table[hash_address]
        hash_table[hash_address] = [prev_value, value]

def read_data(data):
    key=get(data)
    hash_address=hashing_function(key)
    return hash_table[hash_address]
  • 내가 만든 함수는 동일한 키값에 여러 데이터를 가지고 있으므로 Chaining 기법으로 충동해결을 방지한 코드가 아니다. 리스트를 사용하는 것은 좋았으나, 아래와 같이 해당 key값을 갖고있어야 동일한 키값이 아닌 각각 고유의 키값을 가져 데이터를 읽어들일 경우에도 정확하게 특정 키값에 해당하는 데이터만을 불러올 수 있기 때문이다.
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 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_address값에 이미 데이터가 존재하는 경우 키값과 동일한 것이라면
        # 값을 저장하지만 그렇지 않다면 리스트로 [index, value]형식으로 저장
        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] = [[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
1
2
3
print (hash('Dave') % 8)
print (hash('Da') % 8)
print (hash('Data') % 8)
결과
1
2
3
6
6
3
  • 동일한 hash함수 값을 갖지만 동일 주소에서 저장을하지만 키값을 다르게 하여 저장한다. 또한, 현재는 Chaning 기법을 사용했으므 링크드리스트로 동일한 주소안에 저장되어 연결되어있음을 확인하자.
1
2
3
4
save_data('Da', '1201023010')
save_data('Dave', '3301023010')
print(read_data('Da'))
print(read_data('Dave'))
결과
1
2
1201023010
3301023010
1
hash_table
결과
1
2
3
4
5
6
7
8
[0,
 0,
 0,
 0,
 0,
 0,
 [[-8338113502661437674, '1201023010'], [909867193312922558, '3301023010']],
 0]

6.2. Linear Probing 기법

  • 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
    • 저장공간 활용도를 높이기 위한 기법
연습3: 연습1의 해쉬 테이블 코드에 Linear Probling 기법으로 충돌해결 코드를 추가해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data) 
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
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]
            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:
        return None
    else:
        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]
  • read_data함수에서 linear probling 기법은 해당 hash_address에 값이 저장되어있다면(동일한 키값은 업데이트하지만) 다음 주소에 값을 저장하므로 만약 다음 주소 중 0값이 있다면 해당 데이터를 저장한적이 없다는 것을 의미하므로 그에 해당하는 코드도 작성해주어야 함을 유의하자!
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
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
                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
1
2
3
print (hash('dk') % 8)
print (hash('dw') % 8)
print (hash('dc') % 8)
결과
1
2
3
4
2
2
1
2
3
4
save_data('dk', '01200123123')
save_data('dw', '3333333333')
save_data('dc', '23456781234')
read_data('dc')
결과
1
'23456781234'

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

  • 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대
    • 예를 들어 저장하고자하는 데이터가 8개라면 이에 2배에 해당하는 공간을 해쉬 테이블 구조로 저장공간을 만들어 두는 것이 일반적이다.
  • 예:
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
import hashlib

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

SHA-256

1
2
3
4
5
6
7
import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig)
결과
1
9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
연습4: 연습2의 Chaining 기법을 적용한 해쉬 테이블 코드에 키 생성 함수를 sha256 해쉬 알고리즘을 사용하도록 변경해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data) 
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
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
1
2
3
print (get_key('dw') % 8)
print (get_key('deo') % 8)
print (get_key('dh') % 8)
결과
1
2
3
2
0
0
1
2
3
save_data('deo', '01200123123')
save_data('dh', '3333333333')
read_data('dh')
결과
1
'3333333333'

7. 시간 복잡도

  • 일반적인 경우(Collision이 없는 경우)는 O(1)
  • 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

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

  • 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
  • 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)
Share