자료구조 - 해싱

- 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)

- 해시 테이블을 이용한 탐색을 해싱(hashing)

- dictionary = map = table

- 해시 함수(hash function)란 탐색 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다.

 

- 탐색 키 k1가 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 하며, 이러한 키들을 동의어(synonym)라고한다. -> 충돌은 곧 오버플로(overflow)

- 해시 함수
  : 충돌이 적어야 한다.
  : 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
  : 계산이 빨라야 한다.
  : 제산 함수(mod 연산), 폴딩 함수, 중간 제곱 함수 등
  : 충돌 해결 방법으로 선형 조사법, 이차 조사법, 이중 해싱법, 체이닝 등