开散列表

实现的结构和闭散列表完全一致，由于开散列表没有扩容机制，因此在创建散列表时要大概估计适合的散列表大小。

另外就是理论上插入到同一个散列表的键值是不能重复的，否则会造成查询和删除时的错误。（leetcode第一题两数之和是可能存在重复键值的，要考虑如何做特殊处理）

#include 
using namespace std;

template<class KEY, class VALUE>
struct PAIR{
    KEY key;
    VALUE value;

    PAIR(){}
    PAIR(KEY k, VALUE v):key(k), value(v){}
};


template<class KEY, class VALUE>
class dynamicSearchTable{
public:
    virtual PAIR* find(const KEY &x) const = 0;
    virtual bool insert(const PAIR &x) = 0;
    virtual bool remove(const KEY &x) = 0;
    virtual ~dynamicSearchTable(){};
};


template<class KEY, class VALUE>
class openHashTable:public dynamicSearchTable{
private:
    struct node{
        PAIR data;
        node* next;

        node(){next = NULL;}
        node(const PAIR &x, node* n = NULL){
            data = x; next = n;
        }
    };

    node** array;
    int size;
    int (*Hash)(const KEY &x);
    static int defaultHash(const KEY &x){return int(x);}

public:
    openHashTable(int s = 101, int (*f)(const KEY &x) = defaultHash);
    ~openHashTable();
    PAIR* find(const KEY &x) const;
    bool insert(const PAIR &x);
    bool remove(const KEY &x);
};

template<class KEY, class VALUE>
openHashTable::openHashTable(int s, int (*f)(const KEY &x)){
    size = s;
    array = new node* [size];
    Hash = f;
    for(int i= 0; i < size; ++i) array[i] = NULL;
}


template<class KEY, class VALUE>
openHashTable::~openHashTable(){
    node *p, *q;

    for(int i = 0; i < size ;++i){
        p = array[i];
        while( p != NULL){q = p->next; delete p; p = q;}
    }
    delete []array;
}


template<class KEY, class VALUE>
PAIR* openHashTable::find(const KEY &x) const{
    int pos = Hash(x) % size;
    node* p = array[pos];

    while(p != NULL && p->data.key != x) p = p->next;
    if(p == NULL) return NULL;
    else return (PAIR*)p;
}


template<class KEY, class VALUE>
bool openHashTable::insert(const PAIR &x){
    int pos = Hash(x.key) % size;
    array[pos] = new node(x, array[pos]);
    return true;
}


template<class KEY, class VALUE>
bool openHashTable::remove(const KEY & x){
    int pos = Hash(x) % size;
    node *p, *q;

    if(array[pos] == NULL) return false;
    p = array[pos];
    if(array[pos]->data.key == x){
        array[pos] = array[pos]->next;
        delete p;
        return true;
    }

    while(p->next != NULL && p->next->data.key != x)
        p = p->next;
    if(p->next != NULL){
        q = p->next;
        p->next = q->next;
        delete q;
        return true;
    }
    return false;
}