数据结构与算法JavaScript （不定时更新）

红太狼 2021-03-23 14:57 613阅读 0赞

*楼楼非计算机专业，但是对计算机也还算喜欢。个人理解若有偏差，欢迎各位批评指正！*

*对于数据结构和算法一直是我的薄弱环节，相信大多数前端工程师可能多少会有些这方面的弱点，加上数据结构和算法本来就有些枯燥，立下个flag，三天过后抛之脑后的也时有发生，好了，收起老妈子的叨叨叨，毕竟楼楼还是个美少女，哈哈哈~*

在JS中，我所知的稍微复杂点的数据结构有数组和对象。

但是统观大多数语言，就会发现自己知道的太少了，当然以下涉及到的我们可能会用的很少。但是个人认为这些是思想上的沉淀，所发生的的变化带给自己的影响也将会是潜移默化的，就当是润物细无声了，哈哈哈~

楼楼借鉴了数据结构与算法JavaScript描述一书，在写这篇帖子时~

==开始----------------------------------------------------------------------------------------------==

#### 关于那些定义： ####

##### 数组： #####

*一个存储元素的线性集合（collection），元素可以通过索引来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。*

###### 数组的那些方法（js） ######

es6新增
    Array.from()//伪数组转数组  不支持的话我们还可以通过call和apply改变this指向，从而达到伪数组调用数组的方法
    Array.of() //将一组值，转换为数组
    Array.prototype.copyWithin(target, start = 0, end = this.length) //指定位置的成员复制到其他位置（会覆盖原有成员），然后返回当前数组。也就是说，使用这个方法，会修改当前数组。
        target（必需）：从该位置开始替换数据。如果为负值，表示倒数。
        start（可选）：从该位置开始读取数据，默认为 0。如果为负值，表示倒数。
        end（可选）：到该位置前停止读取数据，默认等于数组长度。如果为负值，表示倒数。
    Array.find(item => item > 0) 找到数组中符合条件的元素返回，如果没有符合条件的元素返回undefine
    Array.findIndex(item => item > 0) 返回第一个符合条件的数组成员的位置，如果所有成员都不符合条件，则返回-1。
    Array.fill() //使用一个值来填充数组
    entries()【对键值】 keys()【对键】 values()【对值】 用于遍历数组。他们都返回一个遍历器对象。
    Array.includes() 这个方法必须力推，返回布尔值，表示某个数组是否包含特定的值，与字符串includes方法类似
        
    另外还有这些，就不一一赘述了
    join()  push()和pop() shift() 和 unshift() sort()  reverse()  concat()  slice()
    splice()  indexOf()和 lastIndexOf() （ES5新增） forEach() （ES5新增）  map() （ES5新增）
    filter() （ES5新增）  every() （ES5新增）  some() （ES5新增） reduce()和 reduceRight() （ES5新增）

###### 数组中较为复杂的应为二维和多维数组。 ######

JavaScript 只支持一维数组，但是通过在数组里保存数组元素的方式，可以轻松创建多维数组。

##### 列表 #####

*列表是一组有序的数据。每个列表中的数据项称为元素。在 JavaScript 中，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有事先限定，实际使用时元素的数量受到程序内存的限制。列表有前有后（分别对应 front 和 end）。*

##### 栈 #####

*栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。入栈使用 push() 方法，出栈使用 pop() 方法。*

##### 队列 #####

*队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。*

##### 链表 #####

==背景：在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。然而JavaScript 的数组并不存在上述问题，因为使用 split() 方法不需要再访问数组中的其他元素了。==  
*链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。*

我们常说的链表是单向链表  
![图片描述][3102882719-5a7c0df2ce534_articlex]

双向链表示意图：  
![图片描述][3651923655-5a7c0dffe3625_articlex]

循环链表示意图  
![图片描述][3621945894-5a7c0e0a4cc8d_articlex]

通过这三个图片希望你对链表有初步认知。

##### 字典 #####

*字典是一种以键 - 值对形式存储数据的数据结构，一般大家谈到字典会说到电话簿，我觉得在JS里他更像是Object类，一个键对应一个值。但是很多教材中会说，Dictionay 类的基础是 Array 类，而不是 Object 类。OK，That's OK! 毕竟JavaScript中万物皆对象。*

##### 散列 #####

