【概念解释】

【实例】：“存快递”
方式一：
按照手机尾号计算 柜子编号
1032 —- 2号柜子
1042 —- 2号柜子
1043 —- 3号柜子

方式二：
对手机后四位进行取模
1302 % 99 = 15 —- 15号柜子
1402 % 99 = 16 —- 16号柜子

【问题】这两种方法都能够被别人模拟，黑客就可以通过“洪水攻击”的方式对你的应用空间进行攻击

哈希算法：“hash算法”，“散列算法”，“杂凑算法”
把任意长度的输入 通过算法 变成固定长度的输出
相较于顺序存储的方式，当存储量达到一定程度的时候，查找效率会得到提高
“空间换时间”
物品 — 手机号 — 存放位置
映射关系 关键字Key 访问到具体值Value
不同key 映射到同一个地址 就叫做 “哈希碰撞”

常见的哈希函数

1）直接寻址法：取关键字或关键字的线性函数 作为散列地址
2）除留取余法：对关键字或关键字的部分取模 作为散列地址
取模的除数一般都是素数或者质数
3）取随机数法：使用随机函数，取关键字的随机值，作为散列地址
4）数字分析法：根据数字的特性，经过分析，取部分进行计算，比如手机尾号后四位，身份证号后四位等。
5）平方取中法：先求数字的平方，在取平方数的中间几个数字作为散列地址
6）折叠法：取关键字的几部分，取叠加和作为散列地址

发生散列冲突的原因：

数学上的抽屉原理
解决冲突的办法：
再找一个空闲位置
具体如下：
1）线性探测
key 01 —- 1号柜子
如果满了，顺延至下一个位置：2号柜子
2）二次探测
如果满了，按照一定规律顺延，
如以二次方 value value + 1^2 ; value + 2^2
3) 双重hash
使用两种hash函数，第一个位置被占用之后，hash取得第二个函数位置
4）链表法
让一个位置可以存放多个value（用链表串联起来）

【相关算法】

一、两数之和 TwoSum

平生不识TwoSum，刷尽力扣也惘然
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

【示例 1】：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解法一：暴力破解法

依次循环遍历计算两两之和判断与target的值是否相等。
遍历每个元素，将当前元素与后续元素进行求和计算，判断是否等于target
【代码实现】

  1.  public static int[] twoSum(int[] nums,int target){
  2.  //遍历每个元素，判断其后元素与其相加的和 是否等于target
  3.         for (int i = 0; i < nums.length; i++) {
  4.             for (int j = i+1; j < nums.length; j++) {
  5.                 if (nums[i] + nums[j] == target){
  6.                     return new int[]{i,j};
  7.                 }
  8.             }
  9.         }
  10.         return new int[]{-1,-1};
  11.     }

解法二：倒推法

【哈希·两数之和】.jpg
【代码实现】

  1.  public static int[] twoSum1(int[] nums,int target){
  2.         HashMap<Integer, Integer> map = new HashMap<>();
  3.         for (int i = 0; i < nums.length; i++) {
  4.             map.put(nums[i],i);
  5.         }
  6.         for (int i = 0; i < nums.length; i++) {
  7.             int needNum = target - nums[i];
  8.             if (map.containsKey(needNum) && map.get(needNum) != i){
  9.                 return new int[]{i,map.get(needNum)};
  10.             }
  11.         }
  12.         return new int[]{-1,-1};
  13.     }

解法三：一次哈希法

【哈希·两数之和·一次哈希法】.jpg
【代码实现】

  1.   public static int[] twoSum2(int[] nums,int target) {
  2.         HashMap<Integer, Integer> map = new HashMap<>();
  3.       //边遍历边修改map的值
  4.         for (int i = 0; i < nums.length; i++) {
  5.             int needNum = target - nums[i];
  6.             if (map.containsKey(needNum)){
  7.                 return new int[]{map.get(needNum),i};
  8.             }
  9.             map.put(nums[i],i);
  10.         }
  12.         return new int[]{-1,-1};
  13.     }

二、找不同

给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。

示例 1：
输入：s = “abcd”, t = “abcde”
输出：”e”
解释：’e’ 是那个被添加的字母。
示例 2：
输入：s = “”, t = “y”
输出：”y”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-difference

方案一：

使用map分别记录 s和t中 <字母，出现的次数>
查找t中出现次数比s中多一次或者s中未出现的字母
【哈希表·找不同·解法一】.jpg
【代码实现】

  1.   public static char findTheDifference(String s,String t){
  2.         HashMap<Character, Integer> map = new HashMap<>();
  3.         for (char c : s.toCharArray()) {
  4.             if (map.containsKey(c)){
  5.                 int newNum = map.get(c) + 1;
  6.                 map.put(c,newNum);
  7.                 continue;
  8.             }
  9.             map.put(c,1);
  10.         }
  12.         for (char tc : t.toCharArray()) {
  13.             if (!map.containsKey(tc)){
  14.                 return tc;
  15.             }
  16.             if (map.get(tc) == 0){
  17.                 return tc;
  18.             }
  19.             int newNum = map.get(tc) - 1;
  20.             map.put(tc,newNum);
  21.         }
  22.         return '-';
  23.     }

方案二：字符串替换

遍历s中每一个字符，将t中对应的字符替换为空字符串，t最后只剩下一个字符
【代码实现】

  1.  public static char findTheDifference1(String s,String t){
  2.         for (Character c : s.toCharArray()) {
  3.             //replaceFirst方法替换一个
  4.             t = t.replaceFirst(c.toString(),"");
  5.         }
  6.         return t.toCharArray()[0];
  7.     }

方案三：ASCII 码

分别遍历s和t，将每个字母的ASCII码相加，其差值即为多出来的元素
【代码实现】

  1.  public static char findTheDifference2(String s,String t){
  2.         int sSum = 0,tSum = 0;
  3.         for (char sc : s.toCharArray()) {
  4.             sSum += sc;
  5.         }
  6.         for (char tc : t.toCharArray()) {
  7.             tSum += tc;
  8.         }
  9.         return (char) (tSum - sSum);
  10.     }

方案四：异或运算

二进制运算
【哈希表·找不同·异或运算】.jpg
【代码实现】

  1.   public static char findTheDifference3(String s,String t){
  2.         int result = 0;
  3.         for (char c : s.toCharArray()) {
  4.            result = result ^ c;
  5.         }
  6.         for (char c : t.toCharArray()) {
  7.             result = result ^ c;
  8.         }
  9.         return (char) result;
  10.     }