【C++】 哈希 (上)

#pragma once
#include<vector>
#include<iostream>
using namespace std;
enum State //表示三种状态
{
  EMPTY, //空
  EXIST,//存在
  DELETE//删除
};
template<class K,class V>
struct HashData
{
  pair<K, V>_kv;//对应的KV 数据
  State _state=EMPTY;//表示状态
};
template<class K,class V>
class HashTable
{
public:
  bool insert(const pair<K, V>& kv) //插入
  {
    //若数据已经有了，就不要插入了
    if (Find(kv.first))
    {
      return false;
    }
    //负载因子超过0.7就扩容
    if (_tables.size()==0 || _n * 10 / _tables.size() >= 7)
    {
      size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; 
      HashTable<K, V> newht;
      newht._tables.resize(newsize); //将newht中的_tables 进行扩容
      //遍历旧表，重新映射到新表
      for (auto & data : _tables)
      {
        newht.insert(data._kv);//将旧表数据进行插入newht中
      }
      //将_tables 更新为newht中的数据
      _tables.swap(newht._tables);
    }
    //key值%当前表的长度
    size_t hashi = kv.first % _tables.size();
    //线性探测
    size_t i = 1;
    size_t index = hashi;
    while (_tables[index]._state == EXIST)//若当前位置值存在，则继续往后走
    {
      //加i是因为有可能后面的位置被占用，则需要找到一个没有被占用的位置
      index = hashi + i;
      //为了针对绕过去的情况
      index %= _tables.size();
      i++;//i的值从1开始 依次递增
    }
    _tables[index]._kv = kv;//填入数据
    _tables[index]._state = EXIST;//设置为存在状态
    _n++;
    return true;
  }
  HashData<K, V>* Find(const K& key)//查找
  {
    if (_tables.size() == 0)
    {
      return false;
    }
    size_t hashi = key % _tables.size();
    //线性探测
    size_t i = 1;
    size_t index = hashi;
    while (_tables[index]._state != EMPTY)
    {
      if (_tables[index]._state==EXIST&&_tables[index]._kv.first == key)//找到
      {
        return   &_tables[index];
      }
      //加i是因为有可能后面的位置被占用，则需要找到一个没有被占用的位置
      index = hashi + i;
      index %= _tables.size();
      i++;//i的值从1开始 依次递增
      //表里全是删除/存在状态的数据
      if (index == hashi)
      {
        break;
      }
    }
    return nullptr; 
  }
  bool Erase(const K& key)
  {
    HashData<K, V>* ret = Find(key);
    if (ret)
    {
      ret->_state == DELETE;
      --_n;
      return true;
    }
    else
    {
      return false;
    }
  }
private:
  vector<HashData<K,V>> _tables;
  size_t _n = 0; // 存储的数据个数
}; 
void hashtest()
{
  int a[] = { 3,33,2,13,5,12,1002 };
  HashTable<int, int>v;
  for (auto e : a)
  {
    v.insert(make_pair(e, e));
  }
}