哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

在查询的时候只需要通过索引值就可以知道要查找的元素在不在哈希表中，时间复杂度只需要O(1)，而枚举法的时间复杂度则需要达到O(n)。

哈希函数

通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字（所有元素）映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置。接下来就是哈希碰撞的概念。

哈希碰撞

1. 拉链法
发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了。其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

2. 线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。
在这里插入图片描述

常见的三种哈希结构

数组
set（集合）
map（映射）

哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242. 有效的字母异位词

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

最后，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

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;
    }
}

349. 两个数组的交集

如果哈希值比较少、特别分散、跨度非常大，使用数组会造成空间的极大浪费。此题可以使用另一种哈希结构set：先遍历数组1中的元素并添加到set中，之后在遍历数组2的过程中判断哈希表中是否存在该元素。

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> resultSet = new HashSet<>();
        //遍历数组1
        for(int i : nums1){
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for(int i : nums2){
            if(set1.contains(i)){
                resultSet.add(i);
            }
        }
        //将结果几何转化为数组
        return resultSet.stream().mapToInt(x -> x).toArray();
    }
}

202. 快乐数

题目中说了会无限循环，那么也就是说求和的过程中，sum会重复出现。在每一次求和后先在哈希表中查找是否已经存在该元素了，如果没有就存入该元素，否则就实现了无限循环（除非是1）。

class Solution {
    private int getNextNumber(int n){
            int res = 0;
            while(n > 0){
                int temp = n % 10;
                res += temp * temp;
                n = n / 10;
            }
            return res;
        }

    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n != 1 && !record.contains(n)){
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
}

1. 两数之和

我们不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

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

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

这道题我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

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

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);
            }
            map.put(nums[i], i);
        }
        return res;
    }
}