一、哈希表基础知识
1. 哈希表概念
哈希表是一种常见的数据结构，在解决算法面试题的时候经常需要用到哈希表。哈希表最大的优点是高效，在哈希表中插入、删除或查找一个元素都只需要O(1)的时间。因此，哈希表经常被用来优化时间效率。
在Java中，哈希表有两个对应的类型，即HashSet和HashMap。如果每个元素都只有一个值，则用HashSet。例如，HashSet在图搜索时经常用来存储已经搜索过的节点。
2. 哈希表常用函数
2.1 HashSet常见函数
| 序号 | 函数 | 描述 |
|---|---|---|
| 1 | add |
在HashSet中添加一个元素 |
| 2 | contains |
判断HashSet中是否包含某个元 |
| 3 | remove |
移除HashSet中的一个元素 |
| 4 | size |
返回HashSet中的元素个数 |
2.2 HashMap常见函数
| 序号 | 函数 | 描述 |
|---|---|---|
| 1 | containKey |
判断HashMap是否包含某个键 |
| 2 | get |
如果键存在，则返回对应的值，如果不存在，返回null |
| 3 | getOrDefault |
如果键存在，则返回对应的值，如果不存在，返回指定的值 |
| 4 | put |
如果数据不存在，则添加一组键值的映射，否则修改键映射的值 |
| 5 | putIfAbsent |
当前不存在时添加一组键到值得映射 |
| 6 | remove |
删除某个键 |
| 7 | replace |
修改某个键的值 |
| 8 | size |
返回HashMap中键到值得映射数目 |
3. 哈希表后记
尽管哈希表是很高效的数据结构，但这并不意味着哈希表能解决所有的问题。如果用哈希表作为字典存储若干单词，那么只能输入完整的单词在字典中查找。如果对数据集中的元素排序能够有助于解决问题，那么用TreeSet或TreeMap可能更合适。如果需要知道一个动态数据集中的最大值或最小值，那么堆的效率可能更好。如果希望能够根据前缀进行单词查找，如查找字典中所有以ex开头的单词，那么应该用前缀树作为实现字典的数据结构。
二、哈希表知识扩展
1. 哈希表的设计
设计哈希表的前提是待存入的元素需要一个能计算自己哈希值的函数。在 Java 中所有类型都继承了类型 Object，每个 Object 的实例都可以通过定义函数 hashCode 来计算哈希值。哈希表根据每个元素的哈 希值把它存储到合适的位置。
哈希表最重要的特点就是高效，只需要 O(1) 的时间就可以把一个元素存入或读出。在常用的基础数据结构中，数组满足这个要求。只要知道数组中的下标，就可以用 O(1) 的时间存入或读出一个元素。因此，可以考虑基于数组实现哈希表。
把哈希值转换成数组下标可以采用的方法是对数组的长度求余数。如果数组的长度为 4，待存入的元素的哈希值为 5，由于 5 除以 4 的余数为 1，那么它将存入数组下标为 1 的位置。同理，如果待存入的元素的哈希值为 2 和 3，那么它们分别存入下标为 2 和 3 的位置。如图 2.1(a) 所示
再在哈希表中存入一个哈希值为 7 的元素。由于 7 除以 4 的余数为 3，因此它存入的位置应该是 3。下标为 3 的位置之前已经被下标为 3 的元素占用。如果将两个哈希值不同的元素存入数组中的同一位置，就会引起冲突。
为了解决这种冲突，可以把存入数组中同一位置的多个元素用链表存储。也就是说，数组中每个位置对应的不是一个元素，而是一个链表。哈希值为 3 和 7 的这两个元素都存放在数组中下标为 3 的位置，因此它们实际上存入了同一个链表中。接下来如果再添加哈希值分别为 4 和8 的两个元素，那么它们都将被存入数组下标为 0 的位置对应的链表中。此时哈希表的状态如图 2.1(b) 所示。不难想象，如果在哈希表中添加更多的元素，那么就会有更多的冲突，有更多的元素被存入同一个链表中。
接着考虑如何判断哈希表中是否包含一个元素。例如，为了判断 哈希表中是否包含哈希值为 7 的元素，由于 7 除以 4 的余数是 3，因此先找到数组下标为 3 的位置对应的链表，然后从头到尾扫描这个链表查看是否有哈希值为 7 的元素。
在链表中做顺序扫描的时间复杂度为 O(n)，链表越长查找需要的时间就越长。这就违背了设计哈希表最重要的一个初衷：存入和读取一个元素的时间复杂度为 O(1)。因此，必须确保链表不能太长。
可以计算哈希表中元素的数目与数组长度的比值。显然，在数组长度一定的情况下，存入的元素越多，这个比值就越大；在存入元素的数目一定的情况下，数组的长度越长，这个比值就越小。
当哈希表中元素的数目与数组长度的比值超过某一阈值时，就对数组进行扩容（通常让数组的长度翻倍），然后把哈希表中的每个元素根据新的数组大小求余数并存入合适的位置。例如，在图 2.1(c) 中，扩容之后数组的长度为 8，这个时候原本被存入同一链表的 3 和 7 被分别存入下标为 3 和 7 的位置。
通过对数组进行扩容，原本存入同一链表的不同元素就可能会被分散到不同的位置，从而减少链表的长度。当再在哈希表中添加新的元素时，元素的数目与数组长度的比值可能会再次超过阈值，于是需要再次对数组进行扩容。只要阈值设置得合理，哈希表中的链表就不会太长，仍然可以认为存入和读取的时间复杂度都是 O(1)。
由此可知，设计哈希表有3个要点。为了快速确定一个元素在哈希表中的位置，可以使用一个数组，元素的位置为它的哈希值除以数组长度的余数。由于多个哈希值不同的元素可能会被存入同一位置，数组的每个位置都对应一个链表，因此存入同一位置的多个元素都被添加到同一链表中。为了确保链表不会太长，就需要计算哈希表中元素的数目与数组长度的比值。当这个比值超过某个阈值时，就对数组进行扩容并把哈希表中的所有元素重新分配位置。
哈希表题目 | 哈希表的设计
题目一：插入、删除和随机访问都是O(1)的容器
设计一个数据结构，使如下三个操作的时间复杂度都是O(1)；insert(value)：如果数据集中不包含一个数值，则把它添加到数据集中；remove(value)：如果数据集中包含一个数值，则把它删除；getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 插入和删除的随机访问均是O(1)，很容易便想到HashMap，但问题在于随机访问并不能实现O(1)，对于数组而言，通过指针访问的复杂度也是O(1)，所以，可以将数组和HashMap一起使用。通过HashMap记录值和数组下标的关系，而数组中对应下标有存放该值。这样在插入和删除时，通过HashMap可以快速判断是否存在，并找到该值。而随机访问时，只需要做一个随机函数运算，按照数组数据长度随机生成下标，通过下标进行访问数据，这样便可实现随机访问概率相同。如果删除是移动元素，那么此时只有删除的复杂度是O(n)，但如果只是将末尾元素放到被删除元素处进行补位，然后删除末尾元素，此时就能实现O(1)了。
参考代码
List<Integer> list = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
public void insert(int value) {
if (!map.containsKey(value)) {
map.put(value, list.size());
list.add(value);
}
}
public void remove(int value) {
Integer index = map.get(value);
if (index != null) {
// 将最后一位元素放到找到的下标出
Integer last = list.get(list.size() - 1);
list.set(index, last);
// 将最后元素删除
list.remove(list.size() - 1);
map.remove(value);
map.put(last, index);
}
}
public int getRandom() {
int baseNum = list.size();
if (baseNum == 0) {
return -1;
} else {
Random random = new Random();
int index = random.nextInt(baseNum - 1);
return list.get(index);
}
}
Tips：2024-02-05 22:03
题目二：最近最少使用缓存
请设计实现一个最近最少使用(Least Recently Used, LRU)缓存，要求如下两个操作的时间复杂度都是O(1)：
get(key)：如果缓存中存在键key，则返回它对应的值；否则返回-1。
put(key, value)：如果缓存中之前包含键key，则它的值设为value；否则添加键key及对应的值value。
在添加一个键时，如果缓存容量已经满了，则在添加新键之前删除最近最少使用的键（缓存中最长时间没有被使用过的元素）。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 同上题一样，首先想到可以通过HashMap实现取值、放值得过程。其次需要满足溢出移除最近最少使用的值，这时可以使用一个辅助控件来记录最近最少使用的元素。此处选择双向链表比较合适，当元素被使用到，则将元素移动至链尾，如果溢出，则删除链首元素，随后将新元素添加到链尾。
参考代码
import java.util.HashMap;
import java.util.Map;
/**
* 最少使用缓存
* @author nepakina
*/
public class LRULCache {
private final int maxCache;
private final Map<Integer, MapListNode> cache = new HashMap<>();
private final MapListNode head;
private final MapListNode tail;
public LRULCache(int maxCache) {
this.maxCache = maxCache;
// 定义两个空节点
this.head = new MapListNode(-1, -1);
this.tail = new MapListNode(-1, -1);
head.next = tail;
tail.last = head;
}
/**
* 双指双向节点
*/
public static class MapListNode {
public int key;
public int val;
public MapListNode last;
public MapListNode next;
public MapListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
public int getKey(int key) {
MapListNode res = cache.get(key);
if (res == null) {
return -1;
}
// 移动到 tail 前
moveToTail(res, res.val);
return res.val;
}
public void put(int key, int value) {
MapListNode node = cache.get(key);
if (node != null) {
// 添加元素到 tail 前
moveToTail(node, value);
} else {
node = new MapListNode(key, value);
// 在末尾插入
insertToTail(node);
cache.put(key, node);
// 移除 head 后的第一个元素
if (cache.size() > maxCache) {
cache.remove(head.next.key);
deleteNode(head.next);
}
}
}
public void moveToTail(MapListNode node, int value) {
// 先移除列表，再更新值，最后插入到 tail 之前
deleteNode(node);
node.val = value;
insertToTail(node);
}
public void deleteNode(MapListNode node) {
// 将当前元素抹除出链表
node.last.next = node.next;
node.next.last = node.last;
}
public void insertToTail(MapListNode node) {
// 将元素 node 插入到 tail 前
tail.last.next = node;
node.last = tail.last;
node.next = tail;
tail.last = node;
}
}
Tips：2024-02-05 22:11
2. 哈希表的应用
由于哈希表的插入、查找和删除操作的时间复杂度都是 O(1)，因此是效率很高的数据结构。在算法面试中哈希表是经常被使用的数据结构，如用哈希表来记录字符串中每个字符出现的次数或每个字符出现的位置。
如果哈希表的键的取值范围是固定的，并且范围不是很大，则可 以用数组来模拟哈希表。数组的下标和哈希表的键相对应，而数组的值和哈希表的值相对应。
例如，可以用哈希表来记录单词中每个字母出现的次数，键为字 母，值为字母出现的次数。如果单词中只包含英文小写字母，也就是说，键所有可能的值是已知的，只可能是从a到z的字母，总共只有 26 个字母，那么可以用一个长度为 26 的数组来模拟这个哈希表，数组中下标为 0 的值对应字母a出现的次数，下标为 1 的值对应字母b出现的次数，其余的以此类推。
哈希表题目 | 哈希表的应用
题目一：有效的变位词
给定两个字符串s和t，请判断它们是不是一组变位词。在一组变位词中，它们中的字符及每个字符出现的次数都相同，但字符的顺序不能相同。例如，anagram和nagaram就是一组变位词。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 要判断是否是变位词，可以转化为比较两个字符串是否存在相同的元素，且元素个数相等。如果只存在字母，可以通过数组模拟哈希表进行出现次数的缓存。考虑场景的通用性，可以采用哈希表以字符为建，出现次数为值进行缓存；最后比较两个字符所对应的哈希表缓存的数据是否一直即可。
参考代码
// 这里也可以使用数组处理，将字母转化为 0-25 的下标；
// 遍历 s 记录每个字母出现次数；长度不一致如果非变位
// 词那么一定有一个元素的计数为 0，遍历 t 时先判断字
// 母计数是否为 0，为 0 判为 false。
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
boolean allEqual = true;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (sc != tc) {
allEqual = false;
map.put(sc, map.getOrDefault(sc, 0) + 1);
Integer tcCount = map.get(tc);
if (tcCount == 1) {
map.remove(tc);
}
}
}
return !allEqual && map.isEmpty();
}
Tips：2024-02-05 22:12
题目二：变位词组
给定一组单词，只包含英文小写字母，请将它们按照变位词分组。例如，输入一组单词：
["eat", "tea", "tan"，"ate", "nat", "bat"]
这组单词可以分成3组，分别是：
["eat", "tea", "ate"]、["tan", "nat"]、["bat"]
题目分析
难度： ⭐⭐🐇🐇🐇
思路：
方案一：质数换算
该题主要的问题就在于，即使使用哈希表存放字母出现的次数依旧无法对其进行分组，暴力分组复杂度过高。因此可以根据变位词的共性借助乘法交换律的特性以及质数无公倍数的特性对哈希表进行转化处理，定义一个质数数组用以代替字母（2 代表 a，3 代表 b，5 代表 c ......），字符串按字母换算成质数后相乘，其结果作为字符串的所属分组标识，标识一样则说明是变位词，通过这个特性来对字符串进行分组。不难看出方案一存在一个致命缺陷，乘积容易越界。
方案二：字符串排序
将每个元素按字母重新排序，排序后的新字符串作为 key 从而实现分组。
参考代码
// 方案一
public List<List<String>> groupAnagrams(String[] strArr) {
int hash[] = {2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101};
Map<Long, List<String>> map = new HashMap<>();
for (String s : strArr) {
int len = s.length();
long hashVal = 1;
// 计算字母新的 hash 值(质数积)
for (int j = 0; j < len; j++) {
hashVal *= hash[s.charAt(j) - 'a'];
}
// 用质数积作为 key 对字符串进行分组
List<String> list = map.getOrDefault(hashVal, new ArrayList<>());
list.add(s);
map.put(hashVal, list);
}
return new ArrayList<>(map.values());
}
// 方案二
public List<List<String>> groupAnagrams2(String[] strArr) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strArr) {
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
String sorted = new String(charArray);
List<String> list = map.getOrDefault(sorted, new ArrayList<>());
list.add(s);
map.put(sorted, list);
}
return new ArrayList<>(map.values());
}
Tips：2024-02-05 22:12
题目三：外星语言是否排序
有一门外星语言，它的字母表刚好包含所有的英文小写字母，只是字母表的顺序不同。给定一组单词和字母表顺序，请判断这些单词是否按照字母表的顺序排序。例如，输入一组单词["offer"，"is"，"coming"]，以及字母表顺序"zyxwvutsrqponmlkjihgfedcba"，由于字母o在字母表中位于i的前面，因此单词"offer"排在"is"的前面；同样，由于字母i在字母表中位于c的前面，因此单词"is"排在"coming"的前面。因此，这一组单词是按照字母表顺序排序的，应该输出true。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 题意仅要求判断是否是按照已知字母序列排序，如果可以只管的比较字母序列下字母的大小，那么就只需要考虑如何判断两个字符串的顺序是否合适。所有问题被拆解为两部分。第一步，根据字母表序列将其映射到顺序上，这样更加直观；第二步，对字符数组进行遍历，比较前一项和后一项元素是否满足顺序要求。
第一步：计算ASCII码差值（减去字母a），作为键，而字母出现的位置下标作为值。以此记录字母的大小来作为顺序比较的依据。
第二步：通过比较前后两个字符串的每一位字母的大小，判断是否符合要求即可。当后一个字符串字母映射值小于前一个字符串的同位字母时，顺序一定不对；而大于时，顺序一定符合；等于时，最后如果长度一致，也是符合的；且如果是前缀关系，短的元素应该排在前。
参考代码
public boolean isOrder(String[] strArr, String order) {
int[] orderArr = new int[26];
for (int i = 0; i < order.length(); i++) {
orderArr[order.charAt(i) - 'a']++;
}
String pre = strArr[0];
for (int i = 1; i < strArr.length; i++) {
String cur = strArr[i];
for (int j = 0; j < pre.length(); j++) {
if (j >= cur.length()) {
return false;
}
int flag = orderArr[cur.charAt(j) - 'a'] - orderArr[pre.charAt(j) - 'a'];
if (flag < 0) {
// 如果同位，前字母大于后字母，必定是false
return false;
} else if (flag > 0) {
// 如果同为，前字母小于后字母，必定符合要求
break;
}
}
pre = cur;
}
return true;
}
Tips：2024-02-05 22:15
题目四：最小时间差
给定一组范围在00：00至23：59的时间，求任意两个时间之间的最小时间差。例如，输入时间数组["23：50"，"23：59"，"00：00"]、"23：59"和"00：00"之间只有1分钟的间隔，是最小的时间差。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 如果将时间转化为数值，那么会更加的便于比较和计算差值；一天有24 * 60分钟，所以可以分配一个1440大小的数组表示一天的所有时间，对应的时间出现则记录加一（如果时间值不会重复，记录为true也可）；遍历数组，记录两个值为大于0的相邻元素下标差值，求出最小差值即可。由于时间是首位相连的，所以最后要比较首段元素和末端元素的反向差值，即：value = 1400 + firstIndex - lastIndex。
参考代码
public int findMinDifference(String[] timeArr) {
if (timeArr == null || timeArr.length <= 1) {
return -1;
}
int res = Integer.MAX_VALUE;
int[] times = new int[1440];
for (String s : timeArr) {
String[] split = s.split("：");
int hour = Integer.parseInt(split[0]);
int min = Integer.parseInt(split[1]);
times[hour * 60 + min]++;
}
int first = -1, end = -1;
for (int i = 0; i < times.length; i++) {
if (times[i] == 0) {
continue;
}
// 如果出现相同的时间，最小间隔为0
if (times[i] > 1) {
res = 0;
break;
}
// 记录第一个不为0的时间
if (first == -1) {
first = i;
}
// 已记录上一个时间节点是，计算时间间隔
if (end != -1) {
// 计算间隔
res = Math.min(res, i - end);
}
end = i;
}
// 计算边界时间差
res = Math.min(res, 1440 + first - end);
return res;
}
Tips：2024-02-05 22:16
三、章节小结
哈希表的时间效率很高，添加、删除和查找操作的时间复杂度都是 O(1)。
为了设计一个哈希表，首先需要一个数组，把每个键的哈希值映射到数组的一个位置。为了解决冲突，可以把映射到同一位置的多个键用链表存储。同时，为了避免链表太长，当哈希表中元素的数目与数组的长度的比值超过一定的阈值时，则增加数组的长度并根据新的长度重新映射每个键的位置。
如果结合哈希表和其他数据结构的特点，则还可以设计出很多更加高级、更加复杂的数据结构，如最近最少使用缓存。
哈希表是经常被用来记录字符串中字母出现的次数、字符串中字符出现的位置等信息。
如果哈希表的键的数目是固定的，并且数目不太大，那么也可以用数组来模拟哈希表，数组的下标对应哈希表的键，而数组的值与哈希表的值对应。