Determinazione tavolo perfetto Hash Hash di ricerca per Pearson

Question

sto sviluppando un linguaggio di programmazione, e nel mio linguaggio di programmazione, sto memorizzare gli oggetti come tabelle hash. La funzione di hash che sto utilizzando è Pearson hashing , che dipende da una tabella di ricerca a 256 bit . Ecco la funzione:

char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

La mia domanda è, dato un gruppo fisso di meno di 256 nomi dei membri, come si può determinare un tavolo lookup tale che pearson() tornerà personaggi unici all'interno di un intervallo contiguo a partire dal '\0'. In altre parole, ho bisogno di un algoritmo per creare una tabella di ricerca per un perfetta hash . Ciò mi permette di avere oggetti che occupano più spazio rispetto al numero dei loro membri. Ciò sarà fatto al momento della compilazione, quindi la velocità non è un problema enorme, ma più veloce sarebbe meglio. Sarebbe facile a forza bruta, ma credo (spero) c'è un modo migliore.

Ecco un esempio: dato variabili membro 'foo', 'bar', e 'baz' in una classe, voglio stabilire un lookup tale che:

pearson('foo',lookup) == (char) 0
pearson('bar',lookup) == (char) 1
pearson('baz',lookup) == (char) 2

Si noti che l'ordine non importa, quindi il seguente risultato sarebbe anche accettabile:

pearson('foo',lookup) == (char) 2
pearson('bar',lookup) == (char) 0
pearson('baz',lookup) == (char) 1

In un mondo ideale, tutti i nomi che non sono nella tabella potrebbero restituire un valore superiore a 2, perché questo mi avrebbe permesso di evitare un controllo e forse anche evitare di memorizzare i nomi dei membri, ma io non credo che questo è possibile, quindi dovrò aggiungere un controllo in più per vedere se è nella tabella. Dato questo, probabilmente sarebbe risparmiare tempo di non inizializzare i valori nella tabella di ricerca che non sono utilizzati (collisioni non importa, perché se si scontra e non supera il controllo, non è nell'oggetto a tutti, quindi la collisione non ha bisogno di essere risolto,. solo l'errore deve essere maneggiato)

Answer 1

Date un'occhiata a questo su hash perfette minimi - fa riferimento a un paio di implementazioni e ha una breve sezione con alcune riflessioni su minimi hash Pearson perfette.

Answer 2

dubito fortemente che si sarà in grado di trovare una soluzione con la forza bruta, se il numero dei nomi dei membri è troppo alto. Grazie al paradosso del compleanno la probabilità che non esistono collisioni (vale a dire, due hash sono gli stessi) è di circa 1: 5000 per 64 e 1: 850 milioni per 96 nomi dei membri. Dalla struttura della funzione di hash (è derivato da una costruzione di crittografia che è progettato per "mescolare" le cose bene) non mi aspetto che un algoritmi esiste che risolve il problema (ma avrei sicuramente essere interessato a una bestia).

Il tuo mondo ideale è un'illusione (come previsto): ci sono 256 caratteri che è possibile aggiungere a 'foo', non ci sono due di loro dando una nuova parola con uno stesso hash. Come ci sono solo 256 possibilità per i valori di hash, si può quindi aggiungere un carattere di 'foo' in modo che il suo hash è la stessa di una qualsiasi delle hash di 'foo', 'bar' o 'baz'.

Perché non si utilizza una libreria esistente come CMPH ?

Answer 3

Se ho capito bene, quello che ti serve è un ordinato e nessuno elemento duplicato matrice che si può fare ricerca binaria su. Se la chiave è nella matrice, l'indice è il "hash". In caso contrario, si ottiene la dimensione della matrice. E 'O (nlogn) a fronte di tabella di ricerca O (1), ma è abbastanza buono per piccolo numero di elementi -. 256 nel tuo caso