Hash table.

Here, we implement and test a simple hash table that maps integers to integers (key -> value).

Here, collision resolution is done “by chaining”: all entries that should be put in the same bucket, are stored in a vector.

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

// Hash table entry. It's a pair (key, value)
struct Entry {
  int key;
  int val;
};

class Ht {
  private:
    vector< vector<Entry> > bkt;

    // Hash function
    // maps any integer to an integer in the range 0 ... bkt.size()-1
    int hash_fun(int k);

  public:
    Ht();
    Ht(int size);

    // add a pair (k,v) to the hash table
    void add(int k, int v);

    // find an entry for the key `k`
    // returns true if it's found, and then updates the variable `v`
    // with the value corresponding to the key `k`.
    //
    // if `k` is not found, returns false.
    bool find(int k, int &v);
};


int main() {

  Ht ht(50);

  ht.add(1234567, 1);
  ht.add(-1234567, 2);

  ht.add(105, 11);
  ht.add( 55, 12);
  ht.add(-45, 13);

  int test[6] = {1234567, -1234567, 105, 55, -45, 13};

  for (int i = 0; i < 6; i++) {
    int k = test[i];
    int v;
    if (ht.find(k, v))
      cout << k << " ->\t" << v << endl;
    else
      cout << k << " not found" << endl;
  }
}


// Implementation
int Ht::hash_fun(int k) {
  return abs(k) % bkt.size();
}

Ht::Ht() : bkt(1) { }

Ht::Ht(int s) : bkt(s) { }

void Ht::add(int k, int v) {
  int bi = hash_fun(k);
  for(unsigned int i = 0; i<bkt[bi].size(); i++) {
    if (bkt[bi][i].key == k) {
      bkt[bi][i].val = v;
      return;
    }
  }
  // if not found, add a new entry
  Entry e = {k, v};
  bkt[bi].push_back(e);
}

bool Ht::find(int k, int &v) {
  int bi = hash_fun(k);

  for(unsigned int i = 0; i<bkt[bi].size(); i++) {
    if (bkt[bi][i].key == k) {
      v = bkt[bi][i].val;
      return true;
    }
  }

  // if not found
  return false;
}

1234567 ->    1
-1234567 -> 2
105 ->  11
55 ->   12
-45 ->  13
13 not found