문자열 Hash (djb2)

문자열 Hash (djb2)

해당 게시글 전에 아래 내용을 먼저 읽어보시면 좋습니다.

- [해시] Hash란?

- [해시] Hash Chaining 기법 구현

Hash 성능에 있어서 Hash Index 충돌을 낮추는 것이 중요하다.

Hash 충돌을 처리하는 방법은 크게 2가지로 구분할 수 있다.

Chaining 기법 과 Open Address 기법 이다.

 

위 2 가지는 충돌이 발생하는 경우 처리이지만

Key에 해당하는 Hash Index를 구하는 것도 여러 알고리즘이 존재한다.

// djb2
unsigned long djb2(const char* str)
{
    unsigned long hash = 5381;
    int c;
    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c) % TABLE_SIZE;
    }
    return hash % TABLE_SIZE;
}

▷ Horner's Method 방식을 이용한 것이다.

 

만약 Key가 정수인 경우에는 배열 Index를 통해서 Hash를 어렵지 않게 구현할 수 있다.

하지만 Unique한 값이 숫자가 아닌 문자열인 경우

ex) 이름, 문자열 ID, 그룹명 등

해당 문자열을 적절한 Hash Index로 "분배"할 필요가 있다.

Hash Index 자체를 분산시키는 역할이 Hash Function 인 데,

숫자 1 ~ 1000까지의 Unique한 값이 주어질 때, Hash Table 상에

▷ 1 ~ 10 까지의 Hash Index → MOD 10 → Hash Table 크기 = 10

▷ 1 ~ 100 까지의 Hash Index → MOD 100 → Hash Table 크기 = 100

 

메모리 공간도 고려해야 하지만 충돌에 따른 Overhead도 고려해야 한다.

▶ 공간을 절약하면서 충돌을 최대한 적게 발생하는 Hash Function이 필요하다.

---

djb2 함수를 활용한 문자열 Hash 구현

#include <iostream>
#include <string>
using namespace std;

const int TABLE_SIZE = 10;

unsigned long djb2(string str)
{
    unsigned long hash = 5381;
    int c;
    for(int i = 0; i<str.length(); ++i)
    {
        c = str[i];
        hash = (((hash << 5) + hash) + c) % TABLE_SIZE;
    }
    return hash % TABLE_SIZE;
}

int main() {
    
    string str[] = {"test", "harbang", "blackforest", "ctrl" };
    for (auto s : str)
    {
        int key = djb2(s);
        cout << "key = " << key << endl;
    }
}

▷ Hash Index가 문자열 → 정수로 처리되는 것을 확인할 수 있다.

    "test" → Hash Function → Hash Index ( = 3)

    "harbang" → Hash Function → Hash Index ( = 0)

    "blackforest" → Hash Function → Hash Index ( = 1)

    "ctrl" → Hash Function → Hash Index ( = 8)

▷ Table_Size와 주어지는 문자열에 따라 djb2에서 반환되는 값을 다르다.

▷ 구해진 key 값으로 Hash를 구현할 수 있다.

 

★ [Hash] 문자열 Hash 고찰

[Hash] 문자열 Hash 고찰

 

Reference

- [해시] Hash란? 

- [해시] Hash Chaining 기법 구현  

- [해시] Hash Open Address 기법 구현  

- Hash (단방향, 더미노드 0개, *head)   

- Hash 구현 (양방향, 더미노드 0개, *head) 

- Hash (양방향, 더미노드 1개, *head) 

- Hash (양방향, 더미노드 1개, head)  

- Hash (양방향, 더미노드 2개, *head, *tail) 

- Hash (양방향, 더미노드 2개, head, tail) 

- [예제] PS시 자주 사용하는 함수 모음 

- [Hash] 문자열 Hash 고찰