顺序结构以及平衡树中，元素关键码与存储位置之间没有对应关系，因此在查找一个元素的时候，要经过关键码多次比较。顺序表查找的时间复杂度为O(N)，而平衡树中树的高度为O(log_2(N))，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中获取想要的元素。
如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
这种方式叫做哈希(散列)方法，哈希方法中使用的转换函数为哈希(散列)函数，构造出来的结构称为哈希表。
例如：
- 数据集合：{1, 7, 6, 4, 5, 9}
- 哈希函数：hash(key) = key % capacity; capacity是存储元素底层空间的总大小
- 哈希设置（假设容量为10）：
- hash(1) = 1 % 10 = 1
- hash(7) = 7 % 10 = 7
- hash(6) = 6 % 10 = 6
- hash(4) = 4 % 10 = 4
- hash(5) = 5 % 10 = 5
- hash(9) = 9 % 10 = 9
那么，考虑上述的哈希案例，如果这时候插入一个44，会发生什么，会发生两个关键字对应的存储位置有冲突，也就是没办法达到一一映射的关系，我们称这种现象叫做哈希冲突。
引起哈希冲突的一个原因在于哈希函数设计的不够合理。
哈希函数设计原则：
常见的哈希函数：
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置的“下一个”空位置去。
回顾前面讲的案例，如果现在插入一个元素44，那么这个元素会放到那个位置上呢？
线性探测是指 从发送冲突的位置开始，依次向后探测，知道寻找到下一个空位置为止。
- 数据集合：{1, 7, 6, 4, 5, 9}
- 哈希函数：hash(key) = key % capacity; capacity是存储元素底层空间的总大小
那么，我们想要删除哈希表已有的元素，若直接删除会影响其他元素的搜索。比如删除元素4，那么查找44的时候就没有办法找到了，所以我们通常使用标记的伪删除来删除一个元素。
enum State
{
EMPTY, // 空的
EXIST, // 存在
DELETE // 删除
};
线性探测的代码实现：
template <class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
bool Insert(const std::pair<K, V>& kv)
{
if (Find(kv.first))
return false;
// 扩容
CheckCapacity();
// 线性探测法
Hash hash;
size_t hashi = hash(kv.first) % _tables.size();
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_size;
return true;
}
HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hash hash;
size_t hashi = hash(key) % _tables.size();
// 从哈希对应的值开始查找，如果遇到状态为空的表示查找的值不存在
// 如果遇到不是已经被删除并且关键字与映射的值相等，则返回对应位置的地址
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
// 如果找到了就将对应位置设置为删除
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
return false;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXIST)
{
printf("[%ld]:[%d]\n", i, _tables[i]._kv.first);
}
else
{
printf("[%ld]:[%d]\n", i, -1);
}
}
}
private:
std::vector<HashData<K, V>> _tables;
size_t _size = 0; // 存储了多少个有效数据
};
在代码中，我们提到了扩容，那么哈希表什么情况下需要扩容，如何扩容？
void CheckCapacity()
{
if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 负载因子超过0.7就扩容
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
HashTable<K, V, Hash> newHT;
newHT._tables.resize(newSize);
// 旧表的数据遍历到新表
for (auto e : _tables)
{
if (e._state == EXIST)
newHT.Insert(e._kv);
}
std::swap(newHT._tables, _tables);
}
}
线性探测的优点：实现简单。
线性探测的缺点：一旦发生哈希冲突，所有冲突连载一起，容易产生数据堆积。并且寻找关键值需要比较多次比较，大大降低搜索效率。
线性探测的缺点是产生冲突的数据会堆积在一块，这与找下一个空位置有关，而且找空位置的方式是往后挨个挨个寻找，二次探测为了避免这个问题，改变了寻找下一个空位置的方法。也就是Hash(key) % capacity + (i * i)，i=1,2,3,...。
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
代码实现：
// 二次探测法
Hash hash;
size_t start = hash(kv.first) % _tables.size();
size_t i = 0;
size_t hashi = start + i;
while (_tables[hashi]._state == EXIST)
{
++i;
hashi = start + i * i;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_size;
开散列又叫链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集和，每一个子集和称为一个桶，各个桶的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
namespace HashBucket
{
// 哈希表的结点
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
template<class T, class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
// 析构函数
// 遍历数组，对每个结点进行delete内存释放
~HashTable()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
// 哈希桶的元素不能重复
Node* Insert(const T& data)
{
Hash hash;
// 去重
Node* ret = Find(data);
if(ret != nullptr)
{
return nullptr;
}
// 检查是否需要扩容
CheckCapacity();
size_t hashi = hash(data) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_size;
return newnode;
}
Node* Find(const T& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_data) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const T& key)
{
if (_tables.size() == 0)
{
return false;
}
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_data == key)
{
// 1、头删
// 2、中间删
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
size_t Size()
{
return _size;
}
// 表的长度
size_t TablesSize()
{
return _tables.size();
}
// 桶的个数
size_t BucketNum()
{
size_t num = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
++num;
}
}
return num;
}
// 最大桶的长度
size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
size_t len = 0;
Node* cur = _tables[i];
while (cur)
{
++len;
cur = cur->_next;
}
//if (len > 0)
//printf("[%d]号桶长度:%d\n", i, len);
if (len > maxLen)
{
maxLen = len;
}
}
return maxLen;
}
private:
std::vector<Node*> _tables;
size_t _size = 0; // 存储有效数据个数
};
}
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可
能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希
表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，
再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可
以给哈希表增容。
inline size_t __stl_next_prime(size_t n)
{
static const size_t __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return -1;
}
void CheckCapacity()
{
if (_size == _tables.size())
{
vector<Node*> newTables;
newTables.resize(__stl_next_prime(_tables.size()), nullptr);
// 旧表中节点移动映射新表
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
}
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
我们考虑一个场景，如果给你40亿个不重复的无符号整数，没排过序。给你一个无符号整数，如何快速判断一个数是否在这40亿个数中。
解决思路：我们只需要考虑这个值在还是不在这40亿个数之间，所以我们在存储元素的时候只用存储两种状态，一种是在，用比特位1表示，一种是不在，用比特位0表示。假设我们使用前面所说的哈希，那么想要快速定位，那就必须开40亿个空间（每个空间是一个bool类型）去存储，这样显然是不合理的。而这时候就需要用到位图，位图就是就是用一个比特位去存放数据，如果是40亿个数据，只需要40亿个bit位足矣。
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace ming
{
// 位图
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
}
// 把x位设置为1
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
// 把x位设置为0
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
// 检测位图中x是否为1
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
}
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？
布隆过滤器是由布隆提出的，它是用多个哈希函数，将一个数据映射到位图结构中。
布隆过滤器是一个bit数组。
使用三个哈希函数将baidu这个值映射到不同的bit位上，并将其设置为1。
再次插入tencent的时候，也是同样使用三个哈希函数去映射到对应的位置上，如果原本那个位置就是1，那么依然保持还是1。
// 三个哈希函数
struct BKDRHash
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
struct APHash
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& key)
{
size_t hash = 5381;
for(auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash,class Hash3 = DJBHash>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % ( _ratio * N );
_bits.set(hash1);
size_t hash2 = Hash2()(key) % ( _ratio * N );
_bits.set(hash2);
size_t hash3 = Hash3()(key) % ( _ratio * N );
_bits.set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio * N);
if (!_bits.test(hash1))
return false;
size_t hash2 = Hash2()(key) % (_ratio * N);
if (!_bits.test(hash2))
return false;
size_t hash3 = Hash3()(key) % (_ratio * N);
if (!_bits.test(hash3))
return false;
return true; // 可能存在误判
}
private:
const static size_t _ratio = 5; // 比率，比率越大表示误判越小
bitset<_ratio*N> _bits; // 使用位图数组作为底层数据结构
};
布隆过滤器的思想是一个元素用多个哈希函数映射到一个位图中，因此被映射的位置的bite一定是1。查找的思想就是，将我们要查找的元素分别使用不同哈希函数去映射，如果一旦遇到映射的值为0，表示这个值肯定不存在，如果映射的值都为1的话，那么这个值可能存在于布隆过滤器中。
布隆过滤器不支持删除操作，因为一旦删除一个元素的时候，可能会影响到其他元素。