我试图比较哈希表查找和线性搜索的性能。我创建了一个包含 1000 个项目的哈希表,发现在哈希表中查找所需的时间为 0.0002(我曾经DateTime.Now
在查找前后找出系统时间并减去它们)。我在一个数组中有相同的 1000 行,并使用线性搜索查找相同的值。结果证明它比哈希表查找所花费的时间要少。
我认为哈希表比线性搜索更快。它是如何工作的?
我试图比较哈希表查找和线性搜索的性能。我创建了一个包含 1000 个项目的哈希表,发现在哈希表中查找所需的时间为 0.0002(我曾经DateTime.Now
在查找前后找出系统时间并减去它们)。我在一个数组中有相同的 1000 行,并使用线性搜索查找相同的值。结果证明它比哈希表查找所花费的时间要少。
我认为哈希表比线性搜索更快。它是如何工作的?
首先,你的计时机制不好。如果您想测试性能,您应该使用高分辨率计时器,例如System.Diagnostics.Stopwatch
.
其次,您需要找到许多随机且均匀分布在您的查找空间中的查找的平均查找时间,而不仅仅是某个特定项目的查找时间。
答案可以在这篇文章中找到:
在名为“ System.Collections.Hashtable 类”的部分中
这是(非常)简短的概要:
添加到集合(Add(object key, object value)
):
key
和value
参数key
。这是一个复杂的公式,它使用该Object.GetHashCode()
方法并在索引中产生一个介于 0 和 hashsize 之间的位置(哈希表中的槽数(由 使用的内部查找结构System.Collections.HashTable
)。访问集合中的项目(object this[object key] { set; get; }
):
key
参数key
。value
存储在该位置的项目的