HashSet.contains performance

Sono tentato di pensare che il metodo HashSet.contains (Object) funzioni in tempo costante. Semplicemente ottiene il codice hash di un object e poi lo cerca in una tabella hash.

In primo luogo, qualcuno potrebbe confermare per favore se è vero?

In secondo luogo, se è vero, esiste il rischio di collisioni, in cui due oggetti potrebbero avere lo stesso codice hash e quindi HashSet pensa di avere entrambi quando ne ha uno solo?

Funziona in O(1) tempo previsto, come qualsiasi tabella hash (supponendo che la funzione di hash sia decente). È supportato da una HashMap cui la chiave è l’object.

Due oggetti potrebbero avere lo stesso codice hash, ma HashSet non penserebbe che siano identici, a meno che il metodo equals per questi oggetti non sia lo stesso (cioè restituisce true).

Il metodo contains chiamate (indirettamente) getEntry di HashMap , dove key è l’ Object per il quale si desidera sapere se si trova in HashSet .

Come puoi vedere qui sotto, due oggetti possono essere memorizzati in HashMap / HashSet anche se la loro chiave è mappata allo stesso valore dalla funzione hash. Il metodo esegue iterazioni su tutte le chiavi che hanno lo stesso valore di hash ed esegue equals su ciascuna di esse per trovare la chiave corrispondente.

 final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } 

Le prestazioni nel caso peggiore di contiene saranno O (log n) per Java 8 e O (n) per Java 7, ma la media case si avvicina a O (1). Questo perché hashset è supportato da una hashmap e quindi ha la stessa efficienza della ricerca hashmap (ad esempio, HashMap.get (…)). Il mapping effettivo in una hashmap è un tempo costante (O (1)), ma la necessità di gestire le collisioni porta il costo al log n. Cioè, più elementi che hash allo stesso indice di matrice devono essere memorizzati in una infrastruttura secondaria (aka bucket), ed è questo bucket che determina le prestazioni nel caso peggiore. In Java, la gestione della colatura hahsmap è implementata utilizzando un albero auto-bilanciato.

Gli alberi auto bilanciati garantiscono O (log n) per tutte le operazioni, quindi l’inserimento e la ricerca in hashmap (e hashset) ha un costo totale di O (1) + O (log n) = O (log n). L’uso di un albero auto-bilanciato per la gestione delle collisioni è stato introdotto in Java 8 come miglioramento rispetto al concatenamento (usato fino a java 7), che utilizza una lista collegata e ha il caso peggiore di O (n) per la ricerca e l’inserimento (come ha bisogno di attraversare la lista). Si noti che il concatenamento avrebbe tempo costante per l’inserimento (in contrapposizione alla ricerca), poiché gli elementi possono essere aggiunti a un elenco collegato in O (1), ma la proprietà dell’insieme (nessun duplicato) viene imposta nell’elenco collegato nel caso di hashmap, e quindi ha bisogno di attraversare la lista collegata anche nel caso dell’inserzione per assicurare che l’elemento non esista già nella lista / bucket, e finiamo con O (n) sia per l’inserimento che per la ricerca.

Riferimenti:

Questa class implementa l’interfaccia Set, supportata da una tabella hash (in realtà un’istanza di HashMap). https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

I bucket contenenti un numero elevato di chiavi collidenti memorizzeranno le loro voci in un albero bilanciato anziché in un elenco collegato dopo che è stata raggiunta una determinata soglia. ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )

Un consiglio è l’utilizzo di HashSet.get(object) che è nullo o no invece di HashSet.contain(object) , poiché HashSet.get(object) è più veloce.