C++数据结构--哈希表

一.什么是哈希表

哈希表（Hash Table），也叫散列表，是一种根据关键码值（Key）直接访问记录的数据结构。在理想情况下，哈希表进行数据查找、插入和删除操作的时间复杂度接近 O(1)，是目前计算机世界中查找速度最快的结构之一，当然其也存在缺点：空间利用率不高。

二.哈希表的核心原理

1.哈希函数

哈希函数是哈希表的核心，它的作用是把任意长度的输入（Key）转换成固定的数组下标。

哈希函数有很多不同的构造方法，但核心都是将输入的key尽量均匀的地“散列”到整个数组的各个位置上，减少哈希冲突的可能。

最常见的哈希函数是除留余数法：其原理是：index = key % p（这里的p简单的话可以取数组的长度，但在实际应用中，p 通常不等于数组长度 m，而是取小于或等于 m 的最大质数（素数）。）

2.哈希冲突

上面我们说到，哈希函数的一个重要作用就是减少哈希冲突的可能，那么什么是哈希冲突呢？

我们拿最常见的除留余数法来说，由于我们使用的是相除然后取余数的做法，假设我们找到的p为5，我们需要存储6和11两个数字，按照除留余数法，两个结果都取1，那么这两个数字都应该存储在数组的1号位置，但是毫无疑问，我们数组的1号位置只能存储一个元素，那么这两个数字就会发生冲突，当然如果存储的数据量大于数组的长度，冲突就 100% 会发生。

总结一下就是由于数组的长度是有限的，当不同的键（Key）通过哈希函数计算后，得到了相同的数组下标时，就会发生“哈希冲突”（Hash Collision）。

3.哈希冲突的解决方法

目前主流的解决方案有两种：

（1）链地址法（拉链法）

原理：数组的每个位置不直接存储数据，而是挂着一个链表（或红黑树）。当发生冲突时，直接把新数据添加到对应位置的链表末尾即可。
特点：实现简单，删除方便，是目前最主流的做法（C++ 的 unordered_map 就是采用的此法）。

（2）开放寻址法

原理：所有数据都必须存在数组内部。如果算出的位置被占了，就按照某种规则（比如往后挪一位、跳着挪等）去寻找下一个空闲的位置。

这里的挪位规则也存在很多：最简单的是线性探测，就是发生哈希冲突后，向后挪一位，但是这种做法的性能并不好，所以我们通常采用二次探测，向后面挪1²、2²、3²...位。

特点：没有额外的指针开销，内存连续，缓存友好；但删除数据比较麻烦，且数组容易存满。

4.减少哈希冲突的方法

当处理大量数据时，哈希冲突通常无法避免，但是我们能够通过适当的操作尽量减少哈希冲突发生的概率，核心操作有两个。

（1）选择合适的哈希函数

（2）合理的控制动态扩容

为了合理的控制动态扩容，我们定义了负载因子（Load Factor），其是衡量哈希表“拥挤程度”的指标（已存元素数 / 数组总长度），负载因子越大，冲突概率越高，所以我们通常会设定一个阈值（一般为0.75），当元素数量超过阈值时，哈希表会自动创建一个更大的数组（通常是翻倍，更好的做法是按照一个素数标扩容），并将所有旧数据重新计算位置搬运过去。这能有效降低负载因子，从根本上减少后续插入时的冲突概率。

三.代码实现

1.基于开放寻址法线性探测的哈希表

