Hashing   해싱

1. 해싱 (Hashing) 이란?

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

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


2. 해싱 탐색 특징

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


3. 저장 및 검색

  ㅇ 해쉬 표(Hash Table)라는 기억 공간이 필요함
     - 해시 표는, 고정된 크기의 자료구조로써, 처음에 그 크기가 정해짐
  ㅇ 키를 값에 매핑할 수 있는 구조
     - 주어진 키(Key)로 산출된 해쉬값으로, 레코드 저장 주소의 결정 및 저장을 함
     - 같은 방법으로 필요한 레코드의 주소를 산출함으로써, 바로 검색 작업 수행
  ㅇ 해쉬 함수라는 특정 규칙에 의해 해쉬값을 산출 
       


4. 해싱 관련 용어들

  ㅇ 해쉬 함수 (Hash Function)
     - 임의 길이의 메세지를 일정 고정 길이의 해쉬 값으로 변환시켜주는 단방향성 함수

  ㅇ 해쉬 값 (Hash Value)
     - 단방향성 해쉬 함수의 출력 값
        . `Fingerprint`,`메세지 다이제스트(Message Digest)` 이라고도 함

  ㅇ 해쉬/해쉬값 충돌 (Hash Collision)
     - 2개의 다른 메세지가 같은 해시값(해시함수 수행 결과)을 갖는 경우

     - 해싱 탐색에서, 해쉬값 충돌 방지 방법
        . 해결 방법 중 하나로는, 이미 할당된 해쉬값 위치 다음의 빈 위치에 할당하는 등

  ㅇ 해쉬 내성 (Hash Collision Resistance)
     - 해시 충돌을 발견해내는 것이 어려운 성질
        . 약한 충돌 내성
           .. 주어진 해시값을 갖는 다른 메시지를 발견해내기 어려운 성질
        . 강한 충돌 내성
           .. 동일 해시값을 갖는 다른 2개 메시지를 발견해내기 어려운 성질

  ㅇ 해싱표/해쉬표 (Hash Table)
     - 해싱에 이용되는, 일정 크기의 자료구조(기억공간)
        . 고정된 크기의 자료구조로써, 처음에 그 크기가 정해짐
     - 키(Key) 값(Value) 쌍을 기반으로 저장되고, 탐색되어 짐
        . 키와 값이 하나의 쌍을 이루며 데이터가 저장되고 검색되어짐
     - 주로, 배열을 활용하여 구현됨
     - 키를 값에 매핑할 수 있는 자료구조
     - 연관배열 추상자료형(ADT)을 구현할 수 있는 자료구조