1️⃣ 해시함수

(1) 훌륭한 해시 함수란?

1. 어떤 경우(자료형, 데이터의 길이)에도 고정된 크기의 값으로 변환 가능한 함수
2. 해시 충돌이 거의 없는 해시함수
3. simple uniform hashing(확률적으로 골고루 색인에 배정되는 것)을 만족하는 해시함수

(2) 용도에 따른 해시함수

• 현재 개발된 해시 함수들이 많습니다. 해시넷-해시함수에 들어가시면 몇가지 해시함수에 대해 알 수 있습니다. 이처럼 각각의 해시 함수들은 각각의 특징이 존재합니다.
• 어디에서 쓰이는지에 따라 적절한 해시함수를 선택해서 사용하면 됩니다.
  1. 충돌이 많지만 속도가 빠른 해시함수
  2. 속도도 빠르고 충돌도 적은 함수
  3. 속도가 느리더라도 충돌이 거의 없는 함수
  4. 출력값에서 입력값으로 되돌아 갈 수 없는 함수(보안)
     
     

2️⃣ 해시테이블에 문자열 저장하기

(1) 문자열 -> 배열 색인

• 대부분의 해시테이블의 색인은 int형(4바이트)자료형입니다.
• 그러기때문에 문자열(char*)을 단순히 정수형으로 변환만 시켜줄 수 있으면 기존에 구현한 해시테이블을 사용할 수 있습니다.
• 문자는 고유의 아스키코드값을 가지고 있습니다. 문자열의 각자리를 연산하여 정수형 해시값을 만들 수 있습니다.

< 기본적인 해시함수(문자열) >

int hash_function(const char* str)
{
    int code = 0;
    const char* c;

    c = str;
    while (*c != '\0')
        code += *c++;

    return (code);
}

• 이렇게 정수형으로 변환이 가능하면 %기호를 이용하여 좀 더 복잡한 보안과 효율적인 리소스사용이 가능해 집니다.
• 하지만 이렇게 두단계를 거치다보니 두군데(해시충돌, 색인 충돌)에서 일어나게 됩니다. 색인 충돌의 경우 <해쉬 포스트>에서 해결한 문제입니다.
• 사실 해시 충돌의 경우 해결하지 않아도 색인 충돌 문제의 해법으로 해결이 되긴합니다.
• 하지만 만얀, 해시 충돌을 방지할 수 있다면 굳이 char*자료형의 키를 저장할 필요없이 해시 값인 정수형(int) 키값만 저장해도 됩니다.(동적 메모리 할당을 안해도 된다는 뜻)
  
  

3️⃣ 해시값 충돌

(1) 완전히 충돌을 없앨 수 있을까?

• 기술적으로는 완전히 충돌을 없애는 것은 힘듭니다.
• 하지만 특정 조건 하에서는 해시 충돌을 확실히 방지 가능합니다.(이런 조건은 생각보다 많음)
  1. 실행 중에 해시 테이블에 저장될 수 있는 데이터를 모두 알고 있는 경우
     (미리 만들어 놓은 데이터 파일 읽기)
  2. 개발 도중에 해시 충돌이 없다는 걸 확인하고 보장할 수 있는 경우
• 이것이 가능하다면 문자열을 저장할 필요가 없어져 효율이 좋아집니다.

(2) 충돌이 없어질 경우 코드변화(기본 예시)

4️⃣ 해시 함수 예시

< "65599"해시 함수 >

(출처: Compilers: Principles, Techniques, and Tools)

• 65599를 곱해나가는 해시 함수입니다.

size_t hash_65599(const char* string, size_t len)
{
    size_t i;
    size_t hash;

    hash = 0;
    for (i = 0; i < len; i++)
    {
        hash = 65599 * hash + string[i];
    }
    return (hash ^ (hash >> 16));
}

• 65599를 곱해나가다 오버플로우가 일어나고 그러한 특성을 이용합니다.
• 마지막으로 비트연산까지 해줌으로써 좀 더 복잡하게 해시 값을 가질 수 있게 됬습니다.
• 하지만 이와같은 해시 함수도 완전히 안전하다고할 수 없습니다.(언제가는 보안이 뚫림)
• 계속해서 새로운 해시 함수를 개발하거나 솔트 기법을 사용하는 등 보안관련해서는 계속해서 업데이트를 해나가야할 것입니다.
• "65599"해쉬함수에 대해 좀 더 자세히 알고 싶다면 다음의 링크를 참고하면 될 것같습니다.
  >>>>괜찮은 문자열 해쉬함수?