LeetCode 1207 哈希表

好久没摸算法了，今天开始每日来一题，做了每日打卡才发现自己手法生了。

---

1207. 独一无二的出现次数
      难度： 简单
      给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
      如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
      示例 1：
      输入：arr = [1,2,2,1,1,3]
      输出：true
      解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
      来源：力扣（LeetCode）
      链接：https://leetcode-cn.com/problems/unique-number-of-occurrences

显然是哈希表，（嗯 看了题解才说显然，嗯显然我都忘完了），来来来 复习下 数据结构 哈希表：

目前最熟的应该是 我上学期学过的 算法分析 里面提过的 二叉平衡树、B+树，都是从根节点开始查找数值，（感觉挺麻烦的 hhh）

想这道题的时候，我也是想的，有没有什么方法可以让一个数组直接通过数值作为索引来查找。
那其实哈希表就是这样的。

---

什么是哈希表：

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

按照我的理解就是，哈希表，就是将一个个数值（value）放在一个个格子里，并打上一个标签（key），但是这样一点也不专业，实质上的解释就是：
哈希表就是一个函数：hashtable(value，key)

• 存入原理就是把key（预映射）加粗样式通过一个函数（散列函数）转换成一个整型数字（散列值），然后就将该数字对数组长度进行取余（压缩映射），取余结果就当作数组的下标（地址），将 value 存储在以该数字为下标（地址）的数组空间（存储空间）里。
• 取出原理就是再次使用函数定位到存储地址获取存储的 value。

那这么看来，其实就和二维数组差不多嘞，但是其实是有区别的。
如果二维数组，直接一个key，一个value 存的话，空间浪费会很大，因为比如 存两个key的value，比如 [1,1] [999,1] 那就会开 int[2][1000]。
如果哈希表的话，假设散列函数为：H(key)=(1000-key)/100 这样存储就是：

key	index	value
1	9	1
999	0	1

（这个 除号后面的 数，在实现的时候算法决定的）
所以我们发现哈希函数呢

• 优点：按key 一对一查找效率很高；

但是呢显然我们也发现，就比如这个 H(key)=(1000-key)/100 函数，当出现 998 999 两个key，这样存储的位置是一样的，于是就出现了散列冲突。

• 散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。

这个时候哈希函数的效率就是依靠散列函数来决定了。
好的散列函数=计算简单+分布均匀（根据key得到的散列地址分布均匀）

好了这些都是关于实现的，这里先不谈这些。

---

哈希表的使用 java

import java.util.HashMap;
import java.util.Map;
Map<String, Integer> Ages = new HashMap<String, Integer>(); 
// Key 为 String，Value 为 Integer

方法：

Method	Describe
get (Object key)	返回键映射的值，如果该键没有映射值，则返回null
put (key, value)	将键和值建立映射,如果键是第一次存储，就直接存储元素，返回null; 如果键不是第一次存在，就用把以前的值替换掉，返回以前值
remve (key)	移除键存在的映射关系，并将值移除，返回移除值
containsKey (key)	是否存在该键
containsValue (key)	是否存在该值
isEmpty ()	表是否为空
clear ()	移除所有映射，移除所有值
entrySet ()	返回键值对的 Set 集合
keySet ()	获取所有键 Set 集合
values ()	获取所有值 Set 集合
size ()	返回集合的映射数量

---

解题

来看看我咋写的：

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
            int len = arr.length;
            boolean result = true;
            int[][] data = new int[2][2000];
            Stack stack = new Stack();
            // stack 存出现过的值 data 第一行存 出现次数
            for(int i=len-1; i>=0; i--){
                int v = arr[i]+1000;
                data[0][arr[i]+1000]++;
                if(data[0][v] == 1)
                    stack.push(v);
            }
            // data 第二行存 出现次数 计数
            while(!stack.empty()){
                int value = (int)stack.peek();
                stack.pop();
                int j = data[0][value];
                if(data[1][j] == 0)
                    data[1][j] = 1;
                else {
                    return false;
                }
            }
            return true;
    }
}

显然很麻烦啦：

来看官方的：

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> occur;
        for (const auto& x: arr) {
            occur[x]++;
        }
        unordered_set<int> times;
        for (const auto& x: occur) {
            times.insert(x.second);
        }
        return times.size() == occur.size();
    }
};
//来源：力扣（LeetCode）