第八周 - 数据结构 + 算法，网络通信



知识大纲：

时间复杂度

空间复杂度

NP问题：P问题是多项式问题，N问题是

数组：查找快O(1)，插入、删除慢O(n)

链表：查找慢O(n)，插入、删除快O(1)

数组链表结合，实现快速查找和快速增删

Hash表，计算HashCode后对数组长度取模得到下标

Hash冲突处理：使用链表记录

线性表

栈（线程栈）：后进先出

线程调用栈，每个线程都有一个

队列：先进先出

树：

二叉树

二叉排序树

平衡二叉树

旋转恢复平衡二叉树

红黑树

B+树（索引）

跳表（Redis中使用了）

常用算法：

穷举算法

递归算法

贪心算法

改进贪心算法 迪杰斯特拉算法（最快路径）

动态规划

解决背包问题

遗传算法解决背包问题



数组：是一种在连续内存空间上存储相同类型数据的数据结构，可通过数组名和下标进行数据的访问和更新。数组的读写时间复杂度是O(1)

链表：是利用零散的内存空间存储数据的，每个数据节点都是由数据本身和下一个数据的地址指针组成，查询链表数据需要遍历链表，因此链表的读写数据的时间复杂度是O(n)。

Hash表：是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

栈：是一种基于线性表的数据结构，数据先入后出。

队列：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。先进先出。

树：最常见的就是二叉树，二叉树(Binary Tree)是一个有根树，并且每个节点最多只有2科子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树又分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

• 二叉树

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

• 二叉排序树

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

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

• 平衡二叉排序树

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

• 红黑树

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

• 跳跃表

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