.NET中Dictionary<TKey, TValue>浅析

.net中dictionary<tkey, tvalue>是非常常用的key-value的数据结构，也就是其实就是传说中的哈希表。.net中还有一个叫做hashtable的类型，两个类型都是哈希表。这两个类型都可以实现键值对存储的功能，区别就是一个是泛型一个不是并且内部实现有一些不同。今天就研究一下.net中的dictionary<tkey, tvalue>以及一些相关问题。

 

文中如有错误，望指出。

 

什么是哈希表

wikipedia中对于hash table的定义是这样的：

 

in computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values.

 

它是一个通过关键字直接访问内存存储位置的数据结构，这是一个所有数据结构教科书里都会有的一个数据结构，这里不做太多的研究。但是有几个概念还是要提一下，因为对于我们理解dictionary的内部实现很大作用。

 

更多哈希表的内容：wikipedia，hashtable 博客

 

碰撞（collision）及处理

由于我们在数据结构中采用的哈希算法不是一个完美的哈希算法，同时我们会限制我们用来存储的内存空间。所以发生碰撞是不可能避免的，所以很处理如何碰撞就是设计哈希表的时候需要考虑的一个很重要的因素。

 

处理碰撞有很多方法，例如开放寻址法（open adressing），分离链接法（separate chaining）。dictionary中采用的是一个叫做separate chaining with linked lists的方法。

 

通过下面这个wikipedia上的图就可以很清楚的认识到这是一个什么样子的方法。

 

分离链接法例子

 

利用两个数组，buckets数组只保存一个地址，这个地址指向的是entries数组中的一个实例(entry)。当哈希值冲突的时候则需要往当前指向的那个实例的链表的末端添加一个新实例即可。

 

装填因子（load factor）

装填因子的存在是因为在开放定址方法中，当数组中的内容越来越多的时候则冲突的概率就会越来越大，而在开放定址方法中冲突的解决方案是采用探测法，而这种冲突会带来性能的极大损失。wikipedia中的这张图比较了分散链接和线性探测法在不同装填因子的情况下cpu缓存不命中的对应关系。

 

cpu cach miss - load factor

 

在dictionary采用的这种方法里，装填因子并不是一个重要的因素不会对性能有太大影响，所以dictionary默认使用了1并认为没有必要提供任何接口去设置这个值。

 

dictionary内部如何实现

先来介绍几个在dictionary中重要的变量：

 

int[] buckets 和 entry[] entries

iequalitycomparer<tkey> comparer

.

 

这两个就是在上面提到的两个数组，所谓的 separate chaining with linked lists。

在往dictionary中添加一对新值的时候需要计算key的hashcode，冲突的时候也需要判断两个value是不是相等。这个comparer就是来做这个事情的，那么这里为什么不直接调用key重载的gethashcode和equal方法呢？这个会在下文中讲到。

插入

通过一个例子来说明dictionary在插入的时候做了什么。

 

 

dictionary<int, string=""> dict = new dictionary<int, string="">();

dict.add(0, "zero");

dict.add(12, "twelve");

dict.add(15, "fiften");

dict.add(4, "four");

下面这张“图”能够看出两个数组在插入操作中的变化，结合源代码细细品味就能知道发生了什么。

 

 

---------       ---------

|buckets|       |entries|

|-------|       |-------|

|   0   |       |    -->| hashcode=0,key=0,next=-1,value="zero"

|-------|       |-------|

|   -1  |       | empty |

|-------|       |-------|

|   -1  |       | empty |

|-------|       |-------|

 

---------       ---------

|buckets|       |entries|

|-------|       |-------|

|   1   |       |    -->| hashcode=0,key=0,next=-1,value="zero"

|-------|       |-------|

|  -1   |       |    -->| hashcode=12,key=12,next=0,value="twelve"

|-------|       |-------|

|  -1   |       | empty |

|-------|       |-------|

 

---------       ---------

|buckets|       |entries|

|-------|       |-------|

|   2   |       |    -->| hashcode=0,key=0,next=-1,value="zero"

|-------|       |-------|

|  -1   |       |    -->| hashcode=12,key=12,next=0,value="twelve"