*散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用。散列使用的数据结构叫做散列表。在散列表上插入删除和取用数据都非常快，但是对于查找操作来说却效率低下，比如查找一组数据中的最大值和最小值。这些操作得求助于其他数据结构，二叉查找树就是一个很好的选择。*

*即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为碰撞（collision）*

==hashTable的实现就是典型的基于散列的一种数据结构，在这里有兴趣的话还可以去看一下霍纳算法==

当散列函数对于多个输入产生同样的输出时，就产生了碰撞。

碰撞的解决方法：开链法和线性探测法

*开链法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术，即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位置不一样罢了。*

*线性探测法隶属于一种更一般化的散列技术：开放寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存储数据。*

##### 集合 #####

*集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现一次。*

• 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。  
• 如果两个集合的成员完全相同，则称两个集合相等。  
• 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。

###### 对集合的基本操作有下面几种。 ######

• 并集  
将两个集合中的成员进行合并，得到一个新集合。  
• 交集  
两个集合中共同存在的成员组成一个新的集合。  
• 补集  
属于一个集合而不属于另一个集合的成员组成的

##### 树： #####

*树是一种非线性的数据结构，以分层的方式来存储数据。*

##### 树： #####

*树是一种非线性的数据结构，以分层的方式来存储数据。*  
其中树里面常被提起的应当是二叉树。提起二叉树补充一些，这是我一个朋友写的，感觉写的比较好。拿出来分享一下~  
表达顺序集比较合适的数据结构树。。。树最合适。为什么？

二叉搜索树天然可用于排序的二分查找，左子树小于根节点，右子树大于根节点，树的高度即为最大搜索次数，是很小的常数。
二叉搜索树 改进为 二叉平衡搜索树
二叉搜索树有什么劣势？树的构建受数据集合的顺序影响，极端情况下，蜕化为单项链表，失去二叉树的意义，检索复杂度退化到顺序遍历。
因此二叉搜索树需要平衡，即左右子树高度要相近。
二叉平衡搜索树 改进为 B树
搜索复杂度为 log2 (n)，要想进一步降低搜索次数即树高度，怎么办？增大对数的底，底越大，对数值越小。
因此改进为 m 阶树，并对非根节点的key个数进行约定(m/2 ~ m)，成为B树。
B树 改进为 B+树
B树的劣势：B树每个节点包含数据记录本身或指针，内存空间占用大，反复换页导致访存低效；典型业务场景查询的都是一段范围的数据记录，不仅仅是单条，B树比较慢。
改进措施：树的非叶子节点不包含数据记录，叶子节点包含数据记录的指针（聚集索引的key），整体减小索引树占用的内存，提高访存效率；所有数据记录被叶子节点覆盖，叶子节点天然是有序的，以单项链表连接，很方便遍历一段范围的记录。
改进后即为 B+ 树。mariadb-10.3使用的即为B+树。
B+树 改进为 B*树
B+树的劣势：每个非叶子节点可能只包含 m/2 个key，有一半空闲，内存使用率低。
改进措施：将非叶子节点的最小key数增加为 2m/3，提高内存使用率。付出的代价是需要对非叶子节点增加指向兄弟的指针，以便于节点拆分、合并。
改进后即为 B* 树。
基于B+树的一些推论
select * from xxx offset N limit M，不用特别在意N对效率的影响。如果N可能很大，例如过万，区分维护冷、热数据，确保N不会太大。
select * from xxx order by a order by b，联合索引受索引树的影响，天然要求左匹配原则，能利用到联合索引时查找效率很高。
主键用 uuid 还是 int 更好？innobase数据引擎下单调增长的 int 更好。uuid 32字节，用于索引必然比 int 4字节大，索引树占用的内存越大访存效率越低，所以 uuid 差；innobase的文件物理存储结构内涵为主键索引（聚集索引），单调递增的主键确保在连续的disk page 上不断 append 数据，访存效率高，而uuid导致新增数据随机插入disk page，需要大量移动数据，访存效率低。总体上看uuid较差。当然id本身也存在生成时的锁竞争等问题。

对于树结构有兴趣的可以再深入探讨，因为这块确实水比较深

##### 图和图算法 #####

图由边的集合及顶点的集合组成。

[3102882719-5a7c0df2ce534_articlex]: /images/20210323/1616511400421.png
[3651923655-5a7c0dffe3625_articlex]: /images/20210323/1616511374286.png
[3621945894-5a7c0e0a4cc8d_articlex]: /images/20210323/1616511352642.png