[자료구조] 해시(Hash) 1

in Study on Data Structure

해시 테이블이란?

도서관에 가다보면 책과 같은 자료들을 분류할 때 ‘ㄱ’~’ㅎ’으로 시작하는 책으로 분류하거나, 아예 책에다가 고유번호를 분류하고 고유번호에 따라서, 혹은 책의 장르 별로 분류를 하는 경우도 있다.

‘ㄱ’ : 가가멜, 고라니 …
‘ㄴ’ : 날좀 보소, 난나나 …
…
‘ㅂ’ : 바로 보는 과학상식, 발 없는 말이 달걀 말이 먹고 간다 …
‘ㅅ’ : 소 잃고 외양간 고치기, 소고기와 돼지고기
…
‘ㅎ’ : 헬 테이커, 호랑호랑이

이런 식이거나,

판타지 : Re:제로부터 시작하는 이세계 생활, 연애를 하는 나 …
다큐멘터리 : 인간극장, 나는 자연인이다, 말벌 아저씨 …
로맨스 : 내 ID는 강남미인, 치즈인더트랩 …
공포 : 지금 우리 학교는, 맨 인더 다크 …

등등.. 일정한 규칙이나 기준에 따라서 자료를 분류할 수 있는 방법은 많다.
정보처리기사에서도 순차 코드, 블록 코드, 10진 코드, 그룹 분류 코드, 연상 코드, 표의 숫자 코드, 합성 코드 등으로 자료 분류에 관해 비슷한 내용이 나온다.

이렇게 해시 테이블, 해시 구조란 키(Key)에 데이터(Value)를 저장하는 데이터 구조를 가리킨다.
파이썬의 Dictionary가 대표적인 해시 구조이다.

해시 관련 용어

  • 해시(Hash) : 임의 값을 고정 길이로 변환하는 것
  • 해시 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해싱 함수(Hashing Function) : Key에 대해 연산을 하여 데이터의 위치를 찾는 함수
  • 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간

간단한 해시 테이블을 만들어볼까?

Library_books =
{
    '판타지' : [Re:제로부터 시작하는 이세계 생활, 연애를 하는 나, ...], 
    '다큐멘터리' : [인간극장, 나는 자연인이다, 말벌 아저씨, ...],
    '로맨스' : [내 ID는 강남미인, 치즈인더트랩 , ...],
    '공포' : [지금 우리 학교는, 맨 인더 다크 ...]
}

상기했듯이, 파이썬의 Dictionary도 해시구조의 한 종류이기 때문에 위와 같이 Dictionary를 이용해서 자료구조를 만들 수 있다.

하지만 다른 언어를 이용할 때, 혹은 Dictionary를 사용하기 힘든 경우도 있을 테니 코드를 이용해서 해시를 구현해볼 필요가 있다.

hash_table = []

리스트를 이용해서 해시 테이블을 구현해 볼 수 있다.

table = [i for i in range(10)]
# 출력 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

table = [0 for i in range(10)]
# 출력 결과
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

파이썬에서 리스트에 자리 10개를 만들어 놓는 과정이다!
하지만 해시 테이블에서는 데이터가 입력되어있는지 여부를 따지기 위해서 빈 공간은 0으로 표현하는 것이 편하므로 table = [0 for i in range(10)]을 사용하자.

해시 함수 생성 - Division 기법

데이터의 Key를 일정한 수로 나누어서 자료를 찾을 수 있도록 만드는 기법이다.
이 때, 알아두면 좋은 지식으로 ASCII코드가 있다.

ASCII코드란?

컴퓨터는 데이터를 받아들일 때 입출력 여부, 즉 2진법으로 받아들이는데 이를 위해서는 문자 등의 데이터를 숫자로 표현할 필요가 있다. A, B, C, D, E, .. 등의 문자를 컴퓨터가 알아듣게 하려면 이를 숫자로 표현해야 하는데 ASCII코드에 따르면 순서대로 65, 66, 67, 68, 69, …의 숫자로 변환되며, 이를 이진법으로 나타내면

  • A : 1000000
  • B : 1000001
  • C : 1000010
  • D : 1000011
  • E : 1000100 …

