10

Is the insertion/deletion/lookup time of a C++ std::map O(log n)? Is it possible to implement an O(1) hash table?

chrisaycock
  • 36,470
  • 14
  • 88
  • 125
Paul S.
  • 4,362
  • 10
  • 35
  • 52
  • 5
    In c++11 there is `std::unordered_map`, if you have boost `boost::unordered_map` – andre Oct 12 '12 at 20:42
  • 1
    You seem to be operating under the misconception that `std::map` is a hash table, but they're generally binary trees. – Brendan Long Oct 12 '12 at 20:47
  • @BrendanLong Sure, I realize that it's implemented using binary trees. But doesn't it function just like a hash table? – Paul S. Oct 12 '12 at 20:49
  • 1
    Hash tables and binary trees can be made to provide the same interface (like `map` / `unordered_map`), but they function completely different internally. – Brendan Long Oct 12 '12 at 20:54
  • Related: ["Can hash tables really be O(1)?"](http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1). – David Cary Aug 14 '16 at 23:12

3 Answers3

18

Is the insertion/deletion/lookup time of a C++ map O(log n)?

Yes.

Is it possible to implement an O(1) hash table?

Definitely. The standard library also provides one as std::unordered_map.

Kos
  • 70,399
  • 25
  • 169
  • 233
  • I see. Then what is the advantage of `std:map` over `std:unordered_map`? – Paul S. Oct 12 '12 at 20:43
  • 5
    the former is an ordered collection – Cheers and hth. - Alf Oct 12 '12 at 20:44
  • 5
    `std::map` uses a tree and needs its keys to be comparable, while `std::unordered_map` requires its keys to be hashable. Also I wouldn't assume that `std::unordered_map` is always faster, esp. for small data (but don't take my word for it and check if you feel that's important). – Kos Oct 12 '12 at 20:47
  • 1
    @Kos `unordered_map` also requires its keys to be comparable; it's just a different default comparator (`equal_to`) as compared to `map` (`less`) – Praetorian Oct 12 '12 at 20:49
  • 1
    Thanks for the clarification! (C# has this sorted out nice, distinguishing between "comparable" (with some order) and "equatable".) – Kos Oct 12 '12 at 20:51
6

C++ has a unordered_map type. The STL also contains a hash_map type, although this is not in the C++ standard library.

Now, for a bit of algorithmic theory. It is possible to implement an O(1) hash table under perfect conditions, and technically, hash tables are O(1) insertion and lookup. The perfect conditions in this case are that the hash function must be perfect (i.e. collision free), and you have infinite storage.

In practise, let's take a dumb hash table. For any input key, it returns 1. In this case, when there is a collision (i.e. on the second and subsequent insertions), it will have to chain further to find some free space. It can either go to the next storage location, or use a linked list for this.

In any case, in the best case, yes, hash tables are O(1) (until you have exhausted all of your hash values, of course, since it is impractical to have a hash function with an infinite amount of output). In the worst case (e.g. with my completely dumb hash function), hash tables are O(n), since you will have to traverse over the storage in order to find your actual value from the given hash, since the initial value is not the correct value.

slugonamission
  • 9,562
  • 1
  • 34
  • 41
  • `hash_map` is a non-standard extension shipped by most compilers. The standard hash map is called `unordered_map` – Praetorian Oct 12 '12 at 20:46
1

The implementation of std::map is a tree. This is not directly specified in the standard, but as some good books are saying: "It is difficult to imagine that it can be anything else". This means that the insertion/deletion/lookup time for map is O(log n).

Classic hash tables have lookup time O(n/num_slots). Once the expected number of items in the table is comparable with the number of slots, you will have saturated O(1).

Kirill Kobelev
  • 10,252
  • 6
  • 30
  • 51