Hash Function

해시 함수란?

해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. - Wiki

  • 예시 : SHA-1 Hash Function

    EarlyHail: 199b2dce45fa71143b3887fdc851c28aa36cb923

    HojinLee : 076dfe82f08840eb3a6810ea2ed20e86b161a3f8

    Hash : 873507a022b58de26a88deae87268cbd8d6af5b1

    Has : d83b65206df5e5d1922586c72a5853c6c0d71a98

    임이의 길이 데이터에 대한 Hash Code의 길이는 같다.

    http://www.sha1-online.com/에서 SHA-1을 적용해볼 수 있다.

대표적인 해시 함수들

해시 함수는 암호학적 해시 함수와 비암호학적 해시 함수로 나뉜다.

  • 암호학적 해시 함수

    MD5, SHA 계열 해시 함수

  • 비암호학적 해시 함수

    CRC32

  • 암호학적 해시 함수의 조건

    1. 역상 저항성 : Hash Code를 가지고 입력값을 찾는 것이 어렵다.

    2. 제2 역상 저항성 : 입력값에 대해 해시 값을 바꾸지 않으며 입력값을 변경하는 것이 어렵다.

    3. 충돌 저항성 : 같은 Hash Code를 생성하는 두 개의 입력값을 찾는 것이 어렵다.

좋은 해시 함수란 무엇일까

  1. 계산이 빨라야 한다.

  2. 출력 Hash Code의 충돌을 최소화 해야한다.

    해시 충돌이 발생했을 때 O(n) 접근 시간을 가지므로 충돌을 최소화 해야한다.

    • 출력 Hash Code가 가능한 전체 집합에 고르게 분포되어야 한다.

    • 유사한 문자열에 대해 매우 다른 해시 값을 생성해야 한다.

      프로그램에서는 비슷한 문자열에 대해 해시를 적용할 때가 많다.

      따라서 충돌을 줄이기 위해 비슷한 문자열에도 매우 다른 해시값을 제공해야 한다.

      위에서 Hash와 Has에 대해 매우 다른 해시 값이 출력된 것을 확인할 수 있다.

Hash Table

Hash Table이란?

Hash Table은 Hash Function과 함께 데이터를 저장하고 검색하기 위해 사용된다.

Hash Function을 적용한 결과인 Hash Code를 index로 Key와 Value쌍을 저장하거나 검색한다.

Simple Hash

Hash Collision

Hash Function은 다른 Key에 대해 다른 Hash Code를 반환한다는 보장이 없다. 따라서 이러한 상황이 발생했을 때를 대비해야 한다.

  • Separate Chaining

    Separate Chaining

    같은 Hash Code를 가지는 값이 있다면 다음 데이터의 주소를 저장하여 LinkedList 형태로 구현한다.

    Java같은 경우 충돌이 많이 발생할 경우 Tree구조로 변경하여 효율성을 높인다.

  • Open Addressing

    Open Addressing

    충돌이 발생하면 비어있는 다음 위치에 값을 삽입한다.

    다음 위치를 정하는 방법은 여러가지가 있다.

    1. 고정된 간격 이동
    2. 폭을 제곱으로 증가
    3. Hash Code를 한번 더 Hashing

모든 이미지 출처는 Wiki-Hash_Table입니다.