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

hashtablelookupperformancesortedlist

###### Related Question

- Java – Array or List in Java. Which is faster
- C# – .NET HashTable Vs Dictionary – Can the Dictionary be as fast
- Python – Get difference between two lists
- Python – Fastest way to check if a value exists in a list
- Java – Why is processing a sorted array faster than processing an unsorted array
- C# – How to get the index of an item in a list in a single step
- Which is faster: while(1) or while(2)
- Python – Why is [] faster than list()

## Best Solution

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 provideO(log n)access time.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.

For instance, in another problem: sorting an array. For

a few entriesbubble sort whileO(N^2)may be quicker than .. the quick sort, while it isO(n log n).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).

Edit: Have a look to this article to understand the meaning of Big O notation .