哈希表

哈希表理论基础

哈希表，又称为散列表（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：Setresult = 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];
    }
}