사용자 도구

사이트 도구


kb:hashfunction

Hash

해쉬 함수는, HashTable 구성을 위해 사용하는 함수들과, 암호화 등에서 원본 메시지 확인을 위해 사용하는 함수, 이 두 가지로 대충 구분할 수 있다. 절대적인 구분이 존재하는 건 아니지만, 내 맘대로 분류다. 전자는 대부분 함수 하나로 끝나고 정수형의 반환값을 가진다. 후자는 좀 더 덩치가 크고, 문자열 형태의 반환값을 가진다.

해쉬 테이블 구성을 위한 함수들

구글링 약간만 해봐도 엄청 나온다. 해쉬 테이블 구성을 위한 함수는 빠르기도 빨라야하지만, 결과값을 고르게 분포시키는 게 중요하다. 그래야 충돌이 줄어들기 때문이다. 어떤 게 좋은지 테스트 좀 해봐야하는데…

Elf hash algorithm

unsigned long ElfHash(const unsigned char *name)
{
    unsigned long h=0, g;
    while (*name)
    {
        h = (h << 4) + *name++;
        if (g = h & 0xF0000000)
        h ^= g >> 24;
        h &= ~g;
    }
    return h;
}

Peter Weinberger's (PJW) generic hashing algorithm

#include <limits.h>
 
#define BITS_IN_INT     ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS  ( (int) ((BITS_IN_INT * 3) / 4) )
#define ONE_EIGHTH      ( (int) (BITS_IN_INT / 8) )
#define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH) )
 
unsigned int HashPJW(const char *datum)
{
    unsigned int hash_value, i;
    for (hash_value = 0; *datum; ++datum)
    {
        hash_value = (hash_value << ONE_EIGHTH) + *datum;
        if ((i = hash_value & HIGH_BITS) != 0 )
            hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
    }
    return (hash_value);
}

Bob Jenkins' hash algorithm

// The mixing step
#define mix(a,b,c) \
{ \
    a=a-b;  a=a-c;  a=a^(c>>13); \
    b=b-c;  b=b-a;  b=b^(a<<8);  \
    c=c-a;  c=c-b;  c=c^(b>>13); \
    a=a-b;  a=a-c;  a=a^(c>>12); \
    b=b-c;  b=b-a;  b=b^(a<<16); \
    c=c-a;  c=c-b;  c=c^(b>>5);  \
    a=a-b;  a=a-c;  a=a^(c>>3);  \
    b=b-c;  b=b-a;  b=b^(a<<10); \
    c=c-a;  c=c-b;  c=c^(b>>15); \
}
 
/// \brief The whole new hash function
/// \param k the key
/// \param length the length of the key in bytes
/// \param initval the previous hash, or an arbitrary value
/// \return UINT32
UINT32 hash(UINT8* k, UINT32 length, UINT32 initval)
{
    UINT   a   = 0x9e3779b9; // the golden ratio; an arbitrary value
    UINT   b   = a;
    UINT   c   = initval;    // variable initialization of internal state
    UINT32 len = length;     // how many key bytes still need mixing
 
    // handle most of the key --------------------------------------------------
    while (len >= 12)
    {
        a=a+(k[0]+((UINT32)k[1]<<8)+((UINT32)k[2]<<16) +((UINT32)k[3]<<24));
        b=b+(k[4]+((UINT32)k[5]<<8)+((UINT32)k[6]<<16) +((UINT32)k[7]<<24));
        c=c+(k[8]+((UINT32)k[9]<<8)+((UINT32)k[10]<<16)+((UINT32)k[11]<<24));
        mix(a,b,c);
        k = k + 12; len = len - 12;
    }
 
    // handle the last 11 bytes ------------------------------------------------
    c = c + length;
    switch (len) // all the case statements fall through
    {
    case 11: c=c+((UINT32)k[10]<<24);
    case 10: c=c+((UINT32)k[9]<<16);
    case 9 : c=c+((UINT32)k[8]<<8);
        // the first byte of c is reserved for the length
    case 8 : b=b+((UINT32)k[7]<<24);
    case 7 : b=b+((UINT32)k[6]<<16);
    case 6 : b=b+((UINT32)k[5]<<8);
    case 5 : b=b+k[4];
    case 4 : a=a+((UINT32)k[3]<<24);
    case 3 : a=a+((UINT32)k[2]<<16);
    case 2 : a=a+((UINT32)k[1]<<8);
    case 1 : a=a+k[0];
        // case 0: nothing left to add
    }
    mix(a,b,c);
    return c;
}

원본 메시지 확인을 위한 함수들

링크

kb/hashfunction.txt · 마지막으로 수정됨: 2014/11/11 14:54 저자 excel96