LeetCode49 一题学会hash算法

今天是LeetCode专题的第30篇文章，一起来看一道字符串分组的问题。

题意

这题的题意很简单，给定一个字符串数组，要求将所有字符串按照构成分组。

举个例子，比如给定的数组是[eat, ate, tea, tan, nat, bat]。

其中eat，ate，tea这三个单词用到的字母都是e，t和a各一个。tan和nat用到的都是a，n和t，最后剩下bat，所以分组结果就是：[eat, ate, tea]，[tan, nat]和[bat]。

暴力

我们依然从最简单的思路开始想起，我们分组的依据是每一个字符串当中用到的字母的情况。所以我们可以把每一个字符串当中所有的元素拆解出来，放到一个dict当中，然后我们用这个dict来作为分组的标准，将dict相同的字符串放在同一组。

比如eat我们把它变成{'e': 1, 'a': 1, 't': 1}，由于一个字母可能出现多个，所以我们也要记录出现的次数。但有一个问题是，dict是动态数据，在Python当中我们不能用它作为另一个dict的key。这个问题比较简单的方法是我们写一个方法将这个dict拼接成字符串，比如'e1a1t1'。我们用这个作为key。但是这又有了一个问题，dict当中的key并不一定是有序的，所以我们需要对dict进行排序，可以看下下图中的流程。

也就是说我们需要实现一个函数，它的输入是字符串，输出是这个字符串构成的元素。

def splitStr(s):
    d = defaultdict(int)
    for c in s:
        d[c] += 1
    ret = ''
    # 将dict中内容排序
    for k,v in sorted(d.items()):
        ret += (str(k) + str(v))
    return ret

到这里就简单了，我们在外层再创建一个dict用来存储分组后的结果即可，我们很容易就能写出代码：

from collections import defaultdict

class Solution:
    def splitStr(self, s):
        d = defaultdict(int)
        # 拆分字符串中元素
        for c in s:
            d[c] += 1
        ret = ''
        # 将dict中内容排序
        for k,v in sorted(d.items()):
            ret += (str(k) + str(v))
        return ret
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            # 拿到拆分之后的字符串作为key进行分组
            key = self.splitStr(s)
            groups[key].append(s)
            
        ret = []
        for _, v in groups.items():
            ret.append(v)
        return ret

有些小伙伴可能意识到了一个问题，既然我们先转化成dict之后后面还是要拼接成字符串，我们为什么不直接对字符串排序，将排序之后的结果作为key呢？构成元素一样的字符串，排序之后的结果必然是相同的。

比如apple和pplae排序之后都是aelpp，这样可行吗？

思路是OK的，但是提交并不能通过。原因也很简单，三个字可以概括，就是复杂度。这样做的复杂度非常大，因为字符串的长度并不是固定的，我们对它们一一排序需要大量的开销。另外我们用排序之后的结果作为key，也会占用存储资源。所以这不是一个好方法。

hash

接下来就到了我们的正主出场了，大家从标题当中应该就已经看出来了，这道题和hash算法有关。

讲道理，hash算法的名称如雷贯耳，我们经常听到，但是很多人并不知道hash算法是干嘛的，或者我们究竟什么地方要用到它。大家听得比较多的可能是hashMap。

其实hash算法的内容很简单，可以简单理解成映射。我们的输入可以是任何内容，可以是一个数字，也可以是个数组或者是一个对象，但是我们的输出是一个固定若干个字节组成的信息。比如下图当中对4取模就是一个hash函数，我们可以根据对4取模之后的结果将数归类到不同的分桶当中。

我们可以按照我们的意愿让一些数据分在同一个分桶当中，我们也可以让每一条数据hash之后的结果都尽量各不相同，这样做实现的是信息的压缩。比如我们将一个大小2MB的实例进行hash，得到了一个32位的字符串。相当于我们用32位的字符串就可以代表原本2MB的内容，这样我们可以进行高效的查询或者是其他操作。举个例子，比如当下的人脸识别模块，就可以简单理解成一个hash函数。摄像头拍摄照片，算法将照片hash成一个id，再去数据库当中找到这个id对应的个人信息，完成识别过程。

