A sample implementation of a hash table in C++11.

hashtable.cpp

#include <iostream>
#include <random>

// The number of items to insert into the hash table in main()
#define ITEMS 32
// The size of the backing array for the hash table
#define HTSIZE 32

using namespace std;

class HashTable {
public:
    HashTable();
    ~HashTable();

    bool insert(int value);
    bool find(int value);

    string repr();

private:
    size_t hashF(int value);
    vector<int>* store[HTSIZE];
};

HashTable::HashTable() {
    // We don't have to do anything special to construct one of these.
}

HashTable::~HashTable() {
    // Free all the vectors in the store, or we'll leak memory
    cout << "Freeing vectors from store.\n";
    for (vector<int> * v : this->store) {
        cout << ".";
        if (v != nullptr) delete v;
    }
    cout << "\n";
}

// This is a really simple hash function which is guaranteed to lead to lots of collisions. Try
// replacing it with something more complex and see what happens.
size_t HashTable::hashF(int value) { return value % HTSIZE; }

// Inserts a new value into the hash table, returning true if it was added or false if it was not.
bool HashTable::insert(int value) {
    // This value is where it should go.
    size_t targetIndex = this->hashF(value);
    // This is a pointer to the place it should go. There should be a vector there.
    vector<int>* target = this->store[targetIndex];
    // Null pointer means make a new list and link it into the hashmap.
    if (target == nullptr) {
        target = new vector<int>();
        this->store[targetIndex] = target;
    }
    // Now target definitely points to the correct vector.
    // Look through the target vec to see if the target is there.
    for (auto item : *target) {
        // Finding the target means we can't add it; no duplicates are allowed.
        if (item == value) { return false; }
    }
    // Target is NOT there; put it in.
    target->push_back(value);
    return true;
}

// Return true if the given value is in the table, false otherwise.
bool HashTable::find(int value) {
    // This is where the value would be if it were in the table.
    size_t targetIndex = this->hashF(value);
    // target is a pointer to that location.
    vector<int> *target = this->store[targetIndex];
    // Null pointer means there's nothing there; give up.
    if (target == nullptr) { return false; }
    // Look through the target vec to see if the target is there.
    for (auto item : *target) {
        // Found the target!
        if (item == value) { return true; }
    }
    // Target is NOT there; give up.
    return false;
}

// Print a nice string representation of the table.
string HashTable::repr() {
    string s = string();
    int i = 0;
    for (vector<int> * v : this->store) {
        if (v == nullptr) { s += std::to_string(i) + ": .\n"; }
        else {
            s += std::to_string(i) + ": +";
            // Print the items
            for (int item : *v) {
                s += " " + std::to_string(item);
                item;
            }
            s += "\n";
        }
        i++;
    }
    return s;
}

int main() {
    cout << "Create new hash table, size " << std::to_string(HTSIZE) << "." << std::endl;
    auto ht = new HashTable();

    cout << "Adding " << std::to_string(ITEMS) << " items." << std::endl;
    for (int i = 0; i < ITEMS; i++) {
        int val = rand() % 1000;
        ht->insert(val);
    }
    cout << endl;

    cout << "Here's what's in the hash table." << std::endl;
    cout << ht->repr();

    delete ht;

}