#pragma once
创新互联公司成立10年来,这条路我们正越走越好,积累了技术与客户资源,形成了良好的口碑。为客户提供网站设计制作、网站建设、网站策划、网页设计、主机域名、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等,这些对于网站建设都非常重要,创新互联公司通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案,携手广大客户,共同发展进步。#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
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
:_tables(NULL)
, _status(NULL)
{
HashTable
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
{
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
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
{
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;
};
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。