Collezioni Java che mantengono l'ordine di inserzione

Question

Perché alcune strutture di dati di raccolta 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?

Answer 1

Prestazioni. 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?

Answer 2

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

Per Maps è solitamente HashMap e TreeMap utilizzati. 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.

Answer 3

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 è possibile aumentare le prestazioni su punti specifici.

Ogni implementazione di Collection ha la sua particolarità di renderla migliore da utilizzare in una determinata condizione. 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.

Answer 4

non posso citare un riferimento, ma in base alla progettazione dei List e Set implementazioni dell'interfaccia Collection sono fondamentalmente estensibili Array s. Come Collections per impostazione predefinita metodi dinamici aggiungi e rimuovi elementi in qualsiasi punto, che non è possibile - Array - l'ordine di inserimento potrebbe non essere conservato. Quindi, poiché ci sono più metodi per la manipolazione del contenuto, c'è bisogno di implementazioni speciali che mantengano l'ordine.

Un altro punto è la prestazione, in quanto il Collection più efficace potrebbe non essere quello, che conserva il suo ordine di inserimento. Tuttavia non sono sicuro, in che modo esattamente Collections gestiscono i loro contenuti per l'aumento delle prestazioni.

Così, in breve, i due principali motivi che mi viene in mente il motivo per cui ci sono fine-preservare Collection implementazioni sono:

1. architettura Classe
2. prestazioni

Answer 5

• L'ordine di inserimento è intrinsecamente non mantenuto in hash tables - è proprio come funzionano (leggi l'articolo collegato per capire i dettagli). È possibile aggiungere la logica per mantenere l'ordine di inserimento (come nel numero 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, il motivo principale per utilizzarli è l'ordine di iterazione naturale e altre funzionalità aggiunte nell'interfaccia SortedSet/Map.

Answer 6

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

Answer 7

Le raccolte non conservano 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 raccolte lo mantengono per impostazione predefinita e altre no, ciò è causato principalmente dall'implementazione e solo a volte parte della definizione delle raccolte.

• liste mantenere l'ordine di inserimento come solo l'aggiunta di una nuova voce alla fine o l'inizio è il più veloce implementazione del metodo add (Object).

• insiemi Le implementazioni HashSet e TreeSet non mantengono ordine di inserimento degli oggetti sono ordinati per la ricerca veloce e ordine di inserimento mantenimento richiederebbe 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ò utilizzato per la semplice que e stack in modo che si desidera avere '' first in first out '' o '' prima in last out '' il comportamento, sia richiedono che l'ArrayDeque mantiene l'ordine di inserimento. In questo caso l'ordine di inserzione viene mantenuto come parte centrale del contratto di classi.

Answer 8

C'è una sezione nella O'Reilly Cookbook Java chiamato "Evitare la voglia di ordinare" La domanda che dovremmo porci è in realtà l'opposto della vostra domanda originale ... "Dobbiamo ottenere qualcosa di classificare? " 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.

Answer 9

Okay ... quindi questi post sono vecchi rispetto a ora, ma è necessario l'ordine di inserimento in base alle esigenze o ai requisiti dell'applicazione, quindi è sufficiente utilizzare il giusto tipo di raccolta. Per la maggior parte, non è necessario, ma in una situazione in cui è necessario utilizzare gli oggetti nell'ordine in cui sono stati memorizzati, vedo un bisogno preciso. Penso che l'ordine importi quando crei, ad esempio, una procedura guidata o un motore di flusso o qualcosa di quella natura in cui devi passare da uno stato all'altro o qualcosa del genere. In questo senso puoi leggere le cose dalla lista senza che tenga traccia di ciò che ti serve dopo o attraversi una lista per trovare quello che vuoi. Aiuta le prestazioni in questo senso. È importante o altrimenti queste raccolte non avrebbero molto senso.

Answer 10

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