这也就意味着,当元素个数小于容器的大小时,则每一个元素都能够找到自己唯一的一个地址来存放自己。由此引出了直接寻址法。这种思想,在 LeetCode 387 题'字符串中的第一个唯一字符'中有所体现。
class Solution {
public:
int firstUniqChar(string s) {
int count[26] = {0};
for(auto e : s) {
count[e-'a']++;
}
for(int i = 0; i < s.size();i++) {
if(count[s[i] - 'a'] == 1) return i;
}
return -1;
}
};
将每一个字符出现的次数存储到大小为 26 的数组中,找到次数为 1 的字符。但我们的哈希表如果使用上述方式实现,必然会造成效率低下。而 C++ 的大佬们,早已实现各种方法的哈希表,让我们来看看。
一、哈希概念
哈希 (hash) 又称散列,是一种组织数据的方式。从译名来看,有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系,查找时通过这个哈希函数计算出 Key 存储的位置,进行快速查找。
1.1 哈希冲突
两个不同的 key 可能会映射到同一个位置去,这种问题我们叫做哈希冲突,或者哈希碰撞。
哈希冲突的产生原因
哈希冲突是指不同的键通过哈希函数计算后,得到了相同的哈希值,从而被映射到哈希表中相同的位置。产生哈希冲突的原因主要有以下几点:
(一)哈希函数的局限性
哈希函数的设计至关重要,但再好的哈希函数也无法完全避免冲突。理想情况下,哈希函数应该能够将不同的键均匀地分布到哈希表的各个位置,但实际上,由于键的集合通常是无限的,而哈希表的大小是有限的,这就导致了不同键产生相同哈希值的情况。例如,对于简单的取模哈希函数 hash(key) = key % table_size,当键是 5 和 10,且哈希表大小为 5 时,它们的哈希值都是 0,从而产生冲突。
(二)键的分布特性
键本身的分布特性也会影响哈希冲突的发生。如果键的分布较为集中,即大量键的特征相似,那么它们通过哈希函数计算后更容易产生相同的哈希值。比如,在一个存储用户信息的哈希表中,如果用户 ID 是连续的整数,且哈希表大小较小,那么相邻的用户 ID 很可能产生冲突。
1.2 负载因子
假设哈希表中已经映射存储了 N 个值,哈希表的大小为 M,那么负载因子 = N/M。负载因子有些地方也翻译为载荷因子/装载因子等,它的英文为 loadfactor。负载因子越大,哈希冲突的概率越高,空间利用率越高;负载因子越小,哈希冲突的概率越低,空间利用率越低。
1.3 将关键字转为整数
我们将关键字映射到数组中位置,一般是整数好做映射计算,如果不是整数,我们要想办法转换成整数,这个细节我们在后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时,如果关键字不是整数,那么我们讨论的 Key 是关键字转换成的整数。

