学习链接：https://github.com/XPoet/js-data-structures-and-algorithms

JavaScript 数据结构与算法

1.数据结构(data structure)

数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系

是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法

2.解决问题方法的效率，根据数据的组织方式有关

3.常见的数据结构：数组，栈，链表，图，散列表，队列，树，堆

4.算法：一个有限指令集，每条指令的描述不依赖于语言，接收一些输入（有些情况下不需要输入），产生输出，一定在有限步骤之后终止

5.解决问题的方法/步骤逻辑

6.数据结构的实现，离不开算法

7.图书馆的书，先定类别，再二分查找

8.数组

几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。数组通常情况下用于存储一系列同一种数据类型的值。但在JavaScript里，数组中可以保存不同类型的值。但我们还是要遵守最佳实践，别这么做（大多数语言都没这个能力）

9.数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。但是有时候，我们未来实现某些功能，必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构

10.栈：栈(stack)是一种运算受限的线性表

LIFO(last in first out)表示后进先出

栈顶，栈底，进栈（入栈或压栈），出栈（退栈）

特点：先进后出，后进先出

11.递归：为什么没有停止条件的递归会造成栈溢出？比如函数A为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数A压入栈，最后造成栈溢出(Queue Overfloat)

12.peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）

isEmpty(),size()

13.队列(Queue)是一种运算受限的线性表，特点：先进先出 FIFO:first in first out

只允许在表的前端进行删除操作

例如排队，买票

14.优先级队列主要考虑的问题：

每个元素不再只是一个数据，还包含优先级

在添加元素过程中，根据优先级放入到正确位置

15.数组缺点：

数组的创建需要申请一段连续的内存空间（一整块内存），并且大小是固定的，当前数组不能满足容量需求时，需要扩容（一般情况下是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）

在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移

16.链表 例子火车

不同于数组，链表中的元素在内存中不必是连续的空间

链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言称为指针）组成

链表优点：

内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理

链表不必在创建时就确定大小，并且大小可以无限延伸下去

链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多

链表缺点：

访问任何一个位置的元素时，需要从头开始访问（无法跳过第一个元素访问任何一个元素）

无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素

虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的

17.集合比较常见的实现方式是哈希表

18.集合特点：

集合通常是由一组无序的、不能重复的元素构成

数学中常指的集合中的元素时可以重复的，但是计算机中集合的元素不能重复

集合是特殊的数组（没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份）

19.字典存储的是键值对，主要特点是一一对应

可以通过key取出value

在字典中key是不能重复且无序的，而value可以重复

20.字典和映射的关系

有些编程语言中称这种映射关系为字典，如Swift中的Dictonary,Python中的dict

有些编程语言中称这种映射关系为Map,比如Java中的HashMap和TreeMap等

21.哈希表的结构就是数组，但它神奇之处在于对下标值得一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取HashCode

例子：能把员工的姓名转换为它对应的工号，再根据工号查找该员工的信息

也就是说：哈希表最后还是基于数据来实现的，只不过哈希表能够通过哈希函数把字符串转化为对应的下标值，建立字符串和下标值得映射关系

22.编码系统

23.把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现，虽然取余操作得到的结构也有可能重复，但是可以通过其他方式解决

24.哈希化：将大数字转化为数组范围内下标的过程，称之为哈希化

哈希函数：通常会将单词转化为大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数

哈希表：对最终数据插入的数组进行整个结构的封装，得到的就是哈希表

25.地址的冲突

在实际中，经过哈希函数哈希化过后得到的下标值可能有重复，这种情况称为冲突，冲突是不可避免的，我们只能解决冲突

解决冲突常见的两种方案：链地址法（拉链法）和开放地址法

26.链地址法解决冲突的办法是每个数组单位中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）

27.开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项

根据探测空白单元格位置方式的不同，可分为三种方法：线性探测，二次探测，再哈希法

28.线性探测存在一个比较重要的问题，就是聚集（一连串填充单位），

聚集会影响哈希表的性能，无论是插入/查询/删除都会影响

二次探测法可以解决该问题

29.在开放地址法中寻找空白单元格的最好的解决方式为再哈希化

再哈希法的做法为：把关键字用另一个哈希函数，再做一次哈希化，用这次哈希化的结果作为该关键字的步长

30.第二次哈希化需要满足以下两点：

和第一个哈希函数不同，不然哈希化后的结果仍是原来位置

不能输出为0，否则每次探测都是原地踏步的死循环

31.装填因子

平均探测长度以及平均存取时间，取决于装填因子，随着装填因子变大，探测长度会越来越长

装填因子=总数据项/哈希表长度

开放地址法的装填因子最大为1，因为只有空白的单元才能放入元素

链地址法的装填因子可以大于1，因为只要愿意，拉链法可以无限延伸下去

32.哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法

33.性能高的哈希函数应具备以下两个优点：快速的计算，均匀的分布

34.总结：每种数据结构都有自己特定的应用场景

数组：

优点：可以通过下标值访问，效率高

缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作

链表：

优点：数据的插入和删除操作效率都很高

缺点：查找效率低，需要从头开始一次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高

哈希表：

优点：哈希表的插入/查询/删除效率都非常高

缺点：空间利用率不高，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是无序的，不能按照固定顺序便利哈希表中的元素；而且不能快速找出哈希表中最大值或最小值这些特殊值

树结构：

优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等

35.二叉树的概念

如果树中的每一个节点最多只能由两个子节点，这样的树就称为二叉树

36.二叉搜索树(BST,Binary Search Tree)，也称为二叉排序树和二叉查找树

特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中“搜索”的来源

37.以遍历根（父）节点的顺序来区分三种遍历方式。比如：先序遍历先遍历根节点，中序遍历第二遍历根节点。后续遍历最后遍历根节点

38.平衡树

39.在计算机程序设计中，图也是一种非常常见的数据结构，图论其实是一个非常大的话题，在数学上起源于尼斯堡七桥问题

40.在数学的概念上，树是图的一种

41.图通常有什么特点呢？

一组定点：通常用V(Vertex)表示顶点的集合

一组边：通常用E(Edge)表示边的集合

边是顶点和顶点之间的连线

边可以是有向的，也可以是无向的 A ----B A---->B

42.图的术语：顶点，边，相邻顶点，度，路径，无向图，有向图，无权图，带权图

43.图的表示：

邻接矩阵： A B

A 0 1

邻接表： A | B C D

44.图的遍历思想 图的遍历算法的思想在于必须访问每个第一次访问的节点，并且追踪有哪些顶点还没有被访问到

广度优先搜索(Breadth-First Search,简称BFS)

基于队列，入队列的顶点先被搜索

深度优先搜索(Depth-First Search,简称DFS)

基于栈，通过将顶点存入栈中，顶点是沿着路径被搜索的，存在新的相邻顶点就去访问