首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

上一节主要学习了树、二叉树以及二叉树的遍历。本节主要学习一种特殊的二叉树——二叉查找树。它的最大特点是支持动态数据集合的快速插入、删除、查找操作。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

之前讲的都是线性表结构,例如栈、队列等。本节主要讲一种非线性表结构,树。树这种数据结构比线性表复杂的多,内容也比较多。主要如下:

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

本节我们再来看下哈希算法的剩余三种应用:负载均衡、数据分片、分布式存储。这三个应用都是和分布式系统有关的,今天我们主要看下哈希算法是如何解决这些分布式问题的。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

所谓脱库指网站遭到入侵后,黑客盗取其数据库。知道有脱库这种行为后,你会如何存储用户密码这么重要的数据呢?仅仅MD5加密一下存储就行了么?解答这个问题要先弄懂哈希算法。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

在我们学习过的内容中,有很多地方将散列表和链表一起使用。例如:

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好,或者装载因子过高,都可能导致散列冲突发生的概率升高,查询效率下降。极端情况下,如果所有的数据经过散列函数之后,都散射到同一个槽里。如果使用基于链表的冲突解决方法,这个时候,散列表会退化为链表。查询时间复杂度从O(1)为O(n)。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

Word软件有一个单词拼写检查的功能,当写错英文单词时,会以标红的方式提示“拼写错误”。那么这个功能是如何实现的呢?这就要借助散列表(Hash Table)的思想。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

我们知道,二分查找要依赖于数组的随机访问特性,那么如果数据存储在链表中怎么使用二分查找呢?这就需要将链表进行改造,使其支持二分查找。改造后的数据结构称为”跳表“(Skip list)。它是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

首先提出一个问题,如何根据IP地址快速定位地理位置?其实它是通过维护一个很大的 IP 地址库来实现的。地址库中包括 IP 地址范围和归属地的对应关系。例如部分IP地址库如下:

阅读全文 »

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做最简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

首先,我们来看一道思考题:假设我们有 1000 万个整数数据,每个数据占 8 个字节,如何设计数据结构和算法,快速判断某个整数是否出现在这 1000 万数据中? 我们希望这个功能不要占用太多的内存空间,最多不要超过 100MB,你会怎么做呢?

阅读全文 »