해쉬(Hash)

1. 해쉬 구조

---

해쉬 테이블 : 키(key)에 데이터(value)를 저장하는 데이터 구조

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

 

2. 알아둘 용어

---

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

 

3. 간단한 해쉬 예

---

1) hash table 만들기

hash_table = list(i for i in range(10))
hash_table

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2) 초간단 해쉬 함수 만들어 보기

def hash_func(key):
    return key % 5

3) 해쉬 테이블에 저장

data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'

## ord(): 문자의 ASCII 코드 리턴
print(ord(data1[0], ord(data2[0], ord(data3[0])

65 68 84

4) 해쉬 테이블에 값 저장 예

def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

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

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

6) 실제 데이터를 저장하고, 읽어보기

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

get_data('Andy')

01055553333

 

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

---

장점

• 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
• 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

단점

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

주요 용도

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

 

5. 프로그래밍 연습

---

연습1: 리스트 변수를 활용해서 해쉬 테이블 구현해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data)

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]

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

0102030200

 

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

---

해쉬 테이블의 가장 큰 문제는 충돌의 경우이다. 이 문제를 충돌 또는 해쉬 충돌이라고 부른다.

1) Chaining 기법

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

연습2: 연습1의 해쉬 테이블 코드에 Chaining 기법으로 충돌 해결 코드를 추가해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data)

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(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] = list([index_key, value])

  hash_table[hash_address] = value

def read_data(data):
  hash_address = hash_function(get_key(data))
  return hash_table[hash_address]

print(hash('Dave') % 8)
print(hash('David') % 8)
print(hash('Data') % 8)

5
5
6

2) Linear Probing 기법

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