HashTable.cpp

template<typename K, typename V, typename HashFunc = std::hash<K>>
class HashTable {
public:
    HashTable() {
        curr_size = 0;
        load_factor = 1.0;
        capacity = 101;
        slots = new Slot[capacity];
    }

    ~HashTable() {
        delete[] slots;
    }

    void insert(const pair<K, V> &p) {
        int index = getSlotIndex(p.first);
        Slot &slot = slots[index];
        // case 1: already exists
        for (Iterator iter = slot.begin(); iter != slot.end(); iter++)
            if (iter->first == p.first) {
                iter->second = p.second;
                return;
            }
        // case 2: new
        ++curr_size;
        if (curr_size > capacity * load_factor) { // overloaded
            rehash();
            index = getSlotIndex(p.first);
            slot = slots[index];
        }
        slot.push_front(p);
    }

    V& operator[](const K &key) {
        int index = getSlotIndex(key);
        Slot &slot = slots[index];
        // case 1: already exists
        for (Iterator iter = slot.begin(); iter != slot.end(); iter++)
            if (iter->first == key)
                return iter->second;
        // case 2: new
        ++curr_size;
        if (curr_size > capacity * load_factor) { // overloaded
            rehash();
            index = getSlotIndex(key);
            slot = slots[index];
        }
        slot.push_front(make_pair(key, V()));
        return slot.front().second;
    }

    bool contains(const K &key) {
        int index = getSlotIndex(key);
        Slot &slot = slots[index];
        for (Iterator iter = slot.begin(); iter != slot.end(); iter++)
            if (iter->first == key)
                return true;
        return false;
    }

private:
    size_t getSlotIndex(const K &key) {
        return hash(key) % capacity;
    }

    void rehash() {
        int old_capacity = capacity;
        Slot *old_slots = slots;
        capacity = getNextPrime(curr_size); // find next prime as new capacity
        slots = new Slot[capacity];
        for (int i = 0; i < old_capacity; i++) { // copy all
            Slot &slot = old_slots[i];
            for (Iterator iter = slot.begin(); iter != slot.end(); iter++) {
                int new_index = getSlotIndex(iter->first);
                Slot &new_slot = slots[new_index];
                new_slot.push_front(*iter);
            }
        }
        delete[] old_slots;
    }

    int getNextPrime(int n) {
        // TO BE IMPLEMENTED!
        return n;
    }

private:
    int curr_size;
    double load_factor;
    int capacity;
    list<pair<K, V>> *slots;
    HashFunc hash;

    typedef list<pair<K, V>> Slot;
    typedef typename Slot::iterator Iterator;
};