time 33 hash function ( apr에서 사용하는 해시 함수 )

C언어

고요한하늘... 2009. 3. 28. 00:58

apr 소스 코드를 시간날때 살펴보고 있는데 apr 코드중에 동적 해시가 있어서 테스트를 해보았더니 속도가 비교적 빨랐다.

지적 호기심이 발동하여 어떻게 구현했는지 한줄한줄 읽어가며 소스 코드를 분석을 시작했다.

여러가지 이유가 있었지만 정확히 어느 부분이 포인트인지를 보기 위해 메모리플을 제외한 부분을 직접 구현해 보기로 하고

코딩을 시작해 몇일전에 끝이 났다.

그 해시 코드를 주저리주저리 말할려고 하는건 아니고

apr에서 사용하는 해시 함수중 time 33이라는 hash function을 소개할려고 한다.

문자열 관련해서 속도도 빠르고 상당히 잘 분산 시켜준다고 알려져 있고 버클리 DB와 펄에서 사용한다고 한다.

아래는 내가 사용한 함수이고 참고에 링크해놓은 사이트에 들어가면 hash함수들을 볼수 있다.

unsigned int time_33_hash( char *key, int klen )
{
    int i = 0;
    unsigned char   *s;
    unsigned int hash=0;

    for (s = key, i = klen; i; i--, s++)
    {
        hash = hash * 33 + *s;
    }

return hash;

}

ps. 어떤 해시 함수를 사용하는 것도 중요하지만, 어떻게 구현하는지가 훨씬 중요하다.