这张图理论上是有保存过的，但找不到了

IEEE 802.3 以太网、局域网 IEEE 802.5 令牌环网 IEEE 802.11 无线局域网 应用层：数据包、报文 传输层：报文段 网络层：分组 数据链路层：帧 网络层：比特

参考 参考 一 走进多核编程 CPU 发展早期阶段，性能的提升主要来自于主频的提升和架构的优化，当这条优化途径出现瓶颈后，多核 CPU 开始流行起来。多核心同时执行任务极大地提高了系统整体性能，但也对硬件架构和软件编写提出了更大的挑战。各个核心都有自己的 Cache，以及不同层级的 Cache，彼此共享内存。一个典型的多核 CUP 架构如下图所示： 利用多核心的优势在各个核之间互相配合完成任务，如何进行各个核心间的数据同步（各个核心所属 L1 Cache/L2 Cache 数据的同步）是问题的关键所在。虽然发展出多种数据同步方式，以及流水线乱序执行的模式，但数据在各个核之间的一致性和可见性并不是那么理想；再加上编译器也会做优化，最终导致各个核的指令执行顺序和各个变量值的可见性变得不确定。 这种现象可以通称为重排，即原本应该有全序的内存读写操作被打乱。不过无论产生什么样的重排，都会保证对于单线程内部的执行结果不会有任何区别。下面是一个简单例子： 对于 Thread 1 内部，p 和 ready 没有关联，完全可以被重排而不影响正确性，而 Thread 2 依赖 ready 做标识位，一旦重排，Thread 2 在看到 ready 为 true 的时候 p 都可能没有 init，显然这是有问题的。 二 多核编程中临界区保护 利用多线程做并发的任务中通常都会有公共的临界区，比如最常用的一种数据结构：并发队列，生产者和消费者需要访问队列的公共内存进行写入和读取。目前对于临界区的保护方式通常可以分为三个级别：互斥、Lock-free 和 Wait-free。 1、 互 斥 互斥，顾名思义每个线程访问临界区之前都需要获得互斥锁，如果被别的线程占用了就阻塞等待。当进入临界区的线程发生阻塞，或被操作系统换出时，会出现全局阻塞，因为获得锁的线程被换出无法执行操作，而未获得锁的线程也只能一同等待，出现了阻塞传播。如果另一个线程先进入临界区，有可能反而可以更快的顺利完成。因为存在全局阻塞的可能性，采用互斥技术进行临界区保护的算法有着最低的阻塞容忍能力。 2、 Lock-free Lock-free 允许单个线程阻塞，但是会保证系统整体层面上的吞吐。如果当程序线程运行足够长时间的情况下，至少有一个线程取得了进展，那么就可以说这个算法是 Lock-free 的。如果一个线程被挂起，那么 Lock-free […]

