Hash Function

해시 함수.

어떤 입력값을 넣으면,

고유한 과정을 거치게하여 해시값(임의의 길이의 데이터)을 뱉는 함수.

 

우리가 아는 암호화 방식인 SHA512 등도 결국 해시 함수..

 

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

해시 함수 - 위키백과, 우리 모두의 백과사전

https://en.wikipedia.org/wiki/Hash_function

Hash function - Wikipedia

 

 

그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며,

매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다.

 

TreeMap에서 Key를 통해 자료에 접근할 때,

컨테이너의 요소를 전부 훑어야한다면(시간복잡도 O(log(n))),

HashMap은 컨테이너의 각 Bucket/Bin에 해시값에 의한 칸에 자료가 들어가 있으므로,

Key를 해시함수에 넣어 얻은 해시값으로 빠르게 자료에 바로 접근 가능(시간복잡도 O(1)).

 

 

이 해시 결과로 역으로 Source(Key)가 무엇이었는지 복호화는 불가능하며,

단방향 암호화처럼 단방향으로만 작용한다.

동일한 입력값에는 해시함수가 항상 동일한 해시결과를 뱉어주기 때문에,

HashMap에서 넣을 때와 열람할 때 동일한 요소를 보증해 줌.

 

단, 다른 입력값에서도 해시 함수는 동일한 해시결과를 내기도 하여, 이 보증에 차질이 생길 수 있음.

이 것이 해시 충돌.

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C

해시 충돌 - 위키백과, 우리 모두의 백과사전

해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.

해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우,

비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

(비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때

적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.)

 

 

---

 

 

해시 충돌을 피하기 위해서는

충분한 크기의 Bucket과, 훌륭한 해시 함수가 필요하다고 한다.

(Bucket의 크기가 크면 좋지만, 메모리 사용량도 늘어남)

해시 함수 알고리듬에는 소수(Prime Number)가 이용되는 편이 좋다고 한다.

(modulo연산에서 값을 나눌 때(k%m), 나누는 값(m)이 2^n의 형태를 피하고 되도록 소수가 될 수 있게)

 

h(x) = ((k*x) % p) % n

 

 

만약 입력값이 string이라면, 해시 함수를 다음과 같이 짜볼 수 있다.

int makeHash(String input) {
    int hash = 7;
    for (int i = 0; i < input.length(); ++i) {
        hash = (hash * 31) + charAt(i);
    }
    return hash;
}

자, 자릿수가 늘어날 때마다 31을 곱하게 되니, 순서에 따른 결과도 달라질테고..

모든 해시 충돌을 피하진 못해도 어느 정도 유니크하게 해줄 것 같긴 한데,

 

이걸 컨테이너(배열)에 넣으려면,

Bucket의 몇 번째에 들어가게 할지 정해야 하므로,

%Bucket수 등으로 하면 또 한 Bucket에 여러 요소가 들어갈 수 있으니,

이중 배열이 된다든가..

 

 

---

 

 

같은 출력을 내는 서로 다른 두 입력을 찾기가 계산적으로 불가능한 성질을 갖는 해시 함수를

충돌 회피 해시 함수(Collision Resistant Hash Function)라고 하며,

 

모든 키들이 서로 다른 해시번지를 가지는 해시 함수로
해시법에 있어서, 전혀 충돌이 일어나지 않는 해시 함수를
완전 해시 함수(Perfect Hash Function)라고 한다.
예약어표 등 등록하는 키의 전체 집합을 알고 있다면,
완전 해시 함수를 구성할 수 있다고 한다.

https://en.wikipedia.org/wiki/Perfect_hash_function

Perfect hash function - Wikipedia

 

완전 해시 함수를 만드는 Cichelli의 제안법을 보니,

정말 키들의 집합을 다 아는 상태에서 해시 충돌이 일어나지 않는 방향으로

h(s) = (s.length() + g(s.charAt(0)) + g(s.charAt(s.length()-1))) % m

에서 g()를 조정하기 때문에 그렇구나 싶었다.

 

결과의 형태를 정해두고, 그 형태가 나오도록 함수를 짰으니 가능..

들어갈 키들의 집합을 모두 아는 케이스가 더 많을까??

새로운 키들이 들어올 때마다 기존에 있던 키들의 집합에 더해주고, 새로운 해시 함수를 구성하며,

있던 키가 빠져나가면 다시 그 집합에도 변경을 해주고, 새로운 해시 함수를 구성해야 하는가??

 

그렇다면 충돌 회피 해시 함수가 범용적으로는 더 유용할까??

근데 결국 일어날 수도 있는 충돌에 대해 안전하다고 보장할 수는 없고..

적은 충돌에 대해 이중 컨테이너를 마련한다면,

그 내부 컨테이너의 몇 번째 칸이 그 요소인지에 대한 것은 어떻게 정할 것인가..

 

 

---

 

 

Java HashMap은 어떻게 동작하는가?

https://d2.naver.com/helloworld/831311

 

 

---

 

 

해시에 대한 개념과는 별개로

꿈같은 완전 해시 함수와 해시 테이블은 또 아득하게 느껴지네;;

틈틈히 찾아보면서 추가해야 할 듯;;