上篇博客我写的是用线性探测来解决哈希表。http://10739316.blog.51cto.com/10729316/1771958
创新互联公司专业为企业提供
涟源网站建设、涟源做网站、涟源网站设计、涟源网站制作等企业网站建设、网页设计与制作、涟源企业网站模板建站服务，十余年
涟源做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
下面我在介绍另一种解决哈希表的方法，开链法，也叫哈希桶。下面我介绍一下这种方法的思路。
基本思路：
1.先给一个数组，这个数组中存的是指针数组，每个指针数组都指向一个数组。
2.用元素除以存储指针数组的数组的大小。
3.余数与指针数组下标相同的，都链到数组指针指向的这一个数组。
我在进一步用图表示一下：
代码如下：
HashTable.h中
#pragma once
#include
template
struct HashTableNode
{
K _key;
V _value;
HashTableNode* _next;
HashTableNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _next(NULL)
{}
};
template
class HashTable
{
typedef HashTableNode Node;
public:
//拷贝构造
HashTable()
:_table(NULL)
, _size(0)
{}
//拷贝构造
HashTable(const HashTable& ht)
{
_table.resize(ht._table.size());
for (int i = 0; i < ht._table.size(); i++)
{
Node* cur = ht._table[i];
while (cur)
{
Node* tmp = new Node(cur->_key, cur->_value);
tmp->_next = _table[i];
_table[i] = tmp;
_size++;
cur = cur->_next;
}
}
}
//赋值运算符的重载
HashTable operator=( HashTable ht)
{
if (this != &ht)
{
swap(_table, ht._table);
swap(_size, ht._size);
}
return *this;
}
//析构函数
~HashTable()
{
if (_table.size())
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
}
}
}
bool Insert(const K& key, const V& value)
{
//是否需要扩容
if (_size == _table.size())
{
_ExpandCapatity();
}
size_t index = _HashFunc(key);
Node* cur = _table[index];
//防冗余
while (cur)
{
if (cur->_key == key)
{
return false;
}
cur = cur->_next;
}
//插入节点
Node* tmp = new Node(key, value);
tmp->_next = _table[index];
_table[index] = tmp;
_size++;
return true;
}
Node* Find(const K& key)
{
size_t index = _HashFunc(key);
Node* cur = _table[index];
while (cur)
{
if (cur->_key == key)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
bool Remove(const K& key)
{
size_t index = _HashFunc(key);
Node* cur = _table[index];
Node* prev = NULL;
//找到要删除的元素
while (cur)
{
if (cur->_key == key)
{
break;
}
prev = cur;
cur = cur->_next;
}
if (cur)
{
//头删
if (cur == _table[index])
{
_table[index] = cur->_next;
}
//删除中间元素
else
{
Node* next = cur->_next;
prev->_next = next;
}
delete cur;
cur = NULL;
_size--;
return true;
}
return false;
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
cout << i << ":";
while (cur)
{
cout << cur->_key << " ";
cout << cur->_value << " ";
cur = cur->_next;
}
if (_table[i] == NULL)
{
cout << "NULL";
}
cout <_table.size())
{
return _PrimeList[i];//按照素数表来设置容量大小
}
}
//当需要的容量超过素数表的大容量，我们就按照大的来扩容
return _PrimeList[_PrimeSize - 1];
}
//哈希桶扩张容量
void _ExpandCapatity()
{
//开辟一个新的更大容量哈希桶
size_t newsize = _NewSize();
vector newtable;
newtable.resize(newsize);
//把原来哈希桶中的元素再下来，插入到新的哈希桶
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* tmp = cur;
int index = _HashFunc(tmp->_key);
//头插法
tmp->_next = newtable[index];
newtable[index] = tmp;
cur = cur->_next;
}
_table[i] = NULL;
}
_table.swap(newtable);
}
protected:
vector _table;
size_t _size;//数据的多少
};
为了减少哈希冲突，我扩张容量是用到了素数表。你们如果想问我为什么用素数表能减少哈希冲突，其实我也不知道，我只是知道别人这样说，我拿来用而已。
//新的容量
size_t _NewSize()
{
// 使用素数表对齐做哈希表的容量，降低哈希冲突
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
for (int i = 0; i < _PrimeSize; i++)
{
if (_PrimeList[i]>_table.size())
{
return _PrimeList[i];//按照素数表来设置容量大小
}
}
//当需要的容量超过素数表的大容量，我们就按照大的来扩容
return _PrimeList[_PrimeSize - 1];
}
//哈希桶扩张容量
void _ExpandCapatity()
{
//开辟一个新的更大容量哈希桶
size_t newsize = _NewSize();
vector newtable;
newtable.resize(newsize);
//把原来哈希桶中的元素再下来，插入到新的哈希桶
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* tmp = cur;
int index = _HashFunc(tmp->_key);
//头插法
tmp->_next = newtable[index];
newtable[index] = tmp;
cur = cur->_next;
}
_table[i] = NULL;
}
_table.swap(newtable);
} 希望自己的理解能帮到大家，如果有什么错误，希望大家及时提出，谢谢！
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文名称：哈希表——开链法（哈希桶）-创新互联
文章出自：
http://cdkjz.cn/article/dshjid.html
