Hashing, Hash   해싱, 해쉬, 해시

(2017-09-12)

Hash Collision, 해쉬 충돌, 해시 충돌, 해쉬값 충돌

1. 해싱 (Hashing) 또는 해싱 탐색 (Hashing Serach)

  ㅇ 반복 비교를 통하지 않고, 특정 계산 만으로 바로 자료 저장 주소를 알아내는 탐색 방법

  ㅇ 해싱 탐색 이외의 암호학 응용으로는 해시 알고리즘 참조


2. 해싱 탐색 특징

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


3. 저장 및 검색

  ㅇ 해쉬표(Hash Table)라는 기억공간에,
  ㅇ 해쉬함수라는 특정 규칙에 의해, 
       
  ㅇ 주어진 키(Key)로 산출된 해쉬값으로 레코드 저장 주소를 결정 및 저장하고,
  ㅇ 같은 방법으로 필요한 레코드주소를 산출함으로써 바로 검색 작업 수행


4. 해싱 관련 용어들해쉬 함수 (Hash Function)
     - 임의 길이의 메세지를 일정 고정 길이의 해쉬 값으로 변환시켜주는 단방향성 함수

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

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

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

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

  ㅇ 해싱표/해쉬표 (Hash Table)
     - 해싱이 이용하는 일정 크기의 자료구조(기억공간)
        . 1 이상의 Bucket인 <키(Key),자료 슬롯들>로 구성된 기억공간
        . 주로, 배열을 활용


[알고리즘 종류] 1. 알고리즘 분류 2. 탐색 알고리즘 3. 정렬 알고리즘 4. 그래프 알고리즘 5. 해쉬 알고리즘 6. 해싱 탐색 7. 최대 최소 구하기 8. 유클리드 알고리즘

 
        최근수정     요약목록(시험중)     참고문헌