C#基础复习（4） 之 浅析List、Dictionary

参考资料

[1] .netcore 源码 https://github.com/dotnet/corefx
[2] 《unity 3d脚本编程 使用c#语言开发跨平台游戏》陈嘉栋著
[3] 《数据结构 第四版》 叶核亚编著
[4] @incerry【浅析c# dictionary实现原理】https://www.cnblogs.com/incerry/p/10325290.html

基础知识

1. 在c#中，list是最常用的可变长泛型列表，类似数组，用于存储一系列数据，使用下标进行索引。
2. dictionary（字典）是c#中最常用的键值对存储数据结构，通过键（须为不可变类型）来对其中的值进行索引。

疑难解答

list如何实现可变长机制？

list是c#中的可变长数组，它是arraylist的泛型版本，由于arraylist中所有对象都是object，往其中加入值类型数据时会频繁触发装箱拆箱（关于装箱拆箱的详情，可以参考我上一篇博文【c#基础复习（2） 之 装箱拆箱】），导致效率问题，同时还有一些关于强制转换的安全问题，所以一般不使用arraylist。

list底层是通过一个泛型数组进行实现，根据他的无参初始化方法可以知道，当我们使用new list<t>()的方式生成他时，他是将当前内部的数组指向了一个空数组。这段源码内容如下：

public class list<t> : ilist<t>, ilist, ireadonlylist<t>
{
    private const int defaultcapacity = 4;

    private t[] _items; // do not rename (binary serialization)
    private int _size; // do not rename (binary serialization)
    private int _version; // do not rename (binary serialization)

    private static readonly t[] s_emptyarray = new t[0];

    // constructs a list. the list is initially empty and has a capacity
    // of zero. upon adding the first element to the list the capacity is
    // increased to defaultcapacity, and then increased in multiples of two
    // as required.
    public list()
    {
        _items = s_emptyarray;
    }

    ....
}

那么问题就来了，既然初始化的时候，内部数组指向的是一个只读的empty数组，那么为什么我们还可以自如地向list中增加或删除元素呢？他是如何实现可变长机制的呢？

直接跳到list的add方法中查看一下实现。其增加元素主要跟三个方法有联系，分别是add,addwithresize以及ensurecapacity，下面是它们的源码部分。

    [methodimpl(methodimploptions.aggressiveinlining)]
    public void add(t item)
    {
        _version++;
        t[] array = _items;
        int size = _size;
        if ((uint)size < (uint)array.length)
        {
            _size = size + 1;
            array[size] = item;
        }
        else
        {
            addwithresize(item);
        }
    }

    // non-inline from list.add to improve its code quality as uncommon path
    [methodimpl(methodimploptions.noinlining)]
    private void addwithresize(t item)
    {
        int size = _size;
        ensurecapacity(size + 1);
        _size = size + 1;
        _items[size] = item;
    }

    private void ensurecapacity(int min)
    {
        if (_items.length < min)
        {
            int newcapacity = _items.length == 0 ? defaultcapacity : _items.length * 2;
            // allow the list to grow to maximum possible capacity (~2g elements) before encountering overflow.
            // note that this check works even when _items.length overflowed thanks to the (uint) cast
            if ((uint)newcapacity > array.maxarraylength) newcapacity = array.maxarraylength;
            if (newcapacity < min) newcapacity = min;
            capacity = newcapacity;
        }
    }

    public int capacity
    {
        get
        {
            return _items.length;
        }
        set
        {
            if (value < _size)
            {
                throwhelper.throwargumentoutofrangeexception(exceptionargument.value, exceptionresource.argumentoutofrange_smallcapacity);
            }

            if (value != _items.length)
            {
                if (value > 0)
                {
                    t[] newitems = new t[value];
                    if (_size > 0)
                    {
                        array.copy(_items, 0, newitems, 0, _size);
                    }
                    _items = newitems;
                }
                else
                {
                    _items = s_emptyarray;
                }
            }
        }
    }

根据以上代码，可以了解以下情况：

