哈希表理论基础
哈希表是根据关键码的值而直接进行访问的数据结构。哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。一般哈希表都是用来快速判断一个元素是否出现集合里。
通过哈希函数把数组中的数字直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道数字位置。
哈希函数一般是通过特定编码方式,可以将其他数据格式转化为不同的数值。比如说想要把 [123456],如果将每个数字减 1,就可以将他们映射到另一个数组 [012345],另一个数组上的位置就是他们的索引。
但是可能会发生哈希碰撞,比如,两个数字都映射到了 1,那就会发生碰撞。一般哈希碰撞有两种解决方法:拉链法和线性探测法。
拉链法
拉链法就是,如果在索引 1 发生碰撞,那就是说有两个元素都映射到了 1,那就在 1 这个位置存储在链表上。拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法
使用线性探测法,一定要保证 tableSize 大于 dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求 tableSize 一定要大于 dataSize,要不然哈希表上就没有空置的位置来存放冲突的数据了。

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构:
- 数组
- Set(集合)
- Map(映射)
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组、Set 或者是 Map 来存放数据,才能实现快速的查找。
242. 有效的字母异位词
给定两个字符串 s 和 t,编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入:s = "anagram", t = "nagaram" 输出:true
示例 2: 输入:s = "rat", t = "car" 输出:false
字母异位词就是排列,相当于输入一个串 S,一个串 T,判断 T 是不是 S 中的一种排列。
数组其实就是一个简单哈希表,而且这道题目中字符串只有小写字符,那么就可以定义一个数组,来记录字符串 s 里字符出现的次数。
数组大小为 26 的 record 数组,初始化为 0,因为字符 a 到字符 z 的 ASCII 也是 26 个连续的数值。
用这个 record 数组来记录字符串 s 里字符出现的次数,s 里出现的字母 +1,t 里出现的字母 -1,最后 26 个槽全为 0 才能说明是字母异位词。
s 和 t 字符出现的次数一样,那么他们两个肯定是同样的字符进行不同排列的字符串。如果不一样,那连字符都不一样,更不用说是相同字符的不同排列了。
class Solution {
public boolean isAnagram(String s, String t) {
[] record = [];
( ; i < s.length(); i++) {
record[s.charAt(i) - ]++;
}
( ; i < t.length(); i++) {
record[t.charAt(i) - ]--;
}
( count : record) {
(count != ) {
;
}
}
;
}
}

