既知の値の完全なハッシュ

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)キーのアルファベット順のソートが行われ、バイナリ検索アルゴリズムでキールックアップを実行できるため、キールックアップ性能が得られます。 HTH！