1. 当list的容量尚且足够时，会自动向内部的数组后面增加数据
2. 当list的容量不足（即内部维护的_size大于等于实际数组的长度）时，调用addwithresize方法，而addwithresize又会调用ensurecapacity方法进行扩容。
3. 调用ensurecapacity时，如果当前list容量为空（即我们使用无参构造方法new出list时），会让当前容量增加一个默认值（即defaultcapacity），如果当前容量不为空，那么就让当前容量翻倍。

在ensurecapacity方法中仅仅只是对容量（capacity）进行了赋值，而没有去动真正的数组。实际上玄机在capacity的set方法中，当容量改变时，会生成一个新的数组，然后将当前数组的所有值拷贝到新数组中。

这样，list为什么能自动扩容就基本清楚了。

总结一下，实际上list内部还是使用了数组对数据进行存储，只不过在添加数据时，对用于保存数据的数组的长度与list的逻辑长度_size进行比较，当内部用于保存数据的数组的长度过小时，就会自动申请扩容，扩宽的容量是原来的两倍。

list增删查改的效率如何？

list增删查改的效率也可以通过源码分析而来，有兴趣的同学可以去看参考资料[1]。下面直接给出结论：

数据结构	add	remove	find	getbyindex
list	o(1)	o(n)	o(n)	o(1)

其中remove和find都是遍历查找，所以时间复杂度颇高。

dictionary底层如何实现？

说到dictionary，还是要说一下它的非泛型版本hashtable，hashtable和dictionary内部原理类似，都是使用hash的方法来对键值对进行映射，而非传说中的红黑树（c#中的sorteddictionary是由红黑树实现），但细节上不太相同，其中hashtable使用的是双重哈希（double hashing）的方法来避免哈希冲突，而dictionary则是使用链接技术（chaining）。

关于hash

hash(又译作“散列”)是用来按关键字存储和查找的技术，仔细回想一下，如果我们要在数组中查找某一个元素，常用的有以下几种方法：

1. 遍历查找，时间复杂度o(n)，当数组数据量过大时将会有性能瓶颈
2. 二分查找，时间复杂度o(logn)，只对有序的数组有效，条件过于严苛。

而hash表的技术就是将查找时间降为o(1)的一项技术。他的基本原理很简单，就是将关键字与要存储的值建立一个映射关系，当我们使用关键字访问数组时，就能以o(1)的时间内查找到该值。

一个hash函数典型示例图如下所示，其中每一个key经过哈希函数的变换，都变成了对应的hash值。（图片引用自https://www.cnblogs.com/incerry/p/10325290.html）

下面再举一个简单的hash表例子，下面的数组下标与值一一对应，如a[1]=1,a[100]=100，这样，如果我们要查询某个数，如99，只需根据a[99]中的值是否为0即可判断数组内存不存在整型数据99。

下标	0	1	2	...	99	100
值	0	1	0	...	99	0

但是上面这个例子有一个缺陷，那就是，如果要存储数字10000，而就要开辟长度为1w的数组，如果数组元素不密集，将会造成许多浪费。这时，就可以使用hash函数来对关键字进行一些处理。

hash函数中可以通过一系列的操作来使得关键字的数值尽量小而不会重复，比如取余操作。

同样是举一个简单的例子，以 关键字 % length（数组长度） 这样的哈希函数来像下面这样存储数据。

下标	0	1	2	3
值	1000	1009	10	123
hash函数处理关键字	1000%4=0	1009%4=1	10%4=2	123%4=3

其中关键字与值一一对应，关键字通过hash函数的处理变成了对应该值的下标。

hash冲突

根据上面的描述，可以看出hash函数要保证根据关键字算出的每一个hash值都不重复是一件并不简单的事。

举个例子，同样是使用上面那个 关键字 % length 的hash函数，如果要向加入值1000和400就会出现问题，因为它们经过计算之后得到的下标值都为0。这时就发生了hash冲突（也称为hash碰撞）。

关于hash冲突，一个更为准确的定义如下：

设两个关键字k1和k2(k1!=k2)，如果hash(k1)=hash(k2)，即它们的散列地址相同，表示不同关键字的多个元素映射到同一个存储位置，这种现象称为冲突。

当发生hash冲突时，我们就用对冲突进行处理。常见的处理冲突的方法有两种，一种是开放定址法（如线性探查法、二次探查法），一种是链地址法。