이렇게 나타낼 수 있다. 더 많은 아스키코드를 참고하려면 여기, 네이버 지식백과를 방문하시길…

그리고 언어는 매우 다양하고, 컴퓨터에서 한글도 적극적으로 활용할 수 있어야 하므로, ASCII코드와 같은 국제표준코드가 정의가 됐는데, 이 중에 UTF-8이 있다.

data1 = 'Nyago'
data2 = 'Miko'
data3 = 'Karen'

print(ord(data1[0]), ord(data2[0]), ord(data3[0]))

# 출력결과
78 77 75

여기서, ord()함수가 해당 값의 ASCII코드를 10진법으로 반환하는 함수이다!

key를 연산하고, 저장하는 함수를 만들어보자.

def hash_func(key):
    return key % 10

우선, 어디에 저장할지를 저장하는 과정으로 필자는 자료의 맨 첫번째 값을 ASCII코드로 반환한 뒤, 10으로 나눈 나머지에 따라 분류해서 저장을 해보고자 한다. 그래서 위와 같이 hash_func을 정의하였고,

def save_data(data):
    hash_address = hash_func(ord(data[0]))
    table[hash_address] = data
    return

위와 같이 저장하는 함수를 정의하였다.
위에 data1 = ‘Nyago’로 저장했는데, 이를 해시 테이블에 저장한 뒤 출력해보자.

# 저장 전
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

def hash_func(key):
    return key % 10

def save_data(data):
    hash_address = hash_func(ord(data[0]))
    table[hash_address] = data
    return

save_data(data1)
print(table)

# 저장 후 출력 결과
[0, 1, 2, 3, 4, 5, 6, 7, 'Nyago', 9]

‘N’은 ASCII코드로 값을 반환하면 78이므로, hash_func를 통해 8이 반환된다. 따라서 해시 테이블의 8번째 자리에 저장돼야하며, 출력 결과 ‘Nyago’가 해시 테이블의 8번째 자리에 잘 저장된 것을 볼 수 있다.

또한, 저장했으면 데이터를 꺼내올 수 있어야한다. 이를 구현해보자.

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

저장할 때 첫번째 데이터 값의 ASCII코드와 hash_func를 통해 저장했으니, 반환할 때에도 이를 이용하면 된다. 따라서 위와 같이 구현할 수 있다.

save_data(data1)
print(table)
print(get_data('Nyago'))

# 출력 결과
[0, 1, 2, 3, 4, 5, 6, 7, 'Nyago', 9]
Nyago

실행해보니 값이 잘 반환되었다!

또한 배열 안의 item으로 배열을 넣을 수 있는 것을 이용해서 엑셀과 같은 스프레드시트처럼 아래와 같은 테이블을 해시에 저장하는 것도 가능하다.

이름
전화번호
나이
Nyago0101111####12
Miko0102222####5
Karen0103333####8


해시 테이블의 장단점


장점

  • 데이터의 저장, 읽기, 검색 속도가 빠르다.
  • 키에 대한 데이터가 있는 지 여부 확인이 빠르며, 중복 여부 확인이 쉽다.

값의 일치여부를 일일이 확인하는 배열과는 달리, 해시는 일일이 확인하지 않고, Key값을 참조하기 때문에 배열보다 검색속도가 빠르다.

단점


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

하지만 저장 공간이 Key가 많아지면 그만큼 더 많이 필요하며, 다른 값에 대해서 동일한 Key를 사용할 경우 충돌이 일어난다. 당장 Python의 Dictionary도 같은 Key를 여러번 쓸 수 없다.

Hash의 주요 사용처

  • 저장, 삭제가 빈번한 경우
  • 검색할 데이터가 많은 경우
  • 캐쉬 구현시

저장과 삭제가 용이하고, 검색 속도가 빠른 점을 이용해서 위와 같은 상황에 쓸 수 있다.

2편에서 계속..

© 2022.07. by Wookey_Kim

Powered by Hydejack v7.5.2