架构师训练营第八周课后总结

用户头像
Cloud.
关注
发布于: 7 小时前

常用数据结构

  • 数组

需要一段需要连续的存储空间,数组的随机查询效率是O(1),随机插入是O(n)

  • 链表

链表不需要连续空间,链表中的节点会记录下一个节点的指针,链表的插入删除效率都很高,随机访问效率很低。

  • Hash表

hash表是一种key_value的数据结构,根据key值hash后找到对应位置存储,hash表的随机存储和更新效率都很低,是O(1),但因为散列的特性,hash表不具备有序性。

栈是一种基于线性表的数据结构,他要求是数据先入后出,jvm的线程栈就是一种栈结构,在java

中执行方法A,在A方法里面调用了B,B方法又调用了C,那么栈结构的记录就是A最先入栈,然后B入栈,然后C入栈,然后C出栈,B出栈,A出栈。

  • 队列

队列和栈差不多,区别是栈是后进先出,队列是先进先出,平常我们的使用的消息中间件,线程池队列,锁队列都是先进先出的队列。

树定义是从根节点开始,每个根节点最一个或者多个子节点,子节点同样有一个或者多个子节点,以此类推。

  • 二叉树

二叉树和树的区别树节点的子节点只有两个,一个左节点,一个右节点。

  • 二叉排序树

二叉排序树要求节点的左节点总是小于父节点,右节点总大于父节点。

二叉排序树在最差情况会退化为链表。

  • 平衡二叉排序树

平衡二叉树在二叉排序树上进行优化,平衡二叉排序树丛任意节点开始出发,左右子树的深度想差不会超过1,平衡二叉排序树的搜索性能很好,但平衡过程计算很差。

  • 红黑树

红黑树在平衡二叉树上继续进行了优化,红黑树保证的要求是大体平衡,而不是完全平衡,在搜索性能和插入添加性能上都比较均衡。红黑树的实现非常复杂。

  • 跳跃表

由于红黑树实现非常复杂,所以延伸出了跳表,跳表是从有序链表上不断提取部分节点出来组成一个新链表,然后根据新链表再次提取部分节点形成链表,多次以后,最后顶层的链表应该只有两个节点,本质上也是一个二分查找法,这个查询效率和红黑树差不多,但是使用了额外的一倍的空间,所以只要空间允许,跳跃表是一种简单有效的数据结构。



常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

用户头像

Cloud.

关注

还未添加个人签名 2020.05.14 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第八周课后总结