在哈希表或排序列表中找到项目的速度更快? [英] Which is faster to find an item in a hashtable or in a sorted list?

问题描述

在哈希表或排序列表中查找项目更快?

Which is faster to find an item in a hashtable or in a sorted list?

推荐答案

知道算法的复杂性是一件好事，并且哈希表被称为 O(1)，而排序向量(在您的情况我想最好使用排序数组而不是列表)，这样可以提供 O(log n)访问时间.

Algorithm complexity is a good thing to know, and hashtables are known to be O(1) while a sorted vector (in your case I guess it is better to use a sorted array than a list) will provide O(log n) access time.

但是您应该知道，复杂度符号为您提供了N到达无穷大的访问时间.这意味着，如果您知道数据将保持增长，则复杂度符号会为您提供有关选择算法的一些提示.

But you should know that complexity notation gives you the access time for N going to the infinite. That means that if you know that your data will keep growing, complexity notation gives you some hint on the algorithm to chose.

当您知道数据的长度会很短时:例如，数组/哈希表中只有几个条目，那么您必须格外小心.因此，进行测试.

When you know that your data will keep a rather low length: for instance having only a few entries in your array/hashtable, you must go with your watch and measure. So have a test.

例如，在另一个问题中:对数组进行排序.对于一些条目气泡排序，而 O(N ^ 2)可能比..快速排序更快，而 O(n log n).

For instance, in another problem: sorting an array. For a few entries bubble sort while O(N^2) may be quicker than .. the quick sort, while it is O(n log n).

此外，根据其他答案，并且根据您的项目，您必须尝试为哈希表实例找到最佳的哈希函数.否则，这可能会导致哈希表中的查找性能急剧下降(如Hank Gay的回答所指出的那样).

Also, accordingly to other answers, and depending on your item, you must try to find the best hash function for your hashtable instance. Otherwise it may lead to dramatic bad performance for lookup in your hashtable (as pointed out in Hank Gay's answer).

查看本文以了解 Big O表示法的含义.

这篇关于在哈希表或排序列表中找到项目的速度更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！