一、哈希表基础知识
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（第8章）可能更合适。如果需要知道一个动态数据集中的最大值或最小值，那么堆（第9章）的效率可能更好。如果希望能够根据前缀进行单词查找，如查找字典中所有以ex开头的单词，那么应该用前缀树（第10章）作为实现字典的数据结构。
二、哈希表知识扩展
1. 哈希表的设计
- 略
哈希表题目 | 哈希表的设计
题目一：插入、删除和随机访问都是O(1)的容器
设计一个数据结构，使如下三个操作的时间复杂度都是O(1)；insert(value)：如果数据集中不包含一个数值，则把它添加到数据集中remove(value)：如果数据集中包含一个数值，则把它删除。getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同。
题目分析
难度： ⭐
思路： 插入和删除的随机访问均是O(1)，很容易便想到HashMap，但问题在于随机访问并不能实现O(1)，对于数组而言，通过指针访问的复杂度也是O(1)，所以，可以将数组和HashMap一起使用。通过HashMap记录值和数组下标的关系，而数组中对应下标有存放该值。这样在插入和删除时，通过HashMap可以快速判断是否存在，并找到该值。而随机访问时，只需要做一个随机函数运算，按照数组数据长度随机生成下标，通过下标进行访问数据，这样便可实现随机访问概率相同。
参考代码
Tips：2024-02-05 22:03
题目二：最近最少使用缓存
请设计实现一个最近最少使用(Least Recently Used, LRU)缓存，要求如下两个操作的时间复杂度都是 O(1)；get(key)：如果缓存中存在键key，则返回它对应的值；否则返回-1。put(key, value)：如果缓存中之前包含键key，则它的值设为value；否则添加键 key及对应的值value。在添加一个键时，如果缓存容量已经满了，则在添加新键之前删除最近最少使用的键（缓存中最长时间没有被使用过的元素）。
题目分析
难度： ⭐
思路： 同上题一样，首先想到可以通过HashMap实现取值、放值得过程。其次需要满足溢出移除最近最少使用的值，这时可以使用一个辅助控件来记录最近最少使用的元素。此处选择双向链表比较合适，当元素被使用到，则将元素移动至链尾，如果溢出，则删除链首元素，随后将新元素添加到链尾。
参考代码
Tips：2024-02-05 22:11
2. 哈希表的应用
- 略
哈希表题目 | 哈希表的应用
题目一：有效的变位词
给定两个字符串s和t，请判断它们是不是一组变位词。在一组变位词中，它们中的字符及每个字符出现的次数都相同，但字符的顺序不能相同。例如，anagram和nagaram就是一组变位词。
题目分析
难度： ⭐
思路： 要判断是否是变位词，可以转化为比较两个字符串是否存在相同的元素，且元素个数相等。如果只存在字母，可以通过数组模拟哈希表进行出现次数的缓存。考虑场景的通用性，可以采用哈希表以字符为建，出现次数为值进行缓存；最后比较两个字符所对应的哈希表缓存的数据是否一直即可。
参考代码
Tips：2024-02-05 22:12
题目二：变位词组
给定一组单词，请将它们按照变位词分组。例如，输入一组单词["eat"，"tea"，"tan"，"ate"，"nat"，"bat"]，这组单词可以分成3组，分别是["eat"，"tea"，"ate"]、["tan"，"nat"]和["bat"]。假设单词中只包含英文小写字母。
题目分析
难度： ⭐⭐
思路： 该题主要的问题就在于，即使使用哈希表存放字母出现的次数依旧无法对其进行分组，暴力分组复杂度过高。因此可以通过乘法特性以及质数无公倍数的特性对哈希表进行转化处理，定义一个指数数组用以代替字母，字符串按字母换算成质数后相乘，其结果作为字符串的所属分组标识，标识一样则说明是变位词，通过这个特性来对字符串进行分组。
参考代码
Tips：2024-02-05 22:12
题目三：外星语言是否排序
有一门外星语言，它的字母表刚好包含所有的英文小写字母，只是字母表的顺序不同。给定一组单词和字母表顺序，请判断这些单词是否按照字母表的顺序排序。例如，输入一组单词["offer"，"is"，"coming"]，以及字母表顺序"zyxwvutsrqponmlkjihgfedcba"，由于字母o在字母表中位于i的前面，因此单词"offer"排在"is"的前面；同样，由于字母i在字母表中位于c的前面，因此单词"is"排在"coming"的前面。因此，这一组单词是按照字母表顺序排序的，应该输出true。
题目分析
难度： ⭐⭐
思路： 题意仅要求判断是否是按照已知字母序列排序，如果排序规则本身就有大小可比，那么就只需要考虑如何判断两个字符串的顺序是否合适。所有问题被拆解为两部分。第一步，将字母表顺序转化为数值，这样更加直观；第二步，对字符数组进行遍历，比较前一项和后一项元素是否满足顺序要求。
第一步：计算ASCII码差值（减去字母a），作为键，而字母出现的位置下标作为值。以此记录字母的权重来作为顺序比较的依据。
第二步：通过比较前后两个字符串的每一位字母的权重，判断是否符合要求即可。当后一个字符串字母权重小于前一个字符串时，顺序一定不对；大于时，顺序一定符合；等于时，最后如果长度一致，也是符合的。
参考代码
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；遍历数组，记录两个值为true相邻元素下标差值，求出最小差值即可，同时不要忘记计算首元素差值时，差值等于首个值为true的元素下标减去最后一个值为true的元素下标，再加上1440：value = 1400 + firstTrueIndex - lastTrueIndex。
参考代码
Tips：2024-02-05 22:16
三、章节小结
略