🌈 해쉬 테이블(Hash Table)
🔥 해쉬 테이블이란?
🔥 python 내장 함수 hash
🔥 Hash 충돌 해결
1.해쉬 테이블이란?
- 해쉬 테이블은 키(Key)에 데이터를(Value)를 저장하는 데이터 구조로 키(Key)를 통해 데이터를 받아올 수 있기 때문에 속도가 빠름
- python에서는 해쉬를 별도 구현할 필요없이 딕셔너리를 사용할 수 있고, 딕셔너리도 내부적으로 해쉬 테이블의 구조를 띄고 있음
- 해쉬 테이블 관련 용어
- 해쉬 : 임의에 값을 고정 길이로 변환하는 것
- 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 해싱 함수 : Key에 대해 산술 연산을 적용해 해쉬 값으로 변환해주는 함수
- 해쉬 값(해쉬 주소) : Key를 해싱 함수에 대입하여 반환되는 것을 해쉬 값이라하고, 이를 기반으로 테이블에서 해당 Key에 대한 데이터 위치를 탐색
- 슬롯 : 한개의 데이터를 저장할 수 있는 공간
1) 간단 Hash Table 만들기
# 빈 해쉬 테이블 만들기 hash_table = list([0 for i in range(10)]) print(hash_table) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]# 간단 해쉬 함수 : Division 방식 # Division 방식 : 나누기를 통한 나머지 값을 사용하는 기법 def hash_func(key): return key % 5# 해쉬 테이블에 데이터 저장 def storage_data(data, value): # 👈 키와 저장할 데이터를 받음 key = ord(data[0]) # 👈 키를 해쉬함수에 넣어 연산하기 위해 숫자로 변환 hash_address = hash_func(key) # 👈 해쉬 함수 작동하여 해쉬값(해쉬주소) 얻음 hash_table[hash_address] = value # 👈 해쉬 주소를 index로하여 데이터를 테이블에 저장 storage_data('Jaewon', '010-1234-5678') storage_data('Haezin', '010-4444-9999') storage_data('Ginsu', '010-8989-1212') # 해쉬 테이블 저장 후 해쉬 테이블 상태 확인 print(hash_table) # [0, '010-8989-1212', '010-4444-9999', 0, '010-1234-5678', 0, 0, 0, 0, 0]# 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수 def get_data(data): key = ord(data[0]) # 👈 데이터에서 Key를 추출 hash_address = hash_func(key) # 👈 key를 해쉬 함수에 넣어 해쉬 주소를 얻음 return hash_table[hash_address] # 👈 해쉬 주소를 통해 배열에서 데이터를 반환 print(get_data('Jaewon')) # 010-1234-5678 print(get_data('Haezin')) # 010-4444-9999 print(get_data('Ginsu')) # 010-8989-1212
2) Hash Table 특징
- 장점 : 데이터 저장/읽기 속도 빠름, 해쉬는 키에 대한 데이터의 존재여부 확인 및 중복 처리가 쉬움
- 단점 : 불필요한 저장 공간을 확보해두기 때문에 비교적 저장 공간이 많이 필요, 여러 키에 해당하는 주소가 동일할 경우 충돌을 막기 위한 자료구조가 별도로 필요
- 주요 용도 : 검색이 많이 필요한 경우, 저장&삭제&읽기가 빈번한 경우, 캐쉬 구현시
2. python 내장 함수 hash
- python에서는 hash라는 내장함수를 제공하고, 파라미터를 주면 자동으로 키를 생성함
# hash 내장 함수 : 해쉬 키를 자동으로 생성해줌 print(hash('jaewon')) # -2933907617461129694
- 해쉬 기능 구현해보기
# 해쉬 테이블 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('Jaewon', '01011112222') save_data('Haezin', '01088889999') print(hash_table) # [0, '01088889999', 0, 0, 0, '01011112222', 0, 0] print(read_data('Jaewon')) # 01011112222 print(read_data('Haezin')) # 01088889999
3. Hash 충돌 해결
- 0부터 100까지 수를 key라 하고, 8로 나눈 나머지를 구하는 hash_function에 넣어 나올 수 있는 모든 hash address는 0~7이기 때문에 중복이 발생
- 이로 인해 hash의 주소가 동일해 데이터가 덮어씌어져버리는 문제가 발생
l = [i for i in range(100)] data_set = [] for i in l: data = i % 8 data_set.append(data) print(list(set(data_set)))
1) Chaining 기법
- Open Hashing 기법 중 하나로 해쉬 테이블 공간 외의 공간을 마련하여 데이터를 저장함
- 즉, 충돌이 발생 시 연결 리스트 자료 구조를 사용해 데이터를 저장하는 기법
- 단, 공간이 많이 필요함
- Chaining 기법은 데이터를 식별할 수 있는 key값을 함께 저장하여 이를 식별함
- 🔍 index_key = get_key(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) # 👈 index_key라는 별도의 변수에 key값을 저장 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] == 0 👈 없을 때 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(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 None # 해쉬주소 중복 발생 <- 할때마다 변함 print(hash('Jaewon')%8) # 3 print(hash('Haezin')%8) # 2 print(hash('AaLa')%8) # 3 # 저장 save_data('Jaewon', '01011112222') save_data('Haezin', '01088889999') save_data('AaLa', '01033331234') print(hash_table) # [0, 0, [[-3231082452735185358, '01088889999'], [630994963842225842, '01033331234']], [[-6162502635708335149, '01011112222']], 0, 0, 0, 0] # 조회 print(read_data('Jaewon')) # 01011112222 print(read_data('Haezin')) # 01088889999
2) Linear Probing 기법
- Close Hashing 기법 중 하나로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법으로 Linear Probing 기법이 대표적임
- Linear Probing 기법은 충돌 발생 시, hash adress의 다음 adress부터 맨 처음 나오는 빈공간에 저장하는 방식이기 때문에 저장공간 활용도가 높음
# 해쉬 테이블 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)): if hash_table[index] == 0: hash_table[index] = [index_key, value] return elif hash_table[index][0] == index_key: # 업데이트 hash_table[index][1] = value 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 # 해쉬주소 중복 발생 <- 할때마다 변함 print(hash('Jaewon')%8) # 0 print(hash('Haezin')%8) # 0 print(hash('AaLa')%8) # 7 # 저장 save_data('Jaewon', '01011112222') save_data('Haezin', '01088889999') save_data('AaLa', '01033331234') print(hash_table) # [[3214169218863054112, '01011112222'], [-291548128366538008, '01088889999'], 0, 0, 0, 0, 0, [-143120377966334057, '01033331234']] # 조회 print(read_data('Jaewon')) # 01011112222 print(read_data('Haezin')) # 01088889999
- 빈번한 hash 충돌이 나타난다면, 해쉬 함수를 재정의하거나 해쉬 테이블 저장 공간 확대해야 함
3) hash table 시간 복잡도
- 충돌이 없는 경우 : O(1)
- 충돌이 발생하는 경우 : O(N)
Keep Going, Keep Coding!