1哈希算法（上）

        将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法。通过原始数据映射之后得到的二进制值串就是哈希值。

        如：

        这节课的内容比较偏实战，了解了哈希算法的四个应用场景，分别是：

        1.安全加密。我们讲到任何哈希算法都会出现散列冲突，但是这个冲突概率非常小。越是复杂的哈希算法越难破解，但是同样的它的计算时间也会比较长。所以选择哈希算法的时候，要权衡一下安全性和计算时间来决定使用哪种哈希算法。

        2.唯一标识。哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。

        3.数据校验。用于校验数据的完整性和正确性。

        4.散列函数。我们前面讲的散列函数也是哈希算法的一种应用，它对哈希算法的要求非常特别，更加看重的是散列的平均性和哈希算法的执行效率。

    2哈希算法（下）

        上节课讲了哈希算法的四个应用，这节课再补充三个应用，但是它们和上节课的应用稍稍有些不同，因为这节课的三个应用都和分布式系统有关。

        5.负载均衡。通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行进行取模运算，最终得到的值就是应该被路由到的服务器编号。

        利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。

        （会话粘滞我理解为同一个客户端请求服务时都路由到同一个服务器上）

        6.数据分片。

        数据分片这里举了两个例子，一个是统计“搜索关键词”出现的次数：我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度；另一个是快速判断图片是否在库中：通过哈希算法计算这个图片的唯一标识，然后与机器个数n求余取模，得到对应的机器编号。

        通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。

        7.分布式存储。现在互联网面对的都是海量的数据、海量的用户，我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据。和前面的思想一样，通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

         但是此时出现了一个问题，如果数据增多到原先的10个（假如它是10个）已经无法承受了，我们就需要扩容，比如扩到11个机器，那么现在哈希值与机器个数取模得到的结果和之前计算的结果就不一致了。

        这里引入了一致性哈希算法：假如我们有k个机器，数据的哈希值的范围是[0，MAX]。我们将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

        利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致的数据大量搬移的难题。

    3二叉树（上）

        前面我们学习的都是线性表结构，栈、队列等等。今天我们学习一种非线性表结构——树。

        话不多说，看图：

        注意弄清楚树中的父节点、子节点、兄弟节点、叶节点的概念。

        另外几个比较重要的概念就是高度（Height）、深度（Depth）、层（Level），注意不要弄混哦：

        可以参考下面这张图更好的理解它们三个的不同：

        树的结构很多样，但我们最常用的还是二叉树：每个节点最多有两个子节点，分别是左子节点和右子节点。（但是并不要求每个节点都必须有两个子节点哦）

        注意有两种比较特殊的二叉树。

        1.满二叉树。即上图中的编号为2的二叉树。

        2.完全二叉树。即上图中的编号为3的二叉树。注意区分完全二叉树和非完全二叉树哦，这个比较容易弄混。其实满二叉树就是完全二叉树的一种特殊形式。

        想要存储一颗二叉树，有两种办法：1.基于指针或者引用的二叉链式存储法，2.基于数组的顺序存储法。

        链式存储法：

        顺序存储法：

        重点理解一下顺序存储法，完全二叉树就是因为顺序存储法而被引出，它在存储完全二叉树的时候非常节省空间。

        二叉树的遍历方式有：前序遍历、中序遍历、后续遍历，注意它们的不同：

        这三种遍历方式都是通过递归实现哦，并且遍历的复杂度都为O(n)。

    4二叉树（下）

        这节课学习了一种特殊的二叉树，二叉查找树，它支持快速地查找、插入、删除操作。（要掌握这三种操作的实现方式哦）

        二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。不过，这只是针对没有重复数的情况。

        对于存在重复数据的二叉查找树，有两种解决方法：1.让每个节点存储多个值相同的数据，2.每个节点中存储一个数据，将值相同的数据存储在它的右子树中。

        在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比，两个极端情况的时间复杂度分别是O(n)和O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。

        为了避免时间复杂度的退化，针对二叉查找树，又设计了一种更加复杂的树——平衡二叉查找树，时间复杂度可以做到稳定的O(logn)，这就是我们下节课的内容啦~

        另外有一点要注意的是，为什么有的时候会用平衡二叉查找树而不是用散列表，也就是平衡二叉查找树相对散列表的优势（当然散列表也是有自己优势哒，它们各自都有自己的闪光点~）。

    5红黑树（上）

        平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于1。（这样说来其实我们之前说的满二叉树、完全二叉树都是平衡二叉树。但是非完全二叉树也有可能是平衡二叉树哦~）

        平衡二叉查找树：同时满足平衡二叉树和二叉查找树的特点。

        红黑树（R-B Tree）：树中的节点一类被标记为黑色，一类被标记为红色，除此之外还有几个需要满足的小条件，此处略。

        红黑树是“近似平衡”的，它做到了性能不会退化的太严重。其实红黑树并不是严格意义上的平衡查找二叉树，它没有完全符合左右子树相差不能大于1这个条件，但是我们把“平衡”理解为时间复杂度退化不要太严重的时候，它依然是一棵合格的平衡二叉查找树。红黑树的高度接近logn，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。

        红黑树的实现很难。但我们其实不应该把重点放在它的实现上。我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。

        因为红黑树是一种性能非常稳定的二叉查找树，所以在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。

        但它实现起来比较难，如果要自己写代码来实现，我们更倾向于用跳表来代替它。

        另外注意要知道，为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树（如Treap、Splay Tree、AVL数等）呢？

    6红黑树（下）

        这节课讲了红黑树的实现方法，其实我有偷懒没有认真去看它的细节，因为目前来说我不太需要掌握这些细节，毕竟面试官也不会考我手写红黑树的代码，哈哈~当然如果我真的需要去实现的时候，就需要跟着这些步骤把每个细节搞清楚然后一步一步去实现。

        上节课有说红黑树的定义，它还有一些小的要求，我当时没有写出来，现在写出来看一看：

        1.根节点是黑色的；

        2.每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

        3.任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

        4.每个节点，从该节点到达其可达子节点的所有路径，都包含相同数目的黑色节点。

        而在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而我们在实现红黑树的时候，关键点就在于在插入和删除的过程中进行“平衡调整”，实际上就是要把被破坏的第三、四点恢复过来。

        在这个过程中需要用到的操作有：左旋（rotate left）、右旋(rotate right)、改变颜色，左旋右旋有它们的定义，这里不作赘述。正在处理的节点叫做关注节点。

        如果需要实现，我们可以跟着步骤一步一步来做，需要注意以下三点：

        1.把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性，只要按照固定的操作步骤进行就OK了。

        2.找准关注节点，不要搞丢、搞错关注节点。

        3.插入操作的平衡调整比较简单，但是删除操作就比较复杂。