数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?

王争 2019-02-04
短网址服务你用过吗?如果我们在微博里发布一条带网址的信息,微博会把里面的网址转化成一个更短的网址。我们只要访问这个短网址,就相当于访问原始的网址。比如下面这两个网址,尽管长度不同,但是都可以跳转到我的一个 GitHub 开源项目里。其中,第二个网址就是通过新浪提供的短网址服务生成的。
原始网址:https://github.com/wangzheng0822/ratelimiter4j
短网址:http://t.cn/EtR9QEG
从功能上讲,短网址服务其实非常简单,就是把一个长的网址转化成一个短的网址。作为一名软件工程师,你是否思考过,这样一个简单的功能,是如何实现的呢?底层都依赖了哪些数据结构和算法呢?

短网址服务整体介绍

刚刚我们讲了,短网址服务的一个核心功能,就是把原始的长网址转化成短网址。除了这个功能之外,短网址服务还有另外一个必不可少的功能。那就是,当用户点击短网址的时候,短网址服务会将浏览器重定向为原始网址。这个过程是如何实现的呢?
为了方便你理解,我画了一张对比图,你可以看下。
从图中我们可以看出,浏览器会先访问短网址服务,通过短网址获取到原始网址,再通过原始网址访问到页面。不过这部分功能并不是我们今天要讲的重点。我们重点来看,如何将长网址转化成短网址?

如何通过哈希算法生成短网址?

