Truly Immutable Dictionary in .NET_问答_开发者

Good morning, afternoon or ni开发者_运维知识库ght,

Still building on my question about immutable dictionaries in .NET, I came up with the following question: while if then TKey and TValue are value types you can make a dictionary truly immutable, in the sense that neither its inner structure nor the values themselves can change, if those parameters are reference types keys and values can easily be changed, thus changing the dictionary itself. Am I right?

Thank you very much.

if then TKey and TValue are value types you can make a dictionary truly immutable, in the sense that neither its inner structure nor the values themselves can change, if those parameters are reference types keys and values can easily be changed, thus changing the dictionary itself. Am I right?

Not exactly. You've identified a real problem but your characterization of it is not fully thought through.

First off, I note that yes, a value type stuck in an immutable dictionary is immutable, even if it is a mutable value type. Why? Because value types are only mutated by mutating the variable which contains them. If your dictionary does not expose the variables it uses to store the value types then there is no way for those variables to be changed.

However, even if a value type is itself immutable an immutable value type can contain a reference to a mutable reference type, and now we've got the same problem. Restricting the dictionary to value types only pushes the problem off a level, it does not solve it! What you really need to guarantee "deep" immutability is a dictionary of blittable value types. By "blittable", I mean a value type with no fields of reference type. (So-called because you can serialize one of these to storage by "blitting" the bits straight out to disk.)

Unfortunately there is no constraint in the generic type system to constrain to blittable value types.

Let's now consider the general problem of mutable reference types in an immutable dictionary, whether those reference types are there directly or via a field of a value type. What can go wrong if a reference type is mutated out-of-band while it is in an immutable dictionary?

Well, the first thing that comes to mind is that an immutable dictionary should give the same answer twice to the same question twice, and now this is no longer the case. If you say "customers[name].Address" you'd expect to get the same answer twice, but if the customer is a reference type that can mutate, you'll get a potentially different answer. That might or might not be desirable. (And note that the dictionary is giving the same answer twice: it's giving the same reference to the customer object. It is actually the customer object that is not giving the same answer twice.)

Assuming you don't try to memoize answers to questions that can change, this is usually not a big problem.

A bigger problem is when an object that is in a hash table as a key mutates, thereby changing its hash value and "losing" the object in the table.

If that happens then someone is not keeping inside the guidelines. The guidelines are (1) reference types should if possible not base their hash codes (and equality) upon data that can mutate, and (2) an object being used as a key in a hash table should not be mutated.

Structs are value types and are not necessarily immutable - so the answer is no. You can design immutable types (make all fields and properties readonly). However there is no type constraint available (like where TKey : class) which would allow you to enforce it.

Update: An example:

class Bar { public int I; }
struct Foo { public Bar B; }

var b = new Bar();
var f = new Foo { B = b; }

dict[key] = f;
b.I++;

A bit constructed I admit.

Take a look at the new BCL Immutable Collections: http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx

This is still a preview release but it contains the following types:

ImmutableStack<T>
ImmutableQueue<T>
ImmutableList<T>
ImmutableHashSet<T>
ImmutableSortedSet<T>
ImmutableDictionary<K, V>
ImmutableSortedDictionary<K, V>

I wish the next version of C# will include keywords to specify immutability constraints at the class level (similarly to what is suggested here), and a way to clone objects more easily, like what can be done in F# with the keyword with :

var o1 = new CustomObject { Field1 = 0, Field2 = 3 }
var o2 = o1 with { Field1 = 1}

Here's a very quick design, probably wont compile straight off but hopefully will give you some ideas...

[Immutable]
class ImmutableDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
    public ImmutableDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysValues)
    {
        // Ensure TKey is immutable...
        if (typeof(TKey).GetCustomAttribute(typeof(ImmutableAttribute), false).Length == 0)
            throw new InvalidOperationException(String.Format("Type '{0}' must be immutable.", typeof(TKey).AssemblyQualifiedName);

        // Ensure TValue is immutable...
        if (typeof(TValue).GetCustomAttribute(typeof(ImmutableAttribute), false).Length == 0)
            throw new InvalidOperationException(String.Format("Type '{0}' must be immutable.", typeof(TValue).AssemblyQualifiedName);

        foreach(var keyValue in keysValues)
            base.Add(keyValue.Key, keyValue.Value);
    }

    public new void Add(TKey key, TValue value)
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public new void Clear()
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public new void Remove(TKey key)
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public TValue this[TKey key]
    {
        get { return base[key]; }
        set
        {
            throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
        }
    }
}

take a look at this: http://ayende.com/blog/164739/immutable-collections-performance by the way be completely careful when using ImmutableDictionary

To understand what's going on, drop down to a type simpler than a dictionary: a List<T>. If one creates a List<T>, throws some items in it, then creates passes it to the constructor of ReadOnlyCollection<T> and destroys all references to that list other than the one contained within the ReadOnlyCollection<T>, then that list will be immutable. Its state will never change, regardless of whether T mutable or immutable, class or struct. Anyone who would regard such a list as mutable if T is a mutable class type fails is mistakenly regarding the list as holding objects. It doesn't.

If T is a class type, a List<T> does not hold objects--it identifies them. If a List<int[]> is made immutable as described above, after five int array references have been added to it, then as long as it exists it will always hold references to those same five arrays. The contents of the arrays may change, but the properties of the objects referred to by a List<T> form no part of the list's state.

The state of a Dictionary<TKey,TValue> is a little harder to define than the state of a List<T>, especially if one considers the possibilities of muddled states caused by wonky GetHashCode() implementations, but the same principles apply. If TKey is a class type, the only aspects of a TKey instance which form part of the dictionary's state are the value returned by GetHashCode, and the equivalence class implied by its Equals method; both of those things are supposed to be immutable. No legitimately-mutable aspect of a TKey or TValue class object should be regarded as part of the state of a TDictionary<TKey,TValue>.