哈希表.md

# 哈希表
- **概念**
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

- **数据结构**
给定表`M`，存在函数`f(key)`，对任意给定的关键字值`key`，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为`哈希(Hash）表`，函数f(key)为哈希(Hash) 函数。

![在这里插入图片描述](https://user-gold-cdn.xitu.io/2019/10/15/16dce04921e10817?w=508&h=441&f=png&s=15241)

### 两数之和

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。需要实现的函数 twoSum 需要返回这两个数的下标。

> 示例:
> 
>给定 `nums = [2, 7, 11, 15], target = 9`
>
>因为 `nums[0] + nums[1] = 2 + 7 = 9`
>所以返回 `[0, 1]`

##### 解题思路

- 用一个`hashmap`来记录
- `key`记录`target - numbers[i]`的值，`value`记录`numbers[i]`的` i `的值
- 如果碰到一个 `numbers[j]`在`hashmap`中存在
- 那么说明前面的某个`numbers[i]`和`numbers[j]`的和为`target`
- 那么当前的`i`和`j`即为答案

```java
public int[] twoSum(int[] numbers, int target) {

    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
    	// 判断 map 中是否有需要该值的项
        if (map.containsKey(numbers[i])) {
            return new int[]{map.get(numbers[i]), i};
        }
        // 意思可理解为第 i 项，需要 target - numbers[i]
        map.put(target - numbers[i], i);
    }

    return new int[]{};
}
```

<br>
<br>

-----

### 连续数组

给一个`二进制`数组，找到 0 和 1 ` 数量相等`的子数组的`最大长度`

>示例 2:
>
>输入: [0,1,0]
>输出: 2
>说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

##### 步骤

1. 使用一个数字`sum`维护到`i`为止`1`的数量与`0`的数量的差值

2. 在`loop i`的同时维护`sum`并将其插入`hashmap`中

3. 对于某一个sum值，若hashmap中已有这个值

4. 则当前的`i`与`sum`上一次出现的位置之间的序列`0`的数量与`1`的数量相同

```java
public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefix = new HashMap<>();
    int sum = 0;
    int max = 0;
    // 因为在开始时 0 、 1 的数量都为 0 ，所以必须先存 0 
    // 否则第一次为 0 的时候，<- i - prefix.get(sum) -> 找不到 prefix.get(0)
    prefix.put(0, -1); 
    // 当第一个 0 1 数量相等的情况出现时，数组下标减去-1得到正确的长度
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (num == 0) {
            sum--;
        } else {
            sum++;
        }
        // 判断是否已存在 sum 值
        // 存在则说明之前存过
        if (prefix.containsKey(sum)) {
        	// 只做判断，不做存储
            max = Math.max(max, i - prefix.get(sum));
        } else {
            prefix.put(sum, i);
        }
    }
    
    return max;
}
```

<br>
<br>

-----

### 最长无重复字符的子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

>输入: "abcabcbb"
>输出: 3 
>解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

##### 解题思路

用`HashMap`记录每一个字母出现的位置：

1. 设定一个`左边界`，到当前枚举到的位置之间的字符串为不含重复字符的子串。
2. 若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界。

![最长无重复字符的子串](https://user-gold-cdn.xitu.io/2019/10/15/16dce04921982a7d?w=717&h=582&f=png&s=28389)

##### 视频

[大圣算法- 最长无重复字符的子串 ](https://www.bilibili.com/video/av69214707?from=search&seid=10359707628476531981)

```java
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    // 计算无重复字符子串开始的位置
    int start = -1; 
    int current = 0;
    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            int tmp = map.get(s.charAt(i));
            // 上一次的位置在左边界右边, 则需要向右移动左边界
            if (tmp >= start) { 
                start = tmp;
            }
        } 
        
        map.put(s.charAt(i), i);
        max = Math.max(max, i - start);
    }
    return max;
}
```

<br>
<br>

----

### 最多点在一条直线上

给出二维平面上的n个点，求最多有多少点在同一条直线上

> **首先点的定义如下**
> ```java
> class Point {
>     int x;
>     int y;
>     Point() { 
>         x = 0; y = 0; 
>     }
>     Point(int a, int b) { 
>         x = a; y = b; 
>     }
> }
> ```
>
>**示例 :**
>
>输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
>输出: 4
>解释:
>^
>|
>|  o
>|     o        o
>|        o
>|  o        o
>+------------------->
>0  1  2  3  4  5  6

##### 解题思路

提示：我们会发现，其实只需要考虑当前点之后出现的点` i + 1 .. N - 1 `即可，因为通过点 `i-2` 的直线已经在搜索点 `i-2` 的过程中考虑过了。

- 画一条通过点 i 和`之后`出现的点的直线，在哈希表中存储这条边并计数为` 2 ` = 当前这条直线上有两个点。

- 存储时，以斜率来区分线与线之间的关系

- 假设现在 `i` < `i + k` < `i + l` 这三个点在同一条直线上，当画出一条通过 i 和 i+l 的直线会发现`已经记录`过了，因此对`更新`这条边对应的计数：`count++`。


![在这里插入图片描述](https://user-gold-cdn.xitu.io/2019/10/15/16dce04949e1bdd2?w=1652&h=990&f=png&s=92472)    

通过 `HashMap` 记录下两个点之间的斜率相同出现的次数，注意考虑点`重合`的情况

```java
    public int maxPoints(int[][] points) {
        if (points == null) {
            return 0;
        }
        
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> map = new HashMap<>();
            int maxPoints = 0;
            int overlap = 0;
            for (int j = i + 1; j < points.length; j++) {
                int dy = points[i][1] - points[j][1];
                int dx = points[i][0] - points[j][0];
                // 两个点重合的情况记录下来
                if (dy == 0 && dx == 0) {
                    overlap++;
                    continue;
                }
                // 防止 x 相同 y 不同，但 rate 都为 0 
                // 防止 y 相同 x 不同，但 rate 都为 0 
                // 以及超大数约等于 0 的情况：[[0,0],[94911151,94911150],[94911152,94911151]]
                String rate = "";
                if(dy == 0)
                    rate = "yy";
                else if (dx == 0)
                    rate = "xx";
                else
                    rate = ((dy * 1.0) / dx) + "";
                
                map.put(rate, map.getOrDefault(rate, 0) + 1);
                maxPoints = Math.max(maxPoints, map.get(rate));
            }
            max = Math.max(max, overlap + maxPoints + 1);
        }
        return max; 
    }
```