数据结构哈希表的闭散列基本实现

#pragma once

#include<string>

using namespace std;

enum Status//表示当前位置的状态

{

EXITS,

DELETE,

EMPTY,

};

template<class K,class V>

struct KeyValueNode//KV键值对

{

K _key;

V _value;

KeyValueNode(const K& key=K(), const V& value=V())

:_key(key)

, _value(value)

{}

};

static size_t BKDRHash(const char * str)//哈希算法

{

unsigned int seed = 131; // 31 131 1313 13131 131313

unsigned int hash = 0;

while (*str )

{

hash = hash * seed + (* str++);

}

return (hash & 0x7FFFFFFF);

}

template<class K>//仿函数

struct HashFuner

{

size_t operator() (const K& key)

{

return key;

}

};

template<>//特化

struct HashFuner<string>

{

size_t operator() (const string& key)

{

return BKDRHash(key.c_str());

}

};

template<class K,class V,class HashFun = HashFuner<K> >

class HashTable

{

typedef KeyValueNode<K, V> KVNode;

public:

HashTable()

: _tables(NULL)

, _capacity(0)

, _size(0)

, _status(0)

{}

HashTable(int capacity)

:_tables(new KVNode[capacity])

, _capacity(capacity)

, _size(0)

, _status(new Status[capacity])

{

for (int i = 0; i < capacity; ++i)

{

_status[i] = EMPTY;

}

}

HashTable(const HashTable<K, V>& ht)

:_tables(NULL)

, _status(NULL)

{

HashTable<K, V> newtable(ht._capacity);

for (int i = 0; i < _capacity; ++i)

{

_tables[i]._key = ht._tables[i]._key;

_tables[i]._value = ht._tables[i]._value;

_size = ht._size;

_status[i] = ht._status[i];

}

this->Swap(newtable);

}

HashTable<K, V>& operator=(HashTable<K, V> ht)

{

this->Swap(ht);

return *this;

}

~HashTable()

{

if (_tables)

{

delete[] _tables;

delete[] _status;

}

}

public:

bool Insert(const K& key, const V& value)

{

if (_capacity == _size)

{

HashTable<K,V> newtables(_capacity * 2 + 1);

for (size_t i = 0; i < _capacity; ++i)

{

if (_status[i] == EXITS)

{

size_t index = HashFunc0(_tables[i]._key);

while (newtables._status[i] == EXITS)

{

index = HashFunc2(index, i++);

}

newtables._tables[index] = KVNode(_tables[i]._key,_tables[i]._value);

newtables._status[index] = EXITS;

++_size;

}

}

this->Swap(newtables);

}

size_t index = HashFunc0(key);

int i = 1;

while (_status[index] == EXITS)

{

index = HashFunc2(index, i++);

}

_tables[index] = KVNode(key, value);

_status[index] = EXITS;

_size++;

return true;

}

bool Remove(const K& key)

{

size_t index = HashFunc0(key);

int i = 1;

while (_tables[index] != EMPTY)

{

if (_tables[index]._key == key)

{

if (_status[index] == EXITS)

{

--_size;

_status[index] = DELETE;

return true;

}

else

{

return false;

}

}

index = HashFunc2(index, i++);

}

return false;

}

KVNode* Find(const K& key)

{

size_t index = HashFunc0(key);

int i = 0;

while (_status[index] != EMPTY)

{

if (key == _tables[index]._key)

{

if (_status[index] == EXITS)

return &_tables[index];

else

return NULL;

}

index = HashFunc2(index, i++);

}

return NULL;

}

size_t HashFunc0(const K& key)

{

return HashFun()(key) % _capacity;

}

size_t HashFunc2(size_t prevValue, int i)

{

return (prevValue + 2 * i - 1) % _capacity;

}

void Swap(HashTable<K, V, HashFun>& ht)

{

swap(_tables, ht._tables);

swap(_status, ht._status);

swap(_size, ht._size);

swap(_capacity, ht._capacity);

}

protected:

KVNode* _tables;

int _capacity;

int _size;

Status* _status;

};