哈希桶：哈希桶就是盛放不同key链表的容器（即是哈希表），我们可以把每个key的位置看作是一个指针，该指针所指向的位置里放了一个链表，可以认为是指针数组，故该方法也叫开链式。
创新互联公司是一家专注于
网站设计制作、成都网站设计与策划设计,中山网站建设哪家好?
创新互联公司做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:中山等地区。中山做网站价格咨询:18982081108
相比闭散列，哈希桶提高了空间利用率：在实现哈希表时，常见的方法是线性探测、二次探测，这两个算法的具体实现可以查看我的博客。但是这两个算法有一个共同点就是：空间利用率低。为什么这么说呢？线性探测、二次探测的高效性很大程度上要取决于它的载荷因子，载荷因子即：存放关键字个数 / 空间大小。
通过查阅资料，我发现，使用素数做除数可以减少哈希冲突。见下：
素数表：使用素数做除数可以减少哈希冲突
// 使用素数表对齐做哈希表的容量，降低哈希冲突
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
};
下图进行哈希桶处理哈希冲突的展示
下面通过库中的vactor进行存放指向链表的指针，每个结点里包含_key,_value和_next。
#pragma
template
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
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 + (unsigned int)(*str++);
}
return (hash & 0x7FFFFFFF);
}
template<>
struct DefaultHashFunc
{
size_t operator()(const string& str)
{
return BKDRHash(str.c_str());
}
};
template
struct HashTableNode//结点
{
K _key;
V _value;
HashTableNode* _next;
HashTableNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _next(NULL)
{}
};
template>
class HashTableBucket
{
typedef HashTableNode Node;
public:
HashTableBucket();
HashTableBucket(const HashTableBucket& htb);
HashTableBucket& operator=(HashTableBucket htb);
void PrintTables();
bool Insert(const K& key,const V& value);//防冗余，在删除和查找时只需要key
Node* Find(const K& key);
bool Remove(const K& key);
protected:
size_t _HashFunc(const K& key);
size_t _GetNextPrime(size_t size);//获取下一个素数（利用素数表，使用素数做除数可以减少哈希冲突）
void _CheckExpand();
private:
vector _tables;//开链式为指针数组，指针指向链表
size_t _size;//有效数据数，vector中的size()为有效空间数
};
实现_HashFunc(const K& key)，通过伪函数来判断不同类型的key所在链表的位置。
template>
size_t HashTableBucket::_HashFunc(const K& key)
{
HashFunc htb;
return htb(key) % (_tables.size());//htb(key)伪函数
}
1. 插入函数的实现（Insert）
（1）检查容量。调用_CheckExpand()函数检查负载因子a，考虑是否扩张，当a为1时进行扩容。
（2）检查插入的key是否已经存在，不存在返回false，存在进行（3）操作。
（3）进行头插。
template>
bool HashTableBucket::Insert(const K& key, const V& value)
{//防冗余，在删除和查找时只需要key
_CheckExpand();//检查是否扩容
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{//如果插入的元素存在就返回false
if (cur->_key == key)
{
return false;
}
cur = cur->_next;
}
}
//头插
size_t index = _HashFunc(key);
Node* tmp = new Node(key, value);
tmp->_next = _tables[index];
_tables[index] = tmp;
++_size;
return true;
2. 查找函数的实现（Find）
（1）调用_HashFunc()函数找到要寻找的Key所在的链表位置。
（2）通过遍历链表查找key。
template>
HashTableNode* HashTableBucket::Find(const K& key)//查找
{
size_t index = _HashFunc(key);//链表结点位置
Node* cur = _tables[index];
while (cur)
{
if (cur->_key == key)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
3. 删除函数的实现（Remove）
（1）调用Find（）函数，判断需要删除的key是否存在，不存在就返回false，存在就进行（2）操作。
（2）调用_HashFunc()函数找到key所在链表的位置，先通过遍历链表找到del结点的上一个结点prev，然后使prev的下一个结点指向del的下一个结点。
template>
bool HashTableBucket::Remove(const K& key)//删除
{
if (Find(key) == NULL)
{
return false;
}
size_t index = _HashFunc(key);
//需要找到删除结点的前后结点
Node* del = Find(key);
Node* next = del->_next;
Node* prev = _tables[index];
while (prev)
{
if (prev->_next == del)
{
break;
}
prev = prev->_next;
}
if (next)//如果next存在时，进行链接
{
prev->_next = next;
}
del = NULL;
return true;
}
检查是否需要扩容_CheckExpand()的实现。
template>
void HashTableBucket::_CheckExpand()//检查负载因子，考虑是否扩容
{
if (_size >= _tables.size())//负载因子达到了1，进行扩容
{
size_t NewSize = _GetNextPrime(_size);
//进行结点复制
vector NewTables;
NewTables.resize(NewSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)//头插
{
Node* tmp = cur;
cur = cur->_next;
size_t index = _HashFunc(tmp->_key);//重新确定元素在表中位置
tmp->_next = NewTables[index];
NewTables[index] = tmp;
}
}
_tables.swap(NewTables);//调用vector中的swap接口进行交换
}
}
template>
size_t HashTableBucket::_GetNextPrime(size_t size)
{//获取下一个素数（利用素数表，使用素数做除数可以减少哈希冲突）
//使用素数表对齐做哈希表的容量，降低哈希冲突
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 (size_t i = 0; i < _PrimeSize; ++i)
{
if (_PrimeList[i] > size)
{
return _PrimeList[i];
}
return _PrimeList[i - 1];
}
return _PrimeList[_PrimeSize];//如果size大于或等于素数表中数据，就返回表中大数
}
测试用例如下，实现字典（可以一对多）查询。
HashTableBucket> dict;
vector v;
v.push_back("manager");
dict.Insert("经理", v);
v.clear();
v.push_back("移动");
v.push_back("距离");
dict.Insert("remove",v);
HashTableNode>* ret = dict.Find("remove");
ret->_value.push_back("搬家");
vector& words = ret->_value;
for (size_t i = 0; i < words.size(); ++i)//打印对应的多个字符串
{
cout << words[i].c_str() << endl;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
分享标题：哈希桶处理哈希冲突-创新互联
链接URL：
http://cdkjz.cn/article/dhppgs.html
