Perché sono voci in aggiunta ordine .Net Dizionario?

Question

Ho appena visto questo comportamento e mi sono un po ' sorpreso da esso...

Se posso aggiungere 3 o 4 elementi di un Dizionario, e poi fare un "Per Ogni" per ottenere tutte le chiavi, appaiono nello stesso ordine ho aggiunto a loro.

La ragione per questo mi sorprende è che un Dizionario è supposto per essere una HashTable internamente, quindi mi aspettavo cose a venire fuori in QUALSIASI ordine (ordinati dall'hash della chiave, giusto?)

Quello che mi manca qui?È questo un comportamento che posso contare?

EDIT:OK, pensavo già di molti dei motivi per cui questo potrebbe accadere (come l'elenco distinto per voci, se questa è una coincidenza, ecc).La mia domanda è, qualcuno sapere come questo funziona davvero?

Answer 1

Se si utilizza .NET Reflector nelle librerie di classi 3.5, è possibile notare che l'implementazione di Dictionary memorizza effettivamente gli elementi in un array (che viene ridimensionato in base alle esigenze) e hash gli indici in tale array. Quando si ottengono le chiavi, ignora completamente la tabella hash e scorre sull'array di elementi. Per questo motivo, vedrai il comportamento che hai descritto poiché vengono aggiunti nuovi elementi alla fine dell'array. Sembra che tu faccia quanto segue:

add 1
add 2
add 3
add 4
remove 2
add 5

otterrai 1 5 3 4 perché riutilizza slot vuoti.

È importante notare che, come molti altri, non è possibile contare su questo comportamento nelle versioni future (o passate). Se desideri che il tuo dizionario venga ordinato, esiste una classe SortedDictionary per questo scopo.

Answer 2

Un dizionario recupera elementi in hash ordine.Il fatto che sono arrivati in ordine di inserzione è stata una totale coincidenza.

La documentazione di MSDN dice:

L'ordine delle chiavi in KeyCollection non è specificato, ma è lo stesso ordine, con relativi valori in ValueCollection restituiti dai Valori di proprietà.

Answer 3

Non puoi contare su questo comportamento, ma non è sorprendente.

Considera come implementare l'iterazione chiave per una semplice tabella hash. Dovresti iterare su tutti i bucket hash, indipendentemente dal fatto che contenessero o meno qualcosa. Ottenere un piccolo set di dati da una grande hashtable potrebbe essere inefficiente.

Pertanto potrebbe essere una buona ottimizzazione mantenere un elenco separato e duplicato di chiavi. Utilizzando un elenco a doppio collegamento si ottiene comunque l'inserimento / eliminazione a tempo costante. (Manterrai un puntatore dal bucket hashtable a questo elenco.) In questo modo iterare l'elenco delle chiavi dipende solo dal numero di voci, non dal numero di bucket.

Answer 4

Penso che questo provenga dal vecchio .NET 1.1 volte in cui avevi due tipi di dizionari " ListDictionary " e " HybridDictionary " ;. ListDictionary era un dizionario implementato internamente come elenco ordinato ed è stato raccomandato per " piccoli gruppi di voci " ;. Quindi avevi HybridDictionary , che inizialmente era organizzato internamente come un elenco, ma se diventasse più grande di una soglia configurabile diventerebbe una tabella hash. Ciò è stato fatto perché i dizionari basati su hash storicamente appropriati erano considerati costosi. Ora un giorno che non ha molto senso, ma suppongo che .NET abbia appena basato la sua nuova classe generica del dizionario sul vecchio HybridDictionary.

Nota : comunque, come già sottolineato da qualcun altro, non dovresti mai mai fare affidamento sull'ordine del dizionario per nulla

Answer 5

Una citazione da MSDN :

  

L'ordine delle chiavi in   Dizionario & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;). KeyCollection è   non specificato, ma è lo stesso ordine   come valori associati in   Dizionario & Lt; (Of & Lt; (TKey,   TValue gt &;) Gt &;.) ValueCollection   restituito dal dizionario < (Of < (TKey,   TValue & Gt;) & Gt;). Proprietà dei valori.

Answer 6

Con quali chiavi hai aggiunto nel test e in quale ordine?

Answer 7

Le voci potrebbero essere tutte nello stesso bucket hash nel dizionario. Ogni bucket è probabilmente un elenco di voci nel bucket. Questo spiegherebbe le voci che ritornano in ordine.

Answer 8

Da quello che so questo non dovrebbe essere un comportamento su cui fare affidamento. Per verificarlo rapidamente usa gli stessi elementi e cambia l'ordine in cui li aggiungi al dizionario. Vedrai se li riavrai nell'ordine in cui sono stati aggiunti, o è stata solo una coincidenza.

Answer 9

Fino a una certa dimensione dell'elenco è più economico controllare ogni voce invece dell'hash. Questo è probabilmente ciò che sta accadendo.

Aggiungi 100 o 1000 articoli e verifica se sono ancora nello stesso ordine.

Answer 10

Odio questo tipo di " in base alla progettazione " funzionalità. Penso che quando dai alla tua classe un nome generico come & Quot; Dizionario & Quot ;, dovrebbe anche comportarsi & Quot; come generalmente previsto & Quot ;. Ad esempio std :: map mantiene sempre i suoi valori-chiave ordinati.

Modifica: apparentemente la soluzione è usare SortedDictionary, che si comporta in modo simile a std :: map.

Answer 11

La domanda e molte delle risposte sembrano fraintendere lo scopo di una tabella o di un dizionario. Queste strutture di dati non hanno comportamenti specifici rispetto all'enumerazione dei valori (o di fatto le chiavi) degli elementi contenuti nella struttura di dati.

Lo scopo di un dizionario o di una tabella hash è quello di essere in grado di cercare in modo efficiente un valore specifico dato una chiave nota. L'implementazione interna di qualsiasi dizionario o hashtable dovrebbe fornire questa efficienza nelle ricerche ma non è necessario fornire alcun comportamento specifico rispetto alle enumerazioni o alle quotazioni &; Per ciascuna & Quot; digitare iterazioni sui valori o sulle chiavi.

In breve, la struttura interna dei dati può archiviare ed enumerare questi valori in qualsiasi modo desideri, incluso l'ordine in cui sono stati inseriti.