Hash dei valori di puntatore

Question

A volte è necessario eseguire una funzione hash di un puntatore; non l'oggetto al quale punta il puntatore, ma il puntatore stesso. Un sacco di tempo, gente semplicemente punt e usa il valore del puntatore come un numero intero, tagliando alcuni bit alti per adattarlo, magari spostando i bit dello zero noto in basso. Il fatto è che i valori del puntatore non sono necessariamente ben distribuiti nello spazio del codice; in effetti, se il tuo allocatore sta facendo il suo lavoro, ci sono ottime possibilità che siano tutti raggruppati insieme.

Quindi, la mia domanda è, qualcuno ha sviluppato funzioni hash che fanno bene a questo? Prendi un valore a 32 o 64 bit che abbia forse 12 bit di entropia nello da qualche parte nello e diffondilo uniformemente su uno spazio numerico a 32 bit.

Answer 1

This page elenca diversi metodi che potrebbero essere utili. Uno di questi, a causa di Knuth, è un semplice come moltiplicando (in 32 bit) per 2654435761, ma "I risultati di hash male vengono prodotti se i tasti variano nei bit superiori." Nel caso dei puntatori, questa è una situazione abbastanza rara.

Here sono altri algoritmi, inclusi test delle prestazioni.

Sembra che le parole magiche siano "hashing intero".

Answer 2

Perché non utilizzare solo uno hash function esistente?

Answer 3

Probabilmente esporranno la località, sì - ma nei bit più bassi, il che significa che gli oggetti saranno distribuiti attraverso l'hashtable. Vedrai solo le collisioni se l'indirizzo di un puntatore è un multiplo della lunghezza della tabella hash da un altro puntatore.

Answer 4

Se si conosce l'indirizzo del puntatore più basso possibile (che si verifica spesso se si lavora all'interno di un buffer di grandi dimensioni), basta convertire il puntatore in un numero intero sottraendo il valore di puntatore più basso possibile; per esempio. quello potrebbe essere l'indirizzo di base del buffer. -Ricorda: il puntatore sottratto dal puntatore equivale a un offset (intero). Quindi: non "tagliare" i bit; è molto meglio convertire in offset. Ciò comporterà che il valore di offset è molto più piccolo di un valore di puntatore. In alcuni casi può essere utile spostare ulteriormente il valore del puntatore due volte (ad es. Dividere per 4), prima di eseguirne l'hashing. Il problema con i puntatori è spesso che piccoli blocchi di memoria sono probabilmente allocati sullo stesso indirizzo (ad esempio un blocco viene liberato e un altro blocco sta prendendo il posto del blocco liberato).