二次探测是避免哈希冲突的一种常见手段，思想是：
插入：
找到哈希位置（serch）->如果不冲突就插入，冲突就进行第一次探测
第1次探测：
哈希位置变为原有哈希位置加上1*1的偏移->进行插入
....
....
第i次探测：
哈希位置变为原有哈希位置加上i*i的偏移->进行插入
知道插入完成为止。
如图所示：
哈希类代码如下：
#pragma once
#include<vector>
#include<string>
enum Status
{
DELETE,
EMPTY,
EXIST,
};
template<class K, class V>
struct KV
{
KV()
{}
KV(K _key, V _value)
:key(_key)
, value(_value)
{}
Status s;
K key;
V value;
};
template<class K>
struct DefaultHash
{
size_t operator()(const K& k)
{
return k;
}
};
template<>
struct DefaultHash<string>
{
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 K,class V,
class Hash = DefaultHash<K> >
class HashTable
{
public:
HashTable(size_t capacity)
:tables(new KV<K,V>[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<K,V> &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 <<"["<<tables[i].key<<","<< tables[i].value<<"]";
else
cout << "NULL";
cout << endl;
}
cout << endl;
}
int Find(const K& key)
{
Hash Search;
int index = Search(key) % _capacity;
size_t i = 0;
while (tables[index].s != EMPTY)
{
if (tables[index].key == key&&tables[index].s == EXIST)
return index;
i++;
index += 2*i-1;
if (index >= _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<K,V>* tables;
size_t _size;
size_t _capacity;
};如有疑问希望提出，有不足也希望指正
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
