[자료구조] 해쉬 테이블 (Hash Table)

해쉬 구조

• 키 Key, 데이터 Value를 저장하는 데이터
• 파이썬의 Dictionary 타입
• 성능이 좋기 때문에 해쉬 Key(기능)을 확장한 여러가지 함수와 알고리즘 기반으로 블록체인에서 많이 사용된다.

장점

• 데이터 저장/ 읽기 속도가 빠르다
  • 배열은 index 처음부터 탐색하여 데이터를 찾지만 해쉬 테이블은 key를 이용하여 direct하게 바로 찾을 수 있기 때문

단점

• 일반적으로 저장공간을 많이 차지한다. 충동을 피하기 위해서 저장공간을 충분하게 세팅해야함
• 키 해당 주소가 동일할 경우 충돌을 해결하기 위한 자료구조가 필요하다
  • 해결 방안, 체이닝 : Linked List를 사용하여 해쉬 충동시 연결리스트로 데이터를 이어놓는 방법

자주 쓰이는 곳

• 검색이 많이 필요한 곳
• 저장, 삭제, 읽기가 많이 일어나는 작업
• 캐쉬 구현시 (중복 확인이 엄청 쉽기 때문)

---

용어

• 해쉬 (Hash) : 임의 값을 고정 길이로 변환하는 기능
• 해쉬 테이블 (Hash table) :키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수 (Hashing Funtion) : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수(내가 만들거나 이미 만들어진 함수)
• 해쉬 값 (Hash value), 해쉬 주소 (hash Address) : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 찾을 수 있음
• 슬롯 (Slot) : 한 개의 데이터를 저장할 수 있는 공간

 

---

간단한 해쉬 함수 구현

 

#hash table 만들기
hash_tabel = list([0 for _ in range(10)])
print(hash_tabel)

#Key에 무슨 값이 들어오든 고정된 값으로 return 됨
def hash_func(key):
    return key % 5

data1 = 'Andy'
data3 ='Song'

#key를 생성하는 방법
#ord() : 문자의 ASCII 코드를 리턴해줌
#앞의 ASCII 추출
print(ord(data1[0]),ord(data1[1]),ord(data1[2]))

#key와 value를 같이 넣음, Dict과 유사
def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_tabel[hash_address] = value

storage_data('Andy', '01011112222')
storage_data('Song', '01033334444')

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

print(get_data('Song'))