首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
上一节主要学习了树、二叉树以及二叉树的遍历。本节主要学习一种特殊的二叉树——二叉查找树。它的最大特点是支持动态数据集合的快速插入、删除、查找操作。
首先，我们思考一下问题。之前说过，散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。既然有了这么高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢？有没有哪些地方是散列表做不了，必须要用二叉树来做的呢？
二叉查找树（Binary Search Tree）也叫做二叉搜索树，是二叉树中最常用的一种类型。二叉查找树是为了实现快速查找而生的。不过，依赖于二叉查找树的特殊结构，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
本节我们再来看下哈希算法的剩余三种应用：负载均衡、数据分片、分布式存储。这三个应用都是和分布式系统有关的，今天我们主要看下哈希算法是如何解决这些分布式问题的。
负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是，维护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。这种方法简单直观，但也有几个弊端：
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
在我们学习过的内容中，有很多地方将散列表和链表一起使用。例如：
今天我们主要看看散列表和链表是如何组合一起使用的，以及为什么散列表和链表会放在一起使用。
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
所谓脱库指网站遭到入侵后，黑客盗取其数据库。知道有脱库这种行为后，你会如何存储用户密码这么重要的数据呢？仅仅MD5加密一下存储就行了么？解答这个问题要先弄懂哈希算法。
哈希算法包含MD5、SHA等著名算法。我们平时也是直接拿现成的用。本节课不会重点剖析哈希算法的原理，也不会教你如何设计一个哈希算法，而是从实战的角度告诉你，在实际的开发中，我们该如何用哈希算法解决问题。
前几节我们提到过“散列表”、“散列函数”，这里又提到“哈希算法”。实际上，不管是”哈希”还是“散列”，都是中文翻译的区别，英文其实都是“Hash”。所以，我们常听到有人把“散列表”叫作“哈希表”“Hash 表”，把“哈希算法”叫作“Hash 算法”或者“散列算法”。那到底什么是哈希算法呢？
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。极端情况下，如果所有的数据经过散列函数之后，都散射到同一个槽里。如果使用基于链表的冲突解决方法，这个时候，散列表会退化为链表。查询时间复杂度从O(1)为O(n)。
如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。
好的散列函数应该满足如下性质：
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
Word软件有一个单词拼写检查的功能，当写错英文单词时，会以标红的方式提示“拼写错误”。那么这个功能是如何实现的呢？这就要借助散列表（Hash Table）的思想。
散列表（Hash Table），也称为“哈希表”或者“hash 表”。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
先举一个例子，比如89 名选手参加学校运动会，为了方便记录成绩，每个选手胸前都会贴上自己的参赛编号。编号由年级、班级等6为数字组成，比如051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位表示选手编号 1 到 89。这个时候我们该如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
我们知道，二分查找要依赖于数组的随机访问特性，那么如果数据存储在链表中怎么使用二分查找呢？这就需要将链表进行改造，使其支持二分查找。改造后的数据结构称为”跳表“（Skip list）。它是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。
Redis（Key-Value数据库） 中的有序集合（Sorted Set）就是用跳表来实现的。通过后面的讲解我们会知道，红黑树也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢？ 为什么不用红黑树呢？
对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。
首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
首先提出一个问题，如何根据IP地址快速定位地理位置？其实它是通过维护一个很大的 IP 地址库来实现的。地址库中包括 IP 地址范围和归属地的对应关系。例如部分IP地址库如下：
1 | [202.102.133.0, 202.102.133.255] 山东东营市 |
当查询202.102.133.13IP地址时，查询IP地址库发现落在了[202.102.133.0, 202.102.133.255]，所以显示出的地理位置为“山东东营市”。
然而，在庞大的地址库中逐一比对IP地址所在的区间是非常耗时的。假设有12万条这样的IP区间与归属地的对应关系，如何快速定位一个IP地址的归属地？
