Hash Table

1. 해쉬 구조

• Hash Table: (key,value)를 가진 데이터 구조
  • Key를 통해 바로 데이터에 접근 가능하므로, 속도가 획기적으로 빨라짐
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
  • key만 알면 어디에 저장되어야하는지, 어디에 저장되어 있는지 알 수 있다.
  • 파이썬은 Dictionary사용
  • 해쉬테이블 기반으로 만들어진 것이 블록체인
• key -> 해쉬 함수 -> 해쉬 주소 -> 해쉬 테이블 접근

2. 해쉬 테이블 만들기

• 간단한 해쉬 테이블 만들기(python list 이용)

hash_table = list([i for i in range(10)])
print(hash_table)
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

• hash 함수 만들기
  - 다양한 방법이 있으나, 나머지 연산을 많이 사용

def hash_func(key):
    return key % 10

 

• 각 데이터에 대해서 key값을 추출해야한다. 
  ord 함수 사용 (문자에 대해서 아스키 코드 변환)

data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'

#각 데이터에 대해서 key 값을 추출해야됨
#ord는 문자의 아스키값을 표시
print(ord(data1[0]))
print(ord(data2[0]))
print(ord(data3[0]))

3. 해쉬 테이블 충돌 해결 전략

- open hashing 기법(chaining 기법)
   테이블 밖에 값을 저장
   충돌이 일어나면 링크드리스트를 통해 해결

- close hashing 기법(linear probing 기법)

   테이블 안의 빈 공간에 저장

   저장공간의 활용도를 높일 수 있다.

4. 해쉬 테이블 전략

빈번한 충돌 방지해야한다. 

-> 해쉬 함수를 재정의하거나, 테이블의 저장공간을 2배로 늘린다.