#pragma once

成都創(chuàng)新互聯(lián)公司是一家業(yè)務(wù)范圍包括IDC托管業(yè)務(wù),網(wǎng)絡(luò)空間、主機(jī)租用、主機(jī)托管，四川、重慶、廣東電信服務(wù)器租用,德陽(yáng)機(jī)房托管，成都網(wǎng)通服務(wù)器托管,成都服務(wù)器租用,業(yè)務(wù)范圍遍及中國(guó)大陸、港澳臺(tái)以及歐美等多個(gè)國(guó)家及地區(qū)的互聯(lián)網(wǎng)數(shù)據(jù)服務(wù)公司。

#include

using namespace std;

enum Status//表示當(dāng)前位置的狀態(tài)

{

EXITS,

DELETE,

EMPTY,

};

template

struct KeyValueNode//KV鍵值對(duì)

{

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//仿函數(shù)

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;

};