剑指offer-哈希表总结

---

---

前言

如果每个元素都存在一个值到另一个值的映射，那么就用
HashMap。例如，如果不仅要存储一个文档中的所有单词，同时还关心
每个单词在文档中出现的位置，则可以考虑用HashMap，单词作为
HashMap的键而单词的位置作为值。表5.2列举了HashMap的常用函数。

题型

这个题型其实还行，比较固定，做题者主要就是要考虑一下到底key和value到底应该放什么。value指不局限于基础数据类型，可以是list或者其他的。然后再使用key的时候要正反都想一想，到底适合放到哪。

方法

建议多写相关题目，没有什么具体的技巧。

就是要熟练的看上面的常用的函数，特别是getOrDefault（）。平常少用，但是题目会用的比较多。

总结

本章介绍了哈希表。哈希表的时间效率很高，添加、删除和查找
操作的时间复杂度都是O（1）。
为了设计一个哈希表，首先需要一个数组，把每个键的哈希值映
射到数组的一个位置。为了解决冲突，可以把映射到同一位置的多个
键用链表存储。同时，为了避免链表太长，当哈希表中元素的数目与
数组的长度的比值超过一定的阈值时，则增加数组的长度并根据新的
长度重新映射每个键的位置。
如果结合哈希表和其他数据结构的特点，则还可以设计出很多更
加高级、更加复杂的数据结构，如最近最少使用缓存。
在解决算法面试题时，哈希表是经常被使用的工具，用来记录字
符串中字母出现的次数、字符串中字符出现的位置等信息。
如果哈希表的键的数目是固定的，并且数目不太大，那么也可以
用数组来模拟哈希表，数组的下标对应哈希表的键，而数组的值与哈
希表的值对应。