|-------|       |-------|

|  -1   |       |    -->| hashcode=15,key=15,next=1,value="fiften"

|-------|       |-------|

 

---------       ---------

|buckets|       |entries|

|-------|       |-------|

|   0   |       |    -->| hashcode=0,key=0,next=-1,value="zero"

|-------|       |-------|

|   2   |       |    -->| hashcode=12,key=12,next=-1,value="twelve"

|-------|       |-------|

|  -1   |       |    -->| hashcode=15,key=15,next=-1,value="fiften"

|-------|       |-------|

|  -1   |       |    -->| hashcode=4,key=4,next=-1,value="four"

|-------|       |-------|

|   3   |       | empty |

|-------|       |-------|

|   1   |       | empty |

|-------|       |-------|

|  -1   |       | empty |

|-------|       |-------|

扩容

上面例子中最后一个插入时，dictionary就做了一次扩容。它将dictionary的size从原有的3扩展到了7。可以看到entries中的元素在扩容的时候变化不大，只是next有了些变化，这是因为扩容以后他们的哈希值%length不再映射到同一个值上了，也就不需要共享一个值啦。我觉得这里有两点值得一提。

 

扩容的下一个size是如何得到的，在上面的例子中为什么是7？

扩容是两个数组的变化。

对于第一个问题，因为dictionary中数组长度有限，所以是通过key.gethashcode() % length来获得一个bucket数组中的位置然后更改entry的next。那么我们就要保证尽可能的减少取模带来的冲突次数，那么素数就能够很好的保证取模以后能够尽可能的分散在数组的各处。

 

dictionary扩容的时候会先把当前的容量*2，然后再在一个素数表中找到比这个值大的最近的一个素数。这个素数表是长这样子的：

 

 

