哈希表(Hash Table) :通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
哈希函数(Hash Function) :将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希冲突(Hash Collision) :不同的关键字通过同一个哈希函数可能得到同一哈希地址。
哈希表的两个核心问题是: 「哈希函数的构建」 和 「哈希冲突的解决方法」 。
常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。
常用的哈希冲突的解决方法有两种:开放地址法和链地址法。
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。
如果存在则返回 true,不存在返回 false。
给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
力扣217
力扣389
力扣496
内容参考: https://algo.itcharge.cn/05.%E5%93%88%E5%B8%8C%E8%A1%A8/01.%E5%93%88%E5%B8%8C%E8%A1%A8%E7%9F%A5%E8%AF%86/
一开始看到哈希表这个词,感觉非常的陌生,因为是从hash音译过来的,但是哈希表是一种非常有用的数据结构,可以提高效率。其实Python中的字典,就是一种典型的哈希表结构。用字典这个词,其实更好理解:
字典的结构是这样子的,总是成对出现:
{'姓名':'张三' , ’年龄‘:'18', '籍贯':'北京' , ‘三围’:[88,68,94]}
其中“张三”“年龄”“籍贯”“三围”这些叫做键,“张三”“18”“北京”“88,68,94”是他们相对应的值,通过查询键,我们就可以直接访问相对应的值。这个过程就像查字典一样,我们知道一个字的部首,就可以快速的找到这个字在哪一页。
思路:1、首先采用命A=0,C=1,G=2,T=3. 就相当于4进制数字,然后采用karp-Rabin算法转换成唯一十进制数字。由于用此算法的哈希函数为:hash(value)=value*(4^(k-q-1))
value是该字符对应的值,k是kmer长度,q是此字符在字符串的位置范围在[0-(q-1)]。然后把一个kmer里面所有字符的hash值求和就行了。
2、那么很容易看出来,对于连续的下害常愤端莅得缝全俯户一个Kmer,就有推理公式了 hashNew=addValue+(hashOld-deleteValue*(4^(k-1)))*4hashNew就是往右平移一个字符的kmer hash值,hashOld就是平移之前的值,addValue就是平移后右边多的一个字符,deleteValue就是平移后左边少的一个字符。这样整个hash表建立的时间复杂度约为O(m+k),m是整个文本长度。
3、由于kmer长度如果过长,其hash值过大,会造成内存不够溢出的现象,所以kmer内部定死为10 。那么问题就来了,如何应对不同的kmer值。分三种情况。
第一种:q>10
这种可以将kmer以10为单位,将hash表中对应值取出,然后对结果进行分析,这边分析方法为建立两个数组一个二维数组unionName储存位置关系,一个一维数组unionScore,计数用。 思路就是首先第一轮初始化unionName[Name][Pos]全部赋值Pos 并初始化unionScore,然后再第二轮匹配如果unionName[Name][Pos-cycle]=Pos-1则将其赋值为当前Pos,cycle为当前循环次数。并将当前循环数存入unionScore[NAME]中。最后当unionScore[NAME]值也就是循环数为k-1,即我们需要的交集了。
第二种:q=10
直接求出hash值,取出相应的值即可。
第三种:q<10
可以用前缀种子+后缀种子交集产生。
前缀种子:在字符串后面补字符直到长度等于K,这个很容易看出来 最小是全补A,最大是全补T,然后将最小值到最大值之间的hash值即为所求。
后缀种子:后缀种子和前缀种子不同就是在字符串左边补齐字符。所以此时需要进行变换。只要对前置种子产生的值变化下就行了。(preValue-minValue)*(4^(K-q))+hash(p) 。其中preValue就是对应的前置种子的hash值,minValue就是前置种子中最小值也就是全补A的情况,hash(p)就是字符串长度为p时候的hash值。
交集就是先求后缀种子所有的值,再加上 前缀种子中起始位置在[0-(k-1)]中的值。