这是c++11版本的代码#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int n)
{
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n)
{
if (n % 2 == 0)
++n;
for (; !isPrime(n); n += 2)
;
return n;
}
template <typename HashedObj>
class HashTable
{
public:
explicit HashTable(int size = 101) :array(nextPrime(size))
{
makeEmpty();
}
void makeEmpty()
{
currentSize = 0;
for (auto &entry : array)
entry.info = EMPTY;
}
bool contains(const HashedObj &x)const
{
return isActive(findPos(x));
}
bool insert(const HashedObj & x)
{
int currentPos = findPos(x);
if (isActive(currentPos))
return false;
array[currentPos].element = x;
array[currentPos].info = ACTIVE;
//if (++currentSize >= array.size() / 2)
//rehash();
return true;
}
bool insert(HashedObj && x)
{
HashedObj temp;
swap(temp, x);
return insert(temp);
}
bool remove(const HashedObj & x)
{
int currentPos = findPos(x);
if (!isActive(x))
return false;
array[currentPos].info = DELETED;
--currentSize;
return true;
}
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
HashedObj element;
EntryType info;
HashEntry(const HashedObj &e = HashedObj{}, EntryType i = EMPTY) :element{ e }, info{i}
{
cout << e << endl;
}
HashEntry(HashedObj &&e, EntryType i = EMPTY) :element{ std::move(e) }, info{i}
{
}
};
vector<HashEntry> array;
int currentSize;
bool isActive(int currentPos)const
{
return array[currentPos].info == ACTIVE;
}
int findPos(const HashedObj &x)const
{
int offset = 1;
int currentPos = myhash(x);
while (array[currentPos].info != EMPTY && array[currentPos].element != x)
{
currentPos += offset;
offset += 2;
if (currentPos >= (int)array.size())
currentPos -= array.size();
}
return currentPos;
}
size_t myhash(const HashedObj &x)const
{
static hash<HashedObj> hf;
return hf(x) % array.size();
}
//void rehash();
};
int main()
{
vector<int> a;
HashTable<vector<int> *> b;
}
|