완벽한 해시 함수는 서로 다른 입력 값에 대해 충돌이 발생하지 않는 함수를 의미합니다. 정의역 X와 치환역 Y가 주어졌을 때, |X|=n, |Y|=m이라면 m≥n이어야 하며, 모든 key1≠key2에 대해 h(key1)≠h(key2)인 경우 이를 완벽한 해시 함수라고 합니다. m=n인 경우 일대일 매핑이 가능해 최소 완벽 해시 함수로 불립니다.

대규모 문자열 데이터 처리 시 각 문자열에 고유한 정수 식별자를 할당하기 위해 문자열 해시 함수가 사용됩니다. 효과적인 문자열 해시 함수를 찾기 위해 다양한 알고리즘이 개발되었습니다. 대표적인 예로는 BKDRHash, APHash, DJBHash, JSHash, RSHash, SDBMHash, PJWHash, ELFHash 등이 있습니다.

다음은 여러 문자열 해시 함수에 대한 분석 자료입니다. 참조

ELFHash, APHash 등은 비트 연산을 통해 각 문자가 최종 결과에 영향을 미치도록 설계된 간단하면서도 효과적인 방법입니다. MD5나 SHA1과 같은 해시 함수는 충돌이 거의 불가능한 수준입니다.

다음 표는 다양한 해시 함수의 성능 평가 결과입니다:

데이터1은 10만 개의 알파벳 및 숫자로 구성된 랜덤 문자열의 해시 충돌 횟수를 나타냅니다. 데이터2는 10만 개의 의미 있는 영문 문장의 해시 충돌 횟수입니다. 데이터3은 데이터1의 해시 값에 1000003(대규모 소수)을 나눈 후 선형 배열에 저장했을 때의 충돌 횟수입니다. 데이터4는 데이터1의 해시 값에 10000019(더 큰 소수)을 나눈 후 저장한 경우의 충돌 횟수입니다.

평가 결과, BKDRHash가 실제 효과성과 구현 편의성에서 가장 우수했습니다. APHash도 뛰어난 성능을 보였습니다. DJBHash, JSHash, RSHash, SDBMHash는 각각의 강점이 있었습니다. 반면 PJWHash와 ELFHash는 성능이 가장 낮았으나, 알고리즘 본질이 유사해 유사한 점수를 기록했습니다.

unsigned int sdbmHash(char *str) {
    unsigned int hashValue = 0;
    while (*str) {
        hashValue = *str++ + (hashValue << 6) + (hashValue << 16) - hashValue;
    }
    return (hashValue & 0x7FFFFFFF);
}

unsigned int jsHash(char *str) {
    unsigned int hash = 1315423911;
    while (*str) {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }
    return (hash & 0x7FFFFFFF);
}

unsigned int bkdrHash(char *str) {
    unsigned int seed = 131;
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

unsigned int djbHash(char *str) {
    unsigned int hash = 5381;
    while (*str) {
        hash += (hash << 5) + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

프로그래밍 주절에서 인용된 해시 함수 예제:

#define TABLE_SIZE 29989
#define MULTIPLIER 31

unsigned int hashFunction(char *p) {
    unsigned int h = 0;
    for (; *p; p++) {
        h = MULTIPLIER * h + *p;
    }
    return h % TABLE_SIZE;
}