0%

자료구조 - 해시 테이블

작성일 In Disqus:

해쉬 테이블

용어

  • 해쉬(hash) : 임의 값을 고정 길이로 변환하는 것
  • 해쉬 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 테이터 구조
  • 해싱 함수(hashing function) : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
  • 해쉬 값(hash value) 또는 해쉬 주소(hash address) : key를 해싱 함수로 연산한 값, 이 값의 위치에 해당 key에 대한 값을 저장한다
  • 슬롯(slot) : 한 개의 데이터를 저장할 수 있는 공간

예시

해쉬 테이블 만들기

  1. 간단한 해시 함수 (Division 이용)
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
def hash_func(key):
    return key % 5

#ord() -> 문자의 아스키 코드 리턴
# 해쉬 테이블에 데이터를 저장
def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

#해쉬 테이블에서 해당 데이터의 값을 가져온다
def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]
    
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'

storage_data('Andy', '01055553333')
storage_data('Dave', '01012341234')
storage_data('Trump', '01009876543')

get_data('Andy')
# '01055553333'

해쉬 테이블의 장단점

  • 장점
    • 데이터 저장/읽기 속도가 빠르다
    • 데이터의 중복 확인이 쉽다
  • 단점
    • 저장 공간이 많이 필요하다.
    • 키가 충돌할 경우 처리할 별도의 자료구조가 필요하다
      • 공간을 늘리는 것으로 어느정도 해결이 가능

충돌 해결 알고리즘

다른 data 가 값은 해쉬 값을 가지는 것을 충돌이라 한다.

Chaining 기법

  • 해쉬 테이블 외의 저장공간을 이용
    • 개방 해싱(Open hashing) 기법
  • 충돌이 일어나면, 링크드 리스트로 데이터를 뒤에 연결함

Linear Probing 기법

  • 해쉬 테이블 내의 저장공간을 이용
    • 폐쇄 해슁(Close hashing) 기법
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장

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
def get_key(data):
    return hash(data)

def hash_func(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_func(index_key)
    if not hash_table2[hash_address]:
        hash_table2[hash_address].append([index_key, value])
    else:
        for index in hash_table2[hash_address]:
            if index[0] == index_key:
                index[1] = value
                return
        hash_table2[hash_address].append([index_key, value])

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_func(index_key)
    for index in hash_table2[hash_address]:
        if index[0] == index_key:
            print(index[1])
            return index[1]
    
    print('데이터가 없습니다')
    return None