数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

布隆过滤器
添加B+树索引
特殊字符处理
存储对应关系
实现高性能的ID生成器
处理相同原始网址对应不同短网址问题
转化为62进制表示
维护ID自增生成器
优化性能
解决哈希冲突问题
转化为62进制表示
生成32位哈希值
MurmurHash算法
处理数据库存储压力
用户自定义短网址功能
ID生成器生成短网址
哈希算法生成短网址
短网址服务

该思维导图由 AI 生成,仅供参考

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

短网址服务整体介绍

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

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

我们前面学过哈希算法。哈希算法可以将一个不管多长的字符串,转化成一个长度固定的哈希值。我们可以利用哈希算法,来生成短网址。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文介绍了如何用数据结构和算法实现短网址系统的核心功能和实现原理。首先介绍了利用哈希算法生成短网址的方法,包括使用MurmurHash算法和将哈希值转化为更高进制的方法来缩短短网址长度,并讨论了解决哈希冲突问题的方法。然后讲解了如何优化哈希算法生成短网址的性能,包括通过数据库索引和布隆过滤器减少SQL语句执行次数。另外,还介绍了通过ID生成器生成短网址的方法,以及处理相同原始网址对应不同短网址和实现高性能ID生成器的思路。总结了两种实现方法的特点和优劣势,并提出了课后思考问题,引发读者思考。整体来说,本文内容涵盖了短网址系统的实现原理和优化方法,对读者快速了解短网址系统的实现具有指导意义。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(95)

  • 最新
  • 精选
  • 蚂蚁内推+v
    王老师短网址有什么作用吗? 我上网查了下理由不能说服我? 可能网上说得比较浅显,王老师方便指导下吗?

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

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

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

    2019-10-08
    2
    11
  • 实验室清洁工
    应该是16进制吧,62进制???

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

    2019-02-13
    3
    7
  • Csquare
    如果选用Murmurhash的32bit版本,用户量/数据量上去以后,哈希冲突是不是就会比较频繁?

    作者回复: 是的

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

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

    2019-10-20
    2
  • 刘強
    哈哈 2019年4月12日晚上2点 终于把专栏刷完了。开始跟着学发现不到一半,就跟不上节奏了,又从头开始看。开始时间这么长了,估计留言都没人看了,但还是留个言。看到有个兄弟昨天也留言了,还好没有放弃,虽然慢,但是跟上来了。 虽然学完了,但我感觉学算法和懂算法之间的鸿沟还是相当难跨越的。我们可能学完后遇到相应的问题可以用相应的算法解决,但是我们还是没法明白为什么这样做就可以。我们为什么想不到?这些算法只是科学家,天才灵光一现才能发明出来?有没有更本质的东西在后面?学的越来,发现自己越渺小,什么也不懂了。

    作者回复: 兄弟 对自己要求太高了

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

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

    2019-09-25
  • 森林
    课程终于输完了,问问小争哥画图软件是?

    作者回复: ipad paper

    2019-04-25
  • Smallfly
    随着新年的到来,我们的算法专栏也到了尾声。有点怀念那段时间工作不忙,一天能有好几个小时,阅读和思考算法专栏。 专栏给我带来的收获不仅仅是数据结构和算法的知识。在这之前虽然也每天学习,但总是东一块西一块,没有系统和脉络,一段时间之后,看似学了很多,但并没有什么效果。 在学习算法课程的过程中,基本都在学习和思考专栏的内容。一般第一天过一遍概念,一边阅读一边手敲。第二天会把重点放在思考上,为什么需要这种数据结构和算法,它的利弊是什么,以及解答思考题。 真正有收获的是思考和实践而不是阅读,阅读只是表象;如果只是阅读,也没有生字,会很轻松,但效果甚微。 这让我切身体会到系统和专注的重要性。 这种经历帮助我在实际工作中解决不少问题,不是说用到了哪种算法,而是在遇到问题时善于花时间去思考解决方案,而不是一味地寻找替代方案,把问题绕过去。 紧跟着老师的脚步学下来了,不能说都掌握了,但有几点学习的心得想跟大家分享。 1、迈出第一步。很多事情不是我们不会做,而是不想开始。一想到前面可能会有重重困难,思想上就先败下阵来了。只要开始一点点的弄懂,重在培养兴趣。 2、慢一点,不贪多。可能有同学落下很多课,看看还有这么多没学,干脆就放弃了。其实并不需要掌握所有的,可以挑选自己感兴趣的内容,细嚼慢咽,先掌握一部分。再从已知探索未知,其实文章之间很多是有关联的,学习过程中可能自个儿就串起来了。 3、多动手。阅读和思考还是远远不够的,带着文章的思路,用自己熟悉的语言实现一遍,跑起来测一测,会更有成就感,也是自己学习的痕迹。 虽然专栏学完了,然而有些内容很快就会忘记,后面我还会偶尔拿出来读一读,回顾一下思路。我现在已经欣然接受,学习的东西很快会遗忘,但回顾的时候会迅速地想起来,印象也更深刻了。 最后,祝王争老师和编辑小姐姐新年快乐,辛苦了。(´▽`ʃ♡ƪ)
    2019-02-04
    5
    176
  • 以前觉得数据结构和算法很难,学了之后,确实也难,但通过系统学习,心中有了一张完整的地图,以后只要不断反复看,反复学习,反复练习,一定能真正融合贯通。 另外,最大的感受是学了数据结构和算法后,看其它中间件和框架的源代码,发现大部分底层就是数据结构和算法。感觉练了九阳神功一样,学习其它功夫快了很多
    2019-02-04
    3
    42
收起评论
显示
设置
留言
95
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部