2012-11-15 12 views
5

Ho una classe immutabile, ListaToken, che consiste in un elenco di oggetti token, che sono anche immutabili:Uso UUID per equals a basso costo() e hashCode()

@Immutable 
public final class TokenList { 

    private final List<Token> tokens; 

    public TokenList(List<Token> tokens) { 
     this.tokens = Collections.unmodifiableList(new ArrayList(tokens)); 
    } 

    public List<Token> getTokens() { 
     return tokens; 
    } 
} 

che faccio diverse operazioni su queste TokenLists che prende più TokenList come input e restituisce un singolo TokenList come output. Possono esserci arbitrariamente molti TokenList che entrano, e ognuno può avere arbitrariamente molti Token.

Queste operazioni sono costose e vi sono buone probabilità che la stessa operazione (vale a dire gli stessi ingressi) venga eseguita più volte, quindi mi piacerebbe memorizzare le uscite in cache. Tuttavia, le prestazioni sono critiche, e sono preoccupato per le spese di esecuzione di hashCode() ed equals() su questi oggetti che possono contenere arbitrariamente molti elementi (dato che sono immutabili allora hashCode potrebbe essere memorizzato nella cache, ma equals sarà ancora costoso).

Questo mi ha portato a chiedermi se potevo usare un'UUID per fornire equals() e hashCode() semplice ed economico facendo i seguenti aggiornamenti per ListaToken:

@Immutable 
public final class TokenList { 

    private final List<Token> tokens; 
    private final UUID uuid; 

    public TokenList(List<Token> tokens) { 
     this.tokens = Collections.unmodifiableList(new ArrayList(tokens)); 
     this.uuid = UUID.randomUUID(); 
    } 

    public List<Token> getTokens() { 
     return tokens; 
    } 

    public UUID getUuid() { 
     return uuid; 
    } 
} 

E qualcosa di simile ad agire come un chiave di cache:

@Immutable 
public final class TopicListCacheKey { 

    private final UUID[] uuids; 

    public TopicListCacheKey(TopicList... topicLists) { 
     uuids = new UUID[topicLists.length]; 
     for (int i = 0; i < uuids.length; i++) { 
      uuids[i] = topicLists[i].getUuid(); 
     } 
    } 

    @Override 
    public int hashCode() { 
     return Arrays.hashCode(uuids); 
    } 

    @Override 
    public boolean equals(Object other) { 
     if (other == this) return true; 
     if (other instanceof TopicListCacheKey) 
      return Arrays.equals(uuids, ((TopicListCacheKey) other).uuids); 
     return false; 
    } 
} 

I capire che ci sono 2^128 UUID differenti e avrò probabilmente al massimo circa 1.000.000 ListaToken oggetti attivo nell'applicazione in qualsiasi momento. Dato questo, e il fatto che gli UUID siano usati in modo combinatorio nelle chiavi della cache, sembra che le probabilità che questo produca il risultato sbagliato sono estremamente piccole. Tuttavia, mi sento a disagio ad andare avanti con esso in quanto sembra solo 'sporco'. Ci sono dei motivi per cui non dovrei usare questo sistema? I costi delle prestazioni di SecureRandom utilizzati da UUID.randomUUID() superano i guadagni (soprattutto perché mi aspetto che più thread lo facciano allo stesso tempo)? Le collisioni saranno più probabili di quanto penso? Fondamentalmente, c'è qualcosa di sbagliato nel farlo in questo modo ??

Grazie.

+0

Perché stai implementando gli uguali in primo luogo? Se non ne hai bisogno (e stai cercando di sostituirlo con un UUID che suggerisci di non farlo), non sovrascrivere equals/hashcode. Se lo si desidera è necessario assicurarsi che lo stesso elenco di token esegua la mappatura allo stesso uuid ogni volta. –

+1

In questo modo si potrebbe interrompere il contratto generale su ['List.equals()'] (http://docs.oracle.com/javase/7/docs/api/java/util/List.html#equals (java.lang .Oggetto)), è quello che vuoi? Anche se equals è costoso, usa 'hashCode' prima negli uguali e poi passa agli equivalenti reali se sono gli stessi. –

risposta

0

SecureRandom non ti darà alcuna spinta, è solo "più" casuale di un normale Random. La possibilità di una collisione è qualcosa nell'ordine del numero al quadrato diviso per il totale possibile di UUID, quindi un numero molto piccolo. Tuttavia, non farei affidamento sul fatto che il numero sia sempre unico. Potresti provare questo, ma sarebbe meglio controllare e assicurarsi che il numero non sia già incluso da qualche altra parte nell'elenco hashcode. Altrimenti potresti trovarti in problemi molto strani ...

3

Quello che stai provando è molto complicato e richiede un'analisi dettagliata. Quindi è necessario controllare le domande sottostanti prima di decidere su qualsiasi approccio.

Queste operazioni sono costosi, e c'è una buona probabilità che la stessa operazione (cioè gli stessi input) viene eseguita più volte

1) Quando si dice "Stessa input" in quanto sopra linea, cosa intendi esattamente? Questo significa, esatto stesso oggetto, cioè un oggetto riferito attraverso diversi riferimenti (stessa posizione di memoria) o significa oggetti separati dal punto di vista della memoria ma che hanno logicamente gli stessi dati ??

Qui se l'oggetto è lo stesso, vale a dire la stessa posizione di memoria, quindi il confronto == andrebbe bene. Per questo devi mantenere il riferimento all'oggetto come chiave nella cache.

Ma se è il secondo caso, ad es.oggetti separati dalla memoria ma logicamente uguali, quindi non credo che l'UUID ti aiuterà. Perché devi assicurarti che questi 2 oggetti separati ottengano lo stesso UUID. Questo non sarà molto facile dato che comunque devi passare interi dati TokenList per assicurarti che questo

2) Usare hashcode nella cache, è sicuro? Suggerisco di non usare hashcode come chiave perché anche se 2 oggetti sono diversi, potrebbero avere lo stesso codice hash. Quindi la tua logica potrebbe andare terribilmente storta.

Quindi ottenere risposte per queste domande chiarire prima & solo quindi pensare all'approccio.

+0

Eventuali TokenList di "prima generazione" che sono logicamente uguali saranno uguali sotto '=='. Le TokenList di "seconda generazione" - gli output delle operazioni che utilizzano la prima generazione - saranno oggetti diversi anche se logicamente identici, a meno che non utilizzi la cache per restituire lo stesso oggetto. Così ho potuto memorizzare nella cache l'hashCode e fare affidamento su == per i confronti - tutto molto veloce. Grazie! –

Problemi correlati