线性探查法

线性探查法的描述如下(引用自《数据结构》)：

1. 设一个元素关键字为k，其散列地址为i = hash(k)。
2. 若散列表中i位置已存储元素，则产生冲突，探测下一个位置i+1是否为空，若空，则存储该元素；
3. 否则继续探测下一个位置i+2，以此类推。

探测的地址序列是i+1、i+2、....直至找到一个空位置。

设有hash函数如下：

int hash(int data,int[] nums){
    return data % nums.length;
}

线性探查法的查找过程如下图所示：

根据以上描述，可以发现，使用线性探查法来解决hash冲突，当冲突越多时，hash表查找速度越慢，这是因为在下次插入或者查找hash表的时候，冲突依然存在。

二次探查法

针对线性探查法出现的问题，一种改进方法是二次探查法。
也就是hash冲突聚集在某个范围内，每次向下检查平方的步长。

举个例子，对于线性探查法来说，如果位置index满了，他会检查index+1,index+2,index+3,....,index+n，以此类推。

对于二次探查法来说，如果位置index满了，他会检查index+1^2^ ,index+2^2^ , index+3^2^ , ... , index+n^2^。

其操作过程如图所示：

链地址法

与开放定址法不同，链地址法在遇到冲突时不会将冲突的元素放到当前数组的前面或后面，而是将同类冲突（即hash(i)都等于k的元素）放入一个链表，在查找时，首先根据hash函数找到键值，然后沿着这条链表向后面进行查找。

《数据结构》一书中对此是这样描述的：

1. 采用散列数组存储元素，将元素key存储在数组的hash(key)位置
   
2. 采用一条同义词单链表存储一组同义词冲突元素，散列数组中各元素都可链接同一条同义词单链表。

设有hash函数如下：

int hash(int data,int[] nums){
    return data % nums.length;
}

链地址法的操作流程如下图所示：

负载因子

从上面的分析中可以看出，当散列表一开始申请的数组空间越小、冲突的元素越多时，每次插入、查询元素的所消耗的时间会越来越多（无论采用哪种解决冲突的方法）。

对于这一点，c#在hashtable中设计了一个叫负载因子的东西。在《unity跨平台开发》中是这样描述它的：

负载因子loadfactor定义范围在0.1~1.0，它指定了哈希表中元素数量与位置数量之间最大的比例。例如，当loadfactor=0.5时，说明哈希表中只有一半的空间存放了元素值，其余一半都为空。
向hashtable类的实例添加新元素时，需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了，hashtable类实例的空间将被扩充。

dictionary也会在必要时扩容，但它的扩容并不是依据loadfactor设计的。这个在后面说说。

hash桶

有时候hash函数算出来的hashcode会大于我们用于存放数据的数组的长度，这时我们就不能粗暴的将hashcode直接作为键值（内部实现就是作为保存数据的下标）对数据进行映射。

对于这个问题，我们可以使用hash桶算法来解决。

对于hash桶我理解的还不是很透彻，这里引用一下@incerry博主对hash桶算法的介绍：

因为这样的一个问题，所以人们就将生成的hashcode以分段的形式来映射，把每一段称之为一个bucket（桶），一般常见的hash桶就是直接对结果取余。

假设将生成的hashcode可能取值有2^32个，然后将其切分成一段一段，使用8个桶来映射，那么就可以通过bucketindex = hashfunc(key1) % 8这样一个算法来确定这个hashcode映射到具体的哪个桶中。

大家可以看出来，通过hash桶这种形式来进行映射，所以会加剧hash的冲突。

dictionary实现细节

有了上面的理论基础，我们就可以来看一下dictionary的源码到底是如何实现的了。

重要数据项

dictionary中重要的属性如下所示：

private struct entry
{
    public int hashcode;    // 当前键经过hash函数运算后得到的值，如果为-1表示此项为空
    public int next;        // 表示当前数据的key的同类冲突的下一个元素，-1表示结尾
    public tkey key;           // 当前数据的键
    public tvalue value;         // 当前数据的值
}
private int[] _buckets;     // hash桶，它的值是指向_entries数组的下标
private entry[] _entries;   // 用于存储数据的数组
private int _count;         // 当前entries的下标
private int _freelist;  // 被删除的entry在entries中的下标，构成一个单链表，该链表中所有元素都是空闲的
private int _freecount; // 有多少个空闲的位置（即有多少个数据项entry被删除了）
private int _version;   // 当前dictionary版本，用于防止字典在迭代过程中被修改  

