알려진 값에 대한 완벽한 해시

Question

해시 테이블을 만들려는 일부 알려진 값이 있다고 가정 해보십시오. 예를 들어, 너무 스위치/ 경우 사용할 수없는 등

For 0x78409 -> 1 
For 0x89934 -> 2 
For 0x89834 -> 3 

...

그러나 이러한 값 (0x78409, 0x89934, 0x89834)가 런타임에만 알려져있다. 그러나 실행 초기에 알려 지므로 완벽한 해시 테이블을 만들기 위해 자체적으로 적응하는 해시 함수를 만들 수 있습니다. 그래서 제 질문은 그러한 경우에 완벽한 해시 함수를 만들 수 있습니까?

Answer 1

해시 맵을 만들기 전에 입력의 전체 도메인을 알고있는 경우 가능하지만 VM이나 JIT (LuaJIT와 같은 스크립팅 언어를 통해)를 통해 런타임 코드 생성 형식이 필요합니다. gperf과 그 ilk를 사용하여 런타임에 해시를 생성하고 컴파일 한 다음이를 사용하여 맵을 채우고 검색 할 수 있습니다.

보다 쉽고 더 실용적인 해법은 주어진 입력 치환 집합 (예 : 알파벳 소문자 만 사용할 수 있음)에 대해 충돌이 매우 적은 해시 함수를 사용하는 것입니다.

Murmur3과 crapwow는 (비록 내가 쓰레기에 신중할 것입니다), Google's CityHash 및 xxHash도 살펴볼 가치가 있습니다. Bob Jenkins는 유효한 최소한의 완벽한 해시 기반지도도 제공합니다. here도 괜찮습니다. ?

Answer 2

위키 피 디아는 this page을 제공합니다. 하지만 완벽한 해시 함수를 원하십니까? 아마도 좋고 빠른 해시 함수로 충분할 수 있습니까?

Answer 3

이러한 속성은 당신을 위해 충분하지 않습니다 :

• 더 충돌
• 최악의 경우 키 룩업 성능 =>O(log n)

다음 개념 증명 구현 :

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define MAX_PAIRS 3 
#define KEY_SIZE 20 

#define VALUE_OR_KEY_NOT_FOUND(v) ((v==NULL)? "(__KEY_NOT_FOUND__)":v) 

typedef struct { 
    char Key[KEY_SIZE]; 
    char Val[KEY_SIZE]; 
} Pair; 

typedef struct { 
    unsigned int lastPairIndex; 
    Pair pairs[MAX_PAIRS]; 
} HashTable; 

int comparePairs(const void * a, const void * b) 
{ 
    return strcmp(((Pair *)a)->Key, ((Pair *)b)->Key); 
} 

void hashInsert(HashTable * hashTable, char * key, char * val) { 
    unsigned int ix = hashTable->lastPairIndex++; 
    strcpy(hashTable->pairs[ix].Key,key); 
    strcpy(hashTable->pairs[ix].Val,val); 
} 

void hashFinalize(HashTable * hashTable) { 
    qsort(hashTable->pairs, MAX_PAIRS, sizeof(Pair), comparePairs); 
} 

char * hashLookup(HashTable * hashTable, char * key) { 
    char * r = bsearch(key, hashTable->pairs, MAX_PAIRS, sizeof(Pair), comparePairs); 
    if (r != NULL) 
    return r + KEY_SIZE; 
    return NULL; 
} 

int main() 
{ 
    HashTable ht = {0}; 
    char * res; 
    char * key_1 = "jkl"; 
    char * key_2 = "oops"; 

    hashInsert(&ht, "jkl", "some val"); 
    hashInsert(&ht, "def", "other val"); 
    hashInsert(&ht, "abc", "this val"); 
    hashFinalize(&ht); 

    res = hashLookup(&ht, key_1); 
    printf("\"%s\" key => value: \"%s\"\n", key_1, VALUE_OR_KEY_NOT_FOUND(res)); 
    res = hashLookup(&ht, key_2); 
    printf("\"%s\" key => value: \"%s\"\n", key_2, VALUE_OR_KEY_NOT_FOUND(res)); 

    return 0; 
} 

많은 오류가 확인되지 않았습니다. 예를 들어 삽입 할 때와 같은 이미 거기에 존재할 수 있습니다. 이것은 단지 개념 증명입니다. O(log n) 키가 사전 순으로 정렬되어 키 조회가 2 진 검색 알고리즘으로 수행 될 수 있으므로 키 조회 성능이 달성됩니다. HTH!