1

我试图比较哈希表查找和线性搜索的性能。我创建了一个包含 1000 个项目的哈希表，发现在哈希表中查找所需的时间为 0.0002（我曾经DateTime.Now在查找前后找出系统时间并减去它们）。我在一个数组中有相同的 1000 行，并使用线性搜索查找相同的值。结果证明它比哈希表查找所花费的时间要少。

我认为哈希表比线性搜索更快。它是如何工作的？

4

2 回答 2

3

首先，你的计时机制不好。如果您想测试性能，您应该使用高分辨率计时器，例如System.Diagnostics.Stopwatch.

其次，您需要找到许多随机且均匀分布在您的查找空间中的查找的平均查找时间，而不仅仅是某个特定项目的查找时间。

于 2011-08-13T00:29:04.467 回答
1

答案可以在这篇文章中找到：

使用 C# 2.0 对数据结构进行广泛检查，

在名为“ System.Collections.Hashtable 类”的部分中

这是（非常）简短的概要：

添加到集合（Add(object key, object value)）：

  1. 接收key和value参数
  2. 对参数应用哈希算法key。这是一个复杂的公式，它使用该Object.GetHashCode()方法并在索引中产生一个介于 0 和 hashsize 之间的位置（哈希表中的槽数（由 使用的内部查找结构System.Collections.HashTable）。
  3. 在该位置插入一个 DictionaryEntry 对象。

访问集合中的项目（object this[object key] { set; get; }）：

  1. 接收key参数
  2. 使用参数上的哈希算法计算哈希表中的位置key。
  3. 返回value存储在该位置的项目的
于 2013-10-15T22:50:12.117 回答