miang 的博客

反思是成功之父

图的表示:如何存储微博、微信等社交网络中的好友关系?

微博、微信、LinkedIn这些社交软件我想你肯定都玩过吧。在微博中,两个人可以互相关注;在微信中,两个人可以互加好友。那你知道,如何存储微博、微信等这些社交网络的好友关系吗?

这就要用到我们今天要讲的这种数据结构:图。实际上,涉及图的算法有很多,也非常复杂,比如图的搜索、最短路径、最小生成树、二分图等等。我们今天聚焦在图存储这一方面,后面会分好几节来依次讲解图相关的算法。

堆的应用:如何快速获取到Top 10最热门的搜索关键词?

搜索引擎的热门搜索排行榜功能你用过吗?你知道这个功能是如何实现的吗?实际上,它的实现并不复杂。搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的 Top 10 搜索关键词。

那请你思考下,假设现在我们有一个包含 10 亿个搜索关键词的日志文件,如何能快速获取到热门榜 Top 10 的搜索关键词呢?

这个问题就可以用堆来解决,这也是堆这种数据结构一个非常典型的应用。上一节我们讲了堆和堆排序的一些理论知识,今天我们就来讲一讲,堆这种数据结构几个非常重要的应用:优先级队列、求 Top K 和求中位数。

红黑树(下):掌握这些技巧,你也可以实现一个红黑树 有更新!

红黑树是一个让我又爱又恨的数据结构,“爱”是因为它稳定、高效的性能,“恨”是因为实现起来实在太难了。我今天讲的红黑树的实现,对于基础不太好的同学,理解起来可能会有些困难。但是,我觉得没必要去死磕它。

我为什么这么说呢?因为,即便你将左右旋背得滚瓜烂熟,我保证你过不几天就忘光了。因为,学习红黑树的代码实现,对于你平时做项目开发没有太大帮助。对于绝大部分开发工程师来说,这辈子你可能都用不着亲手写一个红黑树。除此之外,它对于算法面试也几乎没什么用,一般情况下,靠谱的面试官也不会让你手写红黑树的。

如果你对数据结构和算法很感兴趣,想要开拓眼界、训练思维,我还是很推荐你看一看这节的内容。但是如果学完今天的内容你还觉得懵懵懂懂的话,也不要纠结。我们要有的放矢去学习。你先把平时要用的、基础的东西都搞会了,如果有余力了,再来深入地研究这节内容。

排序(上):为什么插入排序比冒泡排序更受欢迎? 有更新!

本文章是从极客时间抄写的,仅仅是看不懂,抄了一遍,分享给大家。 ©版权归极客邦科技所有 排序对于任何一个程序员来说,可能都不会陌生。你学的第一个算法,可能就是排序。大部分编程语言中,也都提供了排序函数。在平常的项目中,我们也经常会用到排序。排序非常重要,所以我会花多一点时间来详细讲一讲经典的排序算法。 排序算法太多了,有很多可能你连名字都没听说过,比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮,也是最经典的、最常用的:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我按照时间复杂度把他们分成了三类,分三节课讲解。 在这问题去学习,是最有效的学习方法。所以按照惯例,我还是先给你出一个思考题:插入排序和冒泡排序的时间复杂度相同,都是O(n2),在实际的软件开发里,为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢 ? 你可以思考一两分钟,带着这个问题,我们开始今天的内容! 如何分一个“排序算法”? 学习排序算法,我们除了学习它的算法原理、代码原理之外,更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法,要从哪几个方面入手呢….

递归:如何用三行代码找到“最终推荐人”? 有更新!

推荐注册佣金的这个功能我想你应该不陌生吧?现在很多App都有这个功能。我们可以说,用户C的 “最终推荐人” 为用户 A,用户B的 “最终推荐人” 也为用户A,而用户A没有 “最终推荐人”。

一般来说,我们会通过数据库来记录这种推荐关系。在数据库表中,我们可以记录两行数据,其中 actor_id 表示用户id,referrer_id表示推荐人id。

2984d45578440e9a348144c70d124a0ejpg

基于这个背景,我的问题是,给定一个用户ID,如何查找这个用户的 “最终推荐人”?带着这个问题,我们来学习今天的内容,递归(Recursion)!

线性排序:如何根据年龄给 100 万用户数据排序? 有更新!

本文章是从极客时间抄写的,仅仅是看不懂,抄了一遍,分享给大家。 ©版权归极客邦科技所有 上两节中,我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天我会讲三种时间复杂度是O(n)的排序算法:桶排序、技术排序、基数排序。因为这些排序算法的时间复杂度是线性的,所以我们把这类排序算法叫做线性排序(Linear Sort)。之所以能做到线性的时间复杂度,主要原因是,这三个算法是非基于比较的排序算法,都不涉及元素之间的比较操作。 这几种排序算法那理解起来都不难,时间、空间复杂度分析起来也很简单,但是对要排序的数据要求很苛刻,所以我们今天学习重点是掌握这些排序算法的使用场景。 按照惯例,我先给你出一道思考题:**如何根据年龄给100万用户排序?**你可能会说,我用上一节讲的归并、快排就可以搞定啊!是的,它们也可以完成功能,但是时间复杂度最低也是O(nlogn)。有没有更快的排序方法呢?让我们一起进入今天的内容! 桶排序(Bucket Sort) 首先,我们来看桶排序。桶排序,顾名思义,会用到 “桶”,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据在单独进行….

