哈希表
哈希表理论基础
哈希表,又称为散列表(Hash Table),是根据关键码的值而直接进行访问的数据结构
其中,数组就是一张哈希表;表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素
- 哈希表解决的问题:一般哈希表都是用来快速判断一个元素是否出现在集合中
- 哈希函数:把学生的姓名直接映射为哈希表上的索引。
- index = hashFunction(name);
- hashFunction() : hashCode(name) % tableSize;
- 对数值取模的操作,保证数值一定可以映射到哈希表上
- 哈希碰撞:拉链法和线性探测法
- 拉链法:直接延伸链表
- 线性探测法:放在表的下一个位置
常见的三种哈希结构
- 数组
- set(集合)
在C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:
集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
- map(映射)
映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。
- 总结:当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法
- 但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组
有效的字母异位词(力扣242.)
- 数组就是一个简单哈希表
- 可以定义一个数组,来记录字符串s里字符出现次数
- 只需要将s[i] - 'a' 所在的元素做+1操作即可
class Solution {
public boolean isAnagram(String s, String t) {
//新建数组
int[] data = new int[26];
for(int i = 0;i < s.length();i++){
//s.charAt(i)为字符串s的第i个元素
data[s.charAt(i) - 'a']++;
}
for(int j = 0;j < t.length();j++){
data[t.charAt(j) - 'a']--;
}
//遍历data数组
for(int count : data){
if(count != 0){
return false;
}
}
return true;
}
}
两个数组的交集(力扣349.)
使用数组做哈希
- 数组在原基础上多建一些空间,防止溢出
- 底部为哈希表的set:Set
result = new HashSet<>(); - 新建一个数组,如果nums1存在值,就在数组下标中++;
- 遍历nums2,对比数组,如果都显示存在,则插入到result中
- 最后将result转换为数组,并返回
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums2 == null){
return null;
}
//用数组实现
int[] data = new int[1005];
for(int i = 0; i < data.length;i++){
data[i] = 0;
}
Set<Integer> result = new HashSet<>();
for(int count : nums1){
data[count] = 1;
}
for(int count2 : nums2){
if(data[count2] == 1){
result.add(count2);
}
}
//set转换为数组
int[] resultArr = new int[result.size()];
int index = 0;
for(int j : result){
resultArr[index ++] = j;
}
return resultArr;
}
}
用Set实现
- 过程中间暂存的容器变为集合(set),其他不变
- 暂存容器变为set集合,在不限定数值大小及规模时更有效
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums2 == null){
return null;
}
//用集合(SET)实现,set属性即不存在重复的元素
Set<Integer> result = new HashSet<>();
Set<Integer> set1 = new HashSet<>();
for(int i : nums1){
set1.add(i);
}
for(int j : nums2){
if(set1.contains(j)){
result.add(j);
}
}
//set转换为数组
int[] resultArr = new int[result.size()];
int index = 0;
for(int j : result){
resultArr[index ++] = j;
}
return resultArr;
}
}
快乐数(力扣202.)
- 这道题目看上去貌似一道数学问题,其实并不是!
- 题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!
- 还有一个难点就是求和的过程,如果对取数值各个位上的单数操作不熟悉的话,做这道题也会比较艰难。
class Solution {
public boolean isHappy(int n) {
Set<Integer> plant = new HashSet<>();
while(n != 1 && !plant.contains(n)){
plant.add(n);
n = getNextNumber(n);
}
return n==1;
}
public int getNextNumber(int n){
int res = 0;
while(n > 0){
res += (n%10) * (n%10);
n = n /10;
}
return res;
}
}
两数之和(力扣1.)
- 首先我在强调一下 什么时候使用哈希法,当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。
- 本题呢,我就需要一个集合来存放我们遍历过的元素,然后在遍历数组的时候去询问这个集合,某元素是否遍历过,也就是 是否出现在这个集合。
- 因为本地,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适。
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums==null||nums.length<2){
return new int[2];
}
Map<Integer,Integer> map = new HashMap<>();
for(int i =0;i < nums.length;i++){
int temp = target - nums[i];
if(map.containsKey(temp)){
return new int[]{map.get(temp),i};
}
map.put(nums[i],i);
}
return new int[2];
}
}
标签:map,set,哈希,int,数组,力扣,key,242,两数
From: https://www.cnblogs.com/zcctxr/p/17595301.html