10
\$\begingroup\$

I'm trying to brush up on my algorithms and data structures and wrote a fixed sized hash map assuming both key and value will be only integers. This is a significant simplification of the real case and is supposed to be so. Any comments regarding bugs, best practices, style is gladly appreciated.

#include <vector>
#include <iostream>
#include <exception>
#include <stdexcept>
#include <assert.h>
#define SIZE 10

class HashEntry {
public:
    int _k;
    int _v;
    HashEntry(int k, int v) : _k(k), _v(v) {};
};

class HashMap {
private:
    std::vector<HashEntry> buckets[SIZE];
    int hashFunc(int key);
    std::vector<HashEntry>& getBucket(int key);

public:
    bool keyExists(int k);
    HashEntry get(int k);
    bool put(int k, int v);
    bool remove(int k);
};

int HashMap::hashFunc(int key) {
    return key % SIZE;
}

std::vector<HashEntry>& HashMap::getBucket(int key) {
    if (key < 0) {
        throw std::runtime_error("key should be >= 0");
    }
    return buckets[hashFunc(key)];
}

HashEntry HashMap::get(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    for (HashEntry entry : bucket) {
        if (entry._k == k) {
            return entry;
        }
    }
    throw std::runtime_error("Key not found");
}
bool HashMap::keyExists(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    for (HashEntry entry : bucket) {
        if (entry._k == k) {

            // key already exists
            return true;
        }
    }
    return false;
}

bool HashMap::put(int k, int v) {
    std::vector<HashEntry>& bucket = getBucket(k);
    if (keyExists(k)) return false;
    bucket.push_back(HashEntry(k, v));
    return true;
}

bool HashMap::remove(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    if (!(keyExists(k))) return false;
    for (auto itr = bucket.begin(); itr != bucket.end(); ++itr) {
        HashEntry entry = static_cast<HashEntry>(*itr);
        if (entry._k == k) {
            bucket.erase(itr);
            return true;
            break;
        }
    }
    return false;
}

int main() {
    HashMap map;
    for (int i=0; i < 10; ++i) {
        assert(map.put(i, i*10));
    }
    for (int i=0; i < 10; ++i) {
        assert(map.keyExists(i) == true);
    }
    assert(map.keyExists(0) == true);
    assert(map.get(0)._v == 0);
    assert(map.remove(0) == true);
    assert(map.remove(0) == false);
    assert(map.keyExists(0) == false);

    bool exceptionThrown = false;
    try {
        map.get(0);
    } catch (std::exception &e) {
        exceptionThrown = true;
    };
    assert(exceptionThrown);
    return 1;
}
\$\endgroup\$
6
\$\begingroup\$

I would nest HashEntry inside of HashMap as just Entry since it's not very likely to ever stand on its own.


The _ prefix is a bit dangerous as the standard reserves the underscore prefix in a few situations (though not this situation). Still though, it's a bit awkward for it to be there not only in case of bad habits, but also because it serves no purpose. And, map.get(3)._k reads a little oddly.

I would call them key and value. It's just a few more characters to type, and it makes the code read a lot clearer (map.get(3).key).


hashFunc is a bit of an odd name. I would just call it hash instead since it's clearly a function.


