Submit deadline: 16:00, 2 October 2024, Wednesday

What you need to accomplish in this lab:

Implement a hash table class with the following interface:

class HashTable // for open addressing
{
  public:
    HashTable();
    ~HashTable();
    void insert(int k, string e);
    string lookup(int k);
  private:
    const int N = 79;
    const int p = 1163;
    const int a = 7;
    const int b = 11;
    int hashing(int k);
    int probing(int step, int k)

    const int unoccupied = -2;
    const int removed = -1;
    int keyTable[N];
    string dataTable[N];
    int size;
    string probingType;
};

HashTable::HashTable()
{
    size = 0;
    probingType = "linear";
    for(int i = 0; i < N; i++)
        keyTable[i] = unoccupied;
}

int HashTable::hashing(int k)
{
    return ((a*k+b) % p) % N;
}

int HashTable::probing(int step, int k)
{
    if (probingType == "linear")
        return 1;
    else if (probingType == "quadratic")
        return step * step;
    else    // must be double hashing
        return (11*k+3)%7; // randomly picked a hash function
                           // reasonably assuming N > 7
}

// linear probing
void HashTable::insert(int k, string e)
{
    if (size >= N)
        throw except of "hash table full!";
    int index = hasing(k);
    int step = 0;
    while (keyTable[index] >= 0 && step < N ) { // cell index is occupied
        step++;
        index = (index + probing(step, k)) % N; // try next spot
    }
    if (step >= N)
        throw exception of "can't find a vacancy";
    else {
        keyTable[index] = k;
        dataTable[index] = e;
        size ++;
    }
}

string HashTable::lookup(int k)
{
    int index = hasing(k);
    int step = 0;

    while (keyTable[index] >= 0 && keyTable[index] != k
           || keyTable[index] == removed) { // cell index is not unoccupied
                                            // but key is not in the cell index
        step++;
        index = (index + probing(step, k)) % N; // try next spot
    }
    if (keyTable[index] == unoccupied)
        throw exception of "can't find the given key";
    else {
        return dataTable[index];
    }
}