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. 유클리드 알고리즘
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램,프로그래밍
      1.   프로그래밍 언어론
      2.   객체지향
      3.   자료구조
      4.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
        1.   알고리즘 종류
          1.   1. 알고리즘 분류
              2. 탐색 알고리즘
              3. 정렬 알고리즘
              4. 그래프 알고리즘
              5. 해쉬 알고리즘
              6. 해싱 탐색
              7. 최대 최소 구하기
              8. 유클리드 알고리즘
      5.   자료표현(알파벳/코드)
      6.   시스템 소프트웨어
      7.   프로그래밍언어 종류
      8.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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