哈希表

1、内容

1、哈希表

1、哈希表就是散列表

2、作用：一般哈希表都是用来快速判断一个元素是否出现集合里

2、哈希函数

1、

2、异位词

1、什么是异位词：

3、总结

1、哈希函数

1、把传入的key映射到符号表上的索引上

2、哈希碰撞

1、就是处理多个key映射到相同索引上的情景，我们一般用哈希表+链表

3、三种常见的哈希结构

1、数组

2、set（集合）

3、map（映射）

4、数组作为哈希表

1、242力扣题

1、里面就是用到数组作为哈希表

2、用ASIC码值来作为数组值，每个字母作为数组索引

3、然后遍历，是否出现，出现就把数组值+1，最后判断数组是否为0，==0就说明没有重复的，!=0就是有重复的

4、统计写法

for(int i =0;i<s.length();i++){
            recrud[s.charAt(i) - 'a']++;
        }

2、383力扣题

1、也是同理

5、set作为哈希表

1、349力扣题

1、没有给出任何长度限制，就没办法用数组，只能用set了

2、如果用数组就会出现空间浪费或脚标越界

3、直接利用set的特性，就是不能添加重复的数据（其中跟哈希值相关）

2、202力扣题

1、也是一样的思路

6、map作为哈希表

1、利用map的key-value的结构

1、1力扣题

1、因为没有要求key是否有序，所以用map效率高

2、15、18、1力扣题

1、这三个题都是利用map的key-value属性

2、但是这里最重要的是去重！

3、还要结合双指针进行操作，能提高效率

4、推荐使用双指针结合

1、15去重

1、求3个数a,b,c相加=0，这里我们先排序（为双指针做准备）

2、然后对a去重，这里重点是这个

if(nums[i] ==nums[i-1]){
    continue;
}
nums[i] ==nums[i-1]判断的是a是否有重复的值
nums[i] ==nums[i+1]判断的是a和b是否重复，就是一个结果集是否有重复，与题意不符

3、 不能有重复的三元组，但三元组内的元素是可以重复的！

4、举例：

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

5、对b,c去重，重点是这个

result.add(Arrays.asList(nums[i], nums[left], nums[right]));
            // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

哈希表