std::invalid_argument fits a bit better in getBucket than runtime_error does. The more the type of an exception can tell you, the better (in general -- don't take it to an extreme).


for (HashEntry entry : bucket) {

It probably doesn't matter in practice since HashEntry's are fairly cheap, but this creates a copy of each bucket entry. If HashEntry weren't guaranteed to be such a trivial type, this could be devastating to performance. It should be for (const HashEntry& entry : bucket) {.


Any method that doesn't permute that map should be const (keyExists, get, getBucket). Const correctness is an important part of C++, and it should always be kept in mind when designing/implementing classes.


Why does main return 1? It seems the flow that reaches main is a successful execution, which means that the return value should be 0 (or EXIT_SUCCESS).


You do a lot of the same "loop over and find the correct bucket slot" logic. That should be pulled into a function. That can be done by either making a Bucket type that has the concept searching built in, or, more simply, just write a function that loops over a vector<HashEntry> and returns an iterator to the HashEntry (or end()).


When possible, constants in the form of macros should typically be avoided in favor of const constants. const int SIZE = 10 -- or, since it's being used an array size/index, you might find const std::size_t SIZE = 10; more fitting (I would just stick with an int).

Macros do not have a type, and their names are typically lost as debugging symbols. A const variable has either of those drawbacks, and it also doesn't sacrifice anything.


Since getBucket is a very straightforward constant time operation, it doesn't really matter, but containers activate my super picky mode with regards to performance :).

Try to avoid doing the same work twice. For example, consider your implementation of put. It calls getBucket and it calls keyExists, which behind the scenes calls getBucket. This implies that it might be good to have an additional method behind the scenes and leverage that for checking if keys exists:

bool HashMap::keyExists(const std::vector<HashEntry>& bucket, int k) const {
    for (const HashEntry& entry : bucket) {
        if (entry.key == k) {
            return true;
        }
    }
    return false;
}

bool HashMap::keyExists(int k) const {
    return keyExists(getBucket(k), k);
}

bool HashMap::put(int k, int v) {
    std::vector<HashEntry>& bucket = getBucket(k);
    if (keyExists(bucket, k)) return false;
    bucket.push_back(HashEntry(k, v));
    return true;
}

While I'm being a bit performance paranoid, it would also be better to call getBucket after keyExists in your current implementation. That way, for the case when keys don't exist, you don't bother doing the work of getting the bucket.


HashEntry entry = static_cast<HashEntry>(*itr);

Is this cast necessary? I can't imagine that it is. Also, HashEntry entry = static_cast<HashEntry>(*itr) should be const HashEntry& entry = ... (and really it should be const HashEntry& entry = *itr; or const auto& entry = *itr;).

I also wouldn't bother deferencing the iterator:

if (itr->key == k) {
    bucket.erase(itr);
    return true;
}

A break; immediately following a return is just noise. Since the function has already been exited, the loop will have been too.


In the spirit of more performance paranoia, it would be nice to allow a single operation for both checking the existence of a key and retrieving the value of it if it does exist. This allows you to avoid the same loop over the bucket twice.

Something like bool find(int key, int& value); or std::pair<bool, int> find(int key) would do the trick (provided it was implemented to take advantage of the ability to do only a single pass).

If you had the concept of an iterator, you could also do this in the form of having a find() that returns an iterator either to the element or to the end(). It's actually a bit icky to do this without iterators since you don't really have anything meaningful to return if you want to avoid a reference parameter. You would have to have either a std::pair<bool, int*> will a null value, or you'd have to have a junk value in the int component of a std::pair<bool, int>. With an int, the junk value approach works pretty well since you can just throw a 0 in it, but if this were to become generic, it becomes more of a concern.


The key in HashEntry should be const since it should never change after construction. Currently this doesn't matter, but if you were ever to return a reference to the HashEntry so that the value could be changed, it would be necessary to maintain the contract of the map. This is why the value_type of std::map<K, V> and std::unordered_map<K, V> is std::pair<const K, V> instead of std::pair<K, V>.


You probably realize this already, but this HashMap is not really a hash map in the strict sense. In particular, it does not honor the expected O(1) lookup and insertion run times. Instead, all of the meaningful operations are all O(n). The unbounded linear scans over the vectors kill it.

There are essentially three main components to a hash table: look up, insertion, and deletion.

The run time of insertion is of course T(lookup) + T(insertion), and with deletion, it's T(lookup) + T(deletion). This means that lookup, insertion, and deletion all have to be constant time operations for insertion and deletion to be constant time.

This means that hashing must be constant time, and it means that whatever is done in the case of a collision must be constant time. In your case, the buckets grow indefinitely, so the lookup across them is linear time. Provided randomly distributed data (which is likely to happen, but bear with me), if you have n keys and S buckets, each bucket will have n/S items in it. A linear scan over that is O(n/S) = O(1) time for constant S.

The easiest solution to this is to make S non-constant. How you do this actually turns out to be relatively important since pathological cases can exploit most approaches. For example, ensuring S >= N/c for some constant c gives you a decent average case, but if keys are not distributed well across buckets, you're essentially back to linear scans.

Another approach might be to decide that whenever a bucket goes over a certain size, double the size of buckets. This would work well at first glance since it would mean resizing and rehashing the map rarely, but once again, pathological cases could purposely target the same bucket so a relatively small amount of keys could cause a hugely sparse map. (Provided the bucket size case was constant, a linear number of keys could cause quadratic growth in the number of buckets).

So, where am I going with this? Go find a well known, well understood, commonly used approach to implementing a hash map, and implement it. I might do linear probing since it's pretty easy to implement and it's relatively drawback free. Other viable approaches can be found on Wikipedia, in a well known implementation (e.g. clang or gcc's unordered_map, or Oracle Java's java.util.HashMap), or in an algorithms text book.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. These are very helpful. I noticed that my operations are O(n) as well. I need to work on my coding more. \$\endgroup\$ – dev_nut Oct 23 '14 at 2:32
  • \$\begingroup\$ While allowing any integer to be a key, could you point out a way to make insert/lookup to be O(1)? \$\endgroup\$ – dev_nut Oct 23 '14 at 2:49
  • \$\begingroup\$ @dev_nut I started to cram it into a comment, but I ended up rambling on and on, so I edited the answer to have a bit on it :). The short version is that it's more difficult than it seems like it should be. The high level idea is to scale the size of the map proportional to the number of keys. How exactly to do that varies wildly. \$\endgroup\$ – Corbin Oct 23 '14 at 3:16
5
\$\begingroup\$

Corbin has provided a pretty comprehensive answer.

The part that I immediatley noticed though is the accessible HashEntry class, and how it is leaked through using the get() method.

Your hash is a mapping of a key to a value. Your put method is bool put(int,int), and to be symmetrical, the get should be int get(int)

Your get returns the HashEntry which should never be released. Because you do that, people can mess up your entry because the _k and _v are public too.

The get should return int, and you should establish a protocol that allows you to determine whether the key did not exist (return 0?) or whether it exists (the keyExists(int) can be a double-check).

\$\endgroup\$
  • \$\begingroup\$ Ah, glad you added this. If we want to go all the way, it could be int& get(int). Currently there's no way to change a value in the map without removing it and reinserting. \$\endgroup\$ – Corbin Oct 23 '14 at 2:02
  • \$\begingroup\$ When you say I should establish a protocol to check whether the key did not exist, do you mean something other than keyExists(int)? \$\endgroup\$ – dev_nut Oct 23 '14 at 2:34
  • \$\begingroup\$ You need to return a value from the get() even if the key is not there. So, you need to document what that is. The logical value is 0 (false), so you can link a false return from the get() to a false return from keyExists(). You only need to call keyExists on a possibly-failed get(). If the system is established through documentation I often call it a 'protocol'.... \$\endgroup\$ – rolfl Oct 23 '14 at 2:37
  • \$\begingroup\$ At first I wanted to return int from get(), and return -1 when no value exists. But, I thought this might be confusing since -1 can also be a valid value. So, I threw an exception if there is no valid value. So, while everything you point is valid I'm not so sure about returning 0, if no value exists. Maybe, just throwing an exception if there is no key would be a better and get better performance. \$\endgroup\$ – dev_nut Oct 23 '14 at 2:54
  • 2
    \$\begingroup\$ I agree that a sentinel return is a bad idea. It's convoluted in it's special-case-ness, and in the generic case, it doesn't work. Instead, @dev_nut, I would suggest you either continue throwing an exception, you insert a default value into the map and return a reference to the newly created item, or you either have an output parameter (i.e. bool get(int key, int& val)), or you return an indirection like int* get(int key)). These all happen to be the approaches the standard maps use (except an iterator instead of a pointer) in at, operator[] and find, respectively. \$\endgroup\$ – Corbin Oct 23 '14 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.