其中entry是dictionary中的重要数据结构，对于它的属性，简单举个例子，比如我们平常使用add("xx",yy)方法，那么就会创建出一个新的entry对象，它的key是"xx"，它的hashcode是hash("xx")，它的value是yy。可以看出我们放进字典中的键和值被包装成了这个数据结构。

其中next属性我注释说的比较模糊，这里再仔细的说一下。
前面我们说过c#中的dictionary是使用链地址法来解决hash冲突的，这个next属性就是用来实现链地址法的，它指向了下一个、键的hashcode值与当前数据的hashcode值相同的数据。

什么意思呢？简单来说就是entry中的next表示在entries数组中的某一个数据项，next的值就是该数据项（entry）在entries数组中的下标。下面画了一幅图来解释这个next的意思，通过这样next的连接，就实现了一个同类冲突的单链表。

字典中的add方法实现细节与效率分析

下面我们直接围绕一次add方法中，发生了什么过程了讲解它的实现细节。为啥是add方法呢，因为观察源码我们可以知道，我们平时常用的map["xx"]=yy这种方法原理和add实际上是差不多的，只不过add方法在遇到已有key时会抛出异常，add和this[]=yy方法如下所示：

public tvalue this[tkey key]
{
    get
    {
        int i = findentry(key);
        if (i >= 0) return _entries[i].value;
        throwhelper.throwkeynotfoundexception(key);
        return default;
    }
    set
    {
        bool modified = tryinsert(key, value, insertionbehavior.overwriteexisting);
        debug.assert(modified);
    }
}

public void add(tkey key, tvalue value)
{
    bool modified = tryinsert(key, value, insertionbehavior.throwonexisting);
    debug.assert(modified); // if there was an existing key and the add failed, an exception will already have been thrown.
}

首先，假设dictionary中已有hash桶和entries数组的长度均为7，hash("aa")==hash("bb")==hash("cc")=11，hash("dd")=2（注意只是假设），其大致示意图如下：

下面根据将待插入数据全部插入dictionary数据结构中。

1. 首先对第一个待插入数据"aa"->99的键进行hash操作，可知hash("aa")=11，hashcode大于hash桶的数量所以要对它进行一个取余操作，即 hash("aa") % len(_buckets) = 4。
   可知我们要在hash桶中下标为4的地方存放数据。但是_buckets是整型数组，不能存entry型数据，所以将entry数据存放到_entries数组的空闲位置。
   空闲位置是什么呢，其实就是count属性所表示的下标。

上面的步骤用伪代码来描述是这样的：

// entries当前空闲位置存放当前数据
_entries[_count] = entry;(即当前数据)
// 计算数据放到hash桶的哪个地方
int index = hash("aa") % len(_buckets);    // => 4
// 使buckets中的数指向entries中存放这个数据的下标处
_buckets[index] = count;

_count++;   // 使得count指向下一个空闲数据

插入数据"aa"->99后，示意图如下：

1. 对第二个待插入数据"dd"->11的键进行hash操作，可知 hash("dd")%len(_buckets)=2，即要在下标为2的地方存数据。流程大致跟步骤1类似。

插入数据"dd"->11后，内部结构示意图如下：

1. 对第三个待插入数据"cc"->3的键进行hash操作，可知hash("cc")%len(_buckets)=4，即要在hash桶下标为4的地方保存数据。但是下标为4的地方已经有数据了，这时就发生了冲突。

dictionary使用链地址法来解决hash冲突，此时将新的entry（包装了"cc"数据的对象）的next指向之前已经存在的元素，再让_buckets[index]指向当前新的entry，这样，就在_buckets[index]处形成了一个同类冲突元素的单链表。

插入数据“cc”后，内部结构示意图如下所示：

总结
经过前面的三个步骤，三个待插入数据就被插入进了dictionary中，这里总结一下dictionary中插入一个数据要进行的步骤：

