yve*_*mes 29
算法复杂度是一件好事,并且哈希表已知为O(1),而排序向量(在您的情况下我认为使用排序数组比列表更好)将提供O(log n)访问时间.
但是你应该知道复杂符号可以让你获得N进入无限的访问时间.这意味着如果您知道您的数据将继续增长,复杂性表示法会为您提供一些选择的算法提示.
当您知道数据的长度相当低时:例如,您的数组/哈希表中只有少数条目,您必须使用手表并进行测量.所以有一个测试.
例如,在另一个问题中:对数组进行排序.对于一些条目冒泡排序,而O(N ^ 2)可能比快速排序更快,而它是O(n log n).
此外,相应于其他答案,并且根据您的项目,您必须尝试为哈希表实例找到最佳哈希函数.否则,它可能会导致哈希表中查找的显着不良性能(正如Hank Gay的回答中指出的那样).
编辑:看看这篇文章,了解Big O符号的含义.
xto*_*ofl 14
假设"排序列表"是指"随机可访问,已排序的集合".列表具有您只能逐个元素遍历它的属性,这将导致O(N)复杂性.
在排序的可索引集合中查找元素的最快方法是通过N-ary搜索O(logN),而没有重合的哈希表具有O(1)的查找复杂度.
除非散列算法非常慢(和/或差),否则哈希表会更快.
更新:正如评论者指出的那样,你也可能因太多的冲突而降低性能,不是因为你的哈希算法很糟糕,而是因为哈希表不够大.大多数库实现(至少在高级语言中)将在幕后自动增加哈希表 - 这将导致插件上的性能低于预期,从而触发增长 - 但如果你自己滚动,那肯定是考虑一下.
a中的get操作SortedList是O(log n)与HashTable相同的操作O(1).所以,通常,HashTable会更快.但这取决于许多因素: