해쉬 테이블
- key에 value를 입력해 저장하는 데이터 구조
- python dictionary 타입이 대표적인 해시 테이블 유형 → python에서는 따로 해쉬를 구현하지 않아도 됨, dictionary 사용
해쉬 테이블 관련 용어
- 해쉬: 임의 값을 고정 길이로 변환하는 것
- 해싱 함수: Key를 이용해 데이터 위치를 찾을 수 있는 함수 → 해시 주소를 리턴하는 함수
- 해쉬 값 / 해쉬 주소: Key를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
- 슬롯: 한 개의 데이터를 저장할 수 있는 공간
- 저장할 데이터에 대해 Key를 추출할 수 있는 별도의 함수도 존재
해쉬 예시
해쉬 테이블 만들기
hash_table = list([i for i in range(10)])list comprehension
사용법
[출력표현식 for 요소 in 입력Sequence [if 조건식]]
- 입력 sequence는 iteration이 가능한 데이타 Sequence 혹은 컬렉션
- [if 조건식]에서 []은 리스트 괄호가 아니라, 옵션이라는 뜻, 조건이 있을때만 사용하면 됨
예시 #종류가 다른 데이터에서 정수 리스트만 가져오기
dadtaset = [4, True, 'Dave', 2.1, 3]
int_data = [num for num in dataset if type(num)==int]
print(int_data) //[4,3]Set comprehension
사용법
{출력표현식 for 요소 in 입력Sequence [if조건식]}
- 조건에 맞는 새로운 Set 컬렉션을 리턴
- set은 중복이 없고 변경 가능한 데이터 구조
Dictionary comprehension
사용법
{Key:Value for 요소 in 입력Sequence [if 조건식]}
id_name = {1: 'Dave', 2: 'David', 3: 'Anthony'}
# 아이디가 2 이상인 데이터를 이름:아이디 형식으로 새로운 dic 만들기
name_id = {val:key for key,val in id_name.items() if key>1 }해쉬 함수
해쉬 함수를 만드는 방법은 여러가지가 있지만 그 중 가장 간단한 방식이 Division
- Division : 키 값을 특정 값으로 나눠서 나머지 값으로 해쉬 주소를 정하는 기법 (해쉬 주소가 일정한 길이로 나오게 됨)
def hash_func(key):
return key%5
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'
print(ord(data1[0]) #ord(): 문자의 아스키 코드 값 리턴해주는 함수
# 65
print(hash_func(ord(data1[0]))
#여기서 key는 ord(data1[0])
#hash_func(ord(data1[0]))는 해쉬 값 (해쉬 주소)해쉬 활용 함수
- 해쉬 테이블에 값 저장
def storage_data(data, value):
key = ord(data[0]) #key
hash_address = hash_func(key) #해쉬주소
hash_table[hash_address] = value
#우리가 원하는 data, 우리가 진짜 저장하고 싶은 값을 넣으면 data로
#key값을 만들고 그 key값으로 만든 address에 해당하는 slot에 value 저장
storage_data('Andy', '01035134211')- 해쉬 테이블에 저장된 값 읽기
def get_data(data):
key = ord(data[0])
hash_address = hash_func(key)
return hash_table[hash_address]
# data로 키, address 만들고 그 address에 저장된 value 리턴하는 함수해쉬 테이블의 장단점 / 주요 용도
- 장점
데이터 저장 / 읽기 속도가 빠르다 (검색 속도 빠름)
키에 대한 데이터가 있는지 확인이 쉬움
- 단점
저장공간이 좀 더 많이 필요하다
여러 키에 대한 주소가 동일할 경우 충돌을 해결하기 위한 추가적인 알고리즘이 필요함
- 주요 용도
검색이 많이 필요한 경우
저장, 삭제, 읽기가 빈번한 경우
캐쉬 구현시
연습1: 리스트 변수를 활용해서 해쉬 테이블 구현해보기
-
해쉬 함수: key % 8
-
해쉬 키 생성: hash(data) #내장 함수
hash_table = list([i for i in range(8)])
def get_key(data):
return hash(data)
def hash_func(key):
return key % 8
def add(data, value):
address = hash_func(get_key(data))
hash_table[address] = value
def read_data(data):
address = hash_func(get_key(data))
return hash_table[address]충돌 해결 알고리즘
: 한 개 이상의 데이터가 동일한 해시 어드레스에 저장될 경우에 충돌 발생
1. Open Hashing (Chaining이 대표적)
: 개방 해슁
: 충돌이 발생하면 해시 테이블 밖의 공간에 저장하는 방법
: 링크드 리스트 사용해서 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
: 코드에서는 링크드 리스트 대신 python의 list 활용해서 붙여넣기
- Chaining
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) #index_key를 추후에 value와 같이 저장하기 위해서 따로 변수로 지정
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: #만약에 저장돼있는 데이터의 key와 저장하려는 데이터의 key가 동일하다면~
hash_table[hash_address][index][1] = value #그 위치에 저장하려던 value 넣기
return
hash_table[hash_address].append([index_key, value]) #만약 key가 다르다면 뒤에 추가 연결, 이중 배열같은 느낌
else:
hash_table[hash_address] = [[index_key, value]] #데이터가 없기 때문에 key와 value 저장
def read_data(data):
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:
return hash_table[hash_address][index][1]
return None
else:
return None2. Close Hashing (Linear Probing이 대표적)
: 폐쇄 해슁
: 충돌이 발생하면 해시 테이블 안에 남는 공간을 찾아서 저장하는 방법 → 남는 공간을 활용하는거라서 저장공간 활용도가 높음
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(hash_address, len(hash_table)): #넣으려고 했던 칸의 index부터 해당 배열의 끝까지
if hash_table[index] == 0: #다른 칸에 데이터가 없으면 바로 저장
hash_table[index] = [index_key, value]
return
elif hash_table[index][0] == index_key: #해당 칸에 데이터가 있긴한데 index_key가 동일한 경우 value 업데이트
hash_table[index][1] = value
return
else: # 데이터가 들어간 적이 없는 경우 바로 저장
hash_table[hash_address] = [index_key, value]
def read_data(data):
index_key = get_key(data)
hash_address = hash_function(index_key)
if hash_table[hash_address] != 0:#데이터가 있는 경우
for index in range(hash_address, len(hash_table)):
if hash_table[index] == 0:#해당 데이터에 대한 값이 저장된 적이 없다~, 왜냐면 빈 공간이 나왔으면 내가 저장했을거기때문에 빈공간이 있을수가 없음
return None
elif hash_table[index][0] == index_key:
return hash_table[index][1]
else:
return None #데이터가 없는 경우 none 리턴빈번한 충돌을 막는 법
저장 공간의 50% 이상에 저장하려고 하면 충돌이 일어날 확률이 높아지기 때문에 저장 공간을 확대해주면 충돌이 일어날 확률이 낮아짐
해쉬 함수와 키 생성 함수
: hash() 함수는 실행할 때 마다 값이 달라질 수 있음
: 대표적인 해쉬 함수 SHA(Secure Hash Algorithm)
: 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해줌
:SHA 사용하려면 라이브러리 설치 후 사용해야함 → import hashlib (pip install)
SHA-1
import hashlib
data = 'test'.encode() # = (b.'test'), 스트링을 바이트로 바꿔줌
hash_object = hashlib.sha1()
hash_object.update(data) # update(b.'test')로 써도 됨
hex_dig = hash_object.hexdigest() #몇진수로 추출할 것 이냐 -> 16진수 (hexdigest())
print (hex_dig) #해쉬 주소임, 문자열SHA-256(블록체인에서도 많이 사용됨)도 사용방법이 동일함
def get_key(data):
hash_object = hashlib.sha256()
hash_object.update(data.encode())
hex_dig = hash_object.hexdigest()
return int(hex_dig, 16) #hexdigest로 문자열로 뽑았기 때문에 int로 바꿔줘야 하는데 이거는 또 16진수이기 떄문에 10주소 이루어진 주소로 만들어주기 위해서는 int(hex_id,16) 꼭 해줘야함시간 복잡도
일반적인 경우: O(1)
모두 충돌하는 최악의 경우: O(n) (읽거나 저장하는 경우)
해쉬 테이블이 배열보다 저장, 검색에 있어서는 더 좋은 자료구조다~!
