8.2 常见数据结构与 Hash 表原理分析



1.时间复杂度VS空间复杂度

• 时间复杂度：     并不是指程度具体运行的时间，而是算法执行语句的次数。

                                    1.O(2^N)表示对N数据处理需要进行2^N次计算

                                    2.O(1),O(log(n)),O(n^a) 多项式时间复杂度

                                    3.O(a^n),O(n!)非多项式的时间复杂度。

• 空间复杂度：     一个算法在运行过程中，临时占用存储空间大小的量度。

                                    O(n)表示需要临时存储n个数据。



2.数组

      数组特点： 内存空间连续。相同数据类型。随机访问速度最快（根据下标索引访问数据），时间复杂度为O(1),

      数据元素相同，逻辑相同。核心诉求：数据元素长度一样--相同数据类型，数据长度一样===>目的：快速随机访问。

      不需要变量数组，只要计算出下标，快速访问数据。

      缺点：彻底删除数据，需要移动后面的所有数据。

3.链表

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

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

       要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(N) 

      优点：增加，删除数据访问速度很高。复杂度O(1)

        链表增删数据要比数组性能好很多。

        如何实现：快速查找，快速增删？

        分析：数组--快速查找；链表--快速增删。结合二者优点。整合两种数据结构，获取两种特性。

4.数组+链表

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



4.Hash表

     数组要求数据元素长度一致。字符串没有办法保持数据长度一致。==>不能将数据直接保存在数组中。数组中保存指针执行数据元素。

5.Hash冲突

      Hash攻击。Hash表蜕化成链表。内存被这个链表消耗完。

6.栈

        数组，链表被称为线性表。

        栈=线性表+操作权限限制=后添加的数据，在删除的时候必须先删除（后进先出）。（货栈）

        线程运行时专有内存为什么被称为线程栈？

7.线程调用栈

       void f(){

                     int x=g(1);

                     x++;//g函数返回，当前堆栈顶部为f函数栈帧，在当前栈帧继续执行f函数的代码

        }

        int g(int x){ return x+1;}



8.队列

       队列：操作受限制-----先进先出。

       典型应用场景：生产者消费者；阻塞等待的线程被放入队列。



     用队列搜索好友总关系最近的有钱人。

     解析：自己先进队列。出队时，检查好友，好友进队列。



     队列搜索最短路径：

   1.A先进入队列

   2.A出队列，检查A是否为结束点，同时记录前一个节点，同时将A的邻居节点CD进入队列

   3.C出队，将C的邻居节点BF进入队列。