排序优化:如何实现一个通用的、高性能的排序函数? 有更新!

本文章是从极客时间抄写的,仅仅是看不懂,抄了一遍,分享给大家。 ©版权归极客邦科技所有 几乎所有的编程语言都会提供排序函数,比如C语言中qsort(),C++ STL中的sort()、stable_sort(),还有Java语言中的Collections,sort()。在平时的开发中,我们也都是直接使用这些现成的函数来实现业务逻辑中的排序功能。那你知道这些排序函数是如何实现的吗?底层都利用了哪种排序算法呢? 基于这些问题,今天我们就来看排序这部分的最后一块内容:如何实现一个通用的、高性能的排序函数? 如何选择合适的排序算法? 如果要实现一个通用的、高效率的排序函数,我们应该选择哪种排序算法?我们先回顾一下前面讲过的几种排序算法。 我们前面讲过,线性排序算法的时间复杂度比较低,适合场景比较特殊。所以如果要写一个通用的排序函数,不能选择线性排序算法。 如果对小规模数据进行排序,可以选择时间复杂度是O(n2)的算法;如果对大规模数据进行排序,时间复杂度是O(nlogn)的算法更加高效。所以,为了兼顾任意规模数据的排序,一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。 时….

二分查找(上):如何用最省内存的方式实现快速查找功能? 有更新!

今天我们讲一种针对有序数据集合的查找算法:二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,很多非计算机专业的同学很容易就能理解,但是看似越简单的东西往往越难掌握好,想要灵活应用就更加困难。

老规矩,我们还是来看一道思考题。

假设我们有1000万个整数数据,每个数据占8个字节,**如何设计数据结构和算法,快速判断某个整数是否出现在这1000万数据中?**我们希望这个功能不要占用太多的内存空间,最多不要超过100MB,你会怎么做?带着这个问题,让我们进入今天的内容吧!

二分查找(下):如何快速定位IP对应的省份地址? 有更新!

通过IP地址来查找IP归属地的功能,不知道你有没有用过?没用过也没关系,你现在可以打开百度,在搜索框里随便输一个IP地址,就会看到它的归属地。
这个功能并不复杂,它是通过维护一个很大的IP地址库来实现的。地址库中包括IP地址范围和归属地的对应关系。

当我们要查询202.102.133.13这个IP地址的归属地时,我们就在地址库中搜索,发现这个IP地址落在[202.102.133.0,202.102.133.255] 这个地址范围内,那我们就可以将这个IP地址范围对应的归属地 “山东东营市” 显示给用户了。

跳表:为什么Redis一定要用跳表来实现有序集合? 有更新!

上两节我们讲了二分查找算法。当时我讲到,因为二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?

实际上,我们只需要对链表稍加改造,就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表(Skip list),也就是今天要讲的内容。

跳表这种数据结构对你来说,可能会比较陌生,因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。

Redis 中的有序集合(Sorted Set)就是用跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速的插入、删除和查找操作。**那 Redis 为什么会选择用跳表来实现有序集合呢?**为什么不用红黑树呢?学完今天的内容,你就知道答案了。

散列表(上):Word文档中的单词拼写检查功能是如何实现的? 有更新!

Word这种文本编辑器你平时应该经常用把,那你有没有留意过它的拼写检查功能呢?一旦我们在Word里输入一个错误的英文单词,它就会用标红的方式提示 “拼写错误”。Word的这个单词拼写检查功能,虽然很小但却非常实用。你有没有想过,这个功能是如何实现的呢?

其实啊,一点儿不难。只要你学完今天的内容,散列表(Hash Table)。你就能像微软 Office 的工程师一样,轻松实现这个功能。

散列表(中):如何打造一个工业级水平的散列表? 有更新!

在极端情况下,有些恶意的攻击者,还有可能通过精心构造的数据,使得所有的数据经过散列函数之后,都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法,那这个时候,散列表就会退化为链表,查询的时间复杂度就从 O(1) 急剧退化为 O(n)。

如果散列表中有 10 万个数据,退化后的散列表查询的效率就下降了 10 万倍。更直接点说,如果之前运行 100 次查询只需要 0.1 秒,那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源,导致系统无法响应其他请求,从而达到拒绝服务攻击(DoS)的目的。这也就是散列表碰撞攻击的基本原理。

散列表(下):为什么散列表和链表经常会一起使用? 有更新!

在链表那一节,我讲到如何用链表来实现 LRU 缓存淘汰算法,但是链表实现的 LRU 缓存淘汰算法的时间复杂度是 O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到 O(1)。

在跳表那一节,我提到 Redis 的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。当时我们也提到,Redis 有序集合不仅使用了跳表,还用到了散列表。

除此之外,如果你熟悉 Java 编程语言,你会发现 LinkedHashMap 这样一个常用的容器,也用到了散列表和链表两种数据结构。

