funzione hash per carri

Question

Attualmente sto attuare una tabella hash in C++ e sto cercando di fare una funzione di hash per i galleggianti ...

stavo andando per il trattamento di carri come numeri interi imbottitura i numeri decimali, ma poi ho capito che probabilmente avrei raggiunto l'overflow con grandi numeri ...

C'è un buon modo per fare hash float?

Non devi darmi la funzione direttamente, ma mi piacerebbe vedere/capire i concetti diversi ...

Note:

1. non ne ho bisogno a essere molto veloce, distribuito equamente, se possibile.

2. Ho letto che i float non devono essere sottoposti a hash a causa della velocità del calcolo, qualcuno può confermare/spiegare questo e darmi altri motivi per cui i float non dovrebbero essere sottoposti a hash? Io non capisco il motivo per cui (oltre alla velocità)

Answer 1

Dipende dall'applicazione ma la maggior parte del tempo non deve essere sottoposto a hash, poiché l'hashing viene utilizzato per la ricerca rapida di corrispondenze esatte e la maggior parte dei float sono il risultato di calcoli che generano un float che è solo un'approssimazione della risposta corretta. Il metodo solitamente per verificare l'uguaglianza fluttuante consiste nel verificare se rientra in qualche delta (in valore assoluto) della risposta corretta. Questo tipo di controllo non si presta alle tabelle di ricerca con hash.

EDIT:

Normalmente, a causa di errori di arrotondamento e limitazioni intrinseche di aritmetica in virgola mobile, se ci si aspetta che i numeri in virgola mobile a e b dovrebbe essere uguali tra loro, perché la matematica dice così, è necessario selezionare relativamente piccolo delta > 0 e quindi dichiarare a e b uguale a abs(a-b) < delta, dove abs è la funzione del valore assoluto. Per ulteriori dettagli, vedere this article.

Ecco un piccolo esempio che illustra il problema:

float x = 1.0f; 
x = x/41; 
x = x * 41; 
if (x != 1.0f) 
{ 
    std::cout << "ooops...\n"; 
} 

A seconda della piattaforma, compilatore e ottimizzazione livelli, questo può stampare ooops... al vostro schermo, il che significa che l'equazione matematica x/y * y = x non necessariamente tenere su il tuo computer.

Ci sono casi in cui l'aritmetica in virgola mobile produce risultati esatti, ad es. interi e razionali di dimensioni ragionevoli con denominatori di potenza di 2.

Answer 2

unsigned hash(float x) 
{ 
    union 
    { 
     float f; 
     unsigned u; 
    }; 
    f = x; 
    return u; 
} 

comportamento Tecnicamente non definito, ma la maggior parte dei compilatori supportano questo. Soluzione alternativa:

unsigned hash(float x) 
{ 
    return (unsigned&)x; 
} 

Entrambe le soluzioni dipendono dalla endianness della vostra macchina, così per esempio su x86 e SPARC, produrranno risultati diversi. Se ciò non ti infastidisce, usa una di queste soluzioni.

Answer 3

Se la funzione di hash ha fatto la seguente si otterrebbe un certo grado di indeterminatezza sul hash ricerca

unsigned int Hash(float f) 
{ 
    unsigned int ui; 
    memcpy(&ui, &f, sizeof(float)); 
    return ui & 0xfffff000; 
} 

In questo modo potrai mascherare i 12 bit meno significativi che consentono un certo grado di incertezza .. Tuttavia dipende davvero dall'applicazione.

Answer 4

Potete naturalmente rappresentano un float come int tipo delle stesse dimensioni di hash, tuttavia questo approccio ingenuo ha alcune insidie ​​che è necessario stare attenti a ...

semplice conversione ad una rappresentazione binaria è soggetto a errore poiché i valori uguali non necessariamente hanno la stessa rappresentazione binaria.

Un caso ovvio: -0.0 non corrisponde a 0.0 per esempio. *

Inoltre, semplicemente conversione in un int delle stesse dimensioni solito invia distribuzione molto uniforme, che è spesso importante (che implementa un hash/set che utilizza benne per esempio).

passi suggeriti per l'attuazione:

• filtrare i casi non finite (nan, inf) e (0.0, -0.0se è necessario fare questo in modo esplicito o meno dipende dal metodo utilizzato).
• convertire in int della stessa dimensione
  (cioè - utilizzare un sindacato, ad esempio per rappresentare il float come int, non semplicemente gettati a un int).
• ridistribuisci i bit, (intenzionalmente vago qui!), questo è fondamentalmente un compromesso tra velocità e qualità. Ma se hai molti valori in un piccolo intervallo probabilmente non li vuoi anche in un intervallo simile.

*: Si può wan't per controllare (e nan-nan) troppo. Come gestire quelli esattamente dipende dal tuo caso d'uso (potresti voler ignorare il segno per tutti gli nan come fa CPython).

di Python _Py_HashDouble è un buon riferimento per come si potrebbe hash un float, nel codice di produzione (ignorare il controllo -1 alla fine, dato che è un valore speciale per Python).

Answer 5

È possibile utilizzare l'hash std, non è male:

std::size_t myHash = std::cout << std::hash<float>{}(myFloat); 

Answer 6

Se siete interessati, ho appena fatto una funzione di hash che usa in virgola mobile e in grado di hash galleggianti. Passa anche SMHasher (che è il test di bias principale per le funzioni hash non crittografiche). È molto più lento delle normali funzioni hash non crittografiche a causa dei calcoli float.

Non sono sicuro che se tifuhash diventerà utile per tutte le applicazioni, ma è interessante vedere una semplice funzione in virgola mobile passare sia PractRand che SMHasher.

La funzione di aggiornamento di stato principale è molto semplice, e si presenta come:

function q(state, val, numerator, denominator) { 
    // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction" 
    // with denominator = val + pos/state[1] 
    state[0] += numerator/denominator; 
    state[0] = 1.0/state[0]; 

    // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1 
    state[1] += val; 
    state[1] = numerator/state[1]; 
} 

In ogni caso, è possibile get it on npm Oppure si può check out the github

Utilizzando è semplice:

const tifu = require('tifuhash'); 

const message = 'The medium is the message.'; 
const number = 333333333; 
const float = Math.PI; 

console.log(tifu.hash(message), 
    tifu.hash(number), 
    tifu.hash(float), 
tifu.hash()); 

C'è una demo di alcuni hash su runkit qui https://runkit.com/593a239c56ebfd0012d15fc9/593e4d7014d66100120ecdb9

Nota a margine: penso che in futuro l'utilizzo di virgola mobile, possibilmente di grandi matrici di calcoli in virgola mobile, potrebbe essere un modo utile per rendere più complicate le funzioni di hash in futuro. Uno strano effetto collaterale che ho scoperto di usare il floating point è che gli hash dipendono dall'obiettivo, e suppongo che potrebbero essere usati per impronte digitali delle piattaforme su cui sono stati calcolati.