CODEWITHSUNDEEP
c#
Tim
Tim

Reputation: 3803

C# Dictionary not adding new item at last index after remove the same key?

I just discover this behavior when using Dictionary from C#, after I remove a key from the dictionary, and then I would like to add using the same key, but the new added key is not at the last index of the dictionary?

Dictionary<string, byte> test = new Dictionary<string, byte>();

test.Add("c", 1);  // [{"c", 1}]
test.Add("b", 2);  // [{"c", 1}, {"b", 2}]
test.Add("a", 3);  // [{"c", 1}, {"b", 2}, {"a", 3}]
test.Remove("b");  // [{"c", 1}, {"a", 3}]

test.Add("b", 2);  // [{"c", 1}, {"b", 2}, {"a", 3}] <= why this happen?
                   // [{"c", 1}, {"a", 3}, {"b", 2}] and not this?

May I know why? and how can I make the newly added key to the last index of dictionary?

Upvotes: 1

Views: 4586

Answers (4)

dba
dba

Reputation: 1195

Late to the party, but as of adding to the end... Answers suggest the "garbage" on manipulating the dict. To get rid of the garbage, create a new dict after removing elements

Dictionary<string, byte> test = new Dictionary<string, byte>();

test.Add("c", 1);
test.Add("b", 2);
test.Add("a", 3);
test.Remove("b");

var test2 = new Dictionary<string, byte>(test);

test2.Add("b", 2);

add new items to test2 and they appear at the end...

Upvotes: -1

Ann
Ann

Reputation: 41

We can achieve this by creating a new dictionary and add the values to it.

// you can run this code here: https://www.programiz.com/csharp-programming/online-compiler/
// Online C# Editor for free
// Write, Edit and Run your C# code using C# Online Compiler

using System;
using System.Collections.Generic;

public class HelloWorld
{
    public static void Main(string[] args)
    {
        
        var cities = new Dictionary<string, string>(){
            {"UK", "London, Manchester, Birmingham"},
            {"USA", "Chicago, New York, Washington"},
            {"India", "Mumbai, New Delhi, Pune"}
        };
        
        //creating a new dictionary
        var newVersion = new Dictionary<string, string>();
        
        //print all the values exist in the cities
        Console.WriteLine("..............Initial values in cities \n");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
        }
        
        cities.Remove("UK"); // removes UK 
        
        //print all the values in the cities after removing "UK" and also add each value to the new dictionary
        Console.WriteLine("\n ..............Values in cities after removal");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
            newVersion[kvp.Key] = kvp.Value;
        }
        
        //add new key value pairs to cities and new dictionary
        cities["test"] = "test1";
        cities["test2"] = "test2";
        newVersion["test"] = "test1";
        newVersion["test2"] = "test2";
        
        //print values in the old dictionary
        Console.WriteLine("\n..............Values in cities after adding new test values");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
        }
        
        //print values in the new dictionary. New dictionary will add the values at the end
        Console.WriteLine("\n..............New version");
        foreach (var kvp in newVersion) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
            
        }
    }
}

**Sample output:**
..............**Initial values in cities**    
Key = UK, Value = London, Manchester, Birmingham
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune

 ..............**Values in cities after removal**
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune

..............**Values in cities after adding new test values**
Key = test, Value = test1
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
Key = test2, Value = test2

..............**New version**
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
Key = test, Value = test1
Key = test2, Value = test2

Upvotes: 1

Fede
Fede

Reputation: 4016

You can see the implementation code of the Dictionary class over here

As you can see, the implementation uses a technique that tracks a list of free positions in the entries array, and when a new value is added, the free entries are used first.

There is a non generic ListDictionary class in the framework, that I believe adds new items always at the end of the list. Keep in mind that access to that IDictionary implementation will typically be O(n) in average, in contrast to the O(1) in average to the generic Dictionary you are currently using.

Upvotes: 1

atlaste
atlaste

Reputation: 31146

Dictionary's are hash tables. If you look at the definition of a hash table, you'll notice that hash tables are unordered.

It's been some time since I looked at the specific details of the .NET dictionary implementation, so there might be some errors in the rest of my story -- but this is what I remember from the details:

There are a lot of different schemes for implementing hash tables, but the one that .NET uses works like the 'Open Addressing' algorithm with some variations. Basically new items are added at a list (at the end) and the hash table (a static array) adds pointers in this list. That's why it actually seems to preserve the order.

At some point the data will become filled with 'garbage', due to modifications or growth. At that point, the implementation will do a rehash. If I recall correctly, that is also the point at which it will check if there are too many collisions -- and if that's the case, it'll use a random prime to multiply all hash values with (thereby reducing the number of collisions). It's quite elegant really.

Since the open addressing scheme points to elements in a list, order in the list is not important. When you enumerate a dictionary, you basically look at this list.

You might wonder why it's not enumerating the array of hash codes instead. Well, hash tables are normally over-allocated, and data is stored in another list anyways. That simply means that this alternative would be far less efficient. If you would enumerate the hash table, you would also probably get a more consistent result - but because of the collisions still wouldn't get a completely consistent result. (e.g. if A and B are on the same hash code, the order of insertion would decide if A follows B or visa versa).

If you're looking for algorithms like 'set union' that require a consistent ordering, I suggest using containers like SortedDictionary instead.

Upvotes: 2

Related Questions