[자료구조] 해쉬테이블

해쉬테이블

• key에 value를 저장하는 데이터 구조
• key를 통해 바로 데이터를 불러 올 수 있으므로 검색 속도가 매우 빠름
• 파이썬에는 딕셔너리 를 씀
• 보통 해쉬테이블크기만큼 배열을 만들어놓음
• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음
• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)
• 시간복잡도
  • 일반적인 경우(Collision이 없는 경우)는 O(1)
  • 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
  • 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

해쉬테이블, 해쉬함수 만들기

#해쉬테이블 만들기
hash_table = list([0 for i in range (8)])
#해쉬함수
hash_func(data):
    return data % 8
#데이터 저장
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'
data4 = 'Anthor'
# ord(): 문자의 ASCII(아스키)코드 리턴
def store_hash(data,value):
   key_ord = ord(data[0])
   hash_address = hash_func(key_ord)
   hash_table[hash_address]=value
#데이터 읽기
def read_hash(data,value):
   key_ord = ord(data[0])
   hash_address = hash_func(key_ord)
   return hash_table[hash_address]

hash 함수를 이용하여 해쉬테이블 구현

hash_table = list([0 for i in range (8)])
def get_key(data):
    return hash(data)
def hash_fuc(data):
     return get_key(data) % 8
def store_hash(data,value):
    hash_address = hash_fun(data)
    hash_table[hash_address]=value
def read_hash(data):
    hash_address = hash_fun(data)
    return hash_tabale[hash_address]

충돌 해결하기

• chaining 기법 (open hashing, 개방 해슁)
• 해쉬 테이블 저장공간 외의 공간 활용
• 충돌이 일어나면, 링크드리스트를 이용해서 추가로 데이터를 뒤에 연결함

hash_table = list[(0 for i in range(8))]
def get_key(data):
    return hash(data)
def hash_fuc(data):
    return get_key(data) % 8
def store_hash(data,value):
    hash_address = hash_fuc(data)
    #해당 주소에 데이터가 0이 아니라면 (즉, 하나이상의 데이터가 들어있다면)
    if hash_table[hash_address] != 0:
    #해당 주소에 들어있는 리스트 중 해쉬 값이 data의 해쉬값과 같다면 value를 업데이트 
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0]==get_key(data):
                hash_table[hash_address][index][1]=value            
	#포문을 다 돌았는데도 data의 해쉬값으로 된 리스트가 없다
        #리스트에 추가하면 됨
	hash_table[hash_address].append([get_key(data),value)]             
           #해당 주소에 데이터가 0이라면 (즉, 데이터가 하나도 들어있지 않다면)
             else:
                hash_table[hash_address]=[[get_key(data),value]]
def read_hash(data):
    hash_address = hash_fuc(data)
    #해당 주소의 값이 0 이 아니라면(데이터가 하나라도 저장되어 있다면)
    if hash_table[hash_address] !=0:
    #해당 주소의 리스트를 들면서 key값이 get_hash(data) 인것의 value를 return
        for index in range(len(hash_table[hash_address]):
            if hash_table[hash_address][index][0]=get_key(data):
                return ash_table[hash_address][index][1]
        #포문을 다 돌았는데도 key값이 get_hash(data) 인것이 없다면 None을 리턴      
        return None
    #해당 주소의 값이 0이라면 (데이터가 하나도 저장되어 있지 않다면)    
    else:
        return None
        

• Linear Probing 기법(폐쇄 해슁, Close Hashing 기법)
• 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
• 저장공간 활용도를 높이기 위한 기법

hash_table = list[(0 for i in range(8))]
def get_key(data):
    return hash(data)
def hash_fuc(data):
    return get_key(data) % 8
def store_hash(data,value):
    hash_address = hash_fuc(data)
    #해당 해쉬함수 주소에 하나이상이 저장되어 있다면
    if hash_table[hash_address] !=0
    #그 주소부터 hash_table 끝까지 돌면서 
        for index in range(hash_table[hash_address],len(hash_table)):
            # 빈공간에 저장
            if hash_table[index]==0:
                hash_table[index]=[get_key(data),value]
                return
            # 이미 저장되어 있다면 업데이트
            elif hash_table[index][0] == get_key(data):
                hash_table[index][1]=value
                return
            
    #해당 해쉬함수 주소에 아무것도 저장되어 있지 않다면 (값이 0이라면)
    else:
        hash_table[hash_address]=[get_key(data),value]
def read_hash(data):
    hash_address=hash_func(data)
    #hash_table의 해당 주소값에 하나이상이 저장되어 있다면
    if hash_table[hash_address] !=0:
    #해당 주소부터 테이블 끝까지 돌면서 
        for index in range(hash_address,len(hahs_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]              
    else: 
        return None