1. 计算待插入数据键的hashcode值
2. 将hashcode映射到hash桶中，int index = hashcode % _buckets.length
3. 在_entries数组的空闲处（即count或freelist下标处）“创建”一个包装好插入数据的entry对象。（这里不是说真创建了一个对象，而是将那个位置的entry属性的key,hashcode,value值改为待插入数据的属性）
4. _buckets[index] 指向 _entries[count]处，插入完成

上面步骤对应的源码部分如下：

private bool tryinsert(tkey key, tvalue value, insertionbehavior behavior)
{
    ....
    // 找到hashcode对应的hash桶的位置
    ref int bucket = ref _buckets[hashcode % _buckets.length];
    ....

    // 获得当前数组中的空闲位置
    int count = _count;

    // 如果位置不够，那么扩容
    if (count == entries.length)
    {
        resize();
        bucket = ref _buckets[hashcode % _buckets.length];
    }
    index = count;
    _count = count + 1;
    entries = _entries;

    ....

    // 目标entry
    ref entry entry = ref entries[index];

    ....

    // 将该处空闲的entry的属性改完插入数据的属性
    entry.hashcode = hashcode;
    // value in _buckets is 1-based
    entry.next = bucket - 1;
    entry.key = key;
    entry.value = value;
    // value in _buckets is 1-based
    bucket = index + 1;
    _version++;

    ....
}

在前面插入的步骤中，我们可以看到内部变量freelist和freecount并没有发生变动，这是因为他们是跟删除操作(remove)息息相关的,后面讲讲。

效率分析
根据上面的操作，可以看出dictionary中，插入一个数据的时间是常数时间，即时间复杂度o(1)。

字典中的find方法实现细节与效率分析

以上面插入完三个数据的dictionary为例，下面讲讲find方法的实现细节和效率。

该dictionary的内部结构如下所示：

假设现在我们执行类似

map["aa"] 

的操作，要获取键为"aa"存储的数据，会经过如下步骤：

1. 计算key的hash值，并算出在hash桶的位置，即 hash("aa") % length
2. 到达该hash桶后，沿着这个entry的next方法一路用"aa" == entry.key?比较过去。这里表达的意思是，一直沿着这个单链表向前找，直到找到key值相同的entry，那么这个entry保存的数据就是我们要找的值。

在dictionary中还有一个常见的方法是getvalueordefault（）,这个方法与上面步骤不同的地方是当沿着单链表一直找不到对应键值且entry.next==-1时，就会返回默认值。

效率分析
根据以上操作，很显然查找时间也是常数时间，也就是时间复杂度o(1)，但是这个时间会随着dictionary内部冲突的变多而增大，当所有元素冲突到一起时，每次查找都要消耗o(n)的时间。

为了解决这个问题，dictionary内部会在合适的时候进行扩容并更换hash函数。

字典中的remove方法实现细节与效率分析

老实说我比较少用到字典的remove方法额（汗颜），关于remove方法，前面的步骤和查找是类似的。即先找到当前数据对应的hash桶位置（不如说增删改查中查是最核心的，因为增删改第一个操作都是查）。

后面的步骤的执行如下带注释的代码所示。（代码引用自@incerry的博文《浅析c# dictionary实现原理》）

public bool remove(tkey key) {
    if(key == null) {
        throwhelper.throwargumentnullexception(exceptionargument.key);
    }

    if (buckets != null) {
        // 1. 通过key获取hashcode
        int hashcode = comparer.gethashcode(key) & 0x7fffffff;
        // 2. 取余获取bucket位置
        int bucket = hashcode % buckets.length;
        // last用于确定是否当前bucket的单链表中最后一个元素
        int last = -1;
        // 3. 遍历bucket对应的单链表
        for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
            if (entries[i].hashcode == hashcode && comparer.equals(entries[i].key, key)) {
                // 4. 找到元素后，如果last< 0，代表当前是bucket中最后一个元素，那么直接让bucket内下标赋值为 entries[i].next即可
                if (last < 0) {
                    buckets[bucket] = entries[i].next;
                }
                else {
                    // 4.1 last不小于0，代表当前元素处于bucket单链表中间位置，需要将该元素的头结点和尾节点相连起来,防止链表中断
                    entries[last].next = entries[i].next;
                }
                // 5. 将entry结构体内数据初始化
                entries[i].hashcode = -1;
                // 5.1 建立freelist单链表
                entries[i].next = freelist;
                entries[i].key = default(tkey);
                entries[i].value = default(tvalue);
                // *6. 关键的代码，freelist等于当前的entry位置，下一次add元素会优先add到该位置
                freelist = i;
                freecount++;
                // 7. 版本号+1
                version++;
                return true;
            }
        }
    }
    return false;
}

