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;//当前使用的素数表中的下标
};更多推荐
11
0- 0
已为社区贡献23条内容
所有评论(0)