이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을
오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
● 잔재미코딩 유투브 오픈
[구독해보기]
6. 대표적인 데이터 구조5: 해쉬 테이블 (Hash Table)¶
- Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
- Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
- 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
- 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨
알아둘 용어¶
- 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
- 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터(Value) 위치를 찾을 수 있는 함수
- Key를 해싱 함수로 연산해서,
해쉬 주소를 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 알 수 있음
간단한 해쉬 예¶
1) key 와 데이터를 국제전화코드를 예로 만들어 봅니다.¶
In [141]:
dial_code = dict()
dial_code[86] = 'China'
dial_code[91] = 'India'
2) 이번엔 초간단 해쉬 함수를 만들어봅니다.¶
In [142]:
# 해쉬 함수로 키를 넣으면 해쉬값을 리턴해줌 (해쉬값이 주소가 될 수 있음)
def hash_func(data):
return data % 10
3) 해쉬 테이블에 저장해 봅니다.¶
In [143]:
hash_table = list([0 for i in range(10)])
def storage_data(hash_address, data):
hash_table[hash_address] = data
4) 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수도 만들어 봅니다.¶
In [144]:
def get_data(key):
return hash_table[hash_func(key)]
5) 실제 데이터를 저장하고, 읽어 봅니다.¶
In [145]:
address = hash_func(86)
storage_data(address, dial_code[86])
print (get_data(86))
파이썬 딕셔너리(Dictionary)¶
- 내부적으로는 결국 hash로 구현
- 예: 스마트폰에 전화번호 저장하기
- 전화번호 저장시 이름을 저장하기
- 이름: 여친, 전화번호: 000-2222-3333
- 이름으로 전화번호 찾기
- 전화번호 저장시 이름을 저장하기
1) 해쉬 테이블을 위한 데이터 저장공간 만들기¶
In [146]:
data = list([0 for i in range(8)])
print (data)
참고 (numpy 라이브러리 활용해서 데이터 저장공간 만들기)¶
In [29]:
import numpy as np
# np.empty(공간사이즈, dtype=object) 문자열(객체)를 넣을 수 있는 데이터 공간을 공간 사이즈만큼 배열로 만들기
data = np.empty(8, dtype=object)
print (data)
2) 내장함수 hash() 로 해쉬키 만들기¶
In [148]:
hash('Dave')
Out[148]:
In [150]:
hash('David')
Out[150]:
In [151]:
hash('Dave') % 8
Out[151]:
In [152]:
hash('David') % 8
Out[152]:
3) 해쉬 함수 만들기¶
In [153]:
# 임의로 8개의 해싱함수 만들어보기
def hash_function(string):
return hash(string) % 8
4) Key를 해싱함수를 사용해서 데이터(Value) 저장하기¶
In [154]:
data[hash_function('Dave')] = '000-1111-2222'
data[hash_function('David')] = '000-2222-3333'
5) Key를 해싱함수를 사용해서 데이터(Value) 읽어오기¶
In [155]:
data[hash_function('Dave')]
Out[155]:
In [156]:
data[hash_function('David')]
Out[156]:
딕셔너리(Dictionary)를 사용하지 않고 hash 함수 만들어보기¶
- 나머지를 기준으로 Hash Function 만들어보기
In [5]:
tel_dict['Dave']
Out[5]:
In [3]:
tel_dict = dict()
In [157]:
def hash_function(string):
return hash(string) % 8
In [161]:
class HashMap:
def __init__(self):
self.items = list([0 for i in range(8)])
def save(self, key, data):
self.items[hash_function(key)] = data
def get(self, key):
return self.items[hash_function(key)]
hash_list = HashMap()
hash_list.save('Dave', '000-1111-2222')
hash_list.get('Dave')
Out[161]:
프로그래밍 연습
다음 메서드로
save: data 를 인자로 data 저장하고(내부 hash_function 함수 적용) 해쉬키를 리턴해주는 메서드
get: key를 인자로 해쉬키를 넣으면 저장된 데이터를 리턴해주는 메서드
다음 메서드로
save: data 를 인자로 data 저장하고(내부 hash_function 함수 적용) 해쉬키를 리턴해주는 메서드
get: key를 인자로 해쉬키를 넣으면 저장된 데이터를 리턴해주는 메서드
def hash_function(string):
return hash(string) % 8
다음과 같은 코드가 실행될 수 있도록 해보기
hash_list = HashMap()
key1 = hash_list.save('Dave')
hash_list.get(key1)
In [112]:
class HashMap:
def __init__(self):
self.items = list([0 for i in range(8)])
def __hash_func(self, data):
return hash(data) % 8
def __add(self, key, data):
self.items[key] = data
def save(self, data):
key = self.__hash_func(data)
self.__add(key, data)
return key
def get(self, key):
return self.items[key]
프로그래밍 연습
위 코드에서 해쉬키가 동일할 경우에는 기존 데이터를 덮어씌우지 않고, 추가할 수 있도록 리스트 변수를 사용해서 만들어보세요 get 메서드에는 해쉬키가 동일한 데이터를 리스트 변수에 담아 리턴하도록 변경하기
위 코드에서 해쉬키가 동일할 경우에는 기존 데이터를 덮어씌우지 않고, 추가할 수 있도록 리스트 변수를 사용해서 만들어보세요 get 메서드에는 해쉬키가 동일한 데이터를 리스트 변수에 담아 리턴하도록 변경하기
def hash_function(string):
return hash(string) % 8
다음과 같은 코드가 실행될 수 있도록 해보기
hash_list = HashMap()
key1 = hash_list.save('Dave')
hash_list.get(key1)
동일 해쉬 주소에 여러 데이터가 있을 때 (심화)¶
In [102]:
class LinearMap:
def __init__(self):
self.items = list()
def add(self, k, v):
self.items.append((k, v))
def get(self, k):
data = list()
for key, val in self.items:
if key == k:
data.append(val)
return data
In [103]:
linear_map = LinearMap()
linear_map.add(1, 2)
linear_map.add(1, 3)
linear_map.get(1)
Out[103]:
In [104]:
class BetterMap:
def __init__(self, n=100):
self.maps = []
for i in range(n):
self.maps.append(LinearMap())
def find_map(self, k):
index = hash(k) % len(self.maps)
return self.maps[index]
def add(self, k, v):
m = self.find_map(k)
m.add(k, v)
def get(self, k):
m = self.find_map(k)
return m.get(k)
In [105]:
better_map = BetterMap()
better_map.add(1, 2)
better_map.add(1, 3)
better_map.get(1)
Out[105]:
In [106]:
class HashMap:
def __init__(self):
self.maps = BetterMap(2)
self.num = 0
def get(self, k):
return self.maps.get(k)
def add(self, k, v):
if self.num == len(self.maps.maps):
self.resize()
self.maps.add(k, v)
self.num += 1
def resize(self):
new_maps = BetterMap(self.num * 2)
for m in self.maps.maps:
for k, v in m.items:
new_maps.add(k, v)
self.maps = new_maps
In [107]:
hash_map = HashMap()
hash_map.add(1, 2)
hash_map.add(1, 3)
hash_map.get(1)
Out[107]:
hash 장단점¶
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
- 캐쉬로 활용 시에도 유용함
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
- 예: 알파벳을 키로 하는 해쉬테이블 공간을 10개로 놓았을 경우,
- 몇몇은 공간이 충돌됨
- 예: 알파벳을 키로 하는 해쉬테이블 공간을 10개로 놓았을 경우,
좋은 해쉬 함수 사용하기¶
- 충돌이 많은 해쉬 함수는 성능을 떨어뜨림
- 주소에 키에 대한 데이터를 고루 분표시키는 함수
- 근래 SHA(Secure Hash Algorithm) 함수등이 많이 사용됨
적합한 해쉬 테이블 사이즈¶
- 해쉬 테이블 사용률: 해쉬 테이블에 있는 항목의 수 / 해쉬 테이블에 있는 공간의 수
- 보통 해쉬 테이블 사용률이 0.7 이상이면 해쉬 테이블 사이즈를 2배로 늘림
실제 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)¶
SHA-1¶
In [76]:
import hashlib
hash_object = hashlib.sha1() # 어떤 해쉬 알고리즘 쓸래?
hash_object.update(b'Hello World') # 어떤 값을 해슁할 것인가?
hex_dig = hash_object.hexdigest() # 16진수로 해쉬값을 리턴해줌
print(hex_dig)
SHA-256¶
In [77]:
import hashlib
hash_object = hashlib.sha256() # 어떤 해쉬 알고리즘 쓸래?
hash_object.update(b'Hello World') # 어떤 값을 해슁할 것인가?
hex_dig = hash_object.hexdigest() # 16진수로 해쉬값을 리턴해줌
print(hex_dig)