在这道题当中，我们希望设计一个hash函数，它读入一个字符串，根据字符串当中的内容进行hash，保证构造相同的字符串hash得到的结果一致。我们就通过这个hash之后的结果来进行分桶，从本质上来说，上面这一种做法也可以看成是一种hash方法。但是由于涉及到了排序，稍稍复杂了一些，并且最后返回的是一个字符串，从时间复杂度和空间复杂度上来看，都还有优化的空间，下面我们就来看一个比较常用的hash算法。

在这个算法当中，我们会选择一个质数作为hash因子，这样发生hash碰撞的概率会比较低。通过质数的幂来构造hash结果，我们来看代码：

def hash(dict):
    ret = 0
    prime = 23
    # k代表字符，v表示出现次数
    for k, v in dict:
        ret += v * pow(23, ord(k) - ord('a'))
        # 对2^32取模，控制返回值在32个bit内
        ret %= (1 << 32)
    return ret

这里的ord是取ascii码的运算，即将英文字母转成数字。我们用某一个质数不同的幂来表示不同的字母，再乘上字母出现的次数作为系数。最后将每个字母hash的值累加起来就得到了整个字符串的hash值，构造相同的字符串的系数和幂都是一样的，那么最后求和的结果显然也会相等，这个结论没有问题。但是反过来，hash值相等的字符串真的一样吗？

其实我们想一下是可以想到反例的，比如说如果我们单个的字符a，它的hash值的结果是，单个b的hash值也很好算，是23。请问23个a的hash值是多少？算一下就知道，也是23。因为虽然我们用的幂不同，但是它们的底数是一样的，我们可以用前面的系数来弥补指数的差。这种不同的对象hash结果一样的情况叫做hash碰撞，这种是不符合我们预期的。但是可以肯定的是，大多数情况下hash碰撞几乎是不可避免的。因为我们hash的目的就是为了用一个简单的数字或者字符串代替原本复杂庞大的数据，就好像拍照一样，两个不同的人，也可能拍出来看起来很像。

我们在这个过程当中存在大量的信息压缩或者信息丢失，比如说我们用10个bit的数字代表了原本2000个bit的数据。不管我们用什么样的策略，10个bit能表达的数据就是有限的。根据鸽笼原理，只要我们hash的数据足够多，总有两个不一样的数据hash的结果碰撞。

不过通过设计合适的因子和算法，可以降低或者控制出现碰撞的概率。比如这题当中，我们选择越大的素数越不容易出现碰撞，因为选择的素数越大，构成碰撞需要重复的字符就越多，这种可能性也就越低。

最后，我们来看完整代码：

from collections import defaultdict
import math


class Solution:
    def splitStr(self, s):
        hashtable = [0 for _ in range(30)]
        ret = 0
        for c in s:
            hashtable[ord(c) - ord('a')] += 1
            
        # hash算法
        for i in range(26):
            ret = ret * 23 + hashtable[i]
            # 控制返回值在32个bit内
            ret %= (1 << 32)
        return ret
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = self.splitStr(s)
            groups[key].append(s)
        
            
        ret = []
        for _, v in groups.items():
            ret.append(v)
        return ret

代码里有一个细节，我们刚才写的是v * pow(23, k)，为什么到这里我们换了一种写法？

因为Python当中pow函数返回的是浮点数，精度会有丢失，这样会导致hash碰撞的概率大大增加，所以我们换了不适用pow函数的方法。

总结

从难度上来说今天的题目并不难，即使是不知道hash算法的人也能想到解法。但是我们的目的并不是切题，而是从切题当中获得成长，并且hash算法是一个非常重要也是非常基础的算法，在很多应用和场景当中都有应用。因此我们了解一下hash算法的原理，对于我们日后的成长非常有帮助。

今天的文章就是这些，如果觉得有所收获，请顺手点个在看或者转发吧，你们的举手之劳对我来说很重要。