Return to Answer

• 1

• 17.3k
• 4
• 31
• 89

Focusing mainly on the hash-table:

The main reason for using a hash-table-like data structure is to get constant-time (or near constant) lookup. When you decided to use a linked list for the backing-store of your hash-table, you lost that benefit. indexOfKey() is linear time. I would just throw that list out and use a std::vector as the backing store. Then there are several strategies you can use to resolve collisions. You can find an overview of each on Wikipedia.

If you're interested in leaning templates, use them for the table. Why limit it to integers only? The key type in a hash-table is often a string, but again, you don't have to be limited to that, the key type could also be templated.

I question the necessity for the hashmap_ function pointer and this:

int hashmap(int prehashedKey, int tableSize)
{
 return prehashedKey % tableSize;
}

Is there any other way to index into a hash-table other than the modulo operator? Not that I know of. I mean, you could use key & (size - 1) if the size is known to be power-of-two, but that's a micro optimization that the compiler is probably already doing. Remove that extra member function pointer and use % directly. It will make your code clearer and faster.

The hash function, which you call prehash_, could also be a template parameter. Take a leaf out of the C++ Standard Library's book, make it compatible with std::hash and you won't even have to provide a custom hasher for common types like integers and strings.

All in all, your HashTable should be looking something like this:

template
<
 class Key,
 class Val,
 class Hasher = std::hash<Key>
>
class HashTable
{
public:
 // your interface...
private:
 std::vector<Val> buckets;
};

Since the hasher is resolved at compiler time, you don't even need to store a copy of it, you can instantiate directly when applying it on a key:

static std::size_t hashOf(const Key & key)
{
 return Hasher{}(key);
}

Other general details and guidelines:

• When you're taking a potentially large object, such as a std::string, in a function parameter, and the function is only looking at the object without copying it, pass by const reference to avoid the copy. E.g.:

   bool search(const std::string & key) { ...
   ^^^^^ ^
  

Simple types like integers can be passed by value, of course. The hardware has built-in registers for those.

• const on a return type (const bool search(std::string key) const) is meaningless at best, but can prevent optimal code from being generated if applied to objects. Don't get into the habit of doing that.

• Node and LLNode seems like gratuitous obfuscation. Just make Node an inner private class of the linked list. No need at all for it to be a public type. Also, just leave next publicly visible. Having a get/set pair is just a verbose way of defining a public variable.

• Don't assign zero to pointers (like in here LLNode<T>* pp = 0;), not anymore, at least. Now there's the nullptr literal (since C++11).