Skip to main content
added 702 characters in body
Source Link
G. Sliepen
  • 61.7k
  • 3
  • 61
  • 152

One issue with r-value references is that they cannot bind to a const l-value. Consider writing this:

std::string key = "First Two";
auto firstTwo = table.Get(key);

This would fail to compile if Get() takes an r-value reference. A const reference parameter will take anything.

Furthermore, an empty std::list uses 24 bytes on a 64-bit architecture, and the moment you start using it, it will have to allocate memory to store the actual contents. Instead of using buckets, consider just using a single array of KeyValuePairs, and use open addressing to handle collisions. This does require that you can resize your hash table though.

Fix your hash function

GCC and Clang will warn about using the result of the assignment in the while-loop in hashFunction() as the condition. You could solve it by adding some parentheses, but I would rewrite it to proper C++ instead:

for (auto c: key)
    hash = ((hash << 5) + hash) + c; 

Also note that std::strings can contain an arbitrary number of NUL-characters.

Furthermore, an empty std::list uses 24 bytes on a 64-bit architecture, and the moment you start using it, it will have to allocate memory to store the actual contents. Instead of using buckets, consider just using a single array of KeyValuePairs, and use open addressing to handle collisions. This does require that you can resize your hash table though.

One issue with r-value references is that they cannot bind to a const l-value. Consider writing this:

std::string key = "First Two";
auto firstTwo = table.Get(key);

This would fail to compile if Get() takes an r-value reference. A const reference parameter will take anything.

Furthermore, an empty std::list uses 24 bytes on a 64-bit architecture, and the moment you start using it, it will have to allocate memory to store the actual contents. Instead of using buckets, consider just using a single array of KeyValuePairs, and use open addressing to handle collisions. This does require that you can resize your hash table though.

Fix your hash function

GCC and Clang will warn about using the result of the assignment in the while-loop in hashFunction() as the condition. You could solve it by adding some parentheses, but I would rewrite it to proper C++ instead:

for (auto c: key)
    hash = ((hash << 5) + hash) + c; 

Also note that std::strings can contain an arbitrary number of NUL-characters.

added 20 characters in body
Source Link
G. Sliepen
  • 61.7k
  • 3
  • 61
  • 152

Note that the STL containers don't return std::optionals. Of course, the STL containers themselves were designed way before std::optional was a thing. SomethingSometimes you know the item already exists, or maybe if you don't and it doesn't, you just want a default-constructed one. In those cases, operator[]() and at() do exactly what you want. A different function that returns a std::optional might be nice though, since the standard way to do the same with STL containers:

Note that the STL containers don't return std::optionals. Of course, the STL containers themselves were designed way before std::optional was a thing. Something you know the item already exists, or if it doesn't, you just want a default-constructed one. In those cases, operator[]() and at() do exactly what you want. A different function that returns a std::optional might be nice though, since the standard way to do the same with STL containers:

Note that the STL containers don't return std::optionals. Of course, the STL containers themselves were designed way before std::optional was a thing. Sometimes you know the item already exists, or maybe if you don't and it doesn't, you just want a default-constructed one. In those cases, operator[]() and at() do exactly what you want. A different function that returns a std::optional might be nice though, since the standard way to do the same with STL containers:

Source Link
G. Sliepen
  • 61.7k
  • 3
  • 61
  • 152

Make it look like std::unordered_map

When in Rome, do as the Romans do. In C++, if you are writing a container, it would be very nice if it has the same API as any other STL container. This avoids having to learn a different interface, and also makes it easier to use your container as a drop-in for an STL container without having to rewrite a lot of code that uses it. This is also part of making code more generic.

In particular, make sure the public member functions look like those of the closest matching STL container, which would be a std::unordered_map. So:

  • Change EmplaceBack() to emplace()
  • Consider changing Get() to operator[] which looks up or inserts.
  • Add other typical STL container functions, like clear(), size(), erase().

Note that the STL containers don't return std::optionals. Of course, the STL containers themselves were designed way before std::optional was a thing. Something you know the item already exists, or if it doesn't, you just want a default-constructed one. In those cases, operator[]() and at() do exactly what you want. A different function that returns a std::optional might be nice though, since the standard way to do the same with STL containers:

auto it = container.find(key);
if (it != container.end()) {
    auto &value = it->second;
    ...
}

...is quite annoying. Perhaps a better name than Get() could be used though, which hints that an optional value will be returned.

Passing a hash function

Passing a function as a template parameter limits the types of functions you can pass. The STL containers that take a hash function take this as a parameter to the constructor. You can do the same thing:

template < class KeyType, class ValueType, size_t nHashGroups, class HashFunction>
class BasicHash
{
public:
    BasicHash(const HashFunction& hashFunction = HashFunction()) :
        hashFunction(hashFunction) {}
    ...
private:
    size_t Hash(const KeyType& key)
    {
        return hashFunction(key) % nHashGroups;
    }
    ...
    HashFunction hashFunction;
};

The only drawback is that you have to pass the hash function as a function object, but that's not a problem if you use lambdas:

auto hashFunction = [](const std::string& key) -> size_t {
    ...
    return hash;
}
...
BasicHash<std::string, TwoNumberStore, 50, decltype(hashFunction)> table(hashFunction);

Another option would be to not make the hash function type a template parameter, but to pass the hash function using a std::function<size_t(const KeyType&)>. This has pros and cons; the advantage is that you don't need to specify the hash function type explicitly anymore, and you can pass a regular function to the constructor. The con is that there might be some performance overhead associated with std::function.

Pass by const reference where appropriate

You pass key to Get() and Hash() using an r-value reference. However, this is not necessary, since you are not going to move from it. It also might prevent some optimizations. Prefer using const reference whenever you want to pass a parameter you are not going to modify in any way.

Missing std::move() in the constructor of KeyValuePair

The constructor of KeyValuePair takes r-value references, but it just copies the values of the parameters into the member variables. You have to explicitly use std::move() to ensure the move constructor is used if possible:

KeyValuePair(KeyType&& key, ValueType&& value) :
    key(std::move(key)), value(std::move(value)) {}

Efficient storage of keys and values

Your hash table works well if you provide a good hash function and now up front how many elements you are going to store. However, it is usually hard to know exactly how much you are going to store up front, and therefore requiring nHashGroups to be specified as a template constant is either going to make the hash table too small, leading to large buckets and eventually \$O(N)\$ performance, or it is too large and you waste a lot of memory on empty buckets.

Consider making the size of the hash table dynamic. Let the user optionally reserve() a certain size if they do have a good estimate.

Furthermore, an empty std::list uses 24 bytes on a 64-bit architecture, and the moment you start using it, it will have to allocate memory to store the actual contents. Instead of using buckets, consider just using a single array of KeyValuePairs, and use open addressing to handle collisions. This does require that you can resize your hash table though.