Domanda Collezioni Java che mantengono l'ordine di inserimento


Perché alcune strutture di raccolta dati non mantengono l'ordine di inserimento? Qual è la cosa speciale raggiunta rispetto al mantenimento dell'ordine di inserimento? Guadagniamo qualcosa se non manteniamo l'ordine?


44
2017-09-12 08:02


origine


risposte:


Prestazione. Se si desidera l'ordine di inserimento originale, esistono le classi LinkedXXX, che mantengono un elenco collegato aggiuntivo nell'ordine di inserimento. La maggior parte delle volte non ti interessa, quindi usi un HashXXX o vuoi un ordine naturale, quindi usi TreeXXX. In entrambi i casi, perché dovresti pagare il costo aggiuntivo dell'elenco collegato?


73
2017-09-12 08:06



Le raccolte non mantengono l'ordine di inserimento. Alcuni solo per default aggiungono un nuovo valore alla fine. Mantenere l'ordine di inserimento è utile solo se si assegna la priorità agli oggetti o se lo si usa per ordinare gli oggetti in qualche modo.

Per quanto riguarda il motivo per cui alcune collezioni la mantengono per impostazione predefinita e altre no, ciò è causato principalmente dall'implementazione e solo a volte parte della definizione delle collezioni.

  • elenchi mantenere l'ordine di inserimento semplicemente aggiungendo una nuova voce alla fine o l'inizio è l'implementazione più rapida del metodo add (Object).

  • Imposta Le implementazioni HashSet e TreeSet non mantengono l'ordine di inserimento poiché gli oggetti vengono ordinati per una rapida ricerca e il mantenimento dell'ordine di inserimento richiede memoria aggiuntiva. Ciò si traduce in un miglioramento delle prestazioni poiché l'ordine di inserimento non è quasi mai interessante per gli insiemi.

  • ArrayDeque un deque può essere usato per semplici que e stack in modo da avere il comportamento "first in first out" o "first in last out", entrambi richiedono che ArrayDeque mantenga l'ordine di inserimento. In questo caso l'ordine di inserzione viene mantenuto come parte centrale del contratto di classi.


16
2017-09-12 19:19



  • L'ordine di inserzione è intrinsecamente non mantenuto in tavoli di hash - è proprio come funzionano (leggi l'articolo collegato per capire i dettagli). È possibile aggiungere la logica per mantenere l'ordine di inserimento (come nel file LinkedHashMap), ma richiede più codice e in fase di esecuzione più memoria e più tempo. La perdita di prestazioni di solito non è significativa, ma può esserlo.
  • Per TreeSet/Map, la ragione principale per usarli è l'ordine di iterazione naturale e altre funzionalità aggiunte nel SortedSet/Map interfaccia.

7
2017-09-12 08:26



Dipende da ciò di cui hai bisogno per attuare l'implementazione. L'ordine di inserimento di solito non è interessante, quindi non è necessario mantenerlo in modo da poter riorganizzare per ottenere prestazioni migliori.

Per Maps è solitamente utilizzato HashMap e TreeMap. Usando i codici hash, le voci possono essere inserite in piccoli gruppi facili da cercare. La TreeMap mantiene un ordine ordinato delle voci inserite al costo di una ricerca più lenta, ma più facile da ordinare rispetto a una HashMap.


2
2017-09-12 08:22



Quando si utilizza un HashSet (o una HashMap) i dati vengono memorizzati in "bucket" in base all'hash del proprio oggetto. In questo modo è più facile accedere ai tuoi dati perché non devi cercare questi particolari dati nell'intero Set, devi solo cercare nel bucket giusto.

In questo modo puoi aumentare le prestazioni su punti specifici.

Ogni implementazione della Collezione ha la sua particolarità per renderla migliore da utilizzare in determinate condizioni. Ognuna di queste particolarità ha un costo. Quindi, se non ne hai davvero bisogno (ad esempio l'ordine di inserimento) è meglio utilizzare un'implementazione che non lo offre e si adatta meglio alle tue esigenze.


2
2017-09-12 08:23



Perché è necessario mantenere l'ordine di inserimento? Se usi HashMap, puoi ottenere la voce da key. Ciò non significa che non fornisce classi che fanno ciò che vuoi.


0
2017-09-12 10:15



C'è una sezione nell'O'Reilly Java Cookbook intitolata "Evitare l'impulso di ordinare" La domanda che dovresti porre è in realtà l'opposto della tua domanda originale ... "Guadagniamo qualcosa ordinando?" Ci vuole un grande sforzo per ordinare e mantenere quell'ordine. Certo, l'ordinamento è semplice ma di solito non è scalabile nella maggior parte dei programmi. Se dovrai gestire migliaia o decine di migliaia di richieste (insrt, del, get, ecc.) Al secondo, se non stai utilizzando una struttura dati ordinata o non ordinata, il problema sarà serio.


0
2017-09-13 02:23



alcune raccolte non mantengono l'ordine a causa di, calcolano il codice hash del contenuto e lo memorizzano di conseguenza nel bucket appropriato.


0
2018-01-28 10:50