CPython의 실제 hash함수

작성일 | In | |
hash를 직접 구현해야하는 경우 참고할 것

코드

in file Objects/stringobject.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static long string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    // cpython에서 string의 hash는 ob_hash에 저장해두는데, 항상 hash하는것이 아닌 값을 사용할때 hash한다.
    // -1은 기본값으로, hash가 이뤄지지 않았음을 의미한다.
    if (a->ob_shash != -1)
        return a->ob_shash;
    
    len = Py_SIZE(a);

    // ob_sval은 실제 스트링이다.
    p = (unsigned char *) a->ob_sval;


    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);

    // hash의 결과로 -1이 나온경우 hash가 이뤄지지 않은 경우와 겹치므로, -2로 처리한다.
    if (x == -1)
        x = -2;
    
    a->ob_shash = x;
    return x;
}

pure C

1
2
3
4
5
6
7
8
9
10
11
long hash(const char *str)
{
    register long x;
    register size_t i;
    register const unsigned char *p = (const unsigned char*)str;
    x = *p << 7;
    for(i=0;str[i];i++)
        x = (1000003*x) ^ *p++;
    x ^= i;
    return x;
}
  • null-terminated string을 가정한다.
  • cpython은 특수한 경우였으므로, 이 구현에서는 hash여부를 체크하지 않는다.