LeetCode第一讲:哈希表相关讲解

哈希表简单说明

哈希表的建立需要有哈希地址,那么哈希地址地址的生成需要一个哈希函数,什么是哈希函数呢?
哈希函数就是一个精心设计好的函数,该函数可以计算出存储的数据要放在什么位置,举个例子说明:

例:有4条电话数据:
王二蛋 12345678985
李狗蛋 11554456555
赵二狗 18816848615
李桂花 15899484538

如果我想查找王二蛋的电话,我需要拿出这个列表,一个一个找。但我想要通过名字快速查找王二蛋如何做呢?

答:我构建一个哈希表,来快速查找。那么通过名字来存的话,我需要构建一套规则来定位数据的存储位置。那么我构建如下的函数 Addr = H(”姓名“的首字母 ASCII - 65 ),需要一个32大小数组来存储数据。

但是如果按照刚刚的设计,那么”李桂花“与”李狗蛋“的存储就会发生冲突,那么在设计哈希函数有如下几种方式(对于哈希表而言,冲突只能尽可能地少,无法完全避免。)

哈希表构建

1、直接定址法
例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。
2、数字分析法
有学生的生日数据如下:
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15

经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。
3、平方取中法
取关键字平方后的中间几位为哈希地址。
4、折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。
例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。
5、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
6、随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即
H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。
若已知哈希函数及冲突处理方法,哈希表的建立步骤如下:
Step1. 取出一个数据元素的关键字key,计算其在哈希表中的存储地址D=H(key)。若存储地址为D的存储空间还没有被占用,则将该数据元素存入;否则发生冲突,执行Step2。
Step2. 根据规定的冲突处理方法,计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用,则存入;否则继续执行Step2,直到找出一个存储空间没有被占用的存储地址为止。

冲突处理

1、拉链法
拉出一个动态链表代替静态顺序存储结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度。此法可以完全避免哈希函数的冲突。
2、多哈希法
设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低(除非人品太差,否则几乎不可能冲突)。
3、开放地址法
开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。
如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)
称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。
4、建域法
假设哈希函数的值域为[0,m-1],则设向量HashTable[0…m-1]为基本表,另外设立存储空间向量OverTable[0…v]用以存储发生冲突的记录。

题目1:

给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]

说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

题目地址:https://leetcode-cn.com/problems/intersection-of-two-arrays
来源:力扣(LeetCode)

题目解答:

public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for(int i :nums1){
set.add(i);
}
Set<Integer> set2 = new HashSet<>();
for(int j:nums2){
if(set.contains(j)){
set2.add(j);
}
}
int[] st = new int[set2.size()];
Object[] kk = set2.toArray();
for(int i=0;i<kk.length;i++){
st[i] = (int)kk[i];
}
return st;
}

解答说明:
该题由于要算交集,数组还有重复的可能行,那么就采用java中有的HashSet来处理问题,HashSet底层源码是实现了一个hashMap,HashMap实际上就是哈希表的实现,那么可以直接用hash表的特点来去重,再由hash表的特点来查询交集。算法实际时间复杂度为O(m+n) 空间复杂度:O(m+n)

题目2:

写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3]

示例2:
输入:[1, 1, 1, 1, 2]
输出:[1, 2]
提示:

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
题目地址:https://leetcode-cn.com/problems/remove-duplicate-node-lcci
来源:力扣(LeetCode)

题目解答:

public ListNode removeDuplicateNodes(ListNode head) {
Set<Integer> set = new HashSet<>();
ListNode root = head;
ListNode temp = head;
ListNode pre = null;
while (temp!=null){
if(set.contains(temp.val)){
temp = temp.next;
pre.next = temp;
}else{
set.add(temp.val);
pre = temp;
temp = temp.next;
}
}
return root;
}

解答说明:
采用hash表的hash唯一性来做缓冲区,时间复杂度:O(n) 空间复杂度:O(n)

2 个评论

顶 好帖子。火钳刘明
贼6贼6

要回复文章请先登录注册