Hash table in C++

Question

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

Solution 1

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.

Solution 2

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.

Solution 3

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).

Comments

[Paul S.]

I see. Then what is the advantage of std:map over std:unordered_map?

[Cheers and hth. - Alf]

the former is an ordered collection

[Praetorian]

hash_map is a non-standard extension shipped by most compilers. The standard hash map is called unordered_map

[Kos]

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).

[Praetorian]

@Kos unordered_map also requires its keys to be comparable; it's just a different default comparator (equal_to) as compared to map (less)

[im so confused]

I have a question. Is O(0) == O(1)? Is O(0) even defined?

[Kos]

Thanks for the clarification! (C# has this sorted out nice, distinguishing between "comparable" (with some order) and "equatable".)

[Kirill Kobelev]

I do not think that O(0) is a valid notation. O(1) means "constant time".

[im so confused]

yeah, just an idle thought that came up while reading your answer. thanks!

[slugonamission]

O(0) would probably imply that the algorithm had fetched the results for you before your even asked it what you wanted ;)

[im so confused]

@slugonamission hahaha the beginnings of Minority Report?