#pragma once#include 
     
      #include 
      
       using namespace std; enum State{EMPTY,DELETE,EXIST,}; template
       
        struct __HashFunc // 产生键值(如把string的转化成数字) 默认的返回哈希键值key的 仿函数{size_t operator()(const K& key){return key;}}; template
        
         class HashTable{// Key形式的线性探测public:HashTable(size_t capacity = 10):_tables(new K[capacity]), _size(0), _capacity(capacity), _states(new State[capacity]){// memset 有问题 是以字节为单位初始化的 但第二个参数值为int// 会出问题 本来初始化为0x00000001 结果初始化为0x01010101//memset(_states, EMPTY, sizeof(State) * capacity);for (size_t i = 0; i < capacity; i++){_states[i] = EMPTY;}} ~HashTable(){if (NULL != _tables){delete[] _tables;_tables = NULL;} if (NULL != _states){delete[] _states;_states = NULL;}} bool Insert(const K& key){_CheckCapacity(); size_t index = _HashFunc(key); while (EXIST == _states[index])//对应键值存在数据的时候,就依次往后找空位置{index++;if (_capacity == index)//若已经等于容量时，就从头开始继续找空{index = 0;}} _tables[index] = key;   //对应键值不存在数据的时候，就往该位置放数据_states[index] = EXIST;_size++;return true;} int Find(const K& key){size_t index = _HashFunc(key);size_t start = index;// 存在 或者 被删除 两种状态while (EMPTY != _states[index]){if (_tables[index] == key){if (_states[index] == EXIST){return index;}else // 被删除 DELETE{return -1;}} index++; if (index == _capacity){index = 0;}// 找一圈 没找到就停止 防止死循环if (index == start){return -1;}} return -1;} bool Remove(const K& key){int index = Find(key);if (-1 != index){_states[index] = DELETE;--_size;return true;} return false;}  // 线性探测计算出存放位置（假设不哈希冲突）size_t _HashFunc(const K& key){__HashFunc
         
           hf;return hf(key) % _capacity; //  仿函数hf() } void Print(){for (size_t i = 0; i < _capacity; i++){if (EXIST == _states[i]){cout << i << "EXIST:" << _tables[i] << endl;}else if (DELETE == _states[i]){cout << i << "DELETE:" << _tables[i] << endl;}else{cout << i << "EMPTY" << _tables[i] << endl;}}} void Swap(HashTable
          
           & ht){swap(_size, ht._size);swap(_states, ht._states);swap(_tables, ht._tables);swap(_capacity, ht._capacity);} protected:void _CheckCapacity() // 扩容{// 动态的 可扩容的// 高效哈希表的载荷因子大概在0.7-0.8较好if (10 * _size / _capacity >= 7)  // _size/_capacity为0 因为都是××× 所以乘10// 保证载荷因子在0.7之内{HashTable
           
             tmp(2 * _capacity);for (size_t i = 0; i < _capacity; i++){if (EXIST == _states[i]){tmp.Insert(_tables[i]);}}Swap(tmp);}} protected:K* _tables;     //  哈希表State* _states; //  状态表size_t _size;size_t _capacity;}; void test(){ HashTable
            
              ht;ht.Insert(89);ht.Insert(18);ht.Insert(49);ht.Insert(58);ht.Insert(9);ht.Print();} int main(){test();system("pause");return 0;}