黄骅市网站建设,做自媒体网站,网站页面自动还原代码,太原在建算法01之哈希法 1.哈希法理论基础1.1哈希表#xff08;1#xff09;哈希表#xff08;2#xff09;哈希函数#xff08;3#xff09;哈希碰撞 1.2哈希法基本思想1.3哈希法适用场景与最常用的哈希结构 2.LeetCode242#xff1a;有效的字母异位词#xff08;1#xff09… 算法01之哈希法 1.哈希法理论基础1.1哈希表1哈希表2哈希函数3哈希碰撞 1.2哈希法基本思想1.3哈希法适用场景与最常用的哈希结构 2.LeetCode242有效的字母异位词1图解本题的哈希内核2cpp代码 3.LeetCode349两个数组的交集1图解本题哈希内核2cpp代码 4.LeetCode202快乐数5.LeetCode11. 两数之和 1.哈希法理论基础
1.1哈希表
1哈希表 哈希表是一种数据结构用于存储键值对key-value pairs。它通过将键key通过哈希函数映射到一个特定的索引位置来实现快速的数据访问。这个索引位置在内存中的数组或桶buckets中使得在常数时间复杂度内可以进行查找、插入和删除操作。 想象一下你的家里有一个带有标签的抽屉。每个标签都对应着一个抽屉里的物品。当你需要某样东西时你不必搜索整个房子而是直接根据标签找到对应的抽屉这就像哈希表根据键找到对应的数值一样。这种快速定位的方式使得你能够在瞬间找到你需要的物品就像哈希表可以在常数时间内找到相应的值。
2哈希函数 哈希函数是一种将输入数据映射为固定长度散列值哈希值的函数。其主要目的是将任意长度的数据转换为固定长度的输出通常是一个固定大小的数字或字节序列。 哈希函数具有以下特性
确定性 相同的输入始终产生相同的哈希值。高效性 计算速度快能在合理时间内完成计算。离散性 输入数据的微小变化应该导致输出哈希值的显著变化。不可逆性 理论上不可通过哈希值逆向计算出原始输入数据。
常见的哈希函数有MD5、SHA-1、SHA-256等它们被广泛用于数据加密、数据完整性验证、密码存储等领域。
想象你是一位魔术师你有一个魔法箱子用来存放各种物品。你的目标是将每样物品放进箱子里并在箱子的每个格子上放置一个标签。这个标签不仅告诉你物品存放在哪里还得保证这个标签是独一无二的。你使用一个特殊的变化魔法哈希函数这个魔法会将每件物品都转化成一个独特的魔法标签让你可以快速地找到它们。所以当你需要取出某样物品时你只需使用这个特殊魔法它会让你知道这个物品的魔法标签而这个标签对应着箱子的一个格子。这就好像哈希函数把数据变成一个特殊的“标签”让你可以迅速找到存放的位置。而哈希函数的“魔法”在于无论你放进去什么样的物品它总是能给你一个独一无二的标签就像每件物品都有一个特殊的魔法标签一样。
3哈希碰撞 哈希碰撞指的是不同的输入数据经过哈希函数计算后得到了相同的哈希值。在理想情况下哈希函数应该能够将不同的输入映射到不同的哈希值但在实际应用中由于哈希函数将无限的输入空间映射到有限的输出空间发生哈希碰撞是可能的。 想象一下你是一个魔术师你的“蓝条”是有限的当你的蓝条不足时你的魔术可能会失灵而不准确。在你的魔法失效时这就可能会发生原来是一个标签对应一个物品的情况而编程一个标签对应两个或两个以上的物品。“蓝条”就相当于是哈希表的存储空间一个标签对应多个物品就是哈希碰撞。
哈希冲突可以通过以下几种方法解决
开放寻址法Open Addressing这种方法在哈希冲突发生时会寻找哈希表中的下一个可用位置并尝试将数据存储在那里。这包括线性探测、二次探测、双重哈希等技术逐个检查直到找到空槽来解决冲突。 链表法Chaining哈希表中的每个槽位不只是一个单独的位置而是一个链表或其他数据结构。当发生哈希冲突时将新的键值对添加到该位置的链表中。这样相同哈希值的元素都可以存储在同一个位置上而不会发生覆盖。 再哈希Rehashing当哈希表负载因子过高时可以重新调整哈希表的大小通常是增大容量然后重新哈希所有的键值对到新的表中。这可以减少冲突的发生因为新的更大的表提供了更多的空间来均匀分布键值对。 完美哈希函数Perfect Hashing这是一种在特定情况下能够完全避免冲突的方法。完美哈希函数能够保证每个键都映射到不同的位置但在实际中找到完美哈希函数可能比较困难。
选择哪种方法取决于应用的需求和数据特性。链表法在处理冲突时比较灵活但需要更多的存储空间。开放寻址法则在空间效率上更高但可能需要更多的探测步骤来解决冲突。再哈希和完美哈希函数则更多地关注于降低冲突的概率。
1.2哈希法基本思想 哈希法是一种基于哈希函数和哈希表的技术用于将数据映射到一个固定范围的索引位置以实现快速的查找、插入和删除操作。这个技术的核心是哈希函数它将数据转换为哈希值然后将该哈希值映射到哈希表中的特定位置。 1.3哈希法适用场景与最常用的哈希结构
在算法问题中哈希法通常用于
快速查找 哈希函数将数据映射为索引使得在哈希表中能够以常数时间复杂度O(1)进行查找操作。判断元素是否存在 通过哈希表的结构可以快速判断一个元素是否在集合中。去重操作 将数据存储在哈希表中可以自动去除重复元素只保留唯一的元素。
2.LeetCode242有效的字母异位词 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
示例 1: 输入: s “anagram”, t “nagaram” 输出: true 示例 2: 输入: s “rat”, t “car” 输出: false 提示: 1 s.length, t.length 5 * 104 s 和 t 仅包含小写字母 1图解本题的哈希内核 2cpp代码
//在s中出现的一个字母我们就增加其在OrccrenceWord中的值
//在t中出现该字母我们就减少其在orccrenceWord中的值
//如果s和t字符串是有效字母的异位词OrccurenceWord的每一项最后应该都是0
//因为对一组异位词s对一个字母提供的正增量刚好等于t对一个字母提供的负增量
class Solution {
public:bool isAnagram(string s, string t) {int OrccrenceWord[26] {0};for(int i: s){OrccrenceWord[i - a];}for(int i: t){OrccrenceWord[i - a]--;}for(int i 0; i 26; i){if(OrccrenceWord[i] ! 0){return false;}}return true;}
};3.LeetCode349两个数组的交集 给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1 输入nums1 [1,2,2,1], nums2 [2,2] 输出[2] 示例 2 输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4] 解释[4,9] 也是可通过的 提示 1 nums1.length, nums2.length 1000 0 nums1[i], nums2[i] 1000 1图解本题哈希内核 2cpp代码
//unordered_set是一种常用的数据结构适合在原数据规模很大或者原数据十分离散的情况
//unordered_set就像我们数学中的集合一样满足两个主要特性1.无需2.不重复
//result存储结果
//nums1_set利用这个数据结构类的构造函数哈希映射nums1对齐进行去重
//遍历nums2如果nums2中的元素在nums1中出现了就把它插入到结果哈希表result中最后返回结果哈希表
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result;unordered_setint nums1_set(nums1.begin(), nums1.end());for(int n: nums2){if(nums1_set.find(n) ! nums1_set.end()){result.insert(n);}}return vectorint(result.begin(), result.end()); }
};4.LeetCode202快乐数
5.LeetCode11. 两数之和
