C++手动实现HashTable

思路都写代码注释上了
头文件：

#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_
#include 
#include 
#include 
#include 


class Node {
 public:
  Node(int key = 0, int val = 0, bool isexit = false)
      : _key(key), _val(val), _isExit(isexit) {}
  int _key, _val;
  bool _isExit;
};

class HashTable {
 public:
  
  HashTable();
  
  int find(int val);
  
  void insert(int x);
  
  void erase(int x);
  
  int getval(int key);
  
  int getsize();
  
  int getcapcity();

 private:
  
  Node* _arry;
  
  int _size;
  
  int _capcity;
  
  float _factor;
  
  int _expansionFactor;
  
  bool isExpansion();
  
  void AutoExpansion();
  
  Node ReHash(Node& _arry1);
  
  void ReaseMemory(Node* tmp);
  
  int Hash1(int val);
  
  int Hash2(int val);
  
  int Hash3(int val);
  
  int Hash(int val);
};
#endif

#include "hashtable.h"



HashTable::HashTable() {
  _size = 0;
  _capcity = 10;
  _factor = 0.7;
  _arry = new Node[_capcity];
  _expansionFactor = 2;
}

HashTable::~HashTable() {
  if (_arry != nullptr) {
    delete[] _arry;
  }
}

bool HashTable::isExpansion() {
  float xs = 1.0 * _size / _capcity;
  return xs >= _factor;
}

Node HashTable::ReHash(Node& _arry1) {
  Node node(0, 0, false);
  node._val = _arry1._val;
  node._key = Hash(node._val);
  node._isExit = true;
  return node;
}

void HashTable::AutoExpansion() {
  int Len = _capcity;
  _capcity *= _expansionFactor;
  Node* arry = new Node[_capcity];
  Node* tmp = _arry;
  _arry = arry;
  for (int i = 0; i < Len; i++) {
    if (tmp[i]._isExit) {
      auto node = ReHash(tmp[i]);
      arry[node._key] = node;
    }
  }
  ReaseMemory(tmp);
}

void HashTable::ReaseMemory(Node* tmp) {
  delete[] tmp;
}

int HashTable::Hash1(int val) {
  int times = 3;
  int k = 1;
  while (times--) {
    val = (val + k * k + _capcity) % _capcity;
    k++;
  }
  return val;
}

int HashTable::Hash2(int val) {
  int times = 2;
  while (times--) {
    val = (val + 1 + _capcity) % _capcity;
  }
  return val;
}

int HashTable::Hash3(int val) {
  int times = 4;
  while (times--) {
    val = (val + times * 51 + _capcity) % _capcity;
  }
  return val;
}

int HashTable::Hash(int val) {
  int nowval = val;
  do {
    val = Hash1(Hash2(Hash3(val)));
  } while (_arry[val]._isExit && (nowval != _arry[val]._val));
  return val;
}



void HashTable::insert(int val) {
  Node node(0, 0, false);
  node._key = Hash(val);
  if (_arry[node._key]._isExit) {
    return;
  }
  node._val = val;
  node._isExit = true;
  _arry[node._key] = node;
  _size++;
  if (isExpansion()) {
    AutoExpansion();
  }
}

int HashTable::find(int val) {
  int key = Hash(val);
  return _arry[key]._isExit ? key : -1;
}

int HashTable::getval(int key) {
  return _arry[key]._val;
}

int HashTable::getsize() {
  return _size;
}

int HashTable::getcapcity() {
  return _capcity;
}

void HashTable::erase(int x) {
  int key = find(x);
  _arry[key] = Node{0, 0, false};
  _size--;
}

测试代码

#include 
#include 
#include 
#include "hashtable.h"
int main() {
  
  HashTable test;
  std::vector v(1000000, 0);
  std::vector _Ms(1000000, 0);
  for (int i = 0; i < 1000000; i++) {
    // v[i] = rand();
    test.insert(i);
  }
  for (int i = 0; i < 1000000; i++) {
    int start = clock();
    int a = test.find(i);
    int end = clock();
    _Ms[i] = end - start;
    if (test.getval(a) != i) {
      puts("-1");
    }
  }

  std::sort(_Ms.begin(), _Ms.end());
  std::cout << _Ms[_Ms.size() - 1] << std::endl;
  std::cout << test.getsize() << std::endl;
  test.erase(5);
  std::cout << test.find(5) << std::endl;
  std::cout << test.getsize() << std::endl;

  return 0;
}