哈希表和字典在编程中有什么区别?


回答 1:

从技术角度来看,它们基本上可以相同。 两者均用于存储具有特定索引集的数据,从而以独特的方式标识每个记录。 通常,以键值对的形式,其中键和值都可以是任何数据类型,包括结构/类。

这些类型的数据收集的用途是基于键值快速真正地找到特定记录。 如果索引/键以升序或降序排序,则效果最佳。 这样可以进行二进制搜索,因此您可以找到具有最少比较数的记录。 但是,当您需要插入新记录时,这可能会增加额外的开销,因为您可能需要将其插入索引中间的某个位置以保持排序顺序。 这意味着索引中超出索引的任何键都需要在索引上上移。 结果,虽然搜索速度很快,但不添加新记录。 (如果使用搜索树,则添加记录的速度可能会相当快,尽管您可能会使树失去平衡……)

哈希表通过计算键上的哈希值来解决此问题。 然后,此值标识存储桶在内存中的位置。 因此,哈希值可能会导致介于0到100之间的值,并且一个数组将包含100个存储桶。 因此,查找特定记录只是计算散列以到达正确存储桶的问题。

存储桶本身最好只有一个记录,但是散列可能会导致冲突,因此存储桶中可能有很多记录。 如果您有1,000个记录,那么如果我们有100个存储桶,则平均每个存储桶将有10个记录。 尽管如此,搜索10条记录比搜索1,000条记录要快得多。 通过使用更大的存储桶列表,通常每个存储桶的记录会更少。

因此,哈希表会牺牲内存以加快搜索速度。 通常,存储桶是指向(键)记录数组的指针,因此每个存储桶需要4或8个字节。 如果您使用一百万个存储桶,那么索引的大小将小于4或8兆字节,但是它将允许您存储数百万条记录并立即(几乎)找到每个键! 这使它们对于数据库如此强大。

字典被视为关联数组,哈希表被视为无序关联数组。 使用字典,您可以选择一个排序的或未排序的一个。 大多数开发人员将使用未排序的表,该表通常只是一个哈希表! 那是因为它在许多方面都很快。

但是也可以使用排序字典,然后它将使用搜索树来存储数据。 这些搜索树还用于存储桶中的哈希表中,因为一旦找到正确的存储桶,您可能仍需要在存储桶中进行搜索。 但是,排序字典的唯一用途是按键顺序枚举所有记录。 或者查找适合两个键值之间的记录。

这给我带来了哈希树的缺点,因为您可能想查找与适合特定模式的键匹配的记录。 例如,每个名字以字母“ W”开头的人。 或介于45到60之间的任何数字。在搜索树中,当您搜索与该查询匹配的第一条记录然后向上和向下移动以查找更多记录,直到找到不符合要求的记录时,便可以轻松找到所需的内容。不再匹配。 使用散列表,您将不得不检查所有记录。

因此,如果您有一棵具有一百万条记录的二叉树,那么可能最多需要进行20次比较才能找到与搜索关键字匹配的第一条记录,然后向上和向下进行的比较与匹配搜索关键字的数量一样多。 加两个比较第一个和最后一个不匹配的密钥。 因此,如果有50条记录匹配,那么您最多可以进行70条比较才能找到所有记录。

在哈希表中,您需要进行一百万次比较…

为了找到确切的密钥,散列表只需要进行一次比较,而二叉树仍然可以达到20…

至于字典。 这些要么是哈希表,要么是搜索树。 它由背后的代码定义。 字典的某些实现甚至可以同时使用这两种方法,因为它们将对存储桶使用单独的数组,而对下一个和上一个记录使用指针来构成搜索树。 因此,对这些结构执行查询将首先确定哪种搜索方法将是最有效的。 如果要查找特定的键,它将使用哈希表。 如果您需要搜索特定范围,它将使用搜索树代替。

那么,区别呢? 哈希表只是存储键值对的一种技术。 词典存储键数据对,但未指定存储方法。 字典后面可能有哈希表!


回答 2:

在哈希表中,数据以数组格式存储,其中每个数据值都有自己的唯一索引值。 如果我们知道所需数据的索引,则数据访问将变得非常快。 因此,它成为一种数据结构,其中插入和搜索操作非常快,而与数据的大小无关。

而字典是用于存储一组对象的通用数据结构。 字典有一组键,每个键都有一个关联的值。 当显示一个键时,字典将返回关联的值。

字典使用键直接在关联数组内部引用值。

即(KEY => VALUE)

哈希通常被描述为哈希表,该哈希表使用哈希函数来计算该值在内存(或更容易地为数组)中的位置。 哈希将把KEY作为输入,并给出一个值作为输出。 然后将该值插入内存或数组索引。

即KEY => HASH FUNCTION => VALUE

哈希数据结构


回答 3:

字典是泛型类型,而HashTable是非泛型类型。由于Dictionary是泛型,因此它比HashTable更快(插入,删除,搜索等操作)。由于装箱/拆箱,数据检索比Dictionary慢。在Hashtable中,如果您尝试访问给定Hashtable中不存在的键,则它将提供空值。在Dictionary中,如果尝试访问给定Dictionary中不存在的键,则将给出错误。

HashTable是线程安全的。字典也是线程安全的,但仅适用于公共静态成员。