数电也是需要了解的部分，24年开始抽点时间吧 （1）与门 与门（英语：AND gate）又称“与电路”、逻辑“积”、逻辑“与”电路。是执行“与”运算的基本逻辑门电路。有多个输入端，一个输出端。当所有的输入同时为高电平（逻辑1）时，输出才为高电平，否则输出为低电平（逻辑0）。 逻辑表达式: F=AB. （2）或门 或门（OR gate），又称或电路、逻辑和电路。如果几个条件中，只要有一个条件得到满足，某事件就会发生，这种关系叫做“或”逻辑关系。具有“或”逻辑关系的电路叫做或门。或门有多个输入端，一个输出端，只要输入中有一个为高电平时（逻辑“1”），输出就为高电平（逻辑“1”）；只有当所有的输入全为低电平（逻辑“0”）时，输出才为低电平（逻辑“0”）。 逻辑表达式:F= A+B. （3）非门 非门（英文：NOT gate）又称非电路、反相器、倒相器、逻辑否定电路，简称非门，，是逻辑电路的基本单元。非门有一个输入和一个输出端。当其输入端为高电平（逻辑1）时输出端为低电平（逻辑0），当其输入端为低电平时输出端为高电平。也就是说，输入端和输出端的电平状态总是反相的。非门的逻辑功能相当于逻辑代数中的非,电路功能相当于反相,这种运算亦称非运算。 逻辑表达式: （4）与非门 与非门（英语：NAND gate）是数字电路的一种基本逻辑电路。若当输入均为高电平（1），则输出为低电平（0）；若输入中至少有一个为低电平（0），则输出为高电平（1）。与非门可以看作是与门和非门的叠加。 逻辑表达式: （5）或非门 或非门（英语：NOR gate）是数字逻辑电路中的基本元件，实现逻辑或非功能。有多个输入端，1个输出端，多输入或非门可由2输入或非门和反相器构成。只有当两个输入A和B为低电平（逻辑0）时输出为高电平（逻辑1）。也可以理解为任意输入为高电平（逻辑1），输出为低电平（逻辑0）。 逻辑表达式: （6）异或门 异或门 （英语：Exclusive-OR gate，简称XOR gate，又称EOR gate、ExOR gate）是数字逻辑中实现逻辑异或的逻辑门。有多个输入端、1个输出端，多输入异或门可由2输入异或门构成。若两个输入的电平相异，则输出为高电平1；若两个输入的电平相同，则输出为低电平0。亦即，如果两个输入不同，则异或门输出高电平。 逻辑表达式: （7）同或门 同或门（英语：XNOR gate或equivalence gate）也称为异或非门，是数字逻辑电路的基本单元，有2个输入端、1个输出端。当2个输入端中有且只有一个是低电平（逻辑0）时，输出为低电平。亦即当输入电平相同时，输出为高电平（逻辑1）。 逻辑表达式: 下面这个图记一下，主要是1,2,3,4,5,7,8 与非门和或非门分别是由与门+非门；或门+非门组合而成，在数字电路中也很常见

转自 下面我们就来介绍一下关于寄存器的相关内容。我们知道，寄存器是 CPU 内部的构造，它主要用于信息的存储。除此之外，CPU 内部还有运算器，负责处理数据；控制器控制其他组件；外部总线连接 CPU 和各种部件，进行数据传输；内部总线负责 CPU 内部各种组件的数据处理。 那么对于我们所了解的汇编语言来说，我们的主要关注点就是 寄存器。 为什么会出现寄存器？因为我们知道，程序在内存中装载，由 CPU 来运行，CPU 的主要职责就是用来处理数据。那么这个过程势必涉及到从存储器中读取和写入数据，因为它涉及通过控制总线发送数据请求并进入存储器存储单元，通过同一通道获取数据，这个过程非常的繁琐并且会涉及到大量的内存占用，而且有一些常用的内存页存在，其实是没有必要的，因此出现了寄存器，存储在 CPU 内部。 认识寄存器 寄存器的官方叫法有很多，Wiki 上面的叫法是 Processing Register， 也可以称为CPU Register，计算机中经常有一个东西多种叫法的情况，反正你知道都说的是寄存器就可以了。 认识寄存器之前，我们首先先来看一下 CPU 内部的构造。 CPU 从逻辑上可以分为 3 个模块，分别是控制单元、运算单元和存储单元，这三部分由 CPU 内部总线连接起来。 几乎所有的冯·诺伊曼型计算机的 CPU，其工作都可以分为5个阶段：「取指令、指令译码、执行指令、访存取数、结果写回」。 计算机架构中的寄存器 寄存器是一块速度非常快的计算机内存，下面是现代计算机中具有存储功能的部件比对，可以看到，寄存器的速度是最快的，同时也是造价最高昂的。 我们以 intel 8086 处理器为例来进行探讨，8086 处理器是 x86 架构的前身。在 8086 后面又衍生出来了 8088 。 在 8086 CPU 中，地址总线达到 20 根，因此最大寻址能力是 2^20 […]

