Come andresti a progettare una funzione per un hash perfetto?

Question

Il dominio di interesse è la corrispondenza delle stringhe. Supponiamo che io abbia una struttura come questa.

typedef struct 
{ 
    char *name, 
    int (*function)(); 

} StringArray 

StringArray s[] = 
{ 
    {"George", func1}, 
    {"Paul", func2}, 
    {"Ringo", func3}, 
    {"John", func4}, 
    {"",  NULL} /* End of list */ 
} 

C'è un numero fisso di stringhe nell'array. Sono hardcoded come nell'esempio. Se la tabella cambia, è necessario rivalutare la qualità della funzione di hash.

Desidero applicare una funzione di hash a una stringa e, se la stringa corrisponde a una nell'array, chiamare la funzione . Per questo è necessaria una perfetta funzione di hash. Nessuna collisione è consentita. Lo scopo di richiedere l'hashing è quello di ottenere prestazioni O (1) nella ricerca.

Che idee avete nel progettare una funzione per fare questo?

Answer 1

Vedere la gperf home page.

Answer 2

È possibile utilizzare la mappa

std::string foo() { return "Foo"; } 
std::string bar() { return "Bar"; } 

int main() 
{ 
    std::map<std::string, std::string (*)()> m; 
    m["foo"] = &foo; 
    m["bar"] = &bar; 
} 

Answer 3

Vedi:

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates?

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 4

Se le collisioni sono assolutamente non ammessi, l'unica opzione è quella di tenere traccia di ogni stringa nel database, che probabilmente non è un modo migliore per partire.

Quello che vorrei fare è applicare uno degli algoritmi di hashing più comuni, come MD5 o SHA. Ci sono miriadi di campioni in tutto, eccone uno per esempio: http://www.codeproject.com/KB/security/cryptest.aspx

Answer 5

Bene, non esiste una funzione di hash perfetta.

Ne esistono diverse che riducono al minimo le collisioni, ma nessuna le elimina.

non posso consigliare un però: P

EDIT: La soluzione non può essere trovare una funzione di hash perfetta. La soluzione è essere consapevoli delle collisioni. Generalmente una funzione hash ha collisioni. Questo ovviamente dipende dal set di dati e dalla dimensione del codice hash risultante.

Answer 6

Utilizzare un albero binario bilanciato. Quindi il tuo comportamento KNOW è SEMPRE O (logn).

Non mi piacciono gli hash. Le persone non si rendono conto di quanto rischio assumano con il loro algoritmo. Eseguono alcuni dati di test e quindi si distribuiscono sul campo. Non ho mai visto un algoritmo di hash distribuito controllato per il comportamento nel campo.

O (log n) è quasi sempre accettabile al posto di O (1).

Answer 7

Il sommario elenca sia C che C++. Quale di loro stai cercando? C e C++ sono due linguaggi distinti e si differenziano notevolmente per la gestione delle stringhe e le strutture dati (e il fatto che le C funzionino in C++ non lo cambia).

Perché, in particolare, vuoi una perfetta funzione di hash? Vuoi associare una stringa a una funzione e pensare che sarebbe un buon modo per farlo? È una specie di compito a casa? Hai un motivo per non utilizzare la mappa <> in C++? (Oppure unordered_map <> se disponibile?)

Se hai bisogno di un hash perfetto, quali sono i vincoli sulle stringhe? Ci sarà un certo set fisso su cui vuoi effettuare l'invio? Che dire delle stringhe che non corrispondono a quelle del set? Sei disposto ad accettare hit da stringhe casuali o il numero di stringhe in entrata è limitato?

Se potessi modificare la tua domanda per includere informazioni del genere, potremmo essere molto più utili.

EDIT (in risposta ai primi due commenti):

OK, dovremmo esaminare soluzioni C, dal momento che si desidera probabilmente questo sia per il vostro lavoro C e C++. Preferibilmente vuoi la performance, ma hai provato? Se abbiamo a che fare con le stringhe che entrano nel sistema I/O, è probabile che il tempo non superi il tempo di invio.

Ci si aspetta stringhe arbitrarie. È un po 'troppo aspettarsi una perfetta funzione di hash che eviti tutte le collisioni da dati casuali, quindi è necessario tenerne conto.

Avete considerato un trie? Potrebbe essere più efficiente di una perfetta funzione di hash (o potrebbe non esserlo), dovrebbe essere abbastanza facile da implementare in C, ed eviterà problemi con la ripetizione dell'elenco di stringhe di dispacciamento o possibili collisioni.

Answer 8

Il risultato finale di questo esercizio era di

• rubare un certo numero di funzioni hash corda orientata dalla rete.
• Costruire una sorta di classe factory che ha testato ciascuna funzione rispetto al set di dati con un intervallo di valori operatore mod, cercando l'hash più piccolo perfetto che funzioni con quella funzione.
• Questo costruttore predefinito della classe factory restituisce una stringa, che rappresenta un insieme di argomenti che quando si utilizza la funzione hash corretta e la dimensione della mod per fornire l'hash perfetto che richiede la minor quantità di memoria.
• in condizioni di utilizzo normale, si semplifica l'istanza della classe con gli argomenti restituiti e la classe si mette in uno stato funzionante con le funzioni desiderate.
• Questo costruttore convalida che non ci sono collisioni e si interrompe se ci sono.
• Nel caso in cui non venga trovato un hash perfetto, degrada in una ricerca binaria su una versione ordinata della tabella di input.

Per il set di matrici che ho nel mio dominio, questo sembra funzionare molto molto bene. Una possibile ottimizzazione futura sarebbe quella di eseguire lo stesso tipo di test, su sottostringhe dell'input. Nel caso di esempio, la prima lettera del nome di ogni musicista è sufficiente per distinguerli. Quindi è necessario bilanciare il costo dell'effettiva funzione di hash contro della memoria utilizzata.

Grazie a tutti coloro che hanno contribuito con le idee.

Male