Was ist eine gute Möglichkeit, eine feste Hash-Funktion für eine hartcodierte Hash-Tabelle zu bestimmen?

Question

Oft brauche ich eine Hash-Tabelle, deren Werte zur Kompilierungszeit bekannt sind und von der bekannt ist, dass sie sich nie ändert.

Ich möchte wissen, ob es eine Standardmethode gibt, einen maßgeschneiderten Algorithmus zu generieren, der nur für eine bestimmte Hashtabelle verwendet wird, so dass er zur Laufzeit nicht erstellt werden muss und keine Kollisionen auftreten .

Der schlimmste Algorithmus dieser Art wäre nur eine Reihe von if-Anweisungen, aber diese Art ruiniert die O (N) -Ness.

Ich möchte wissen, ob es einen vorhandenen Algorithmus für die Zuordnung einer festen Anzahl von eindeutigen Strings zu Indizes von 0 bis zur Anzahl der eindeutigen Strings gibt.

Zum Beispiel; Ich könnte eine Hash-Tabelle wäre zu schaffen, um eine Funktion mit einer internen Tabelle Eintritt Paare zu machen und unten mit einer willkürlichen Diskriminierung, wie man kommt

{ 
    "one": "1", 
    "two": "2", 
    "three": "3" 
} 

Einen naiven Versuch solch eine hartkodierte Tabelle.

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

static const char *my_hash(const char *input) 
{ 
    const struct { 
     const char *key; 
     const char *value; 
    } h_table[] = { 
     {"three", "3"}, 
     {"one", "1"}, 
     {"two", "2"} 
    }; 

    int hash; 
    int len = strlen(input); 

    if (len != 3 && len != 5) { 
     return (char *)0; 
    }   

    hash = (int)ceil((((input[1] - 102)/4) - 1)/2.0);  

    return h_table[hash].value; 
} 

int main(int argc, char **argv) 
{ 
    puts(my_hash("one")); 
    puts(my_hash("two")); 
    puts(my_hash("three")); 

    return 0; 
} 

Gibt es einen bekannten Algorithmus zum Generieren von Algorithmen dieser Art?

Zusammenfassung: Gibt es einen bekannten Algorithmus zum Zuordnen von N verschiedenen Strings zu N verschiedenen ganzen Zahlen von 0 bis N-1?

Ich habe das Gefühl, dass so etwas schon existiert.

Answer 1

Diese sind bekannt als minimal perfect hash functions, und es gibt tatsächlich bekannte Algorithmen, um sie zu finden. Ich kenne die Algorithmen nicht persönlich, aber das ist in Ordnung. Bestehende Bibliotheken können das für Sie tun.

CMPH ist gut für die Suche nach minimalen perfekten Hash-Funktionen für sehr viele Schlüssel.

gperf konzentriert sich auf Hash-Auswertung Geschwindigkeit für kleine Zahlen von Schlüsseln, wo die perfekte Hash-Funktion ist nicht erforderlich, um minimal zu sein (so kann es einige leeren Raum in der Tabelle sein).