public static readonly int[] primes = {

    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,

    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,

    17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,

    187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,

    1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

至于第二个问题，我们在上文中也提到过了，这个方法在扩容的时候是不需要对哈希表中存储的内容进行重新哈希。我们只需要将bucket中的分布的元素所对应的哈希值重新进行取模运算，然后放到新的位置上即可，这个操作是极快的。

 

查找

key.gethashcode() % length --> 遍历链表找到equal的key

 

删除

同查找。

 

几个注意事项

性能问题

我们使用dictionary的时候一般的习惯应该就跟代码1中那样，这种使用方法在我们使用内置的类型当key的时候没有问题，但是如果我们需要将一个自定义的值类型(struct)当作key的时候就需要注意了。这里有一个很容易忽略的问题，会导致使用dictionary的时候带来大量不必要的性能开销。

 

当我们需要定义一些自定义结构并且要把这些实例放在集合中的时候我们往往会采用值类型而不会定义成一个类，如果这些类型只存在数据的话值类型在性能上比类要好很多。（choosing between class and struct）

 

我们先做一个实验来比较一下值类型和类作为key的性能有多大的差距。实验代码如下，这段代码中我插入1000个到10000个数据来得到所需要的时间。

 

 

public class/struct customkey

{

    public int field1;

    public int field2;

    public override int gethashcode()

    {

        return field1.gethashcode() ^

                field2.gethashcode();

    }

 

    public override bool equals(object obj)

    {

        customkey key = (customkey)obj;

        return this.field1 == key.field1 &&

                this.field2 == key.field2;

    }

}

 

dictionary<mykey, int=""> dict = new dictionary<mykey, int="">();

int trycount = 50;

double totaltime = 0.0;

for (int count = 1000; count < 10000; count += 1000)

{

    for (int j = 0; j < trycount; j++)

    {

        stopwatch watcher = stopwatch.startnew();

        for (int i = 0; i < count; i++)

        {

            mykey key = new mykey() { field1 = i * 2, field2 = i * 2 + 1 };

            dict.add(key, i);

        }

        watcher.stop();

        dict.clear();

        totaltime += watcher.elapsedmilliseconds;

    }

    console.writeline("{0},{1}", count, totaltime / trycount);

}

结果是这样子的：

 

class vs struct

 

wtf？为什么和我的预期不一样，不是应该值类型要快才对不是么？orz....

 

这里就要提到刚刚在上文中提到的那个iequalitycomparer<tkey> comparer，dictioanry内部的比较都是通过这个实例来进行的。但是我们没有指定它，那么它使用的就是equalitycomparer<tkey>.default。让我们看一下源代码来了解一下这个default到底是怎么来的，在createcomparer我们可以看到如果我们的类型不是byte、没实现iequatable<t>接口、不是nullable<t>、不是enum的话，会默认给我们创建一个objectequalitycomparer<t>()。

 

而objectequalitycomparer<t>()中的equal和gethashcode方法看上去也没啥问题，那到底问题出在哪里呢？

 

跟值类型有关的性能问题，马上能够想到的就是装箱和拆箱所带来的性能损耗。这里那里存在这种操作呢？我们来看一下下面的两段代码就明白了。

 

 

objectequalitycomparer.equals(t x, t y)的il代码

// methods

.method public hidebysig virtual

    instance bool equals (

        !t x,

        !t y

    ) cil managed 

{

    // method begins at rva 0x62a39

    // code size 50 (0x32)

    .maxstack 8

 

    il_0000: ldarg.1

    il_0001: box !t

    il_0006: brfalse.s il_0026

 

    il_0008: ldarg.2

    il_0009: box !t

    il_000e: brfalse.s il_0024

 

    il_0010: ldarga.s x

    il_0012: ldarg.2

    il_0013: box !t

    il_0018: constrained. !t

    il_001e: callvirt instance bool system.object::equals(object)

    il_0023: ret

 

    il_0024: ldc.i4.0

    il_0025: ret

 

    il_0026: ldarg.2

    il_0027: box !t

    il_002c: brfalse.s il_0030

 

    il_002e: ldc.i4.0

    il_002f: ret

 

    il_0030: ldc.i4.1

    il_0031: ret

} // end of method objectequalitycomparer`1::equals

 

 

 

objectequalitycomparer.equals(t x, t y)的il代码

.method public hidebysig virtual

    instance int32 gethashcode (

        !t obj

    ) cil managed 

{

    .custom instance void system.runtime.targetedpatchingoptoutattribute::.ctor(string) = (

        01 00 3b 50 65 72 66 6f 72 6d 61 6e 63 65 20 63

        72 69 74 69 63 61 6c 20 74 6f 20 69 6e 6c 69 6e

        65 20 61 63 72 6f 73 73 20 4e 47 65 6e 20 69 6d

        61 67 65 20 62 6f 75 6e 64 61 72 69 65 73 00 00

    )

    // method begins at rva 0x62a6c

    // code size 24 (0x18)

    .maxstack 8

 

    il_0000: ldarg.1

    il_0001: box !t

    il_0006: brtrue.s il_000a

 

    il_0008: ldc.i4.0

    il_0009: ret

 

    il_000a: ldarga.s obj

    il_000c: constrained. !t

    il_0012: callvirt instance int32 system.object::gethashcode()

    il_0017: ret

} // end of method objectequalitycomparer`1::gethashcode

从上面两段代码中可以看到在objectequalitycomparer的默认实现中会存在着很多的box(见高亮行)操作，它是用来将值类型装箱成引用类型的。这个操作是很耗时的，因为它需要创建一个object并将值类型中的值拷贝到新创建的对象中。（customkey.equal方法中也有一个unbox操作）。

 

怎么破？

 

我觉得只要避免装箱不就行了，那我们自己创建一个comparer。

 

 

public class mykeycomparer : iequalitycomparer

{

    #region iequalitycomparer members

 

    public bool equals(customkey x, customkey y)

    {

        return x.field1 == y.field1 &&

               x.field2 == y.field2;

    }

 

    public int gethashcode(customkey obj)

    {

        return obj.field1.gethashcode() ^

               obj.field2.gethashcode();

    }

 

    #endregion

}

那我们将实验代码稍作修改（dictionary<customkey, int> dict = new dictionary<customkey, int>(new mykeycomparer());）在测试一把。这次的结果显示性能提高了很多。

如对本文有疑问， 点击进行留言回复！！