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

常用数据结构

• 数组

需要一段需要连续的存储空间，数组的随机查询效率是 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，平衡二叉排序树的搜索性能很好，但平衡过程计算很差。

• 红黑树

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

• 跳跃表

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

常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划