2

On this website, section 4.4, it is suggested to binary search an array rather than using a hash table. How is that?

2
  • 2
    Right below the suggestion, it says "A binary search on an array has logarithmic complexity, like search trees, but has the advantage of compactness and locality of reference typical of arrays." Sep 27, 2012 at 22:46
  • 1
    Probably depends on how many buckets are in the hash table, and the efficiency of the hashing algorithm involved. I doubt you can make a blanket statement that one is faster. Sep 27, 2012 at 22:47

2 Answers 2

8

There are too many factors to make a blanket statement.

  • The number of elements in the container.
  • The speed of the hash function.
  • The speed of the comparison function.
  • The number of hash collisions.
1
  • +1. For small arrays, both binary and hash searches may have more overhead than a simple linear search. Sep 27, 2012 at 23:21
3

Hashtables (with good hash functions) have O(1) complexity (which is better than O(log n) ;), since they directly "link you to" the result.

But using hashtables for small sets of data/arrays might not be worth the overhead of allocating the memory needed for the table.

5
  • This is flawed. We are talking about lookup tables here, so talking about computational complexity is simply not right.
    – orlp
    Sep 27, 2012 at 22:50
  • 3
    @nightcracker what? It seems relevant to me. Looking up an element in an array using binary search vs a hash table is what the question is about no? Sep 27, 2012 at 22:51
  • 1
    @Seth Carnegie: for small N (for example 0 < N < 2^32) solutions with O(1) and log(N) complexity compete very much, because the hidden constants dominate. Take for example the binary search I wrote in this answer: stackoverflow.com/a/5296669/565635
    – orlp
    Sep 27, 2012 at 22:54
  • 1
    @nightcracker I realise that and completely agree with you, but that doesn't mean that talking about computational complexity is completely not germane to this question. Sep 27, 2012 at 22:55
  • @nightcracker: For lookup tables, nothing beats a random access array, if possible. A map container may be more efficient, or even a hashmap. Sep 27, 2012 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.