2

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

qdii
  • 12,505
  • 10
  • 59
  • 116
  • 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."* – Robert Harvey Sep 27 '12 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. – Mike Christensen Sep 27 '12 at 22:47

2 Answers2

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.
Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
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.

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
Gung Foo
  • 13,392
  • 5
  • 31
  • 39
  • This is flawed. We are talking about lookup tables here, so talking about computational complexity is simply not right. – orlp Sep 27 '12 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? – Seth Carnegie Sep 27 '12 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: http://stackoverflow.com/a/5296669/565635 – orlp Sep 27 '12 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. – Seth Carnegie Sep 27 '12 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. – Thomas Matthews Sep 27 '12 at 23:23