//桶的状态 enum State { STATE_UNUSE,//桶从未被使用过 STATE_USING,//桶正在被使用 STATE_DEL//桶元素被删除了 }; //桶的类型 struct Bucket { Bucket(int key = 0, State state = STATE_UNUSE) :m_key(key) , m_state(state) { } int m_key;//存储的元素 State m_state;//桶的状态 }; //线性探测哈希表 class HashTable { public: HashTable(int size = prime[0], double loadFactor = 0.75) : m_loadFactor(loadFactor) , m_useBucketnum(0) , primeIdx(0) { if (size != prime[0]) { for (; primeIdx < PRIME_SIZE; primeIdx++) { if (prime[primeIdx] > size) { size = prime[primeIdx]; break; } if (primeIdx == PRIME_SIZE) { primeIdx--; } } } m_tableSize = prime[primeIdx]; m_table = new Bucket[m_tableSize]; } ~HashTable() { delete[] m_table; m_table = nullptr; } public: //插入元素(key可重复) bool insert(int key) { //扩容 double factor = m_useBucketnum*1.0 / m_tableSize; if (factor >= m_loadFactor) { expend(); } int idx = key % m_tableSize; int i = idx; do { if (m_table[i].m_state!= STATE_USING) { m_table[i].m_state = STATE_USING; m_table[i].m_key = key; m_useBucketnum++; return true; } i = (i + 1) % m_tableSize; } while (i!=idx); return false; } //删除(同值的全部元素) bool erase(int key) { if (m_useBucketnum == 0) { throw "HashTable is empty"; } else { bool flag = false; int idx = key % m_tableSize; int i = idx; do { if (m_table[i].m_state== STATE_USING&&m_table[i].m_key==key) { m_table[i].m_state = STATE_DEL; m_useBucketnum--; flag = true; } i = (i + 1) % m_tableSize; } while (i!=idx&&m_table[i].m_state!= STATE_UNUSE); return flag; } } //查找 bool find(int key) { if(m_tableSize==0) throw "HashTable is empty"; else { int idx = key % m_tableSize; int i = idx; do { if (m_table[i].m_state == STATE_USING && m_table[i].m_key == key) { return true; } i = (i + 1) % m_tableSize; } while (i != idx && m_table[i].m_state != STATE_UNUSE); return false; } } private: //扩容 void expend() { primeIdx++; if (primeIdx == PRIME_SIZE) { throw "HashTable is too large can not expend"; } else { Bucket* new_m_table = new Bucket[prime[primeIdx]]; for (size_t i = 0; i < m_tableSize; i++) { if (m_table[i].m_state== STATE_USING) { int idx =m_table[i].m_key % prime[primeIdx]; int k = idx; do { if (new_m_table[k].m_state != STATE_USING) { new_m_table[k].m_key = m_table[i].m_key; new_m_table[k].m_state = STATE_USING; break; } k = (k + 1) % prime[primeIdx]; } while (k!=idx); } } m_tableSize = prime[primeIdx]; delete[] m_table; m_table = nullptr; m_table = new_m_table; } } private: Bucket* m_table;//指向动态开辟的哈希表 int m_tableSize;//哈希表的长度 int m_useBucketnum;//已经使用的桶的个数 double m_loadFactor;//装载因子 static const int PRIME_SIZE = 10;//素数表元数个数 static int prime[PRIME_SIZE];//素数表 int primeIdx;//当前使用的素数表中的下标 };

2.基于链地址法实现的哈希表

class HashTable { public: HashTable(int size = prime[0], double loadFactor = 0.75) :m_useBucketnum(0) , m_loadFactor(loadFactor) , primeIdx(0) { if (size != prime[0]) { for (; primeIdx < PRIME_SIZE; primeIdx++) { if (prime[primeIdx] > size) { size = prime[primeIdx]; break; } if (primeIdx == PRIME_SIZE) { primeIdx--; } } } m_table.resize(size); } //增加元素（key不可重复) void insert(int key) { double factor = m_useBucketnum * 1.0 / m_table.size(); if (factor >= m_loadFactor) { expend(); } int idx = key % m_table.size(); if (m_table[idx].empty()) { m_useBucketnum++; m_table[idx].emplace_front(key); } else { auto it = ::find(m_table[idx].begin(), m_table[idx].end(), key); if (it == m_table[idx].end()) { m_table[idx].emplace_front(key); } } } //删除 void erase(int key) { if (m_useBucketnum == 0) throw "HashTable is empty"; else { int idx = key % m_table.size(); auto it = ::find(m_table[idx].begin(), m_table[idx].end(), key); if (it != m_table[idx].end()) { m_table[idx].erase(it); if (m_table[idx].empty()) m_useBucketnum--; } } } //查找 bool find(int key) { if (m_useBucketnum == 0) throw "HashTable is empty"; else { int idx = key % m_table.size(); auto it = ::find(m_table[idx].begin(), m_table[idx].end(), key); if (it != m_table[idx].end()) { return true; } else return false; } } private: //扩容 void expend() { if (primeIdx + 1 == PRIME_SIZE) { throw "HashTable is too large can not expend"; } else { primeIdx++; m_useBucketnum = 0; vector<list<int>>new_m_table; m_table.swap(new_m_table); m_table.resize(primeIdx); for (auto list:new_m_table) { for (auto key:list) { int idx = key % m_table.size(); if (m_table[idx].empty()) { m_useBucketnum++; } m_table[idx].emplace_front(key); } } } } private: vector<list<int>>m_table;//哈希表数据结构 int m_useBucketnum;//记录使用的桶的个数 double m_loadFactor;//装载因子 static const int PRIME_SIZE = 10;//素数表元数个数 static int prime[PRIME_SIZE];//素数表 int primeIdx;//当前使用的素数表中的下标 };