这也就意味着当元素个数小于容器的大小时则每一个元素都能够找到自己唯一的一个地址来存放自己。由此引出了直接寻址法。 这种思想在之前的leetcode387题字符串中的第一个唯一字符中使用过。在这里插入图片描述代码语言javascriptAI代码解释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是关键字转换成的整数。1.4 哈希函数⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个⽅向去考量设计。除法散列法/除留余数法除法散列法是一种基于取模运算的散列函数设计方法。其基本思想是将键值 k 通过取模运算映射到散列表的某个位置。具体来说散列函数可以表示为 h(k) k % m 其中k 是键值m 是散列表的大小即表的长度h(k) 是计算得到的散列地址。取模运算的作用 取模运算的核心作用是将键值 k 映射到一个较小的范围内即 [0,m−1]。这样无论键值 k 有多大都可以通过取模运算将其“折叠”到散列表的有效索引范围内。选择合适的 m 选择合适的散列表大小 m 对于除法散列法的性能至关重要。理论上m 应该是一个质数因为质数可以减少键值之间的相关性从而降低冲突的概率。例如如果 m 是 2 的幂如 16、32、64 等那么取模运算可以简化为位运算但这种情况下冲突的概率可能会增加。因此选择一个质数作为 m 是一个较好的选择。乘法散列法乘法散列法的核心思想是通过乘法和位运算将键值映射到散列表的某个位置。其基本步骤如下选择一个常数 A常数 A 是一个介于 0 和 1 之间的浮点数通常选择为一个无理数如黄金分割比 ≈ 0.6180339887。选择无理数的原因是它可以更好地将键值分布到散列表的不同位置减少冲突的概率。计算乘积将键值 k 与常数 A 相乘得到一个浮点数 kA。提取小数部分从 kA 中提取小数部分即 {kA}kA−⌊kA⌋其中 ⌊x⌋ 表示对 x 向下取整。计算散列地址将提取的小数部分乘以散列表的大小 m并向下取整得到最终的散列地址。具体公式为h(k)⌊m⋅{kA}⌋全域散列法全域散列法Universal Hashing是一种高效的散列函数设计方法通过随机选择散列函数来减少冲突的概率从而提高散列表的性能。在这里插入图片描述P需要选⼀个⾜够⼤的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了⼀个P*(P-1)组全域散列函数组。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的⼀个散列函数使⽤后续增删查改都固定使⽤这个散列函数否则每次哈希都是随机选⼀个散列函数那么插⼊是⼀个散列函数查找⼜是另⼀个散列函数就会导致找不到插⼊的key了。1.5解决哈希冲突为了解决哈希冲突C 中主要有以下几种常用的方法一链地址法链地址法是将所有具有相同哈希值的键存储在一个链表中。每个哈希表的槽位对应一个链表的头指针。当发生冲突时新的键会被添加到相应链表的末尾。这种方法的优点是实现简单且能够很好地处理大量冲突的情况。例如对于上述提到的键 5 和 10 的冲突它们会被存储在同一个链表中通过遍历链表可以找到对应的键值对。二开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测、⼆次探测、双重探测。线性探测在这里插入图片描述二次探测在这里插入图片描述双重探测在这里插入图片描述.三再哈希法再哈希法是当发生冲突时使用另一个哈希函数重新计算哈希值直到找到空闲位置。这种方法可以有效避免聚集现象但需要设计两个合适的哈希函数且计算成本相对较高。例如第一个哈希函数是hash1(key) key % table_size第二个哈希函数是hash2(key) prime - (key % prime)其中 prime 是小于哈希表大小的质数。当发生冲突时通过hash(key, i) (hash1(key) i * hash2(key)) % table_size来寻找新的位置i 是探测次数。
C++之哈希表的基本介绍以及其自我实现
这也就意味着当元素个数小于容器的大小时则每一个元素都能够找到自己唯一的一个地址来存放自己。由此引出了直接寻址法。 这种思想在之前的leetcode387题字符串中的第一个唯一字符中使用过。在这里插入图片描述代码语言javascriptAI代码解释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是关键字转换成的整数。1.4 哈希函数⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个⽅向去考量设计。除法散列法/除留余数法除法散列法是一种基于取模运算的散列函数设计方法。其基本思想是将键值 k 通过取模运算映射到散列表的某个位置。具体来说散列函数可以表示为 h(k) k % m 其中k 是键值m 是散列表的大小即表的长度h(k) 是计算得到的散列地址。取模运算的作用 取模运算的核心作用是将键值 k 映射到一个较小的范围内即 [0,m−1]。这样无论键值 k 有多大都可以通过取模运算将其“折叠”到散列表的有效索引范围内。选择合适的 m 选择合适的散列表大小 m 对于除法散列法的性能至关重要。理论上m 应该是一个质数因为质数可以减少键值之间的相关性从而降低冲突的概率。例如如果 m 是 2 的幂如 16、32、64 等那么取模运算可以简化为位运算但这种情况下冲突的概率可能会增加。因此选择一个质数作为 m 是一个较好的选择。乘法散列法乘法散列法的核心思想是通过乘法和位运算将键值映射到散列表的某个位置。其基本步骤如下选择一个常数 A常数 A 是一个介于 0 和 1 之间的浮点数通常选择为一个无理数如黄金分割比 ≈ 0.6180339887。选择无理数的原因是它可以更好地将键值分布到散列表的不同位置减少冲突的概率。计算乘积将键值 k 与常数 A 相乘得到一个浮点数 kA。提取小数部分从 kA 中提取小数部分即 {kA}kA−⌊kA⌋其中 ⌊x⌋ 表示对 x 向下取整。计算散列地址将提取的小数部分乘以散列表的大小 m并向下取整得到最终的散列地址。具体公式为h(k)⌊m⋅{kA}⌋全域散列法全域散列法Universal Hashing是一种高效的散列函数设计方法通过随机选择散列函数来减少冲突的概率从而提高散列表的性能。在这里插入图片描述P需要选⼀个⾜够⼤的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了⼀个P*(P-1)组全域散列函数组。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的⼀个散列函数使⽤后续增删查改都固定使⽤这个散列函数否则每次哈希都是随机选⼀个散列函数那么插⼊是⼀个散列函数查找⼜是另⼀个散列函数就会导致找不到插⼊的key了。1.5解决哈希冲突为了解决哈希冲突C 中主要有以下几种常用的方法一链地址法链地址法是将所有具有相同哈希值的键存储在一个链表中。每个哈希表的槽位对应一个链表的头指针。当发生冲突时新的键会被添加到相应链表的末尾。这种方法的优点是实现简单且能够很好地处理大量冲突的情况。例如对于上述提到的键 5 和 10 的冲突它们会被存储在同一个链表中通过遍历链表可以找到对应的键值对。二开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测、⼆次探测、双重探测。线性探测在这里插入图片描述二次探测在这里插入图片描述双重探测在这里插入图片描述.三再哈希法再哈希法是当发生冲突时使用另一个哈希函数重新计算哈希值直到找到空闲位置。这种方法可以有效避免聚集现象但需要设计两个合适的哈希函数且计算成本相对较高。例如第一个哈希函数是hash1(key) key % table_size第二个哈希函数是hash2(key) prime - (key % prime)其中 prime 是小于哈希表大小的质数。当发生冲突时通过hash(key, i) (hash1(key) i * hash2(key)) % table_size来寻找新的位置i 是探测次数。
