Konstruowanie tabeli mieszania/funkcji mieszania

Question

Chciałbym utworzyć tablicę asocjacyjną, która wyszukuje klucze w ciągach (ciągach) bajtów od 1 do 15 bajtów.

Chciałbym zapisać wartość całkowitą, więc wyobrażam sobie, że wystarczałaby tablica do mieszania. Mam trudności z konceptualizacją sposobu skonstruowania funkcji mieszania, tak aby dany klucz dał indeks do tablicy.

Każda pomoc będzie bardzo doceniona.

Maksymalna liczba wpisów w hash jest: * 15 + 4081 4081 * 14 + ... 4081 = 4081 ((15 * (16))/2) = 489720.

Tak na przykład:

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
} 

Co to są dobre opcje dla funkcji skrótu, lub jak mam ją zaprojektować?

Dzięki.

Answer 1

Jeśli chcesz uzyskać doskonały skrót, możesz zacząć od przeczytania artykułu z Wikipedii pod adresem perfect hashing. Jeśli napotkasz przeszkody, możesz poprosić o pomoc tutaj.

Answer 2

Jeśli średnia liczba ciągów znaków znajdujących się w tabeli jest niska - podobnie jak w przypadku mniej niż 10 000 wpisów - tablica asocjacyjna byłaby rozsądnym podejściem, nawet przy użyciu wyszukiwania liniowego, jeśli dotyczy to nowoczesnej architektury procesora.

W przeciwnym razie skonstruowanie "idealnego skrótu" wymaga sprawdzenia każdego znaku ciągu i obliczenia unikalnej wartości w oparciu o możliwy zakres. Na przykład, jeśli tylko A..Z 26 znaków są dozwolone w kluczu, to będzie działać:

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
} 

Answer 3

Twój klucz przestrzeń jest duża (ok 2^(8 * 15)), więc jeśli chcesz idealne hash, musisz wiedzieć, co 489720 rzeczywistych kluczy pojawi się z góry. Nawet wtedy praktycznie niemożliwe jest znalezienie idealnego skrótu dla tych kluczy, nawet jeśli pozwoliłeś na znacznie większy stół (a.k.a. bardzo niski współczynnik obciążenia). Jedyny znany mi sposób znalezienia idealnego skrótu to próba i błąd, a losowy hash prawdopodobnie zawiedzie, chyba że Twój stół ma blisko 489720^2 wpisów.

Bardzo polecam używanie regular (non-perfect) hash i deal with collisions appropriately, np. z łańcuchowym:

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
} 

Polecam również nie realizować ten sam - korzystać z biblioteki standardowej jak c++ hashmap.

Answer 4

hash ciągi C, zawsze stosować tę funkcję (wziąć% wynik rozmiarze Twojego tablica mieszająca'S):

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
} 

nie pamiętam, gdzie mam go od początku, ale od wielu lat to mnie nie zawiodło.