我们前面学过哈希算法。哈希算法可以将一个不管多长的字符串,转化成一个长度固定的哈希值。我们可以利用哈希算法,来生成短网址。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(44)

  • Smallfly
    随着新年的到来,我们的算法专栏也到了尾声。有点怀念那段时间工作不忙,一天能有好几个小时,阅读和思考算法专栏。

    专栏给我带来的收获不仅仅是数据结构和算法的知识。在这之前虽然也每天学习,但总是东一块西一块,没有系统和脉络,一段时间之后,看似学了很多,但并没有什么效果。

    在学习算法课程的过程中,基本都在学习和思考专栏的内容。一般第一天过一遍概念,一边阅读一边手敲。第二天会把重点放在思考上,为什么需要这种数据结构和算法,它的利弊是什么,以及解答思考题。

    真正有收获的是思考和实践而不是阅读,阅读只是表象;如果只是阅读,也没有生字,会很轻松,但效果甚微。

    这让我切身体会到系统和专注的重要性。

    这种经历帮助我在实际工作中解决不少问题,不是说用到了哪种算法,而是在遇到问题时善于花时间去思考解决方案,而不是一味地寻找替代方案,把问题绕过去。

    紧跟着老师的脚步学下来了,不能说都掌握了,但有几点学习的心得想跟大家分享。

    1、迈出第一步。很多事情不是我们不会做,而是不想开始。一想到前面可能会有重重困难,思想上就先败下阵来了。只要开始一点点的弄懂,重在培养兴趣。

    2、慢一点,不贪多。可能有同学落下很多课,看看还有这么多没学,干脆就放弃了。其实并不需要掌握所有的,可以挑选自己感兴趣的内容,细嚼慢咽,先掌握一部分。再从已知探索未知,其实文章之间很多是有关联的,学习过程中可能自个儿就串起来了。

    3、多动手。阅读和思考还是远远不够的,带着文章的思路,用自己熟悉的语言实现一遍,跑起来测一测,会更有成就感,也是自己学习的痕迹。

    虽然专栏学完了,然而有些内容很快就会忘记,后面我还会偶尔拿出来读一读,回顾一下思路。我现在已经欣然接受,学习的东西很快会遗忘,但回顾的时候会迅速地想起来,印象也更深刻了。

    最后,祝王争老师和编辑小姐姐新年快乐,辛苦了。(´▽`ʃ♡ƪ)
    2019-02-04
    1
    54
  • Sharry
    问题一:
    - 尝试将用户 自定义后的短网址 和 原网址的映射关系 存入数据库
      - 插入成功, 则提示用户短网址生成成功
      - 若插入失败, 说明存在冲突, 则进行判重处理
         - 若数据库中短网址对应的原网址与当前正在处理的相同, 提示该短网址有效
         - 若数据库中短网址对应的原网址与当前正在处理的不相同, 提示该短网址已被占用

    问题二:
    可以使用布隆过滤器进行判重验证, 通过之后再插入
    2019-02-11
    10
  • 以前觉得数据结构和算法很难,学了之后,确实也难,但通过系统学习,心中有了一张完整的地图,以后只要不断反复看,反复学习,反复练习,一定能真正融合贯通。
    另外,最大的感受是学了数据结构和算法后,看其它中间件和框架的源代码,发现大部分底层就是数据结构和算法。感觉练了九阳神功一样,学习其它功夫快了很多
    2019-02-04
    9
  • 微秒
    坚持到了最后,虽然只看不写,但也加深了对数据结构的认识,接下来刷第二遍的时候再加深代码实践。最后祝大家新年快乐!顺便说句,老师的这个专栏真的很良心,谢谢了!
    2019-02-04
    8
  • TryTs
    兴趣是最好的老师,这话没有错。如果没有兴趣那就去找。就我个人看法,很多时候一开始不一定非要搞那么枯燥的东西,做一些有趣的东西,慢慢培养自己的兴趣,自己就会有好奇心去往深处学习,如果以来就弄那些很“艰深”的东西,可能不能坚持多久,“从入门到放弃”。学习老师这个专栏,我最大的收获就在于老师把平时课上那些算法讲活了,应用到具体场景之中,相较于一些为了练习而联系的习题,这让我更能体会到算法之美。也在不断激发我的好奇心。我希望自己能够一直抱持这份好奇心。继续努力学习。
    2019-02-04
    5
  • 小美
    王老师短网址有什么作用吗? 我上网查了下理由不能说服我?
    可能网上说得比较浅显,王老师方便指导下吗?

    作者回复: 比如微博里,网址如果很长,看起来不美观。缩短成短网址之后,短短的,不占空间,不是更好看些吗:)

    2019-02-09
    2
    4
  • xuery
    追到这里,终于有底气在简历上写上一行熟悉各种数据结构与算了^_^.
    感谢王争老师,下一步就是利用leetcode进一步提升自己的算法功底,
    将熟悉变成精通
    2019-04-11
    3
  • ./+-@YOU
    第二题:id生成器,不处理,会导致相同的长域名重复。有个解决方案,长域名设置唯一的限制,在重复的情况下,插入表失败后,查询已经存在的长域名,对应的短域名。返回该短域名
    2019-03-17
    2
  • 一涛
    1. 首先查询“用户自定义部分”是否与已经生成的短网址冲突,如果冲突,只能提示用户进行修改。如果不冲突,将“用户自定义部分”和对应的原始网址写入数据库即可。

    2. 给原始网址加唯一索引。如果写入异常,说明原始网址已经存在,再根据原始网址查询一次,取出短网址返回给用户。

    不知道回答对不对,请老师指正
    2019-02-04
    2
  • wahaha
    16进制应该是A到F(不是E)表示10到15,文字和朗读中都弄错了
    2019-03-09
    1
  • 实验室清洁工
    应该是16进制吧,62进制???

    作者回复: 是的,62进制会更短些

    2019-02-13
    1
    1
  • 纯洁的憎恶
    1.短网址的自定义部分是要展示给用户的。是否可以把自定义部分作为第三个字段存入数据库。如果不同用户对相同原网址申请短网址自定义部分不同。要么不允许这种行为,否则就得把自定义部分与原网址拼接输入哈希函数,以实现区分。
    2019-02-07
    1
  • 纯洁的憎恶
    通过哈希函数,在长网址字符串基础上,生成短网址哈希值。将哈希值从10进制提升至62进制,进一步缩短短网址长度。为了通过短网址回溯到原网址,需要建立长短网址的对应关系,存入数据库。

    为了避免散列冲突,需要在在建立新的对应关系时,查询数据库中是否已有短网址,若有再检查长网址是否一致,若不一致则发生冲突,需要给新的长网址字符串加前缀,再用哈希函数生成短网址,直到没有冲突,最终将前缀、对应关系均存入数据库。

    为方便查询,需要在数据库中建立短网址的索引(B+树)。减少SQL语句数量也可以提高性能,把查询+写入两条语句,简化为写入一条。代价是设置短网址唯一索引,不允许出现重复,这样当重复写入时数据库才会报错,此时再通过查询、前缀、写入的方式解决散列冲突。也可以针对短网址建立布隆过滤器,当新的短网址不在过滤器中则正常写入,否则通过查询判重并解决冲突。

    另一种方式是通过全局计数器,给每个请求的原网址分配一个序号,作为短网址的主要部分。但它可能造成同一个原网址对应多个短网址的现象(虽然不影响应用体验)。为提高给号的并发性能,可以针对不同号段设置多个发号器并行发号。
    2019-02-07
    1
  • 与非
    最后一课在一年的最后一天结束,这也算辞旧迎新了吧~希望老师能在最后能出个课后思考题的总结~
    2019-02-04
    1
  • 想当上帝的司机
    用户自定义的,可以将用户的id拼接到hash前的网址上
    2019-02-04
    1
  • 曹昆
    期待所有思考题的标准答案
    2019-11-23
  • Csquare
    如果选用Murmurhash的32bit版本,用户量/数据量上去以后,哈希冲突是不是就会比较频繁?

    作者回复: 是的

    2019-10-26
  • 于林杰
    为什么是62

    作者回复: 文章里不是讲了吗

    2019-10-20
  • steve
    思考题2想了很久没想到好的办法,还请老师解答。
    看大家的方法貌似是把老的url批量删掉,那如果需求不允许失效老url是不是就没有办法了呢?

    作者回复: 分库分表存储啊,或者用一些大型key-value数据库

    2019-10-08
  • steve
    用布隆过滤器 插入新的短网址 布隆过滤器返回true 也不一定存在 那还是得查数据库?

    作者回复: 是true 确实不一定存在

    2019-09-25
收起评论
44
返回
顶部