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

#pragma once

成都创新互联公司是一家业务范围包括IDC托管业务,网络空间、主机租用、主机托管，四川、重庆、广东电信服务器租用,德阳机房托管，成都网通服务器托管,成都服务器租用,业务范围遍及中国大陆、港澳台以及欧美等多个国家及地区的互联网数据服务公司。

#include

using namespace std;

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

{

EXITS,

DELETE,

EMPTY,

};

template

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//仿函数

struct HashFuner

{

size_t operator() (const K& key)

{

return key;

}

};

template<>//特化

struct HashFuner

{

size_t operator() (const string& key)

{

return BKDRHash(key.c_str());

}

};

template >

class HashTable

{

typedef KeyValueNode 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& ht)

:_tables(NULL)

, _status(NULL)

{

HashTable 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& operator=(HashTable 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 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& 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;

};