总结一下，删除操作就是如下步骤：

1. 找到目标entry
2. 将entry初始化（hashcode初始化为-1）
3. 将这个空闲的entry（因为数据被删了，所以空闲）插入到dictionary内部维护的freelist单链表中(entries[i].next=freelist这一句)，等待下一次插入数据时，先找到这个freelist中的entry来插。

效率分析
根据上面代码所示，remove操作主要消耗时间的还是查找这一块，它的时间复杂度和查找相同，为o(1)，但随着冲突的增多查找时间会逐渐加大。

字典何时扩容

dictionary内部实际上是维护了两个数组对数据进行保存，既然是数组，那么自然会有数组放满的风险，根据前面的add方法源码的分析，可以看到其中有一行当count（空闲位置）== hash桶长度时，会进行扩容操作。

这是扩容比较直观的触发条件。在另外一种情况下dictionary也会触发扩容，这就是当碰撞次数过多时，它会自动扩容。

那么什么是碰撞呢？

在findentry方法中，当我们沿着同类冲突元素的单链表一直找下去的时候，每遍历一个元素，碰撞次数collisioncount就+1，当碰撞次数超过设定好的阈值时，就会触发扩容。

findentry方法源码中触发碰撞的代码：

private int findentry(tkey key)
{
    ....
    // 碰撞次数
    int collisioncount = 0;
    ...
    do
    {
        if ((uint)i >= (uint)entries.length || (entries[i].hashcode == hashcode && equalitycomparer<tkey>.default.equals(entries[i].key, key)))
        {
            break;
        }

        i = entries[i].next;
        if (collisioncount >= entries.length)
        {
            throwhelper.throwinvalidoperationexception_concurrentoperationsnotsupported();
        }
        // 在遍历这个单链表的时候，每查找失败一次，碰撞次数+1
        collisioncount++;
    } while (true);
    ...
}

很显然这个碰撞次数就关系到了我们前面说的查找方法的消耗时间，所以当碰撞次数超过阈值，dictionary就自动扩容了，并且在扩容后还会使用新的hash函数来进行hashcode值。

version（版本）和迭代的关系

在c#中，增、删、改操作都会使得dictionary中的version（版本）变量改变。

这里依旧引用一下@incerry大大的博文对于这个的解释。

迭代过程中不允许集合出现变化。如果在java中遍历直接删除元素，会出现诡异的问题，所以.net中就使用了version来实现版本控制。

那么如何在迭代过程中实现版本控制的呢？我们看一看源码就很清楚的知道。

在迭代器初始化时，就会记录dictionary.version版本号，之后每一次迭代过程都会检查版本号是否一致，如果不一致将抛出异常。

dictionary的增删查改效率如何？

经过上面的分析，我们就可以知道dictionary的增删改查效率了，列表如下：

数据结构	add	remove	find	alter
dictionary	o(1)	o(1)	o(1)	o(1)

可以看到字典这个数据结构还是相当给力的，基本的操作流程基本都是o(1)的复杂度，不过它会消耗更多的空间就是了（毕竟使用了两个数组进行维护）。

总结

这篇博文也是写的相当久，因为我基础不是很牢固，一开始写这个系列的就是为了巩固下c#基础，所以可能出现了一些错误，如果有读者看到，还请不吝指出，我会非常感激的。（话说上一篇string和stringbuilder的错误还没改。。懒癌发作。。）

本篇文章后半段关于dictionary的部分大部分是参考@incerry的博文【浅析c# dictionary实现原理】(讲的相当清楚)所写的，emmmm，如果有什么版权方面的问题，请联系我，我会立即删除这篇文章。