关于《哈希表》的基础解析（上）

在���的一篇，我们将认识“哈希表”，并运用哈希表解题。

---

目录

1.哈希表的基础理论

哈希表

 哈希函数

哈希碰撞

2.有效的字母异位词

3.两个数组的交集

---

1.哈希表的基础理论

哈希表

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

简而言之，数组就是一张哈希表。

哈希表的关键码就是数组的索引下标，然后通过直接访问数组中的元素，如下图：

我们发现，哈希表和数组的形式是一样的。

通过哈希表，我们可以快速地判断一个元素是否出现在集合里。 

 哈希函数

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

又是十分专业但抽象的官方解释，简而言之，通过哈希函数我们可以把目标值映射在哈希表上的索引数字。

但是，如上表所示，哈希表的一个索引数字对应的不只有一个元素，这时，“来不及哀悼哈希函数，哈希碰撞登场！”

哈希碰撞

当两个元素映射到了同一索引下标时，这种情况叫做哈希碰撞。

解决哈希碰撞一般有两种方法，拉链法和线性探测法。

拉链法：

拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。

基本结构如上表所示。

线性探测法：

使用线性探测法，要保证tableSize大于dataSize，即哈希表大小大于数组大小。当出现哈希碰撞时，我们可以通过哈希表中的空位来解决冲突。

如：当元素1，2都映射在了索引值为1的位置，那么：

当然，这只是介绍了简单的处理方法，深层的东西需要各位独自研究。

---

作者的能力有限，哈希表的基本理论就介绍到这里。哈希法通过牺牲空间换取了时间，用于快速判断一个元素是否出现在集合里。 

2.有效的字母异位词

 对于“字母异位词”，简单理解就是：两字符串的长度相同，字母相同，但顺序不同。

对于字母异位词的解法很容易想到在关于《长度最小的子数组》的基础解析中的思路，建立两个表格，分别统计两个字符串中的元素种类与出现个数，随后进行比较。

然而代码过于麻烦，今天我们采用更简洁的代码并通过例题对哈希表进行理解。

例1：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"输出: true

示例 2:

输入: s = "rat", t = "car"输出: false

思路：数组作为一张简单的哈希表，我们建立一个新的数组，记录字符串s，t中字符出现的次数，而字符作为索引下标映射在哈希表中。

具体操作为定义数组record，大小为26，初始化为0，因为字符‘a’到字符‘z’在ASCII码表上是26个连续的数值。那么数组下标中，‘a'对应的是0，’z‘对应的是25。

在遍历字符串s时，只需要将s[i]-'a'（其差值就代表了对应的字符）对应的元素+1即可，这样某个字符出现的次数就被统计出来了，之后遍历字符串t时，将t[i]-'a'对应的元素-1。

最后，如果record中的元素都为0，则说明s,t的字符出现的种类与次数一样，即为字母异位词，return true。如果record中有元素不为0，则说明s或t有某个字符串多了或者少了字符，return false。

代码如下：

bool isAnagram(char* s, char* t) {      int record[26] = {0};      int lens=strlen(s);      int lent=strlen(t);        for (int i = 0; i  
例2：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
 
如果可以，返回 true ；否则返回 false 。
 
magazine 中的每个字符只能在 ransomNote 中使用一次。
 
示例 1：
 
输入：ransomNote = "a", magazine = "b"输出：false
 
示例 2：
 
输入：ransomNote = "aa", magazine = "ab"输出：false
 
示例 3：
 
输入：ransomNote = "aa", magazine = "aab"输出：true
 
 思路：基本思路与上一题一样，只是多出一个判断条件，用于判断元素出现的次数是否符合。
 
具体代码如下：
 
bool canConstruct(char* ransomNote, char* magazine) {    int record[26]={0};    int lenr=strlen(ransomNote);    int lenm=strlen(magazine);    if(lenr>lenm){        return false;    }    for(int i=0;i