Double in HashMap

Question

Stavo pensando di usare un Double come chiave per una HashMap ma so che i confronti in virgola mobile non sono sicuri, questo mi ha fatto riflettere. Anche il metodo equals sulla classe Double è pericoloso? Se è così significherebbe che il metodo hashCode è probabilmente anche errato. Ciò significherebbe che usare Double come chiave per una HashMap porterebbe a comportamenti imprevedibili.

Qualcuno può confermare una mia speculazione qui?

Answer 1

Risposta breve: Non farlo

Risposta lunga: Ecco come il la chiave verrà calcolata:

La chiave effettiva sarà un oggetto java.lang.Double, poiché le chiavi devono essere oggetti. Qui è suo metodo hashCode():

public int hashCode() { 
    long bits = doubleToLongBits(value); 
    return (int)(bits^(bits >>> 32)); 
} 

Procedimento doubleToLongBits() prende essenzialmente le 8 byte e li rappresentano a lungo. Ciò significa che piccoli cambiamenti nel calcolo del doppio possono significare un grande affare e tu avrai dei punti critici.

Se è possibile accontentarsi di un determinato numero di punti dopo il punto - moltiplicare per 10^(numero di cifre dopo il punto) e convertire in int (ad esempio - per 2 cifre moltiplicare per 100).

Sarà molto più sicuro.

Answer 2

L'hash del doppio viene utilizzato, non il doppio stesso.

Modifica: Grazie, Jon, in realtà non lo sapevo.

Non sono sicuro di questo (dovresti solo guardare il codice sorgente dell'oggetto Double) ma penserei che qualsiasi problema con confronti in virgola mobile sarebbe preso in considerazione per te.

Answer 3

Dipende da come lo si utilizzerà.

Se siete soddisfatti solo essere in grado di trovare il valore in base al esatto modello stesso bit (o potenzialmente una equivalente, come ad esempio +/- 0 e vari NaNs) allora potrebbe essere a posto .

In particolare, tutti i NaN verrebbero considerati uguali, ma +0 e -0 sarebbero considerati diversi. Dalla documentazione per Double.equals:

Nota che nella maggior parte dei casi, per due istanze della classe doppio, D1 e D2, il valore di d1.equals (d2) è vera se e solo se

d1.doubleValue() == d2.doubleValue() ha anche il valore true. Tuttavia, ci sono due eccezioni:

• Se D1 e D2 entrambi rappresentano Double.NaN, quindi il metodo equals restituisce true, anche se Double.NaN == Double.NaN ha il valore falso.
• Se d1 rappresenta +0.0 mentre d2 rappresenta -0.0, o viceversa, il pari test ha il valore falso, anche se +0.0 == - 0.0 ha il valore vero.

Questa definizione consente alle tabelle hash di di funzionare correttamente.

Molto probabilmente ti interessano i "numeri molto vicini alla chiave", il che lo rende molto meno praticabile. In particolare se hai intenzione di fare una serie di calcoli per ottenere la chiave una volta, quindi una serie diversa di calcoli per ottenere la chiave la seconda volta, avrai dei problemi.

Answer 4

Penso che tu abbia ragione. Sebbene l'hash dei doppi sia intatto, il doppio potrebbe rovinare l'hashish. Ecco perché, come Josh Bloch menziona in Java efficace, quando si usa un doppio come input per una funzione di hash, si dovrebbe usare doubleToLongBits(). Allo stesso modo, usa floatToIntBits per i float.

In particolare, per usare un doppio come hash, seguendo la ricetta di Josh Bloch, si dovrebbe fare:

public int hashCode() { 
    int result = 17; 
    long temp = Double.doubleToLongBits(the_double_field); 
    result = 37 * result + ((int) (temp^(temp >>> 32))); 
    return result; 
} 

Questo è dal punto 8 del Effective Java "ignorare sempre hashCode quando si modifica eguali". Può essere trovato in this pdf of the chapter from the book.

Spero che questo aiuti.

Answer 5

Dipende da come si memorizza e si accede alla mappa, sì valori simili potrebbero risultare leggermente diversi e quindi non ha lo stesso valore.

private static final double key1 = 1.1+1.3-1.6; 
private static final double key2 = 123321; 
... 
map.get(key1); 

sarebbe andato tutto bene, però

map.put(1.1+2.3, value); 
... 
map.get(5.0 - 1.6); 

sarebbe pericoloso

Answer 6

Il problema non è il codice hash ma la precisione dei doppi. Ciò causerà alcuni strani risultati. Esempio:

double x = 371.4; 
    double y = 61.9; 
    double key = x + y; // expected 433.3 

    Map<Double, String> map = new HashMap<Double, String>(); 
    map.put(key, "Sum of " + x + " and " + y); 

    System.out.println(map.get(433.3)); // prints null 

Il valore calcolato (chiave) è "433,29999999999995" che non è uguale a 433,3 e così non si trova la voce nella mappa (il codice hash probabilmente è diverso, ma non è il problema principale).

Se si utilizza

map.get(key) 

dovrebbe trovare la voce ... []]

Answer 7

Forse BigDecimal arrivare dove vuoi andare?

Answer 8

Risposta breve: Probabilmente non funzionerà.

Risposta onesta: dipende tutto.

Risposta più lunga: il codice hash non è il problema, è la natura di confronti uguali su virgola mobile. Come sottolineano Nalandial e i commentatori del suo post, alla fine qualsiasi partita contro una tabella hash finisce per usare uguali per scegliere il giusto valore.

Quindi la domanda è: i tuoi duplicati vengono generati in modo tale che tu sappia che uguaglia significa davvero uguale a? Se leggi o calcoli un valore, memorizzalo nella tabella hash e successivamente leggi o calcola il valore usando esattamente lo stesso calcolo, quindi funzionerà Double.equals. Ma altrimenti è inaffidabile: 1.2 + 2.3 non è necessariamente uguale a 3.5, potrebbe essere uguale a 3.4999995 o altro. (Non è un esempio reale, l'ho appena inventato, ma questo è il genere di cose che succedono.) Puoi confrontare float e double in modo abbastanza affidabile per meno o più, ma non per gli uguali.