#include<iostream>

using namespace std;

//哈希表的结点结构，可以存储键值对，哈希冲突产生的链表
template<typename keyType ,typename valueType>
struct HashNode{
    keyType _key;
    valueType _value;
    HashNode<keyType,valueType>* _next;

    HashNode(const keyType key,const valueType value){
        _key = key;
        _value = value;
        _next = nullptr;
    }
};

//哈希表类，规定属性有大小，一个用于动态创建hashNode的二级指针，构造函数，析构函数，哈希值计算，插入，删除，查找（bool）
template<typename keyType ,typename valueType>
class HashTable
{
private:
    size_t _size;
    HashNode<keyType,valueType> **table;
    keyType hash(const keyType& key);
public:
    HashTable(size_t size);
    ~HashTable();
    void insert(const keyType& key,const valueType& value);
    void remove(const keyType& key);
    bool find(const keyType& key);
    void print();
};

//构造
template<typename keyType ,typename valueType>
HashTable<keyType,valueType>::HashTable(size_t size)
{
    _size = size;
    table = new HashNode<keyType,valueType>*[_size];
    for(int i=0;i<_size;i++){
        table[i] = nullptr;
    }
}

//析构
template<typename keyType ,typename valueType>
HashTable<keyType,valueType>::~HashTable()
{
    for(int i;i<_size;++i){
       if(table[i]){
            HashNode<keyType,valueType>* cur = table[i]->_next;
            delete table[i];
            while(cur){
                HashNode<keyType,valueType>* temp = cur;
                cur = cur->_next;
                delete temp;
            }
        }   
    }
    delete[] table;
}

//哈希值
template<typename keyType ,typename valueType>
keyType HashTable<keyType,valueType>::hash(const keyType& key){
    int hash_key = key % _size;
    if(hash_key < 0) hash_key += _size;
    return hash_key;
}

//插入，传入待插键值对，用hash（）取得key，定位到相应位置，如果为空，则直接插入，如果不为空，采用链表头插
template<typename keyType ,typename valueType>
void HashTable<keyType,valueType>::insert(const keyType& key,const valueType& value){
    int index = hash(key);
    HashNode<keyType,valueType>* new_node = new HashNode<keyType,valueType>(key,value);
    if(table[index] == nullptr){
        table[index] = new_node;
    }else{
        new_node->_next = table[index];
        table[index] = new_node;
    }
}

template<typename keyType ,typename valueType>
void HashTable<keyType,valueType>::remove(const keyType& key){
    int index = hash(key);
    if(table[index]){
        HashNode<keyType,valueType>* cur = table[index];
        if(table[index]->_key == key){
            HashNode<keyType,valueType>* temp = table[index];
            table[index] = temp->_next;
            delete temp;
            return;
        }
        else{
            while (cur->_next && cur->_next->_key != key)
            {
                cur = cur->_next; 
            }
            if(cur->_value){
                HashNode<keyType,valueType>* temp = cur->_next;
                cur->_next = temp->_next;
                delete temp;
                return;
            }
            cout << "没有此键值对" << endl;
        }
    }
}

template<typename keyType ,typename valueType>
bool HashTable<keyType,valueType>::find(const keyType& key){
    int index = hash(key);
    if(table[index]){
         HashNode<keyType,valueType> *cur = table[index];
         while (cur)
         {
            if(cur->_key == key){
                return true;
            }
            cur = cur->_next;
         }
         return false;
         
    }
    return false;
}
template<typename keyType ,typename valueType>
void HashTable<keyType,valueType>::print(){
    for(int i = 0;i < _size;++i){
        cout << "槽" << i << ": {";
        if(table[i]){
            HashNode<keyType,valueType>* cur = table[i];
            while(cur){
                cout << "(" << cur->_key << "," << cur->_value << ") ";
                cur = cur->_next;
            }
            cout << "}" << endl;
        }else{
            cout << "NULL" << "}" << endl;
        }
    }
}

int main(){
    HashTable<char,int> ht(10);
    ht.insert('a',8);
    ht.insert(';',12);
    ht.insert('b',5);
    ht.insert('f',7);
    ht.insert('y',0);
    ht.insert('o',55);

    ht.print();

    ht.remove('o');
    cout << "------------------" << endl;
    ht.print();

    return 0;
}