哈希的概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O( l o g 2 N log_2 N log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)。
比如将数据{1,4,6,8,15}存储到哈希表中：
哈希函数设置为hashi = key % capacity(其中hashi就是元素存储的位置，key就是数据项，capacity为存储元素底层空间总的大小，比如vector)，存储结构如下：
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。
哈希冲突
如果继续向上面哈希表中插入14，hashi(14) = 4。而4这个位置已经被占用，此时就会发生不同的值映射到同一个位置上。这种情况就叫做哈希冲突。
哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
一个好的哈希函数设计应该遵循以下条件：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值 域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
最常见的哈希函数有：
除留余数法(最常用)
对于哈希表长度为m的哈希函数公式为：
hashi(key) = key % p (p <= m)
解决哈希冲突的方法
处理哈希冲突有两种常用的方法：
- 闭散列
- 开散列
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。寻找下一个位置的方式有：
- 线性探测
- 二次探测
线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
比如对下面数据项集合{12,67,56,16,25,37,22,29,15,47,48,34}。哈希表长为12。
哈希函数为hashi(key) = key % p (p <= m)。
计算前五个{12,67,56,16,25}时，都不会发生冲突。直接存入哈希表。如下：
当计算37时，hashi(37) = 1,此时就会与25发生冲突，此时就需要将37存放到25的下一个位置，即下标为2的位置处。
继续存放{22,29,15,47}都没有发生冲突，正常存放。
存放48时，hashi(48) = 0，与12所在的位置发生了冲突，此时下一个位置还是会发生冲突，一直线性探测到29的下一个，才有空位。将48存放到29的下一个。
继续存放34，hash(i) = 10。和22，47，12，37，15，16，29，48，67，56都会发生冲突。只能存放到56的下一个。
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位 置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
hashi = (
H
0
H_0
H0 +
i
2
i^2
i2 )% m, 或者：hashi = (
H
0
H_0
H0 -
i
2
i^2
i2 )% m。
其中：i = 1,2,3…，
H
0
H_0
H0是通过散列函数Hash(key)对元素的关键码 key 进行计算得到的位置，
m是表的大小。
比如上面哈希表存放最后一个34时，
H
0
H_0
H0 = 10，i = 1,hashi = (10-1)%12 = 9。而下标9正好是空，只需一次二次探测即可存放34。
负载因子
以上就是闭散列寻址的两种方式。当然哈希表也是需要扩容的，如果继续对上面哈希表存放数据，哈希表已满，无法存放了。
关于哈希表扩容，引入了一个新的概念，负载因子。
哈希表的负载因子α = 表中的数据个数 / 哈希表长度。
比如下面哈希表的负载因子 = 6 / 12 = 0.5
负载因子是哈希表反馈装满程度的标志，由于表长是定值，负载因子和哈希表中的元素个数成正比，所以负载因子越大，表明哈希表中元素个数越多。产生哈希冲突的概率越大，反之，负载因子越小，哈希表中元素个数越少，发生哈希冲突的概率越低。
对于闭散列，哈希表的负载因子是非常重要的，一般严格控制在0.7~0.8以下(也就是说哈希表的负载因子超过0.8就要扩容，避免产生更多的哈希冲突)。
哈希表闭散列的实现
哈希表的存储结构
哈希表中每个位置除了存储数据元素之外，还要存储当前位置的状态(空，已存放，已删除)。因为采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。因此线性探测采用标记的伪删除法(就是给每个存储位置添加一个存储状态)来删除一个元素。
哈希表存储位置的状态可以使用枚举常量来定义，如下：
enum Status
{
EXIST,//已存储
EMPTY,//空
DELETE//已删除
};
整个哈希表闭散列的结构：
//存储位置状态
enum Status
{
EXIST,
EMPTY,
DELETE
};
//存储位置结构
template<class K, class V>
struct HashData
{
pair<K, V> _kv;//哈希表存储数据元素。
Status _status = EMPTY;//存储位置状态默认为空
};
//哈希表
template<class K, class V>
class HashTable
{
typedef HashData<K, V> HashTableNode;
public:
//哈希表提供的三个方法(插入、删除、查找)
bool Insert();
bool Erase();
HashTableNode* find();
private:
vector<HashTableNode> _tables;//使用vector做为哈希表底层存储结构
size_t n = 0;//哈希表元素个数(方便计算哈希表的负载因子)
};
插入
向哈希表中插入数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
- 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
- 将键值对插入哈希表。
- 哈希表中的有效元素个数加一。
bool Insert(const pair<K, V> kv)
{
//不允许键值冗余
if (find(kv.first) != nullptr)
{
return false;
}
//空哈希表初始化10个存储位置
if (_tables.size() == 0 )//扩容
{
_tables.resize(10);
}
else if((double)_tables_size / (double)_tables.size() > 0.8)//负载因子大于0.8扩容
{
//创建新哈希表对象
HashTable<K,V> newtables;
newtables._tables.resize(_tables.size() * 2);
//遍历旧表，重新映射到新表中
for (auto& data : _tables)
{
if (data._status == EXIST)
{
newtables.Insert(data._kv);
}
}
//交换这两个哈希表
_tables.swap(newtables._tables);
}
//线性探测确认哈希地址
size_t hashi = kv.first % _tables.size();
size_t i = 1;
size_t index = hashi;
while (_tables[index]._status == EXIST)
{
index = hashi + i;
++i;
index %= _tables.size();//从0继续寻找位置。
}
//确认位置进行存储
_tables[index]._kv = kv;
_tables[index]._status = EXIST;
_tables_size++;
return true;
}
注意细节：
- 扩容时创建新哈希表对象，让新哈希表对象调用insert不构成函数递归，来完成扩容后重新建立映射关系。
- index %= _tables.size();//从0继续寻找位置。
查找
HashTableNode* find(const K& key)
{
//空表
if (_tables.size() == 0)
{
return nullptr;
}
//线性探测
size_t hashi = key % _tables.size();
size_t start = hashi;
size_t i = 1;
while (_tables[start]._status != EMPTY)
{
if (_tables[start]._kv.first == key
&& _tables[start]._status == EXIST)
{
return &_tables[start];
}
start = hashi + i;
i++;
start %= _tables.size();
//已经找了一圈了
if (start == hashi)
{
break;
}
}
return nullptr;
}
删除
删除哈希表中的元素采用伪删除法，只需将被删除元素找到，将其状态修改为DELETE即可。
bool Erase(const K& key)
{
HashTableNode* ret = find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_status = DELETE;
--_tables_size;
}
return true;
}
开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个哈希桶，各个哈希桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
哈希桶和vector< list >本质是一样的(本质就是指针数组)。逻辑图如下：
比如对下面数据项集合{1，33，3，5，55，7，9},存放到表长为10的哈希表中。同样哈希函数采用除留余数法，存放到哈希表中如下：
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
实际中哈希表的开散列比闭散列更实用。
开散列同样也要考虑扩容问题，开散列一般负载因子为1时在发生扩容。
这样的话，如果哈希表中所有的元素都发生冲突，都存放在一个哈希桶中，有负载因子的控制扩容，几乎不会出现这种极端情况。
如果真的出现极端场景，可以考虑将这个桶由单链表改为红黑树。
由此可见，哈希表的开散列效率是极高的。增删查改的平均时间复杂度都是O(1)级别的存在，非常的恐怖。
哈希表开散列的模拟实现
在哈希表的开散列中，每个位置存储的是单链表的结点，这里需要实现一个哈希表的结点类。结点类和单链表一样，除了存储数据元素之外，还需要存储一个结点的指针用来指向下一个结点。
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V> kv)
:_next(nullptr)
,_kv(kv)
{}
};
哈希桶框架
template<class K, class V>
class HashBucket
{
typedef HashNode<K, V> Node;
public:
//哈希桶提供的方法...
~HashBucket();
bool Insert(const pair<K, V> kv);
Node* Find(const K& key);
bool Erase(const K& key);
size_t size();
private:
vector<Node*> _tables;
size_t _size = 0;
};
下面就一一实现哈希桶提供的方法
insert函数
- 检查所插入元素是否存在
- 检查容量以及负载因为为1时进行扩容
- 确认插入元素所在桶的位置申请结点进行头插
bool Insert(const pair<K,V> kv)
{
//1.检查所插入元素是否存在
if (Find(kv.first) != nullptr)
{
return false;
}
//2.检查容量以及负载因为为1时进行扩容
if (_tables.size() == 0)
{
_tables.resize(10);
}
else if (_size == _tables.size())//扩容
{
vector<Node*> new_bucket(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur != nullptr)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % new_bucket.size();
cur->_next = new_bucket[hashi];
new_bucket[hashi] = cur;
cur = next;
}
}
_tables.swap(new_bucket);
}
//3.确认插入元素所在桶的位置申请结点进行头插
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_size;
return true;
}
注意： 这里的扩容不像闭散列一样，创建新的哈希表对象调用insert完成插入，会造成同样的数据再次申请结点，还要释放结点。虽然可以解决问题，但是效率不好。采用上面的方式更优，直接与新表重新建立映射关系即可。
// 创建新的哈希表对象调用insert完成插入。会造成同样的数据再次申请和释放。
HashBucket<K, V> new_bucket;
new_bucket._tables.resize(_tables.size() * 2);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur != nullptr)
{
new_bucket.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(new_bucket._tables);
这里哈希表中的结点需要申请，那么也需要写析构函数来完成资源的释放，否则就会造成内存泄漏。
~HashBucket()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur != nullptr)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
cout << "~HashBucket" << endl;
}
Find
- 找到查找元素在桶的位置
- 遍历单链表进行查找
Node* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
//1. 找到查找元素所在桶的位置
size_t hashi = key % _tables.size();//注意/0错误
Node* cur = _tables[hashi];
//2. 遍历单链表查找
while (cur != nullptr)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
Erase
- 找到删除元素所在桶的位置
- 单链表的删除
bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return false;
}
//1.找到删除元素所在桶的位置
size_t hashi = key % _tables.size();//防止除0错误
Node* cur = _tables[hashi];
Node* prev = nullptr;
//2.单链表的删除
while (cur != nullptr)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
开散列的其他问题
当存储的元素不是整形，而是其他类型，比如string等，如何让解决？
哈希函数采用除留余数法，所以被摸的key必须要为整形才可以。解决方法是提供一个仿函数，将key转化为整形,更准确的来说是无符号整形，如果是负数，转化为正整数进行存储。
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
此时，哈希桶需要第三个模板参数将key转化为整形做除余运算(这里第三个模板参数给了缺省值，可以根据自己的需要来实现)。
这里以Find为例,凡是需要%运算的都需要转化。
template<class K, class V,class Hash = HashFunc<K>>
class HashBucket
{
Node* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
//1. 找到查找元素所在桶的位置
size_t hashi = _hash(key) % _tables.size();//注意/0错误
//....
}
private:
Hash _hash;
}
如果数据类型是string，可以使用模板的特殊来完成，也可以自己实现做为模板参数来实例化。
这里以模板的特化为例
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
return str[0];//取字符串第一个字符作为key进行 求%
}
};
这样写的话，如果首字母相同的话，全部在一个桶里面，这样就会造成哈希桶的极端场景。使哈希桶的效率降低，有一种字符串哈希算法BKDRHash(此算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）)。这个算法就是每次累加然后乘31即可(原理目前不知道)。
//BKDRHash算法
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 31;// 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
};
哈希桶的效率
产生一百万个随机数，存放到哈希桶中，取出最大桶下面的个数。求最大桶个数成员函数如下:
size_t MaxBucketSize()
{
size_t max = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
size_t count = 0;
while (cur != nullptr)
{
count++;
cur = cur->_next;
}
printf("[%d]->%d\n", i, count);//打印每个桶下面的元素个数
if (count > max)
{
max = count;
}
}
return max;//最大桶的元素个数
}
测试代码如下：
这里rand()函数产生的不重复随机数最大只用32768个，让rand()+i后 能产生636105个不重复的随机数。
int main()
{
HashBucket<int, int> hb1;
srand((unsigned int)time(0));
for (int i = 0; i < 1000000; ++i)
{
hb1.Insert(make_pair(rand() + i, rand() + i));
}
cout << hb1.MaxBucketSize() << endl;
cout << hb1.size() << endl;
return 0;
}
运行结果：
对于这636105个不重复的随机数，最大的哈希桶数据个数才是2。哈希表的性能非常恐怖。