转自 一文为你讲解清楚： RAM、SRAM、DRAM、SDRAM、DDR SDRAM ROM、PROM、EPROM、EEPROM、NAND flash、NOR flash ROM和RAM指的都是半导体存储器。ROM是Read OnlyMemory的缩写，RAM是Random Access Memory的缩写。ROM在系统停止供电的时候仍然可以保持数据，而RAM通常都是在掉电之后就丢失数据，典型的RAM就是计算机的内存。 RAM RAM 有两大类。一种称为静态RAM（StaticRAM/SRAM），SRAM速度非常快，是目前读写最快的存储设备了，但是它也非常昂贵，所以只在要求很苛刻的地方使用，譬如CPU的一级缓冲，二级缓冲。另一种称为动态RAM（Dynamic RAM/DRAM），DRAM保留数据的时间很短，速度也比SRAM慢，不过它还是比任何的ROM都要快。 DRAM分为很多种，常见的主要有FPRAM/FastPage、EDORAM、SDRAM、DDR RAM、RDRAM、SGRAM以及WRAM等，这里介绍其中的一种DDRRAM。 DDR RAM（Double-Date-Rate RAM）也称作DDR SDRAM，这种改进型的RAM，和SDRAM是基本一样的，不同之处在于它可以在一个时钟读写两次数据，这样就使得数据传输速度加倍了。这是目前电脑中用得最多的内存，而且它有着成本优势。在很多高端的显卡上，也配备了高速DDR RAM来提高带宽，这可以大幅度提高3D加速卡的像素渲染能力。 ROM ROM：只读存储器的总称。 PROM：可编程只读存储器，只能写一次，写错了就得报废，现在用得很少了。 EPROM：可擦除可编程存储器，这东西也比较古老了，是EEPROM的前身，在芯片的上面有个窗口，通过紫外线的照射来擦除数据。非常麻烦。 EEPROM：电可擦除可编程只读存储器，比之EPROM就先进点了，可以用电来擦除里面的数据，也是现在用得比较多的存储器，比如24CXX系列的EEPROM。（现在用的最多，小型存储器） Flsah FLASH 存储器又称闪存，它结合了ROM和RAM的长处，不仅具备电子可擦除可编程（EEPROM）的性能，还不会断电丢失数据同时可以快速读取数据（NVRAM 的优势），U盘和MP3里用的就是这种存储器。在过去的20年里，嵌入式系统一直使用ROM（EPROM）作为它们的存储设备，然而近年来Flash全面代替了ROM（EPROM）在嵌入式系统中的地位，用作存储Bootloader以及操作系统或者程序代码或者直接当硬盘使用（U盘）。 目前Flash主要有两种 ,NOR Flash （小、贵）和 NADN Flash （大，便宜）。NAND FLASH和NOR FLASH 都是现在用得比较多的非易失性闪存(ROM)。 NOR Flash的读取和我们常见的SDRAM的读取是一样，用户可以直接运行装载在NOR FLASH里面的代码，这样可以减少SRAM的容量从而节约了成本。 NAND Flash没有采取内存的随机读取技术，它的读取是以一次读取一块的形式来进行的，通常是一次读取512个字节，采用这种技术的Flash比较廉价。用户不能直接运行NAND Flash上的代码，因此好多使用NAND Flash的开发板除了使用NAND Flah以外，还作上了一块小的NOR Flash来运行启动代码。 一般小容量的用NOR Flash，因为其读取速度快，多用来存储操作系统等重要信息，而大容量的用NAND FLASH，最常见的NAND FLASH应用是嵌入式系统采用的DOC（Disk On […]

