本篇博文，旨在介绍哈希表的基本概念及其用法；介绍了减少哈希冲突的方法；并用代码实现了哈希表的线性探测和哈希桶
哈希表的基本概念
哈希表是一种存储结构，它通过key值可以直接访问该key值在内存中从存储位置；
将关键值映射到表中的位置访问数据，这个映射函数叫做散列函数，存储数据的表叫做散列表；
构造哈希表的几种方法
1、直接定址法
根据关键值直接确定元素存取的位置，该散列函数是一个线性函数；例如 Hash(key) = A*key+B，其中，A和B都为常数
2、除留余数法
取出关键值后，将关键值除以该散列表的长度从而获得的余数，作为散列地址；Hash(key) = key%m
3、平方取中法
取关键字平方后的中间几位为哈希地址。由于一个数的平方的中间几位与这个数的每一位都有关，因而，平方取中法产生冲突的机会相对较小。
平方取中法中所取的位数由表长决定。
例： K = 456,K2 = 207936 若哈希表的长度m=102，则可取79（中间两位）作为哈希函数值。
4、折叠法
将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。
5、随机数法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
6、数学分析法
找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
哈希冲突/哈希碰撞
哈希冲突出现的原因
关键值通过任何的散列函数获得的散列地址都有可能是重复的，这种情况叫做哈希冲突；
载荷因子
散列表的载荷因子的定义为：a = 表中的元素个数/散列表的长度
对于开放定址法，载荷因子特别重要，一般情况下严格控制在0.7-0.8
超过0.8，哈希表的效率会很低
过低的话，浪费的空间会更大
任何的散列函数都是无法避免的，在处理哈希冲突的方法中，我们介绍下面两种方法
a 用开放定址法来处理哈希冲突
a1 线性探测
当有需要插入元素的位置已经有元素存在时，则向后遍历寻找空位置
a2 二次探测
当插入位置冲突时，则向后寻找，但不是每次只挪动一个位置，而是冲突次数的平方次（1,4,9....）
b 用开链法处理哈希冲突
哈希桶是一种顺序表和链表的结合体，定义一个数组，数组存储的内容是节点的指针，下面用一个个桶来存储元素；
这样可以提高哈希表的效率
如何减少哈希冲突
a 素数
使用素数做除数可以有效的减少哈希冲突
//素数表
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
};
b 字符串哈希算法
字符串哈希算法就是将一个字符串转化成一个Key值
字符串哈希算法有很多
下面这个链接有详细的介绍
http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
代码实现
开放定址法的线性检测
节点的定义：
//定义枚举，表示节点的状态
enum Status
{
EXIST,DELETE,EMPTY,};
//节点的定义
template<typename K,typename V>
struct HashNode
{
K _key;
V _value;
Status _status;
HashNode(const K& key = K(),const V& value = V())
:_key(key),_value(value),_status(EMPTY)
{}
};
状态位标识着这个位置有没有值存在，还是之前存在已被删除
哈希表的定义：
//HashFunc是采用的字符串哈希算法
template<typename K,typename V,typename HashFunc = __HashFunc<K>>
class HashTable
{
typedef HashNode<K,V> Node;
public:
//缺省的构造函数
HashTable()
{}
//构造函数
HashTable(size_t size);
//将K值转换成哈希值
size_t HashFunC(const K& key);
//插入一组值
pair<Node*,bool> Insert(const K& key,const V& value);
//查找元素
Node* find(const K& key);
//删除一个节点
void Remove(const K& key);
protected:
vector<Node> _v;//用vector的下标标志位置
size_t _size;//哈希表中元素的数量
protected:
//交换两个哈希表
void Swap(HashTable<K,V> &h);
//进行容量的判别，进行扩容
void CheckCapacity();
};
插入函数的实现：
pair<Node*,const V& value)
{
//检查是否需要扩容
CheckCapacity();
//对K值进行取余，判断插入的位置
size_t index = HashFunC(key);
//如果存在，则循环着继续寻找
while (_v[index]._status == EXIST)
{
index++;
if (index == _v.size())
index = 0;
}
_v[index]._key = key;
_v[index]._value = value;
_v[index]._status = EXIST;
_size++;
return make_pair<Node*,bool>(&_v[index],true);
}
插入函数，要找到关键值对应的位置，冲突的话后移；找到后放入对应的Key和value值，并且将状态位改变即可
查找函数的实现：
Node* find(const K& key)
{
//对K值进行取余，判断插入的位置
size_t index = HashFunC(key);
//如果存在，则继续寻找
while (_v[index]._status == EXIST)
{
//若相等，判断状态是否是删除
//若删除，则没找到，返回空
//若没删除，则返回该位置的地址
if (_v[index]._key == key)
{
if (_v[index]._status == DELETE)
return NULL;
return &_v[index];
}
index++;
if (index == _size)
index = 0;
}
return &_v[index];
}
线性探测中，查找这块有个小问题。当一个关键值是因为冲突后移的话，若后移中的某个值之后删除了，就无法找到这个值了
删除函数的实现：
void Remove(const K& key)
{
//删除仅需要将状态修改
Node* delNode = find(key);
if (delNode)
delNode->_status = DELETE;
}
扩容函数的实现：
载荷因子超过0.7时，进行扩容
void CheckCapacity()
{
//如果_v为空，则扩容到7
if (_v.empty())
{
_v.resize(_PrimeList[0]);
return;
}
//如果超过载荷因子，则需要扩容
if (_size*10 / _v.size() >= 7)
{
/*size_t newSize = 2 * _v.size();*/
size_t index = 0;
while (_PrimeList[index] < _v.size())
{
index++;
}
size_t newSize = _PrimeList[index];
//用一个临时变量来存储新生成的哈希表
//生成完成后，将其和_v交换
HashTable<K,V> tmp(newSize);
for (size_t i = 0; i < _v.size(); ++i)
{
//如果存在，则将该位置的哈希值插入到临时的哈希表中
if (_v[i]._status == EXIST)
tmp.Insert(_v[i]._key,_v[i]._value);
}
//交换两个哈希表
Swap(tmp);
}
}
开链法 哈希桶
节点的定义：
//节点的定义 template<class K,class V> //struct HushNode e2:拼写错误，Hash not hush struct HashNode { K _key; V _value; HashNode<K,V>* _next; HashNode(const K& key,const V& value) :_key(key),_next(NULL) {} };
插入函数的实现：
//插入函数的实现 pair<Node*,const V& value) { //插入之前要先进行是否扩容的检查 CheckCapacity(); //找到这个数的位置 size_t index = _HushFunc(key); Node* cur = _ht[index]; while (cur) { if (cur->_key == key) return make_pair(cur,false); cur = cur->_next; } Node* temp = new Node(key,value); temp->_next = _ht[index]; _ht[index] = temp; return make_pair(temp,true); }
用pair可以返回插入成功后节点的指针（或插入失败，相同关键值的指针），以及判断插入成功与否的TRUE或FALSE
删除函数的实现：
//删除函数的实现 void Erase(const K& key) { //先进行查找这个数的位置 size_t index = _HushFunc(key); Node* pre = NULL; Node* cur = _ht[index]; //删除的时候要进行情况的分析讨论 while (cur) { if (pre == NULL) { _ht[index] = cur->_nex; delete cur; } else { pre->_next = cur->_next; } cur = cur->_next; } delete cur; }
删除元素的时候，需要分两种情况
@H_110_301@a、链上有且仅有该节点
@H_110_301@出现这种情况，就是pre为空时，仅需修改vector对应位置存储的指针
b、链上除该节点外，还有多个节点
将cur的指向下一个节点的指针给pre的下一个
查找函数的实现：
//查找函数的实现 Node* Find(const K& key) { for (int i = 0; i<_size; i++) { Node* cur = _ht[i]; while (cur) { if (cur->_key == key) return cur; cur = cur->_next; } } return NULL; }
扩容函数的实现：
void CheckCapacity()
{
//当哈希桶为空的时候或者负载因子为1的时候,进行扩容
if (_ht.size() == 0 || _size / _ht.size() == 1)
{
//建一个新表
HushTable temp;
size_t newsize = GetNewSize();
temp._ht.resize(newsize);
//将元素放进去
for (int i = 0; i<_ht.size(); i++)
{
Node* cur = _ht[i];
while (cur)
{
temp.Insert(cur->_key,cur->_value);
cur = cur->_next;
}
}
}
}
与线性探测不同的是，这里当载荷因子为1的时候进行扩容；
哈希桶的一种极端情况是，所有值都往同一个位置进行插入
如下：
解决方法：
当一个链上的节点数量达到一个百分比（自己定义，可以是100%,50%,10%），则不再存储链表，而是存储一颗红黑树
这一避免出现这种极端情况而带了的弊端
https://github.com/haohaosong/DataStruct/blob/master/HashTable.h
https://github.com/haohaosong/DataStruct/blob/master/HashTableBucket.h
原文链接：https://www.f2er.com/datastructure/382341.html