c# - 为什么Dictionary比Hashtable更受欢迎?




.net vb.net data-structures (16)

人们在说Dictionary和哈希表是一样的。

这不一定是真的。 散列表是字典的实现 。 这是一个典型的例子,它可能是.NET中默认的一个,但它不是唯一的定义。

你也可以很好地实现一个链接列表或搜索树的字典,它不会像效率一样高效。

在大多数编程语言中,字典比hashtables更受欢迎。 这背后的原因是什么?


字典:

  • 如果我们试图找到一个不存在的键,它会返回/抛出异常。

  • 它比散列表更快,因为没有装箱和拆箱。

  • 只有公共静态成员是线程安全的。

  • 字典是一个泛型类型,这意味着我们可以将它与任何数据类型一起使用(创建时,必须为键和值指定数据类型)。

    示例: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay是Hashtable的类型安全实现, KeysValues是强类型的。

哈希表:

  • 如果我们试图找到一个不存在的键,它将返回null。

  • 它比词典慢,因为它需要装箱和取消装箱。

  • Hashtable中的所有成员都是线程安全的,

  • 哈希表不是泛型类型,

  • 哈希表是松散类型的数据结构,我们可以添加任何类型的键和值。


注意MSDN说:“Dictionary <(Of <(TKey,TValue>)>)类实现为散列表 ”,而不是“Dictionary <(Of <(TKey,TValue>)>)类实现为HashTable

Dictionary不是作为HashTable来实现的,但是它是在哈希表的概念之后实现的。 由于使用泛型,实现与HashTable类无关,尽管内部Microsoft可能使用相同的代码并用TKey和TValue替换了Object类型的符号。

在.NET 1.0中,泛型不存在; 这是HashTable和ArrayList最初开始的地方。


我能弄清的另一个区别是:

我们不能在Web服务中使用Dictionary <KT,VT>(泛型)。 原因是没有Web服务标准支持泛型标准。


在.NET中, Dictionary<,>HashTable之间的区别主要在于前者是泛型类型,所以在静态类型检查(和减少装箱)方面你可以获得泛型的所有好处,但这并不像人们往往会考虑表现 - 尽管拳击确实存在一定的记忆成本)。


哈希表对象由包含集合元素的桶组成。 一个存储桶是Hashtable中的一个虚拟子组, 它使得搜索和检索比大多数集合更容易和更快速

Dictionary类具有与Hashtable类相同的功能。 对于值类型,特定类型的字典(Object除外) 比Hashtable具有更好的性能 ,因为Hashtable的元素的类型为Object,因此,如果存储或检索值类型,通常会发生装箱和拆箱。

进一步阅读: 散列表和字典集合类型


CollectionsGenerics对于处理一组对象很有用。 在.NET中,所有集合对象都位于IEnumerable接口下,而IEnumerable接口又具有ArrayList(Index-Value))HashTable(Key-Value) 。 在.NET框架2.0之后, ArrayListHashTable被替换为ListDictionary 。 现在, ArraylistHashTable在当今的项目中不再被使用。

来到HashTableDictionary之间的区别, Dictionary是泛型的,因为Hastable不是Generic。 我们可以将任何类型的对象添加到HashTable ,但是在检索时我们需要将其转换为所需的类型。 所以,它不是安全的。 但是对于dictionary ,在声明自己的同时我们可以指定键和值的类型,因此在检索时不需要进行投射。

我们来看一个例子:

哈希表

class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}

字典,

class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}

因为Dictionary是一个泛型类( Dictionary<TKey, TValue> ),所以访问它的内容是类型安全的(也就是说,你不需要使用ObjectObject ,就像使用Hashtable )。

比较

var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];

var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;

然而, Dictionary是作为Hashtable内部实现的,所以在技术上它的工作原理是一样的。


根据我使用.NET Reflector看到的内容:

[Serializable, ComVisible(true)]
public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable
{
    // Fields
    private Hashtable hashtable;

    // Methods
    protected DictionaryBase();
    public void Clear();
.
.
.
}
Take note of these lines
// Fields
private Hashtable hashtable;

所以我们可以确定DictionaryBase在内部使用HashTable。


数据结构广泛检查使用 MSDN上的C#文章指出, 冲突解决策略也存在差异:

哈希表类使用了一种称为重新哈希的技术。

重新哈希函数的工作原理如下:有一组哈希函数,H 1 ... H n ,当从哈希表中插入或检索项目时,最初使用H 1哈希函数。 如果这导致碰撞,则尝试H 2 ,并且如果需要则向上至H n

该词典使用了一种称为链接的技术。

