【架构师训练营】第八期笔记

用户头像
云064
关注
发布于: 2020 年 07 月 29 日

数据结构与算法



数组

  • 数组是内存中一块连续的空间

  • 数组中的元素必须是相同的数据类型

  • 数组可以随机快速读写,根据下表访问数据时间复杂度为O(1)



链表

  • 链表可以用零散的内存空间存储数据

  • 链表中每个元素都必须包含指向下一个数据元素的内存地址指针

  • 访问链表元素需要遍历链表,时间复杂度为O(n)



哈希表

  • 通过计算哈希值获取哈希表中的下标,访问数据为数组访问,时间复杂度为O(1)

  • 可能会出现哈希值冲突的情况,此时通过链表的方式来解决key冲突问题



  • 后进先出的线性表



队列

  • 先进先出的线性表





二叉排序树

  • 左子树所有节点的值小于等于它的根节点值

  • 右子树所有节点的值大于等于它的根节点值

  • 左、右子树也分别为二叉排序树



跳表



常用算法:

  • 穷举算法

  • 递归算法(快速排序)

  • 贪心算法(迪杰斯特拉算法)

  • 动态规划



网络通信



Web请求一次网络通信历程



OSI七层模型和TCP/IP四层模型



数据包格式



系统IO复用方式: select, poll, epoll



用户头像

云064

关注

还未添加个人签名 2018.05.24 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营】第八期笔记