1 哈希表(Hash Table)理论
官方说法:哈希表是根据关键码的值直接进行访问的数据结构
这么说比较晦涩,其实一个数组就是一张哈希表.哈希表中关键码就是数组的索引下标.
1.1 哈希表能解决的问题:
用来快速判断一个元素是否在集合里.
或者比较A和B元素个数是否相同(也就是所有A元素都在B集合里,其实就是A和B元素及元素个数相同,看下面第一个例子)/A和B的交集(看下面第二个),这些本质上都是判断某个元素在集合里出现过没
我的理解就是,把西瓜苹果进货,按hashTable放到对应的柜子里,柜子总数是所有水果种类,然后存好了下次问你来找某个水果/或者比较个数
比如一个人是不是在某所学校,用枚举的时间复杂度是O(n).用哈希表的时间复杂度是O(1).
怎么做到的呢?初始化就把所有名字都存到哈希表了.查询的时候就能直接通过索引找了.
而把名字映射到哈希表就涉及到了哈希函数(hash function)
1.2哈希函数
在存储数据时,我们先对数据进行一些简单描述,比如“苹果,22块,快坏了”,对这些信息用哈希函数处理后就得到了一个通过整数index(里面的过程是通过对信息通过特定编码后的hashcode取余tablesize)
- 但是就算通过这个编码方式映射的再均匀,数据个数大于tablesize的话总会有不同的数据落到同一个索引下标的位置(同一个抽屉).由此引出哈希碰撞(hash collision)
1.3 哈希碰撞 hash collision
不同数据映射到同一索引下标的位置
两种解决方法:
-
拉链法
冲突的地方设成链表
image.png 线性探测法
前提:tablesize要大于datasize,才能用表里的空位解决collision
1.4常见的哈希结构
- 数组(数组就是个简单哈希表)
- set
- map
基本判断:hash表范围不大,可控的时候用数组(比如26个字母);
范围特别大或者数值虽然不大,但是分布特别散,一个在1,一个在100W用set;
出现key,value用map
2 242.有效的字母异位词
2.1tips
- [i-'a']在JS里不能自动转化成ASCII码相减(是在C里可以),我一开始和'2'-'1'字符串自动转为number相减混淆了
- 要得到字母对应的ASCII码,JS里用的是字符串的方法
charCodeAt() - JS里用
for...of...可以遍历数组、set、map、字符串.
3 349.两个数组的交集
这个题leecode改过范围,变小了所以用数组也可以做,这里我们要求用set做,练手
3.1 tips
-
JS中的set 用
let mySet = new Set([1,2,3])定义,()里面是个数组.这是ES6引入的,同时引入的还有map- set的元素是唯一的,重复添加也没用,只留一个
比较nums1和nums2的大小,从而后面循环的时候用小的,优化性能.
建了两个set,一个是长的数组的set,其实就是hashTable,另一个放结果.
set的
has()方法直接找索引,时间复杂度O(1)向set添加元素:
set.add()-
最后还要用
Array.from(resSet)来把set转化成array返回- 力扣上大部分都是让返回数组,除非他让你
return(Set<number>)
- 力扣上大部分都是让返回数组,除非他让你
-
学了个if单行代码的炫技写法:
if(A)B;写成A&&BA成立的时候后面的statement肯定是true
(学错了,&&后面得是expression不能是statement,statement不产生value,所以下面的写法不对:)
(nums1.length<nums2.length) && [nums1,nums2] = [nums2,nums1];只有expression才能返回value,&&右边明显是statement
正确的写法:num1Set.has(nums2[i])&&resSet.add(nums2[i]);
4 202.快乐数
题解说也用set,但是我想不出来这个要把什么放到盒子里,不知道要把什么设成hashtable,然后看了眼题目,觉得应该是判断是不是会循环,因为如果出现了之前的就说明循环了
5 1.两数之和
为什么不用array:存字母好存,且能控制长度,但是这个题目n的长度不一定多大.
为什么不用set:返回不了下标.
所以用map.
那么就有两个问题需要解决:
- map用来干嘛
用来在我们遍历当前元素的时候询问map里有没有已经遍历过的与当前元素的值相加=target的元素,没有就把当前元素添加进去 - map的key和value都是什么
这里也有个很容易出错的点:我总是默认把下标当key,元素值当value,
但是我们要找的是value,所以把元素值当value反而更直观
5.1 tips
- 做到这个题的时候我还没复习到map,下意识以为和Set一样要new Set()这样,但是如果不是很复杂的问题,比如要频繁删除键值对的话,直接用对象就行了:
test = {};然后其中的key的表示方法就是test[]所以遍历的时候就可以用test[target-nums[i]]
