Hashing   해싱

1. 해싱 (Hashing) 이란?

  ㅇ 해싱 탐색 (Hashing Search)
     - 통상적인 반복 비교를 통하지 않고, 
     - 특정 계산 만으로 바로 자료 저장 주소를 알아내는 탐색 방법

  ㅇ 해싱 탐색용이 아니고, 암호학적 응용으로는, ☞ 해시 알고리즘 참조


2. 해싱 탐색의 특징

  ㅇ 주로, 빨리 자료를 삽입,저장,가져올 때에 유용
     - 주어진 키 값을 갖는 레코드를 반복적인 비교를 통해 찾는 것이 아니라, 
     - 해시함수로 산출한 주소로 저장위치에 곧바로 접근하는 점이 다름
  ㅇ 따라서, 모든 원소에 대한 접근이, 동일 시간 내에 (즉, O(1) 내에) 이루어짐
  ㅇ 검색 효율은 낮음


3. 해싱에 의한 저장 및 검색

  ㅇ 주로, 해쉬 표 (Hash Table)라는 기억 공간이 필요함
     - 해쉬 표는, 고정된 크기의 자료구조로써, 그 크기가 처음에 정해짐

  ㅇ 키를 값에 매핑할 수 있는 자료구조
     - 주어진 키(Key)로 산출된 해쉬값으로, 레코드 저장 주소의 결정 및 저장을 함
     - 같은 방법으로 필요한 레코드의 주소를 산출함으로써, 바로 검색 작업 수행

  ㅇ 해쉬 함수라는 특정 규칙에 의해, 해쉬값을 산출