在哈希表或排序列表中查找项目哪个更快？
问问题
25300 次
7 回答
32
算法复杂性是一件好事，已知哈希表为O(1)而排序向量（在你的情况下，我猜使用排序数组比列表更好）将提供O(log n)访问时间.
但是您应该知道，复杂性表示法为您提供了 N 进入无穷大的访问时间。这意味着，如果您知道您的数据会不断增长，那么复杂性符号会为您提供一些关于选择算法的提示。
当您知道您的数据将保持相当短的长度时：例如，您的数组/哈希表中只有几个条目，您必须随身携带手表并进行测量。所以做一个测试。
例如，在另一个问题中：对数组进行排序。对于一些条目冒泡排序，而O(N^2)可能比 .. 快速排序更快，而它是O(n log n)。
此外，根据其他答案，并根据您的项目，您必须尝试为您的哈希表实例找到最佳哈希函数。否则，它可能会导致在您的哈希表中查找的性能非常差（正如 Hank Gay 的回答中所指出的那样）。
编辑：查看这篇文章以了解Big O notation 的含义。
于 2009-05-18T09:54:53.057 回答
14
假设“排序列表”是指“随机可访问的排序集合”。列表具有只能逐个元素遍历它的属性，这将导致 O(N) 复杂度。
在已排序的可索引集合中查找元素的最快方法是通过 N 元搜索 O(logN)，而没有冲突的哈希表的查找复杂度为 O(1)。
于 2009-05-18T09:49:51.523 回答
7
除非散列算法非常慢（和/或糟糕），否则散列表会更快。
更新：正如评论者所指出的，您也可能因过多的冲突而降低性能，这不是因为您的哈希算法不好，而仅仅是因为哈希表不够大。大多数库实现（至少在高级语言中）会在幕后自动增长你的哈希表——这将导致触发增长的插入性能低于预期——但如果你自己滚动，那肯定是考虑。
于 2009-05-18T09:49:43.020 回答
5
a 中的get操作SortedList是O(log n)，而 ea HashTable 中的操作相同O(1)。因此，通常情况下，HashTable会快得多。但这取决于许多因素：
- 列表的大小
- 哈希算法的性能
- 冲突次数/哈希算法的质量
于 2009-05-18T09:57:37.823 回答
3
这完全取决于您存储的数据量。
假设你有足够的内存扔给它（所以哈希表足够大），哈希表会在固定的时间内定位目标数据，但是需要计算哈希会增加一些（也是固定的）开销。
搜索排序列表不会有散列开销，但实际定位目标数据所需的时间会随着列表的增长而增加。
因此，一般来说，对于小型数据集，排序列表通常会更快。（对于经常更改和/或不经常搜索的极小数据集，未排序的列表可能更快，因为它避免了进行排序的开销。）随着数据集变大，列表的搜索时间增长掩盖了哈希的固定开销，并且哈希表变得更快。
该断点的位置将根据您的特定哈希表和排序列表搜索实现而有所不同。在许多典型大小的数据集上运行测试和基准性能，看看哪些在您的特定情况下实际上表现更好。（或者，如果代码已经“足够快”地运行，则不要。只需使用您更熟悉的那个，不要担心优化不需要优化的东西。）
于 2009-05-18T10:13:12.723 回答
1
在某些情况下，它取决于集合的大小（以及在较小程度上，实现细节）。如果您的列表非常小，可能有 5-10 项，我猜列表会更快。否则 xtofl 是正确的。
于 2009-05-18T09:53:56.273 回答
1
HashTable 对于包含超过 10 个项目的列表会更有效。如果列表中的项目少于 10 个，则散列算法的开销会更多。
如果您需要快速字典，但还需要以有序的方式保存项目，请使用 OrderedDictionary。（.Net 2.0 以上）
于 2009-05-18T09:57:22.833 回答