4.散列表&哈希&树

18 - 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？

散列表：Hash Table，又称哈希表，或者hash表。

散列表，用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，没有数组就没有散列表。

关键字：键(key)、哈希函数、散列值(value)

哈希函数的三个基本要求：

1.散列值是一个非负正数

2.key1==key2 则hash(key1)==hash(key2)

3.key1!=key2 则hash(key1)!=hash(key2)

第三点几乎不可能。无法避免散列冲突。

装载因子：填入表中的元素个数/散列表的长度

解决散列冲突的方法：

1.开放寻址法、2.链表法

19 - 散列表（中）：如何打造一个工业级水平的散列表？

散列表的查询效率并不能笼统的说成是O(1)。它跟散列函数、装载因子、散列冲突等都有关系。

如果散列函数设计的不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降

散列函数的设计，不能太复杂。

散列函数生成的值要尽可能随机并且均匀分布。

装载因子过大了怎么办？

可以进行动态扩容。重新申请一个更大的散列表，将数据搬移到这个新散列表中。

装载因子阀值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

如何避免低效的扩容？

当装载因子已经到达阈值，需要先进行扩容，再插入数据。这个时候插入数据就会变得很慢，甚至会无法接受。

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。

当装载因子触发阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。

对应查询操作，先从新散列表中查找，如果没有找到，再去老的散列表中查找。

通过均摊的方法，将一次性扩容的代价均摊到多次插入操作中。

开放寻址法VS链表法

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是java中ThreadLocalMap使用开放寻址法解决散列冲突的原因。

链表法比较适合存储大对象、大数据量的散列表，而且它更加灵活，支持更多的优化策略，比如用红黑树(或者跳表)代替链表。

举例分析HashMap

1.初始大小

2.装载因子和动态扩容

3.散列冲突解决方法

4.散列函数

20 - 散列表（下）：为什么散列表和链表经常会一起使用？

链表实现的LRU缓存淘汰算法的时间复杂度是O(n)，通过散列表可以将这个时间复杂度降低到O(1)。

Redis的有序集合不仅使用了跳表，还使用了散列表。

LRU缓存淘汰系统

一个缓存系统主要包含下面几个操作：

1.往缓存中添加一个数据

2.从缓存中删除一个数据

3.在缓存中查找一个数据

这3个操作都要涉及“查找”操作，如果单纯地采用链表的话，时间复杂度只能是O(n)。

如果将链表和散列表组合使用，可以将这3个操作的时间复杂度降低到O(1)。

23 - 二叉树基础（上）：什么样的二叉树适合用数组来存储？

满二叉树：叶子节点都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。

完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

满二叉树，又是完全二叉树的一种特殊情况。

如何表示（或存储）一颗二叉树？

1.基于指针（或者引用）的二叉链式存储法

2.基于数组的顺序存储法

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。

这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历

1.前序遍历：打印自己→左子节点→右子节点

2.中序遍历：左子节点→打印自己→右子节点

3.后序遍历：左子节点→右子节点→打印自己

24 - 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？

1.散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而二叉查找树的中序遍历，可以在O(n)的时间复杂度输出。

2.散列表扩容耗时很多，散列冲突时性能不稳定。二叉查找树性能也不稳定，但是平衡二叉查找树的性能非常稳定，时间复杂度O(logn)

3.哈希冲突以及哈希函数的耗时，性能不一定高

4.散列表的设计比较复杂