前言：耗费了五个多小时，算是差不多了 红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下要求： 下图就是一个典型的红黑树： 但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。 优势和用途 我们知道二叉查找树在不停地添加或删除结点后，可能会导致结点情况如下： 这种情况下，二叉查找树的查找效率最坏会降低为 O(n)。 而红黑树由于在插入和删除结点时都会进行变色旋转等操作，在符合红黑树条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的红黑树高度至多为 2log(n+1)，查找效率最坏为 O(log(n))。 所以红黑树常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中 HashMap 的实现等，所以了解红黑树也很有意义。 下面介绍一下红黑树的等同 2-3-4树。 2-3-4树 2-3-4树是四阶的 B树(Balance Tree)，它的结构有以下限制： 下图是一个典型的 2-3-4树（来自维基百科）： 2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。 红黑树维持平衡的方式 对应红黑树 至于为什么说红黑树是 2-3-4树的一种等同呢，这是因为 2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同结点与红黑树子树的对应。 而上文中的 2-3-4树也可以转换成一棵红黑树： 由红黑树的性质5，和 2-3-4树的性质1，为了便于理解红黑树和 2-3-4树的对应关系，我们可以把红黑树从根结点到叶子结点的黑色结点个数定义为高度。 红黑树和 2-3-4树的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除结点时尽量通过子树内部调整来达到平衡，2-3-4树实现平衡是通过结点的旋转和结点元素数变化，红黑树是通过结点旋转和变色。 下面来对照着 2-3-4树说一下红黑树结点的添加和删除： 结点插入 2-3-4树中结点添加需要遵守以下规则： 而将这些规则对应到红黑树里，就是： 如上图所示，虽然向红黑树中插入了一个新结点，但由于旋转和变色，子树的高度保持不变。 删除结点 红黑树的删除要比插入要复杂一些，我们还是类比 2-3-4树来讲： 将这些规则对应到红黑树中即： […]

基本概念 字典树是一种有序的树状结构，每个节点表示字符与字符串。字典树可以合并储存有相同前缀的字符串。常用于解决前缀匹配和字串查找的问题。是一种牺牲空间换取时间的做法。 插入 字串长度的时间 插入一个新单词 查找 单词长度的时间 查找是否存在某单词 查找是否存在某前缀 实现 通过HashMap实现子节点 class TrieNode {    String word;    HashMap<Character, TrieNode> next;​    public TrieNode() {        next = new HashMap<>();   }}​class TrieTree {    public TrieNode root;​    public TrieTree(TrieNode root) {        this.root = root;   }​    public […]

代码：包含初始化、合并（包含按秩优化）、查询（包含路径压缩）、校验是否为同一集合

转自某论坛 （i）邻接矩阵表示法，如图： 矩阵中，行和列 与图中的节点对应 　　也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。 　　同样，对于网络中的权，也可以用类似邻接矩阵的 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。 （ii）关联矩阵表示法 　　也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 -1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个 1，一个-1）可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有mn 个元素中，只有 2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 　　同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。 （iii）弧表示法 例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如上： 为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。 （iv）邻接表表示法 　　邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为 最后的0应该表示结尾。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n 出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。 例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下： 《星形表示法详解及其转化算法》 注意：上面的第一张表实际上有个错误，仔细看的童鞋应该能发现，起始地址point(i) : 1 , 3 , 4 , 5 , 7 , 9 ,那个6应该是5（这里待核实） 通常情况下会设置一个st[i] 数组，和STL类似， [st[i],st[i+1]) 恰好为以结点i开头的边下标。对应于上个例子的第一张表，则该数组为： st[6]={1,3,4,5,7,9}; 还会有一个数组对应于第二张表，主要使用第三行数据， v[8]={2,3,4,2,3,5,3,4}; 下面的程序把树的前向星表示转化成左儿子-右兄弟表示，以方便后续算法实现。 图最常用的表示法是邻接矩阵和邻接表。对于静态图（建图完毕后不再修改图的结构）往往用前向星来代替邻接表，节省空间和时间。 邻接矩阵不管输入格式如何，总是很容易得到邻接矩阵，只需要注意平行边的情况。前向星邻接矩阵本身就包含了顶点序，因此很容易转化为前向星： 把邻接矩阵转换为前向星表示法： 把边列表转化成前向星的方法类似，只需要把第一顶点相同的结点串成链表，用计数器法进行结点编号分配，和前向星转化成左儿子-右兄弟一样每次插入到链表首部，在O(m)时间内可以建立前向星表示。当然，也可以按第一顶点为关键字直接进行快速排序，不过速度稍微慢一些