今天,我们就来看看,在这几个问题中,散列表和链表都是如何组合起来使用的,以及为什么散列表和链表会经常放到一块使用。

哈希算法(上):如何防止数据库中的用户信息被脱库? 有更新!

还记得 2011 年 CSDN 的“脱库”事件吗?当时,CSDN 网站被黑客攻击,超过 600 万用户的注册邮箱和密码明文被泄露,很多网友对 CSDN 明文保存用户密码行为产生了不满。如果你是 CSDN 的一名工程师,你会如何存储用户密码这么重要的数据吗?仅仅 MD5 加密一下存储就够了吗? 要想搞清楚这个问题,就要先弄明白哈希算法。

哈希算法历史悠久,业界著名的哈希算法也有很多,比如 MD5、SHA 等。在我们平时的开发中,基本上都是拿现成的直接用。所以,我今天不会重点剖析哈希算法的原理,也不会教你如何设计一个哈希算法,而是从实战的角度告诉你,在实际的开发中,我们该如何用哈希算法解决问题

哈希算法(下):哈希算法在分布式系统中有哪些应用? 有更新!

上一节,我讲了哈希算法的四个应用,它们分别是:安全加密、数据校验、唯一标识、散列函数。今天,我们再来看剩余三种应用:负载均衡、数据分片、分布式存储

你可能已经发现,这三个应用都跟分布式系统有关。没错,今天我就带你看下,哈希算法是如何解决这些分布式问题的

二叉树基础(上):什么样的二叉树适合用数组来存储? 有更新!

前面我们讲的都是线性表结构,栈、队列等等。今天我们讲一种非线性表结构,树。树这种数据结构比线性表的数据结构要复杂得多,内容也比较多,所以我会分四节来讲解。

我反复强调过,带着问题学习,是最有效的学习方式之一,所以在正式的内容开始之前,我还是给你出一道思考题:二叉树有哪几种存储方式?什么样的二叉树适合用数组来存储?

带着这些问题,我们就来学习今天的内容,树!

二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? 有更新!

上一节我们学习了树、二叉树以及二叉树的遍历,今天我们再来学习一种特殊的的二叉树,二叉查找树。二叉查找树最大的特点就是,支持动态数据集合的快速插入、删除、查找操作。

我们之前说过,散列表也是支持这些操作的,并且散列表的这些操作比二叉查找树更高效,时间复杂度是 O(1)。既然有了这么高效的散列表,使用二叉树的地方是不是都可以替换成散列表呢?有没有哪些地方是散列表做不了,必须要用二叉树来做的呢?

带着这些问题,我们就来学习今天的内容,二叉查找树!

红黑树(上):为什么工程中都用红黑树这中二叉树? 有更新!

上两节,我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时间复杂度跟树的高度成正比,理想情况下,时间复杂度是O(logn)。

不过,二叉查找树在频繁的动态更新过程中,可能会出现树的高度远大于log2n的情况,从而导致各个操作的效率下降。极端情况下,二叉树会退化为链表,时间复杂度会退化到O(n)。我上一节说了,要解决这个复杂度退化的问题,我们需要设计一种平衡二叉查找树,也就是今天要讲的这种数据结构。

很多书籍里,但凡讲到平衡二叉查找树,就会拿红黑树作为例子。不仅如此,如果你有一定的开发经验,你会发现,在工程中,很多用到平衡二叉查找树的地方都会用到红黑树。你有没有想过,为什么工程中都喜欢红黑树,而不是其他平衡二叉查找树呢?

带着这个问题,让我们一起来学习今天的内容呢?

递归树:如何借助树来求解递归算法的时间复杂度? 有更新!

今天,我们来讲树这种数据结构的一种特殊应用,递归树。

我们都知道,递归代码的时间复杂度分析起来很麻烦。我们在排序(下)那里讲过,如何利用递推公式,求解归并排序、快速排序的时间复杂度,但是,有些情况,比如快排的平均时间复杂度的分析,用递推公式的话,会涉及非常复杂的数学推导。

除了用递推公式这种比较复杂的分析方法,有没有更简单的方法呢?今天,我们就来学习另外一种方法,借助递归树来分析递归算法的时间复杂度

不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫 有更新!

你好,我是王争。

专栏更新过半,我发现有些小伙伴已经掉队,虽然有人掉队也挺正常,但是我还是想尽量拉一把。于是,周末的时间,我就在想,究竟是什么原因让有些小伙伴掉队了?是内容本身太难了吗?是我讲的不够清楚吗?还是小伙伴本身基础太差、不够努力、没有掌握学习方法?

我觉得都不是,让你掉队的原因,从根儿上讲,是你内心的迷茫。如果我们不那么确信能不能看懂、能不能学会的时候,当面对困难的时候,很容易就会否定自己,也就很容易半途而废

这就好比你迷失在沙漠中,对你来说,肆虐的狂风并不可怕,可怕的是,你不知道该努力多久才能走出沙漠,不知道到底能不能走出沙漠。这种对结果的未知、不确定,导致了你内心的恐惧,最后就差那么一点点就可以走出沙漠的时候,你放弃了。