主页 > 优化推广 > 深入解析Hashtable、Dictionary、SortedDictionary、SortedList

深入解析Hashtable、Dictionary、SortedDictionary、SortedList

发布时间：2013/6/11 0:56:52

在《在线用户实体缓存解决方案》方案中使用Dictionary来存储，评论里同事说SortedDictionary采用二分法查找比Dictionary快，于是我们都做了测试，最后发现Dictionary是比SortedDictionary快的，前者用的是Hash算法，而后者是RB-Tree算法。

于是想深入地分析如题的4个字典的原理。

我们先看Hashtable。

MSDN的解释：表示键/值对的集合，这些键/值对根据键的哈希代码进行组织。

Hash算法是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

Hashtable 对象由包含集合元素的存储桶组成。存储桶是 Hashtable 中各元素的虚拟子组，与大多数集合中进行的搜索和检索相比，存储桶可令搜索和检索更为便捷。每一存储桶都与一个哈希代码关联，该哈希代码是使用哈希函数生成的并基于该元素的键。

Hashtable 类默认的装填因子是 1.0，但实际上它默认的装填因子是 0.72。所有从构造函数输入的装填因子，Hashtable 类内部都会将其乘以0.72。这是一个要求苛刻的数字, 某些时刻将装填因子增减 0.01, 可能你的 Hashtable 存取效率就提高或降低了 50%，其原因是装填因子决定散列表容量，而散列表容量又影响 Key 的冲突几率，进而影响性能。0.72 是 Microsoft经过大量实验得出的一个比较平衡的值。

我们看Hashtable的一些源码：

Hashtable .ctor

public Hashtable() : this(0, (float) 1f)
{
}
public Hashtable(int capacity, float loadFactor)
{
    if (capacity < 0)
    {
        throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }
    if ((loadFactor < 0.1f) || (loadFactor > 1f))
    {
        throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", new object[] { 0.1, 1.0 }));
    }
    this.loadFactor = 0.72f × loadFactor;
    double num = ((float) capacity) / this.loadFactor;
    if (num > 2147483647.0)
    {
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
    }
    int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11;
    this

上一篇： C#中SortedDictionary 的使用

下一篇： C#中SortedList 和 SortedDictionary集合类型 .

深入解析Hashtable、Dictionary、SortedDictionary、SortedList

相关新闻推荐

石家庄网站建设的优点

竞价排名对SEO的影响

SEO网站优化的八个步骤