二次探测是避免哈希冲突的一种常见手段，思想是：
创新互联建站专注于卢龙企业网站建设,成都响应式网站建设公司,购物商城网站建设。卢龙网站建设公司,为卢龙等地区提供建站服务。全流程定制制作，专业设计，全程项目跟踪，创新互联建站专业和态度为您提供的服务
插入：
找到哈希位置（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;
};
如有疑问希望提出，有不足也希望指正
文章标题：【代码】key-value模式下的哈希二次探测与简单的哈希类的实现
浏览地址：
http://bzwzjz.com/article/pscidj.html
