数据结构与算法之美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,你会怎么做呢?带着这个问题,让我们进入今天的内容吧!

数据结构与算法之美14 | 排序优化:如何实现一个通用的、高性能的排序函数

  |   0 评论   |   516 浏览

几乎所有的编程语言都会提供排序函数,比如C语言中qsort(),C++ STL中的sort()、stable_sort(),还有Java语言中的Collections.sort()。在平时的开发中,我们也都是直接使用这些现成的函数来实现业务逻辑中的排序功能。那你知道这些排序函数是如何实现的吗?底层都利用了哪种排序算法呢?

数据结构与算法之美13 | 线性排序:如何根据年龄给100万用户数据排序?

  |   0 评论   |   262 浏览

上两节中,我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天,我会讲三种时间复杂度是O(n)的排序算法:桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的,所以我们把这类排序算法叫作线性排序(Linear sort)。之所以能做到线性的时间复杂度,主要原因是,这三个算法是非基于比较的排序算法,都不涉及元素之间的比较操作。

这几种排序算法理解起来都不难,时间、空间复杂度分析起来也很简单,但是对要排序的数据要求很苛刻,所以我们今天学习重点的是掌握这些排序算法的适用场景

按照惯例,我先给你出一道思考题:如何根据年龄给100万用户排序? 你可能会说,我用上一节课讲的归并、快排就可以搞定啊!是的,它们也可以完成功能,但是时间复杂度最低也是O(nlogn)。有没有更快的排序方法呢?让我们一起进入今天的内容!

数据结构与算法之美12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?

  |   0 评论   |   263 浏览

上一节我讲了冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是O(n2),比较高,适合小规模数据的排序。今天,我讲两种时间复杂度为O(nlogn)的排序算法,归并排序快速排序。这两种排序算法适合大规模的数据排序,比上一节讲的那三种排序算法要更常用。

归并排序和快速排序都用到了分治思想,非常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素? 这就要用到我们今天要讲的内容。