Cài đặt Hash Table với Quadratic Probing trong C++

Cấu trúc

• Mảng các entry: key, state (EMPTY/LEGITIMATE/DELETED).
• Kích thước bảng là số nguyên tố (giảm va chạm).

Ví dụ minh họa

#include <iostream>
#include <cstdlib>
using namespace std;

#define TABLE_SIZE 10
enum State { EMPTY, LEGIT, DELETED };

struct Entry { int key; State info; };

class HashTable {
    Entry *table; int size;
    bool isPrime(int n) { if(n<2) return false; for(int i=2;i*i<=n;i++) if(n%i==0) return false; return true; }
    int nextPrime(int n) { while(!isPrime(n)) n++; return n; }
    int hash(int k) { return k % size; }
    int findPos(int k) {
        int pos = hash(k), coll = 0;
        while (table[pos].info != EMPTY && table[pos].key != k) {
            pos += 2*++coll - 1; // i^2 = (i-1)^2 + 2i-1
            if (pos >= size) pos -= size;
        }
        return pos;
    }
public:
    HashTable(int s) : size(nextPrime(s)) { table = new Entry[size](); }
    ~HashTable() { delete[] table; }
    void Insert(int k) {
        int pos = findPos(k);
        if (table[pos].info != LEGIT) { table[pos].key = k; table[pos].info = LEGIT; }
    }
    void Remove(int k) {
        int pos = findPos(k);
        if (table[pos].info == LEGIT) table[pos].info = DELETED;
    }
    void Display() {
        for (int i=0; i

Kết quả (đoạn)
Pos 0: EMPTY
Pos 1: 11
Pos 2: 1
Pos 3: 2
Pos 4: 3
Pos 5: 4
Pos 6: 5
Pos 7: 6
Pos 8: 7
Pos 9: 8
Pos 10: 9
Pos 11: 10
...
Sau xoa 1:
Pos 2: DELETED
...
Sau chen 20:
Pos 0: 20
...