HashSet La struttura dati C# HashSet è stata introdotta in .NET Framework 3.5. Un elenco completo dei membri implementati è disponibile nella pagina HashSet MSDN.Definire: Che cos'è un HashSet?
- Dove viene utilizzato?
- Perché dovresti usarlo?
HashSet La struttura dati C# HashSet è stata introdotta in .NET Framework 3.5. Un elenco completo dei membri implementati è disponibile nella pagina HashSet MSDN.Definire: Che cos'è un HashSet?
Un HashSet
detiene una serie di oggetti, ma in un modo che consente di determinare facilmente e rapidamente se un oggetto è già nel set o no. Lo fa gestendo internamente un array e memorizzando l'oggetto utilizzando un indice calcolato dall'hashcode dell'oggetto. Take a look here
HashSet
è una raccolta non ordinata contenente elementi unici. Ha le operazioni di raccolta standard Aggiungi, Rimuovi, Contiene, ma poiché utilizza un'implementazione basata su hash, queste operazioni sono O (1). (Al contrario alla lista per esempio, che è O (n) per Contiene e rimuova.) HashSet
prevede inoltre impostare operazioni standard come unione, intersezione e simmetrica differenza. Take a look here
Ci sono diverse implementazioni di Set. Alcuni rendono le operazioni di inserimento e ricerca super veloci dagli elementi di hashing. Tuttavia, ciò significa che l'ordine in cui sono stati aggiunti gli elementi è stato perso. Altre implementazioni preservano l'ordine aggiunto al costo di tempi di esecuzione più lenti.
Il HashSet
classe C# vale per il primo approccio, pertanto non preservare l'ordine degli elementi. È molto più veloce di un normale List
. Alcuni benchmark di base hanno mostrato che HashSet è decentemente più veloce quando si tratta di tipi primari (int, double, bool, ecc.). È molto più veloce quando si lavora con oggetti di classe. Quindi quel punto è che HashSet è veloce.
L'unica presa di HashSet
è che non vi è alcun accesso da parte degli indici. Per accedere agli elementi è possibile utilizzare un enumeratore o utilizzare la funzione incorporata per convertire HashSet
in List
e iterare attraverso quello. Take a look here
A HashSet
ha una struttura interna (cancelletto), in cui gli articoli possono essere ricercati e identificati rapidamente. Il rovescio della medaglia è che iterando attraverso un HashSet
(o ottenendo un elemento per indice) è piuttosto lento.
Quindi, perché qualcuno dovrebbe essere in grado di sapere se una voce esiste già in un set?
Una situazione in cui è utile un HashSet
consiste nell'ottenere valori distinti da un elenco in cui possono esistere duplicati. Una volta aggiunto un articolo allo HashSet
, è possibile determinare rapidamente se l'elemento esiste (operatore Contains
).
Altri vantaggi del HashSet
sono le operazioni di impostazione: IntersectWith
, IsSubsetOf
, IsSupersetOf
, Overlaps
, SymmetricExceptWith
, UnionWith
.
Se si ha familiarità con lo object constraint language, si identificheranno queste operazioni. Vedrai anche che è un passo avanti verso un'implementazione di UML eseguibile.
Re: lato negativo. No, iterare attraverso un HashSet è perfettamente veloce. In secondo luogo, non è possibile ottenere un oggetto per indice. In effetti, gli elementi sono archiviati senza ordine. –
@Nigel Touch. L'iterazione è veloce se non ti interessa l'indice (ordine in cui sono stati aggiunti). Tuttavia, se si è preoccupati dell'indice, l'indice deve essere memorizzato con ciascuna chiave hash e quindi può essere piuttosto lento perché l'elenco deve essere cercato in modo esaustivo per recuperare l'elemento corretto. Questo comportamento è molto diverso da un elenco in cui gli elementi sono indicizzati dall'ordine in cui vengono aggiunti. –
Ha senso perché sarebbe veloce, perché non ci sono due hash uguali. Abilitare la query per sfruttare un approccio di "cortocircuito", escludendo rapidamente determinati criteri. –
Dal punto di vista dell'applicazione, se è necessario solo evitare duplicati, è necessario cercare HashSet
poiché Cerca, Inserisci e Rimuovi complexities are O(1) - constant. Ciò significa che non importa quanti elementi HashSet
ha la stessa quantità di tempo per verificare se c'è un tale elemento o meno, in più, dato che anche tu stai inserendo elementi in O (1) lo rende perfetto per questo genere di cose.
semplicemente detto e senza rivelare i segreti della cucina: un set, in generale, è una collezione che non contiene elementi duplicati, e i cui elementi sono in nessun ordine particolare. Quindi, A HashSet<T>
è simile a un generico List<T>
, ma è ottimizzato per ricerche veloci (tramite hashtables, come suggerisce il nome) al costo di perdere l'ordine.
http://en.wikipedia.org/wiki/Set_(computer_science) –
possibile duplicato del [Quando devo utilizzare il tipo HashSet?] (Http://stackoverflow.com/questions/1247442/when-should -i-use-the-hashsett-type) –
nawfal
Utilizza una tabella hash internamente. se hai una buona implementazione di hashtable (ad esempio Dictionary) puoi implementare HashSet da solo facilmente. –