重新哈哈哈哈,在发生冲突时重新计算哈希,并尝试对应于哈希的新时隙。 然而,链接使用辅助数据结构来保存任何碰撞 。 具体而言,Dictionary中的每个插槽都有一组映射到该存储桶的元素。 如果发生碰撞,碰撞元素将被预先存储在存储桶列表中。


仅供参考:在.NET中, Hashtable是线程安全的,可供多个阅读器线程和单个写入线程使用,而Dictionary public static members是线程安全的,但不保证所有实例成员都是线程安全的。

因此,我们必须将所有字典都更改回Hashtable


Dictionary <<< >>> Hashtable差异:

  • 泛型 <<< >>> 非泛型
  • 需要自己的线程同步 <<< >>>通过Synchronized()方法提供线程安全版本
  • 枚举项: KeyValuePair <<< >>>枚举项: DictionaryEntry
  • 较新(> .NET 2.0 )<<< >>>较老(自.NET 1.0起
  • System.Collections.Generic <<< >>>在System.Collections中
  • 请求不存在的键抛出异常 <<< >>>请求不存在的键返回null
  • 对于值类型 <<< >>> 位较慢 (需要装箱/取消装箱)可能会 一点

Dictionary / Hashtable相似之处:

  • 两者都是内部哈希表 ==根据关键字快速访问多项目数据
  • 两者都需要不可变的唯一键
  • 两者的键都需要自己的GetHashCode()方法

类似的 .NET集合(用来代替Dictionary和Hashtable的候选):

  • ConcurrentDictionary - 线程安全 (可以同时从多个线程安全地访问)
  • HybridDictionary - 优化性能 (对于少数项目以及对许多项目)
  • OrderedDictionary - 可以通过int索引访问值(按照添加项目的顺序)
  • SortedDictionary - 自动排序的项目
  • StringDictionary - 为字符串强类型化和优化

Dictionary<>是一个泛型类型,因此它是类型安全的。

您可以在HashTable中插入任何值类型,这有时会引发异常。 但Dictionary<int>只接受整数值,同样Dictionary<string>只接受字符串。

所以,最好使用Dictionary<>来代替HashTable


哈希表:

键/值将被转换为对象(装箱)类型,同时存储到堆中。

键/值需要从堆中读取时转换为所需的类型。

这些操作非常昂贵。 我们需要尽可能避免装箱/取消装箱。

词典: HashTable的泛型变体。

没有拳击/拆箱。 无需转换。


Hashtable是一种松散类型的数据结构,因此您可以将任何类型的键和值添加到HashtableDictionary类是一个类型安全的Hashtable实现,键和值是强类型的。 在创建Dictionary实例时,您必须为键和值指定数据类型。


由于我写了你指的MSDN文章,我想我必须回答这个问题。

首先,我预见到了这个问题,这就是为什么我写了一篇博客文章,其中展示了ExpandoObject的一个或多或少的真实用例: C#4.0中的动态:介绍ExpandoObject

不久之后,ExpandoObject可以帮助您创建复杂的分层对象。 例如,假设你在字典中有一本字典:

Dictionary<String, object> dict = new Dictionary<string, object>();
Dictionary<String, object> address = new Dictionary<string,object>();
dict["Address"] = address;
address["State"] = "WA";
Console.WriteLine(((Dictionary<string,object>)dict["Address"])["State"]);

层次越深,丑陋就是代码。 借助ExpandoObject,它保持优雅和可读性。

dynamic expando = new ExpandoObject();
expando.Address = new ExpandoObject();
expando.Address.State = "WA";
Console.WriteLine(expando.Address.State);

其次,正如已经指出的那样,ExpandoObject实现了INotifyPropertyChanged接口,它使您能够比字典更好地控制属性。

最后,您可以像这样将事件添加到ExpandoObject:

class Program
{

   static void Main(string[] args)
   {
       dynamic d = new ExpandoObject();

       // Initialize the event to null (meaning no handlers)
       d.MyEvent = null;

       // Add some handlers
       d.MyEvent += new EventHandler(OnMyEvent);
       d.MyEvent += new EventHandler(OnMyEvent2);

       // Fire the event
       EventHandler e = d.MyEvent;

       if (e != null)
       {
           e(d, new EventArgs());
       }

       // We could also fire it with...
       //      d.MyEvent(d, new EventArgs());

       // ...if we knew for sure that the event is non-null.
   }

   static void OnMyEvent(object sender, EventArgs e)
   {
       Console.WriteLine("OnMyEvent fired by: {0}", sender);
   }

   static void OnMyEvent2(object sender, EventArgs e)
   {
       Console.WriteLine("OnMyEvent2 fired by: {0}", sender);
   }
}




c# .net vb.net data-structures