哈希表理论基础

hashset

 HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

import java.util.HashSet; // 引入 HashSet 类
HashSet<String> sites = new HashSet<String>(); 

 add()添加元素

contains() 方法来判断元素是否存在于集合当中

remove() 方法来删除集合中的元素

clear 方法删除集合中所有元素可以

size() 方法计算 HashSet 中的元素数量

for-each 来迭代 HashSet 中的元素

hashmap

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

import java.util.HashMap; // 引入 HashMap 类
HashMap<Integer, String> Sites = new HashMap<Integer, String>();

添加键值对(key-value)可以使用 put() 方法

get(key) 方法来获取 key 对应的 value 

remove(key) 方法来删除 key 对应的键值对(key-value)

删除所有键值对(key-value)可以使用 clear 方法

要计算 HashMap 中的元素数量可以使用 size() 方法

for-each 来迭代 HashMap 中的元素

获取 key，可以使用 keySet() 方法，然后可以通过 get(key) 获取对应的 value，如果你只想获取 value，可以使用 values() 方法

方法	描述
clear()	删除 hashMap 中的所有键/值对
clone()	复制一份 hashMap
isEmpty()	判断 hashMap 是否为空
size()	计算 hashMap 中键/值对的数量
put()	将键/值对添加到 hashMap 中
putAll()	将所有键/值对添加到 hashMap 中
putIfAbsent()	如果 hashMap 中不存在指定的键，则将指定的键/值对插入到 hashMap 中。
remove()	删除 hashMap 中指定键 key 的映射关系
containsKey()	检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	检查 hashMap 中是否存在指定的 value 对应的映射关系。
replace()	替换 hashMap 中是指定的 key 对应的 value。
replaceAll()	将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。
get()	获取指定 key 对应对 value
getOrDefault()	获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
forEach()	对 hashMap 中的每个映射执行指定的操作。
entrySet()	返回 hashMap 中所有映射项的集合集合视图。
keySet()	返回 hashMap 中所有 key 组成的集合视图。
values()	返回 hashMap 中存在的所有 value 值。
merge()	添加键值对到 hashMap 中
compute()	对 hashMap 中指定 key 的值进行重新计算
computeIfAbsent()	对 hashMap 中指定 key 的值进行重新计算，如果不存在这个 key，则添加到 hasMap 中
computeIfPresent()	对 hashMap 中指定 key 的值进行重新计算，前提是该 key 存在于 hashMap 中。

242.有效的字母异位词

1.题目描述

力扣链接

2.适用场景

• 时间复杂度: O(n)
• 空间复杂度: O(1)

3.做题思路

建立一个26个字母的数组，将字符串s中的字符每出现一次加一，将字符串t中的字符每出现一次减一，最后查看数组是否为0。记录不同字母的位置使用相对于a的相对位置。

视频讲解

4.代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        int [] record = new int[26];
        for(int i=0;i<s.length();i++){
            record[s.charAt(i)-'a']++;
        }
        for(int i=0;i<t.length();i++){
            record[t.charAt(i)-'a']--;
        }
        for(int count:record){
            if(count != 0){
                return false;
            }
        }
        return true;
    }
}

5.总结

对于字符串的length方法，是一个无参的方法，需要使用()来表示方法的调用。因此，在使用字符串的length方法时，必须写成s.length()，其中的()是不可省略的。

s.charAt(i)：s中的第i个元素的ascii

349. 两个数组的交集

1.题目描述

力扣链接

2.适用场景

• 时间复杂度: O(n + m) m 是最后要把 set转成vector
• 空间复杂度: O(n)

3.做题思路

将数组1所有值存在一个哈希表中，用另一个哈希表保存数组1.2的相同元素，最后改回数组。因为返回值是数组。

b站视频

4.代码实现

hashset方法 

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length ==0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> result = new HashSet<>();
        for(int i : nums1){
            set1.add(i);
        }
        for(int i : nums2){
            if(set1.contains(i)){
                result.add(i);
            }
        }
        int[] arr = new int[result.size()];
        int j = 0;
        for(int i : result){
            arr[j] = i;
            j++;
        }
        return arr;
    }
}

也可以 

return resSet.stream().mapToInt(x -> x).toArray();

5.总结

size通常用于集合类（如List、Set、Map等）中，用来返回集合中元素的数量或大小。

length通常用于数组中，用来返回数组的长度。

resSet.stream()：将集合resSet转换为一个流（Stream），流是Java 8引入的一个新的数据处理方式，可以方便地对集合中的元素进行各种操作。

mapToInt(x -> x)：使用mapToInt方法将流中的每个元素映射为整数。在这里，x -> x表示对流中的每个元素x不做任何处理，直接返回原来的元素即将集合中的元素转为整数。

toArray()：将流中的元素存储到一个新的整型数组中综合起来，这段代码的作用是将集合resSet中的素取出并换为一个整型，便于后续的处理和操作

202. 快乐数

1.题目描述

 力扣链接

2.适用场景

• 时间复杂度: O(logn)
• 空间复杂度: O(logn)

3.做题思路

4.代码实现

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n != 1 && !record.contains(n)){
            record.add(n);
            n = getNewn(n);
        }
        return n == 1;
    }
    public int getNewn(int n){
        int sum =0;
        while(n > 0){
            int temp = n%10;
            sum += temp*temp;
            n = n/10;
        }
        return sum;
    }
}

5.总结

 sum += temp*temp;不能换成sum += temp^2，^运算符表示按位异或操作。

1. 两数之和

1.题目描述

 力扣链接

2.适用场景

• 时间复杂度: O(n)
• 空间复杂度: O(n)

3.做题思路

为什么会想到用哈希表

        需要查询一个元素是否出现过，或者一个元素是否在集合里的时候

哈希表为什么用map

        需要使用 key value结构来存放，key来存元素，value来存下标

本题map是用来存什么的

        map用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

map中的key和value用来存什么的

        这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

        所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

        在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

4.代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
         int[] res = new int[2];
    if(nums == null || nums.length == 0){
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
            break;
        }
        map.put(nums[i], i);
    }
    return res;
    }
}

5.总结