해시 테이블 (Hash Table)

1. 해시 구조

• Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
  • 파이썬 딕셔너리(Dictionary) 타입이 해시 테이블의 예이다. Key를 가지고 데이터(Value)를 꺼내는 것
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용한다. (공간과 탐색 시간을 맞바꾸는 기법)

(단, 파이썬에서는 해시를 별도로 구현할 필요가 없다. 딕셔너리 타입을 사용하면 되기 때문이다.)

 

2. 알아둘 용어

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

https://www.fun-coding.org/00_Images/hash.png

 

3. 간단한 해시 예

파이썬의 리스트 컴프리헨션 문법을 활용해 간단히 해시 테이블(hash table)을 하나 만들어보면,

 

hash_table = list([0 for i in range(10)])
print(hash_table)

# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

이렇게 된다. 미리 10개의 슬롯이 있는 해시 테이블을 만든 것이다.

 

이제 매우 간단한 해싱 함수(hashing function)를 만들어보겠다. 다양한 해시 함수 고안 기법이 있는데, 그 중에서도 가장 간단한 방식은 Division 법이다. 나누기를 통한 나머지 값을 사용하는 기법인 것이다.

 

def hash_func(key):
    return key % 5

 

위와 같이 key값을 넣었을 때 그 값을 5로 나눈 나머지를 리턴하는 해싱 함수를 생성했다.

 

이제 해시 테이블에 저장을 해볼 것이다. 데이터에 따라 key 생성 방법을 정의해야 할 필요가 있을 수 있다. 이 경우에는 데이터의 첫 번째 글자의 아스키 코드(ASCII Code)를 리턴하는 방식으로 할 것이다. 우선 데이터를 몇 개 생성하고, 정의한 key 생성방법에 따라 출력해보면,

 

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

# ord(): 문자의 ASCII(아스키)코드 리턴
print (ord(data1[0]), ord(data2[0]), ord(data3[0]))	# 65 68 84
print (ord(data1[0]), hash_func(ord(data1[0])))	# 65 0

 

위처럼 된다. key값이 ord() 함수를 이용해 추출한 아스키 코드가 되는 것이다.

 

이제 해시 테이블에 값을 저장해볼 것이다. data:value와 같이 data와 value를 넣으면, 해당 data에 대한 key를 찾아서, 해당 key에 대응하는 해시주소에 value를 저장하는 것이다. 이것을 코드로 구현해보면,

 

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

 

이렇게 된다. 데이터의 첫 번째 문자의 아스키 코드값을 key 변수에 저장하고, 앞서 작성한 hash_func() 함수를 이용해 key를 변환해 그것을 hash_address 변수에 저장한 다음, 해시 테이블에 저장하는 것이다.

 

가령, 앞서 예시로 만들었던 사람들의 전화번호를 저장한다고 하면,

 

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

 

이렇게 할 수 있다. Andy, Dave, Trump의 전화번호를 해시 테이블에 value값으로 저장하는 것이다.

 

작성한 해시 테이블의 데이터를 읽어오는 함수를 만들어보면,

 

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

 

이러하다. 이제 이 함수로부터 실제로 데이터를 불러와보겠다.

 

print(get_data('Andy'))

 

 

이렇게 정상적으로 잘 출력된다. 아래는 지금까지 간단히 작성해본 해시 예의 코드 전체이다.

 

hash_table = list([0 for i in range(10)])
# print(hash_table)

def hash_func(key):
    return key % 5

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

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')

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

# print(get_data('Andy'))

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료