HashTable.cpp

typedef unsigned int uint;
#define Item List<Key, Value>
#define KEY_VALUE template <class Key, class Value>
#define FLL(a) for (Item *tmp = (a); tmp != NULL; tmp = tmp->next)

KEY_VALUE
struct List {
  Key k;
  Value value;
  Item *next;
};

KEY_VALUE
class HashTable {
  public:
    int size;
    Item **buckets;

    HashTable(int n) {
      size = n;
      buckets = new Item*[n];
    }

    ~HashTable() {
      for (int i = 0; i < size; i++)
        FLL(buckets[i])
          delete tmp;
    }

    Value & operator[](const Key key) {
      uint index = Hash(key);
      Item *tmp;

      FLL(buckets[index])
        if (key == tmp->k) return tmp->value;

      tmp = new Item;
      tmp->k = key;
      if (buckets[index] != NULL) tmp->next = buckets[index];
      buckets[index] = tmp;
      return tmp->value;
    }

  private:
    uint Hash(Key key) {
      uint value = 0;
      for (int i = 0; i < key.length(); i++)
        value = key[i] + (value << 5) - value;
      
      return value % size;
    }
};