What's the right hash table API?

When it comes to a hash table, there are basically only two interesting operations from an API perspective: lookup and insertion 1. The standard library containers are all very consistent in how these operations are provided, across all the associative containers (maps and sets both, but I’ll just focus on maps):

That’s not the complete API for lookup or insertion, there’s some other functions for lookup (like equal_range and, finally, contains) and insertion (like other overloads that also take an iterator), but these are the crux of the API that everyone uses all the time.

On the plus side, the standard library containers are very consistent. They all offer the same API. Many user-defined containers have followed suit and also offer the same API. This is a big benefit, since it allows abseil’s hashtables to not even bother documenting their interface - you probably already know what it is 2.

Now, of these, find() is the only conditional lookup. map[key] always ends up with an element for that key, whether you had one before or not. And map.at(key) throws if the key isn’t there, but otherwise is nice to use. find() is the only choice for actually checking anything.

Leave a Comment