哈希表工作原理与应用学习笔记

[boji123]

近日遇到了青阳大神，和他聊起了微软研究院的面试。我没去试试还是有点后悔，不过机会总是留给有准备的人，建议大家平时多多学习算法吧，leetcode是个很好的平台。青阳谈到了哈希表，我觉得这十分有趣 / 我孤陋寡闻，因此特地学习了一下并写了这篇笔记。

哈希表即散列表（hash=散列），是一种提供了某种表映射关系的数据结构，哈希表算法则是一种以空间为代价换取时间的算法，在以前存储空间紧张的时候，哈希表算法难以进行，而随着现在内存空间越来越大，哈希表被越来越广泛地应用。特别地，哈希表算法尤其受到ACM（国际大学生程序设计竞赛）的欢迎，因为它具有极其优秀的效率，相比于队列O（n）的查找时间，他只需要O（1）就可以定位内存。

哈希表的原理。首先我们需要定义一种映射关系，例如从字符串到整形数据的映射（MD5也是一种映射），这种映射通常是稀疏的（并不是所有的字符串都是有意义的单词 / 频繁出现）因此，对于一对一的映射，映射后的整形也是稀疏的，为了提高空间利用率，我们对映射后的数据求余，把整形限制在一个区间内，如果这个区间足够大，那么可以认为不存在冲突。如果我们把整形数据作为内存数组的下标来寻址、访问内存空间，那么就实现了从字符串到内存地址的映射。假设我们维护的是一个结构类型，那么我们可以根据指针找回原字符串，实现双向的映射。

一些待解决的问题。由于哈希表做的是一种求余后的映射，所以必然会有许多地址从未被访问、有许多字符串具有相同的哈希值访问相同的地址，产生冲突。由于哈希表是一种以空间换时间的算法，所以空间浪费是可以牺牲的，而对于冲突的问题，我们可以在产生冲突后额外维护一个链表，在访问到内存后继续做一个小的链表查找。由于当内存大小足够大时，冲突是小概率事件，他不会对整个代码的运行效率有多少影响。

哈希表的应用。哈希表最优秀的地方在于其搜索时间，而缺点在于其实现复杂度，因此特别适用于需要巨量搜索的场合，例如微软面试中提到的一个题，假设电脑中所有文件都是文章，里面含有大量的英文单词，要求统计英文单词的出现频率（这里把无关的部分省略了）。那么我们就可以维护一个哈希表，然后每得到一个单词，就进行一次映射（哈希、求余），并把访问的地址里的数据加一。
（例：mapInt=hash(charArr)%10000;buff[mapInt]++）
最后我们再遍历哈希表，根据结构指针找回原来的字符串，然后再输出对应的频率即可（哈希映射后顺序会被打乱，如果需要按字典序输出，需要另外排序）。

设n为单词总量相对于队列O（n^2）、字典树O（nlogn）的复杂度，哈希表只有O（n）的复杂度。

[SihangWu]

微软那题，我觉得构造哈希函数是关键

[hongruiqi]

统计单词频率的话，Trie树效率要比哈希表高吧。
哈希表每次查单词都要计算哈希，匹配到哈希以后，还要再次比对完整的字符串。
哈希表还会有碰撞的问题，如果单词的数量是未知的，那哈希表在扩容过程中的重新哈希和拷贝数据开销也是比较大的。
对于单词这种公共前缀多的，Trie树也比较省空间。

以前面试的时候也问到这个问题，面试官提了一种方法，利用文件系统作Trie树的载体，比如读到abc这个单词，就在磁盘上创建 /a/b/c/count这个文件，在文件里保存计数。这种可能应该用在内存里放不下那么多词的情况。这里会有文件的读取和写入开销，但是文件系统都有文件缓存机制，经常读写的文件会缓存在内存中，实际开销没有想象的那么大，而且相当于让操作系统帮我们管理了热数据。在内存不够用的情况下，即使不利用文件系统，也要自己处理数据在硬盘和内存中的交换，要达到较好的效果，实现起来会比较复杂。利用操作系统自带的机制也不失是一种简便有效的方法。git也是通过这种方式存储数据的。

哈希表作为一个通用高效的内存数据结构还是很好用的，特别是在不要求数据有序的时候。
基本上动态语言也都会内置对哈希表的支持（叫Dict或Map），动态语言底层实现也用到了哈希表，比如Python的全局变量，对象的成员变量等。

哈希表还可以借鉴Trie树，形成多层的哈希表。
Key的哈希值一般为一个32位或64位的int，可以取0..3位作为第一层的索引，4..7位作为第二层的索引，依次类推，形成一个级联的结构，每一层都是一个数组，从顶层到底层构成一个链表。这样可以避免碰撞过多导致哈希表退化为链表。