数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

数据结构与算法开篇

发布于 2020-04-28 | 更新于 2024-05-16

本专栏我们来介绍一下编程中常见的一些数据结构。

为什么要学习数据结构?

随着业务场景越来越复杂,系统并发量越来也高,要处理的数据越来越多,特别是大型互联网的高并发、高性能、高可用系统,对技术要求越来越高,我们引入各种中间件,这些中间件底层涉及到的各种数据结构和算法,是其核心技术之一。如:

  • ElasticSearch中用于压缩倒排索引内存存储空间的FST,用于查询条件合并的SkipList,用于提高范围查找效率的BKDTree;
  • 各种分库分表技术的核心:hash算法;
  • Dubbo或者Nginx等的负载均衡算法;
  • MySQL索引中的B树、B+树等;
  • Redis使用跳跃表作为有序集合键的底层实现之一;
  • Zookeeper的节点树;
  • J.U.C并发包的各种实现的阻塞队列,AQS底层实现涉及到的链式等待队列;
  • JDK对HashMap的Hash冲突引入的优化数据结构红黑树…

可以发现,数据结构和算法真的是无处不在,作为一个热爱技术,拒绝粘贴复制的互联网工程师,怎么能不掌握这些核心技术呢?

image-20200428223005156

与此同时,如果你有耐心听8个小时通俗易懂的数据结构入门课,我强烈建议你看一下以下这个视频,来自Google一位工程师:Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer


阅读完本文,你将了解到一些常见的数据结构(或者温习,因为大部分朋友大学里面其实都是学过的)。在每个数据结构最后一小节都会列出代码实现,以及相关热门的算法题,该部分需要大家自己去探索与书写。只有自己能熟练的编写各种数据结构的代码才是真正的掌握了,大家别光看,动手写起来。阅读完本文,您将了解到:

  • 抽象数据类型与数据结构的关系;
  • 如何评估算法的复杂度;
  • 了解以下数据结构,并且掌握其实现思路:数组,链表,栈,队列,优先级队列,索引式优先队列,二叉树,二叉搜索树BST,平衡二叉搜搜书BBST,AVL树,HashTable,并查集,树状数组,后缀数组。
  • 文章里面不会贴这些数据结构的完整实现,但是会附带实现的链接,同时每种数据类型最后一节的相关实现以及练习题,建议大家多动手尝试编写这些练习题,以及尝试自己动手实现这些数据结构。

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/intro.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。