二次探测是避免哈希冲突的一种常见手段，思想是：
为渭南等地区用户提供了全套网页设计制作服务，及渭南网站建设行业解决方案。主营业务为
成都网站设计、成都网站制作、渭南网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
插入：
找到哈希位置（serch）->如果不冲突就插入，冲突就进行第一次探测
第1次探测：
哈希位置变为原有哈希位置加上1*1的偏移->进行插入
....
....
第i次探测：
哈希位置变为原有哈希位置加上i*i的偏移->进行插入
知道插入完成为止。
如图所示：
哈希类代码如下：
#pragma once
#include
#include
enum Status
{
DELETE,
EMPTY,
EXIST,
};
template
struct KV
{
KV()
{}
KV(K _key, V _value)
:key(_key)
, value(_value)
{}
Status s;
K key;
V value;
};
template
struct DefaultHash
{
size_t operator()(const K& k)
{
return k;
}
};
template<>
struct DefaultHash
{
size_t operator()(const string&k)
{
size_t ret = 0;
for (size_t i = 0; i < k.size(); ++i)
{
ret *= 10;
ret += k[i];
}
return ret;
}
};
template >
class HashTable
{
public:
HashTable(size_t capacity)
:tables(new KV[capacity])
,_size(0)
, _capacity(capacity)
{
for (size_t i = 0; i < _capacity; ++i)
{
tables[i].s = EMPTY;
}
}
HashTable()
:_size(0)
, _capacity(0)
{}
void Push(const KV &x)
{
size_t index = search(x.key);
tables[index].s = EXIST;
tables[index].key = x.key;
tables[index].value = x.value;
++_size;
}
void Print()
{
for (size_t i = 0; i < _capacity; ++i)
{
cout << i << ":";
if (tables[i].s == EXIST)
cout <<"["<= _capacity)
index %= _capacity;
}
return -1;
}
void Pop(const K& key)
{
int index = Find(key);
if (index > 0)
{
tables[index].s = DELETE;
_size--;
}
}
~HashTable()
{
if (tables)
delete[]tables;
_size = 0;
_capacity = 0;
}
protected:
size_t search(K key)
{
if (_size * 2 >= _capacity)
{
HashTable tmp(_capacity * 2 + 10);
for (size_t i = 0; i < _capacity; ++i)
{
if (tables[i].s == EXIST)
tmp.Push(tables[i]);
}
std::swap(tables, tmp.tables);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
}
Hash Search;
size_t index = Search(key)%_capacity;
size_t i = 0;
while (tables[index].s == EXIST)
{
i++;
index += i*i;
if (index >= _capacity)
index %= _capacity;
}
return index;
}
protected:
KV* tables;
size_t _size;
size_t _capacity;
};
如有疑问希望提出，有不足也希望指正
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
标题名称：【代码】key-value模式下的哈希二次探测与简单的哈希类的实现-创新互联
本文路径：
http://jkwzsj.com/article/copdeo.html
