C#中的不可变数据类型介绍（不可变对象、不可变集合）

不可变对象

不可变(immutable)： 即对象一旦被创建初始化后，它们的值就不能被改变，之后的每次改变都会产生一个新对象。

var str="mushroomsir";
str.substring(0, 6)

c#中的string是不可变的，substring(0, 6)返回的是一个新字符串值，而原字符串在共享域中是不变的。另外一个stringbuilder是可变的，这也是推荐使用stringbuilder的原因。

var age=18;

当存储值18的内存分配给age变量时，它的内存值也是不可以被修改的。

age=2;

此时会在栈中开辟新值2赋值给age变量，而不能改变18这个内存里的值，int在c#中也是不可变的。

class contact
{
    public string name { get;  set; }
    public string address { get;  set; }
    public contact(string contactname, string contactaddress)
    {
        name = contactname;
        address = contactaddress;              
    }
}
   var mutable = new contact("二毛", "清华");
   mutable.name = "大毛";
   mutable.address = "北大";

我们实例化mutablecontact赋值给mutable，随后我们可以修改mutablecontact对象内部字段值，它已经不是初始后的值，可称为可变(mutable)对象。

可变对象在多线程并发*享，是存在一些问题的。多线程下a线程赋值到 name = "大毛" 这一步，其他的线程有可能读取到的数据就是：

  mutable.name == "大毛";
  mutable.address == "清华";

很明显这样数据完整性就不能保障，也有称数据撕裂。我们把可变对象更改为不可变对象如下：

public class contact2
{
    public string name { get; private set; }
    public string address { get; private set; }
    private contact2(string contactname, string contactaddress)
    {
        name = contactname;
        address = contactaddress;              
    }
    public static contact2 createcontact(string name, string address)
    {
        return new contact2(name, address);
    }
}

使用时只能通过contact2的构造函数来初始化name和address字段。contact2此时即为不可变对象，因为对象本身是个不可变整体。通过使用不可变对象可以不用担心数据完整性，也能保证数据安全性，不会被其他线程修改。

自定义不可变集合

我们去枚举可变集合时，出于线程安全的考虑我们往往需要进行加锁处理，防止该集合在其他线程被修改，而使用不可变集合则能避免这个问题。我们平常使用的数据结构都是采用可变模式来实现的，那怎么实现一个不可变数据结构呢！以栈来示例，具体代码如下：

public interface istack<t> : ienumerable<t>
{
    istack<t> push(t value);
    istack<t> pop();
    t peek();
    bool isempty { get; }
}
public sealed class stack<t> : istack<t>
{
    private sealed class emptystack : istack<t>
    {
        public bool isempty { get { return true; } }
        public t peek() { throw new exception("empty stack"); }
        public istack<t> push(t value) { return new stack<t>(value, this); }
        public istack<t> pop() { throw new exception("empty stack"); }
        public ienumerator<t> getenumerator() { yield break; }
        ienumerator ienumerable.getenumerator() { return this.getenumerator(); }
    }
    private static readonly emptystack empty = new emptystack();
    public static istack<t> empty { get { return empty; } }
    private readonly t head;
    private readonly istack<t> tail;
    private stack(t head, istack<t> tail)
    {
        this.head = head;
        this.tail = tail;
    }
    public bool isempty { get { return false; } }
    public t peek() { return head; }
    public istack<t> pop() { return tail; }
    public istack<t> push(t value) { return new stack<t>(value, this); }
    public ienumerator<t> getenumerator()
    {
        for (istack<t> stack = this; !stack.isempty; stack = stack.pop())
            yield return stack.peek();
    }
    ienumerator ienumerable.getenumerator() { return this.getenumerator(); }
}

1.入栈时会实例化一个新栈对象
2.将新值通过构造函数传入，并存放在新对象head位置，旧栈对象放在在tail位置引用
3.出栈时返回当前栈对象的tail引用的栈对象

使用方法如下：

