哈希
哈希（散列）是一种数据结构，通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系，如果要查、改数据，就可以直接到对应的位置去，使得时间复杂度达到了 O(1) ，原因如下：
若结构中存在和 关键字K 相等的记录，则必定在 f(K) 的存储位置上。由此，不需比较便可直接取得所查记录。
称上面的对应关系 f 为 散列函数（Hash function），按这个映射关系事先建立的表为散列表，这一映象过程称为 散列造表 或 散列 ，最终所得的存储位置称 散列地址 。
哈希（散列）函数
哈希函数用来建立元素与其存储位置的映射关系。
对于哈希函数来说，必须具有以下特点：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有
m 个地址时，其值域必须在 0 到 m-1 之间。 - 哈希函数计算出来的地址能均匀分布在整个空间中（防止产生密集的哈希冲突）
哈希冲突大量出现往往都是因为哈希函数设计的不够合理，但是即使再优秀的哈希函数，也只能尽量减少哈希冲突的次数，无法避免哈希冲突。
常见的哈希函数
-
直接定址法（常见）
哈希函数：Hash(Key) = A * Key + B
这是最简单的哈希函数，直接取关键字本身或者他的线性函数来作为散列地址。
-
除留余数法（常见）
哈希函数 ：Hash(key) = key % capacity
几乎是最常用的哈希函数，用一个数来对 key 取模，一般来说这个数都是容量。
-
平方取中法
对关键字进行平方，然后取中间的几位来作为地址。
-
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和（去除进位），并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况.
-
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key)，其中 random 为随机数函数。通常应用于关键字长度不等时。
-
数学分析法
分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
字符串哈希函数
因为哈希函数的常用方法如直接定址、除留余数、平方取中等方法需要用的 key值 为整型，而大部分时候我们的 key 都是 string，由于无法对 string 进行算数运算，所以需要考虑新的方法。
常见的字符串哈希算法有 BKD、SDB、RS 等，这些算法大多通过一些公式来对字符串每一个 字符的 ascii值 或者 字符串的大小 进行计算，来推导出一个不容易产生冲突的 key值 。
例如 BKDHash ：
struct _Hash<std::string>
{
const size_t& operator()(const std::string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
这里推荐两篇文章，一篇具体对比各类字符串哈希函数的效率，一篇是实现：
哈希冲突
对不同的关键字可能得到同一散列地址，即 key1≠key2 ，而 f(key1)=f(key2) ，这种现象称碰撞（哈希冲突）。
哈希冲突使得多个数据映射的位置相同，但是每个位置又只能存储一个数据，所以就需要通过某种方法来解决哈希冲突。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高；产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
- 散列函数是否均匀；
- 处理冲突的方法；
- 散列表的负载因子（装填因子）。
第一点取决于上面讲过的哈希函数，不再赘述，下面详细讲一下2、3点。
处理冲突的方法可分为两类：开散列方法( open hashing，也称为拉链法，separate chaining ) 和 闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。
闭散列（开放地址法）
因为闭散列是顺序的结构，所以可以通过遍历哈希表，来将冲突的数据放到空的位置上。
-
线性探测
线性探测即为从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
这种方法实现起来极为简单，但是效率也不高，因为如果同一位置产生了大量的哈希冲突，就会导致每次都在同一个位置进行探测，例如我在10这里连续冲突100次，此时所有探测的次数加起来就会高达100！
-
二次探测
二次探测即为从发生冲突的位置开始，每次往后探测 ±k2(k<=m/2，m为散列表长) 个位置，如：12，-(12)，22，-(22) 等。
这样的话就将每次探测的效率从 O(N) 提升到了 O(logN) ，即使有着大量的冲突堆积，也不会导致效率过低。
-
伪随机数探测
这种方法并不常见，实现方法是：创建一个伪随机数序列，根据序列内容决定每次往后探测的长度。
开散列（链地址法/拉链法）
先用哈希函数计算每个数据的散列地址，把具有相同地址的元素归于同一个集合之中，把该集合处理为一个链表，链表的头节点存储于哈希表之中。
链地址法在每一个映射位置都建立起一个链表（数据过多时可能会转为建立红黑树），将每次插入的数据都直接连接上这个链表，这样就不会像闭散列一样进行大量的探测，但是如果链表过长也会导致效率低下。
负载因子以及增容
哈希冲突出现的较为密集，往往代表着此时数据过多，而能够映射的地址过少，而要想解决这个问题，就需要通过 负载因子（装填因子） 的判断来进行增容。
负载因子的大小 = 表中数据个数 / 表的容量（长度）
对于闭散列
对于闭散列来说，因为其是一种线性的结构，所以一旦负载因子过高，就很容易出现哈希冲突的堆积，所以当负载因子达到一定程度时就需要进行增容，并且增容后，为了保证映射关系，还需要将数据重新映射到新位置。
经过算法科学家的计算， 负载因子应当严格的控制在 0.7-0.8 以下，所以一旦负载因子到达这个范围，就需要进行增容。
因为除留余数法等方法通常是按照表的容量来计算，所以科学家的计算，当对一个质数取模时，冲突的几率会大大的降低，并且因为增容的区间一般是 1.5-2 倍，所以算法科学家列出了一个增容质数表，按照这样的规律增容，冲突的几率会大大的降低。
这也是 STL 中 unordered_map/unordered_set 使用的增容方法。
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
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
};
hashmap 的负载因子为什么默认是 0.75 ？
比如说当前的容器容量是 16，负载因子是 0.75,16*0.75=12，也就是说，当容量达到了 12 的时候就会进行扩容操作。而负载因子定义为 0.75 的原因是：
- 当负载因子是
1.0 的时候，也就意味着，只有当散列地址全部填充了，才会发生扩容。意味着随着数据增长，最后势必会出现大量的冲突，底层的红黑树变得异常复杂。虽然空间利用率上去了，但是查询时间效率降低了。 - 负载因子是
0.5 的时候，这也就意味着，当数组中的元素达到了一半就开始扩容。虽然时间效率提升了，但是空间利用率降低了。 诚然，填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是，这时候空间利用率就会大大的降低，原本存储 1M 的数据，现在就意味着需要 2M 的空间。
对于开散列结构
因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多，随着数据的增多，就可能会导致某一个桶过重，使得效率过低。
所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为 1 时就需要进行扩容。
具体实现
哈希表（闭散列）
创建
对于闭散列，我们需要通过状态来记录一个数据是否在表中，所以这里会使用枚举来实现。
enum State
{
EMPTY,
EXITS,
DELETE,
};
template<class T>
struct HashData
{
HashData(const T& data = T(), const State& state = EMPTY)
: _data(data)
, _state(state)
{}
T _data;
State _state;
};
插入
插入的思路很简单，计算出映射的地址后，开始遍历判断下面几种状态：
- 如果映射位置已存在数据，并且值与当前数据不同，则说明产生冲突，继续往后查找
- 如果映射位置的数据与插入的数据相同，则说明此时数据已经插入过，此时就不需要再次插入
- 如果映射位置的状态为删除或者空，则代表着此时表中没有这个数据，在这个位置插入即可
bool Insert(const T& data)
{
KeyOfT koft;
if (_size * 10 / _table.size() >= 7)
{
std::vector<HashData> newTable(getNextPrime(_size));
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXITS)
{
size_t index = HashFunc(koft(_table[i]._data));
while (newTable[i]._state == EXITS)
{
i++;
if (i == _table.size())
{
i = 0;
}
}
newTable[i] = _table[i];
}
}
_table.swap(newTable);
}
size_t index = HashFunc(koft(data));
while (_table[index]._state == EXITS)
{
if (koft(_table[index]._data) == koft(data))
{
return false;
}
else
{
index++;
index = HashFunc(index);
}
}
_table[index]._data = data;
_table[index]._state = EXITS;
_size++;
return true;
}
查找
查找也分几种情况
- 如果映射的位置为空，则说明查找失败。
- 如果映射的位置的数据不同，则说明产生冲突，继续向后查找
- 如果映射的位置的数据相同，如果状态为删除，则说明数据已经删除，查找失败；而如果数据为存在，则说明查找成功。
HashData* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key);
while (_table[index]._state != EMPTY)
{
if (koft(_table[index]._data) == key)
{
if (_table[index]._state == EXITS)
{
return &_table[index];
}
else if (_table[index]._state == DELETE)
{
return nullptr;
}
}
index++;
if (index == _table.size())
{
index = 0;
}
}
return nullptr;
}
删除
直接遍历查找数据，如果找不到则说明已经被删除，如果找到了则直接将状态改为删除即可。
bool Erase(const K& key)
{
HashData* del = Find(key);
if (del == nullptr)
{
return false;
}
else
{
del->_state = DELETE;
_size--;
return true;
}
}
完整代码
#pragma once
#include<vector>
namespace lee
{
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
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
};
enum State
{
EMPTY,
EXITS,
DELETE,
};
template<class T>
struct HashData
{
HashData(const T& data = T(), const State& state = EMPTY)
: _data(data)
, _state(state)
{}
T _data;
State _state;
};
template<class K, class T, class KeyOfT>
class HashTable
{
public:
typedef HashData<T> HashData;
HashTable(size_t capacity = 10)
: _table(capacity)
, _size(0)
{}
size_t getNextPrime(size_t num)
{
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > num)
{
return primeList[i];
}
}
return primeList[PRIMECOUNT - 1];
}
size_t HashFunc(const K& key)
{
return key % _table.size();
}
bool Insert(const T& data)
{
KeyOfT koft;
if (_size * 10 / _table.size() >= 7)
{
std::vector<HashData> newTable(getNextPrime(_size));
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXITS)
{
size_t index = HashFunc(koft(_table[i]._data));
while (newTable[i]._state == EXITS)
{
i++;
if (i == _table.size())
{
i = 0;
}
}
newTable[i] = _table[i];
}
}
_table.swap(newTable);
}
size_t index = HashFunc(koft(data));
while (_table[index]._state == EXITS)
{
if (koft(_table[index]._data) == koft(data))
{
return false;
}
else
{
index++;
index = HashFunc(index);
}
}
_table[index]._data = data;
_table[index]._state = EXITS;
_size++;
return true;
}
HashData* Find(const K& key)
{
KeyOfT koft;
size_t index = HashFunc(key);
while (_table[index]._state != EMPTY)
{
if (koft(_table[index]._data) == key)
{
if (_table[index]._state == EXITS)
{
return &_table[index];
}
else if (_table[index]._state == DELETE)
{
return nullptr;
}
}
index++;
if (index == _table.size())
{
index = 0;
}
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* del = Find(key);
if (del == nullptr)
{
return false;
}
else
{
del->_state = DELETE;
_size--;
return true;
}
}
private:
std::vector<HashData> _table;
size_t _size;
};
};
哈希桶（开散列）
开散列也叫哈希桶，桶为每一个映射的位置，桶一般用链表或者红黑树实现（这里我用的是链表）。当我们通过映射的地址，找到存放数据的桶，再对桶进行插入或者删除操作即可。
插入
通过计算映射位置找到对应的桶，再判断数据是否存在后将数据头插进去即可（也可以尾插）
bool Insert(const T& data)
{
KeyofT koft;
if (_size == _table.size())
{
size_t newSize = getNextPrime(_table.size());
size_t oldSize = _table.size();
std::vector<Node*> newTable(newSize);
_table.resize(newSize);
for (size_t i = 0; i < oldSize; i++)
{
Node* cur = _table[i];
while (cur)
{
size_t pos = HashFunc(koft(cur->_data));
Node* next = cur->_next;
cur->_next = newTable[pos];
newTable[pos] = cur;
cur = next;
}
_table[i] == nullptr;
}
_table.swap(newTable);
}
size_t pos = HashFunc(koft(data));
Node* cur = _table[pos];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return false;
}
else
{
cur = cur->_next;
}
}
Node* newNode = new Node(data);
newNode->_next = _table[pos];
_table[pos] = newNode;
++_size;
return true;
}
查找
直接根据映射的位置到桶中查找数据即可
Node* Find(const K& key)
{
KeyofT koft;
size_t pos = HashFunc(key);
Node* cur = _table[pos];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
删除
bool Erase(const K& key)
{
KeyofT koft;
size_t pos = HashFunc(key);
Node* cur = _table[pos];
Node* prev = nullptr;
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_table[pos] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
完整代码
#pragma once
#include<vector>
#include<string>
namespace lee
{
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
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
};
template<class K>
struct Hash
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<std::string>
{
const size_t & operator()(const std::string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
template<class T>
struct HashNode
{
HashNode(const T& data = T())
: _data(data)
, _next(nullptr)
{}
T _data;
HashNode<T>* _next;
};
template<class K, class T, class KeyofT, class Hash = Hash<K>>
class HashBucket
{
public:
typedef HashNode<T> Node;
HashBucket(size_t capacity = 10)
: _table(capacity)
, _size(0)
{}
~HashBucket()
{
Clear();
}
size_t getNextPrime(size_t num)
{
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > num)
{
return primeList[i];
}
}
return primeList[PRIMECOUNT - 1];
}
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key) % _table.size();
}
bool Insert(const T& data)
{
KeyofT koft;
if (_size == _table.size())
{
size_t newSize = getNextPrime(_table.size());
size_t oldSize = _table.size();
std::vector<Node*> newTable(newSize);
_table.resize(newSize);
for (size_t i = 0; i < oldSize; i++)
{
Node* cur = _table[i];
while (cur)
{
size_t pos = HashFunc(koft(cur->_data));
Node* next = cur->_next;
cur->_next = newTable[pos];
newTable[pos] = cur;
cur = next;
}
_table[i] == nullptr;
}
_table.swap(newTable);
}
size_t pos = HashFunc(koft(data));
Node* cur = _table[pos];
while (cur)
{
if (koft(cur->_data) == koft(data))
{
return false;
}
else
{
cur = cur->_next;
}
}
Node* newNode = new Node(data);
newNode->_next = _table[pos];
_table[pos] = newNode;
++_size;
return true;
}
bool Erase(const K& key)
{
KeyofT koft;
size_t pos = HashFunc(key);
Node* cur = _table[pos];
Node* prev = nullptr;
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{
_table[pos] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
Node* Find(const K& key)
{
KeyofT koft;
size_t pos = HashFunc(key);
Node* cur = _table[pos];
while (cur)
{
if (koft(cur->_data) == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
void Clear()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
private:
std::vector<Node*> _table;
size_t _size;
};
};
