简介
??哈希表与数组、链表一样，是一种很基础的数据结构，当一道题只会用到哈希表时，哪这题也一定不会太难，相对而言，真正难的是组合题，或者你根本不知道应该用哈希表去解决，比如很多人的一生之敌Two Sum，我一开始也不知道，还可以用哈希去解题。哈希表题里，还有一个小技巧，当节点数量固定时，我们可以用数组去表示哈希表，这样效率高的同时，还不浪费存储空间。
理论基础
??哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。
??给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。
??以上这段话摘自百度百科，可以说是，短短几句话就把哈希表的本质说清楚了。哈希表也常被翻译为散列表，我们看到后，知道是同一个东西就可以了。那他和一般的数据结构有什么区别呢，最大的区别在于：一般的数据结构比如数组，查找的时间复杂度是O(n)，但如果是哈希表的话， 查找数据的时间复杂度为O(1)。接下来介绍几个哈希表的重要概念：哈希函数、哈希碰撞、拉链法、哈希表的优势等。
哈希函数
??若关键字为k，则其值存放在f(k)的存储位置上。这个对应关系f()，就是哈希函数。一个好的哈希函数，应该尽可能的使值均匀的分布在数组中，尽可能减少碰撞的产生。
哈希碰撞
??对不同的关键字可能得到同一哈希地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为哈希碰撞（英语：hash Collision），也可翻译为哈希冲突。如果一个哈希函数，写的不够好，则碰撞的机率越高，碰撞越高，效率也就越低。在极端的情况下，我们的哈希表可能所有值都冲突了，退化成了链表，查找效率自然低。若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀哈希函数（Uniform Hash function），这就是使关键字经过哈希函数得到一个“随机的地址”，从而减少冲突。
拉链法
??那假设我们数组长度为100，我们要存110个值，那不管是多么神奇的哈希函数，最后一定会有至少10个值会碰撞的，那有什么解决办法呢？办法是有的，比如经典的解决办法就是拉链法，只要碰撞产生了，我们就以当前索引为链表头，之后每碰撞一次，链表节点就加1，至于是加在头部还是尾部，各种语言实现方法都不一样，但思路是一样的，其中链表太长后，会影响查找，还可以用红黑树代替链表。这也是Java中哈希表的实现方式。
??Java中哈希表的实现方式为HashMap，关于HashMap的源码实现，感兴趣的同学，可以看我这篇文章：源码系列 之 HashMap。
哈希表的优势
??哈希表通过关键值计算直接获取目标位置，对于海量数据中的精确查找有非常惊人的速度提升，一个实现良好的哈希表可以保持O(1)的查找速度，而O(n)的普通列表此时已经无法正常执行查找操作了。我们平时做题时的数据量其实特别特别的小，如果我们有过大数据方面的开发经验，就会知道，表数据量特别大时，有时可能只是错误的使用了全表扫描一下，都有可能使用整个数据库宕机，这时就要考虑使用我们的哈希表数据结构了。
??话说回来，我们平时解题时，也因为这些特性，常用哈希表来判断，一个元素是否出现在集合中。
解题心得
- 单独的哈希表题，一般不难，难的是你不知道这题应该用哈希表。
- 哈希表是一种用空间换时间的数据结构，因为我们要使用额外的数组、链表、或红黑树才实现了快速查找。
- 哈希表一般都是用来快速判断一个元素是否出现集合里 。
- 需要熟悉哈希表的底层实现，才会更好的发挥哈希表的优势。
- 当节点数量固定时，可考虑用数组表示哈希表。
- 数组不用像HashMap一样维护链表或红黑树，还不用做哈希函数运算，所以数组更节约空间和更方便。
- 题意暗含映射关系时，可以考虑使用哈希表去解题。
- 请记住，哈希查找元素的速度是O(1)，符合题意，不考虑空间的情况下，优先选择。
算法题目
1. 两数之和
题目解析：采用哈希表可将查找时间复杂度降为O(1)。
代码如下：
/**
* 哈希表
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int sub = target - nums[i];
// 查找余数是否在表中，有则返回两个数的索引
// 没有则将其信息添加进哈希表
if (map.containsKey(sub)) {
return new int[]{map.get(sub),i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
13. 罗马数字转整数
题目解析：将字符串倒过来处理，并使用映射存储罗马值。
代码如下：
/**
* 哈希表
*/
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('M', 1000);
map.put('D', 500);
map.put('C', 100);
map.put('L', 50);
map.put('X', 10);
map.put('V', 5);
map.put('I', 1);
int res = 0;
// 从右住左数，前一个字符对应的数值
int pre = 0;
if (s.length() == 0) return res;
for (int i = s.length() - 1; i >= 0; i--) {
int cur = map.get(s.charAt(i));
// 从右往左数，依次增大为结果相加，否则为相减
if (cur >= pre) {
res += cur;
} else {
res -= cur;
}
pre = cur;
}
return res;
}
}
49. 字母异位词分组
题目解析：质数表示26个字母，再把字符串的各个字母相乘，字母异位不会影响sum值，最后分类。用char字母对应的是ASCII码值相乘，会有不同字母但同值的情况出现。
代码如下：
/**
* 哈希表
*/
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<Double, ArrayList<String>> map = new HashMap<>();
Map<Character, Integer> charMap = new HashMap<>();
charMap.put('a', 2);
charMap.put('b', 3);
charMap.put('c', 5);
charMap.put('d', 7);
charMap.put('e', 11);
charMap.put('f', 13);
charMap.put('g', 17);
charMap.put('h', 19);
charMap.put('i', 23);
charMap.put('j', 29);
charMap.put('k', 31);
charMap.put('l', 37);
charMap.put('m', 41);
charMap.put('n', 43);
charMap.put('o', 47);
charMap.put('p', 53);
charMap.put('q', 59);
charMap.put('r', 61);
charMap.put('s', 67);
charMap.put('t', 71);
charMap.put('u', 73);
charMap.put('v', 79);
charMap.put('w', 83);
charMap.put('x', 89);
charMap.put('y', 97);
charMap.put('z', 101);
for (String str : strs) {
char[] chs = str.toCharArray();
double sum = 1.0;
for (int i = 0; i < chs.length; i++) {
sum *= charMap.get(chs[i]);
}
if (!map.containsKey(sum)) {
map.put(sum, new ArrayList<>());
}
map.get(sum).add(str);
}
return new ArrayList<>(map.values());
}
}
128. 最长连续序列
题目解析：该数组可看做很多个范围组成，每次找到各范围最左边的数，然后循环加一，一直到查到到最右边的数，最后比较出最大值即可。
代码如下：
/**
* 哈希表
*/
class Solution {
public int longestConsecutive(int[] nums){
Set<Integer> num_set = new HashSet<Integer>();
// 去重
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
// 遍历
for (int num : num_set) {
// 如果不是各范围最小数，则跳过
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// 选出最大数即可
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
138. 复制带随机指针的链表
题目解析：用哈希表存储Node对应的复制节点，然后递归，如果该节点不存在哈希表中，则新建并存入。
代码如下：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
/**
* 哈希表，递归
*/
class Solution {
// 存储Node对应的复制节点
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
return head == null ? null : helper(head);
}
// 递归
private Node helper(Node node) {
if (node == null) {
return null;
}
Node copyNode = map.get(node);
// 如果该节点不在map里，则新建并存入
if (copyNode == null) {
copyNode = new Node(node.val);
// 先插入，后设置值，否则可能会死循环
map.put(node, copyNode);
copyNode.next = helper(node.next);
copyNode.random = helper(node.random);
}
return copyNode;
}
}
166. 分数到小数
题目解析：用哈希表记录所有被除数的下标，如果出现了重复的被除数，则证明出现了循环，把左括号塞到记录的下标位置，右括号放在最后。
代码如下：
/**
* 哈希表
*/
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
StringBuilder sb = new StringBuilder();
long a = numerator, b = denominator;
if (a > 0 && b < 0 || a < 0 && b > 0) sb.append('-');
a = Math.abs(a);
b = Math.abs(b);
sb.append(a / b);
if (a % b == 0) return sb.toString();
sb.append('.');
Map<Long, Integer> map = new HashMap<>();
while ((a = (a % b) * 10) > 0 && !map.containsKey(a)) {
map.put(a, sb.length());
sb.append(a / b);
}
if (a == 0) return sb.toString();
return sb.insert(map.get(a).intValue(), '(').append(')').toString();
}
}
202. 快乐数
题目解析：根据题意，只要重复出现结果值，则为“不快乐数”，用哈希判断是否重复，或者是否为1。
代码如下：
/**
* 哈希表
*/
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
// 判断结果是否为1，不为1则继续计算
while (n != 1 ) {
// 重复则，一定为不快乐数，直接返回false
if(record.contains(n)){
return false;
}
record.add(n);
n = getNextNumber(n);
}
return true;
}
private int getNextNumber(int n) {
int res = 0;
// 将每个位子上的数的平方相加，返回结果值
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
205. 同构字符串
题目解析：用哈希表维护一个映射表，通过映射表去判断是否为同构字符串。
代码如下：
/**
* 哈希表
*/
class Solution {
public boolean isIsomorphic(String s, String t) {
// 长度不等，直接返回false
if(s.length() != t.length()){
return false;
}
// Key值为S的char字符，Value为T的char字符
HashMap<Character, Character> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
// 查找是否存在映射值key
if(!map.containsKey(s.charAt(i))){
// 若Key值不存在的情况，Value存在，则说明，不是同构，返回false
if(map.containsValue(t.charAt(i))){
return false;
}
// 都不存在，则存储
map.put(s.charAt(i), t.charAt(i));
}else{
// Key值存在，查找Value是否相等
if(map.get(s.charAt(i))!=t.charAt(i)){
return false;
}
}
}
return true;
}
}
219. 存在重复元素 II
题目解析：用哈希表存储值与索引，Map中key为值，value为索引，用value计算，索引值差值是否小于K。
代码如下：
/**
* 哈希表
*/
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (map.get(num) != null) {
if (i - map.get(num) <= k){
return true;
}
}
map.put(num,i);
}
return false;
}
}
242. 有效的字母异位词
题目解析：哈希表，用key记录字母，value记录次数，哈希表操作得当，可以用数组优化，这里用26长度的数组优化。
代码如下：
import java.util.HashMap;
/**
* 哈希表
*/
class Solution {
public boolean isAnagram(String s, String t) {
// 存字符和次数
int[] record = new int[26];
for (char c : s.toCharArray()) {
record[c - 'a'] += 1;
}
for (char c : t.toCharArray()) {
record[c - 'a'] -= 1;
}
// 如果不为0，则次数不相等
for (int i : record) {
if (i != 0) {
return false;
}
}
return true;
}
}
290. 单词规律
题目解析：用哈希表记录，pattern到s的对应关系，如果对应关系有差，返回false即可。
代码如下：
/**
* 哈希表
*/
class Solution {
public boolean wordPattern(String pattern, String s) {
// 存储映射关系
Map<Character, String> map = new HashMap<>();
String[] str = s.split(" ");
// 如果长度不一致，直接返回false
if (pattern.length() != str.length) {
return false;
}
// 查找映射关系
for (int i = 0; i < pattern.length(); i++) {
String temp = map.get(pattern.charAt(i));
if (temp == null) {
// 包括str(i)则说明，之前映射过了
if (map.containsValue(str[i])) {
return false;
}
map.put(pattern.charAt(i), str[i]);
} else {
if (!temp.equals(str[i])) {
return false;
}
}
}
return true;
}
}
299. 猜数字游戏
题目解析：如果是同一位置且数值相等，则A总数加1，如果是不同位置，数值相等，则B加1，这里用数组代替哈希表，可优化速率。
代码如下：
/**
* 遍历
*/
class Solution {
public String getHint(String secret, String guess) {
StringBuilder res = new StringBuilder();
int[] nums = new int[10];
int countA = 0, countB = 0;
for (int i = 0; i < secret.length(); i++) {
if(secret.charAt(i) == guess.charAt(i)) countA++;
else{
if (nums[guess.charAt(i) - '0']-- > 0) countB++;
if(nums[secret.charAt(i) - '0']++ < 0) countB++;
}
}
return res.append(countA).append("A").append(countB).append("B").toString();
}
}