istack<int> s1 = stack<int>.empty;
istack<int> s2 = s1.push(10);
istack<int> s3 = s2.push(20);
istack<int> s4 = s3.push(30);
istack<int> v3 = s4.pop();
foreach (var item in s4)
{
//dosomething
}

每次push都是一个新对象，旧对象不可修改，这样在枚举集合就不需要担心其他线程修改了。

net提供的不可变集合

不可变队列，不可变列表等数据结构如果都自己实现工作量确实有点大。幸好的是net在4.5版本已经提供了不可变集合的基础类库。 使用nuget安装：

install-package microsoft.bcl.immutable

使用如下，和上面我们自定义的几乎一样：

 immutablestack<int> a1 = immutablestack<int>.empty;
        immutablestack<int> a2 = a1.push(10);
        immutablestack<int> a3 = a2.push(20);
        immutablestack<int> a4 = a3.push(30);
        immutablestack<int> iv3 = a4.pop();

使用net不可变列表集合有一点要注意的是，当我们push值时要重新赋值给原变量才正确，因为push后会生成一个新对象，原a1只是旧值：

   immutablestack<int> a1 = immutablestack<int>.empty;
   a1.push(10); //不正确，a1仍是空值值，push会生成新的栈。
   a1 = a1.push(10); //需要将新栈重新赋值给a1

net提供的常用数据结构

1.immutablestack
2.immutablequeue
3.immutablelist
4.immutablehashset
5.immutablesortedset
6.immutabledictionary<k, v>
7.immutablesorteddictionary<k, v>

不可变集合和可变集合在算法复杂度上的不同：

不可变优点

1.集合共享安全，从不被改变
2.访问集合时，不需要锁集合（线程安全）
3.修改集合不担心旧集合被改变
4.书写更简洁，函数式风格。 var list = immutablelist.empty.add(10).add(20).add(30);
5.保证数据完整性，安全性

不可变对象缺点

不可变本身的优点即是缺点，当每次对象/集合操作都会返回个新值。而旧值依旧会保留一段时间，这会使内存有极大开销，也会给gc造成回收负担，性能也比可变集合差的多。

跟string和stringbuild一样，net提供的不可变集合也增加了批量操作的api，用来避免大量创建对象：

immutablelist<string> immutable = immutablelist<string>.empty;
        //转换成可批量操作的集合
        var immutable2 = immutable.tobuilder();
        immutable2.add("xx");
        immutable2.add("xxx");
        //还原成不可变集合
        immutable = immutable2.toimmutable();

我们来对比下可变集合、不可变builder集合、不可变集合的性能，添加新对象1000w次：

比较代码如下：

private static void list()
        {
            var list = new list<object>();
            var sp = stopwatch.startnew();

            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                list.add(obj);
            }
            console.writeline("可变列表集合:"+sp.elapsed);
        }
     
        private static void builderimmutablelist()
        {
            var list = immutablelist<object>.empty;
            var sp = stopwatch.startnew();
            var blist= list.tobuilder();
            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                blist.add(obj);
            }
            list=blist.toimmutable();

            console.writeline("不可变builder列表集合:"+sp.elapsed);
        }
        private static void immutablelist()
        {
            var list = immutablelist<object>.empty;
            var sp = stopwatch.startnew();

            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                list = list.add(obj);
            }

            console.writeline("不可变列表集合:" + sp.elapsed);
        }

另外一个缺点比较有趣，也有不少人忽略。 由于string的不可变特性，所以当我们使用string在保存敏感信息时，就需要特别注意。
比如密码 var pwd="mushroomsir"，此时密码会以明文存储在内存中，也许你稍后会加密置空等，但这都是会生成新值的。而明文会长时间存储在共享域内存中，任何能拿到dump文件的人都可以看到明文，增加了密码被窃取的风险。当然这不是一个新问题，net2.0提供的有securestring来进行安全存储，使用时进行恢复及清理。

intptr addr = marshal.securestringtobstr(securestring);
string temp = marshal.ptrtostringbstr(addr);
marshal.zerofreebstr(addr);
writeprocessmemory(...)