数据结构与算法 数据结构与算法之美

数据结构与算法之美26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树

  |   0 评论   |   385 浏览

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

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

数据结构与算法之美25 | 红黑树(上):为什么工程中都用红黑树这种二叉树

  |   0 评论   |   411 浏览

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

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

数据结构与算法之美24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

  |   0 评论   |   357 浏览

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

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

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

数据结构与算法之美22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?

  |   0 评论   |   308 浏览

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

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

数据结构与算法之美21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?

  |   0 评论   |   348 浏览

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

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

数据结构与算法之美20 | 散列表(下):为什么散列表和链表经常会一起使用?

  |   0 评论   |   339 浏览

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

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

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

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

数据结构与算法之美19 | 散列表(中):如何打造一个工业级水平的散列表?

  |   0 评论   |   438 浏览

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

今天,我们就来学习一下,如何设计一个可以应对各种异常情况的工业级散列表,来避免在散列冲突的情况下,散列表性能的急剧下降,并且能抵抗散列碰撞攻击?

数据结构与算法之美18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?

  |   0 评论   |   347 浏览

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

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

数据结构与算法之美17 | 跳表:为什么Redis一定要用跳表来实现有序集合?

  |   0 评论   |   386 浏览

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

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

数据结构与算法之美15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?

  |   0 评论   |   441 浏览

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

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

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