架构师训练营 4 期 第 8 周

作业一（至少完成一项）：

链表合并

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。 请用代码（或伪代码）描述算法，并给出时间复杂度。

可以使用双指针求解：

1. 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)

2. 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if (headA == null || headB == null) return null;        ListNode pA = headA；        ListNode pB = headB;        while (pA != pB) {            pA = (pA == null ? headB : pA.next);            pB = (pB == null ? headA : pB.next);        }        return pA;    }}

HDFS 的处理过程时序图。

请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

作业二：根据当周学习情况，完成一篇学习总结

本周主要讲解了数据存储、算法与数据结构，还有 IO 相关知识。

文件与硬盘 IO

机械硬盘 vs 固态硬盘

固态硬盘读写速度快、抗震效果好、单位容量价格高； 机械硬盘读写速度相对较慢、抗震性差，单位容量价格低。

数据存储速度： 普通机械硬盘读写速度在几十到一百多 MB/s，固态硬盘则可以去到一千到两千 MB/s 的水平，读写速度上固态硬盘更占优势； 防震抗摔性：传统的机械硬盘内部有高速运转的磁头，其抗震能力很差，因此一般的机械硬盘电如果是在运动中或者震动中使用，很容易损坏硬盘。而机械硬盘采用芯片存储方案，内部无磁头，具备超强的抗震能力，即便是在运动或者震动中使用，也不容易损坏。 价格：固态硬盘单位容量价格较机械硬盘更高，目前市场价格普通的固体硬盘 1GB≈1 元，还是非常实惠的

B+树 vs LSM 树

传统的机械硬盘顺序读写性能较好，随即读写性能较差，所以在使用传统机械硬盘的时候，选择合适的算法与存储结构对于读写性能有很大的影响。 如果事先对数据进行排序，就能很好的利用这一特点，所以数据库或文件系统会使用类似于 B+树 的算法和数据结构对数据进行存储，保证数据的有序性。

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。 百度百科

不过使用 B+树读取数据需要多次读取才能找到，对性能可能有影响

LSM 树的原理：将对数据的修改增量保存在内存中，达到指定大小限制之后批量把数据 flush 到磁盘中，磁盘中树定期可以做 merge 操作，合并成一棵大树，以优化读性能。不过读取的时候稍微麻烦一些，读取时看这些数据在内存中，如果未能命中内存，则需要访问较多的磁盘文件。极端的说，基于 LSM 树实现的 hbase 写性能比 mysql 高了一个数量级，读性能却低了一个数量级。

LSM 树原理把一颗大叔拆分成 N 颗小树，它首先在内存中，它首先写入内存中，随着小树越来越大，内存中的小树会 flush 到磁盘中，磁盘中的树定期可以做 merge 操作，合并成为一个大叔，用来优化读性能。

RAID vs HDFS

RAID 磁盘阵列 由独立磁盘构成的具有冗余能力的阵列的意思。有很多价格较合理的磁盘，组成一个容量巨大的磁盘组，利用个别磁盘提供数据所产生加成效果提升整个磁盘系统的效能陈 RAID 技术。 HDFSHadoop 分布式文件系统。HDFS 有着高容错性（fault-tolerant），并且设计用来不是在低廉的硬件上，而且它提供高吞吐量来访问应用程序的数据，非常的使用超大数据集（large data set）的应用程序。

1. raid 是针对单台服务器，目的是解决高性能的处理器和低性能的磁盘 io 的瓶颈问题。

2. hdfs 是针对服务器集群，目的是解决海量数据的分布式存储问题。

知识点：

1. NameNode 可以说是 HDFS 中的心脏，协调管控着所有 DataNode。通常 NameNode 和 DataNode 都分别部署在独立的物理机。只有一个 NameNode

2. 在执行读或写的过程中，NameNode 和 DataNode 通过 HeartBeat 进行保存通信，确定 DataNode 活着。如果发现 DataNode 死掉了，就将死掉的 DataNode 上的数据，放到其他节点去，读取时，读其他节点。

3. 每次写时 数据同时备份到其他的节点 。宕掉一个节点没关系，还有其他节点可以备份；甚至，宕掉某一个机架也没关系；其他机架上也有备份。

数据结构与算法

时间复杂度与空间复杂度

时间复杂度

• 并不是计算程序具体运行的时间，而是算法执行语句的次数。

• O(2^n) 表示对 n 数据处理需要进行 2^n 次计算

• 多项式时间复杂度

• 非多项式时间复杂度 空间复杂度

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

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

基础数据结构

1. 数组 创建数组必须要内存中一块连续的空间。数组中必须存放相同的数据类型。随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为 O(1)。

2. 链表可以使用零散的内存空间存储数据。所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

所有的数据结构底层存储使用的都是数组或链表实现的。

Hash 表

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。–百度百科

哈希表是使用 O(1)，O(1) 时间进行数据的插入删除和查找，但是哈希表不保证表中数据的有序性，这样在哈希表中查找最大数据或者最小数据的时间是 O(N)，O(N) 实现。

队列和栈

栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。

队列也是是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列可以在 BFS 和 DFS 算法中存储过程数据。