数据结构与算法之美
王争
前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
wahaha16进制应该是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
收起评论