一、硬核知识之CPU

CPU是什么

CPU 的全称是 Central Processing Unit，它是你的电脑中最硬核的组件，这种说法一点不为过。CPU 是能够让你的计算机叫计算机的核心组件，但是它却不能代表你的电脑，CPU 与计算机的关系就相当于大脑和人的关系。它是一种小型的计算机芯片，它嵌入在台式机、笔记本电脑或者平板电脑的主板上。通过在单个计算机芯片上放置数十亿个微型晶体管来构建 CPU。 这些晶体管使它能够执行运行存储在系统内存中的程序所需的计算，也就是说 CPU 决定了你电脑的计算能力。

CPU 实际做什么

CPU 的核心是从程序或应用程序获取指令并执行计算。此过程可以分为三个关键阶段：提取，解码和执行。CPU从系统的 RAM 中提取指令，然后解码该指令的实际内容，然后再由 CPU 的相关部分执行该指令。

RAM : 随机存取存储器（英语：Random Access Memory，缩写：RAM），也叫主存，是与 CPU 直接交换数据的内部存储器。它可以随时读写（刷新时除外），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储介质

CPU 的内部结构

说了这么多 CPU 的重要性，那么 CPU 的内部结构是什么呢？又是由什么组成的呢？下图展示了一般程序的运行流程（以 C 语言为例），可以说了解程序的运行流程是掌握程序运行机制的基础和前提。

在这个流程中，CPU 负责的就是解释和运行最终转换成机器语言的内容。

CPU 主要由两部分构成：控制单元 和 算术逻辑单元（ALU）

控制单元：从内存中提取指令并解码执行算数逻辑单元（ALU）：处理算数和逻辑运算

CPU 是计算机的心脏和大脑，它和内存都是由许多晶体管组成的电子部件。它接收数据输入，执行指令并处理信息。它与输入/输出（I / O）设备进行通信，这些设备向 CPU 发送数据和从 CPU 接收数据。

从功能来看，CPU 的内部由寄存器、控制器、运算器和时钟四部分组成，各部分之间通过电信号连通。

寄存器是中央处理器内的组成部分。它们可以用来暂存指令、数据和地址。可以将其看作是内存的一种。根据种类的不同，一个 CPU 内部会有 20 - 100个寄存器。控制器负责把内存上的指令、数据读入寄存器，并根据指令的结果控制计算机运算器负责运算从内存中读入寄存器的数据时钟 负责发出 CPU 开始计时的时钟信号

接下来简单解释一下内存，为什么说 CPU 需要讲一下内存呢，因为内存是与 CPU 进行沟通的桥梁。计算机所有程序的运行都是在内存中运行的，内存又被称为主存，其作用是存放 CPU 中的运算数据，以及与硬盘等外部存储设备交换的数据。只要计算机在运行中，CPU 就会把需要运算的数据调到主存中进行运算，当运算完成后CPU再将结果传送出来，主存的运行也决定了计算机的稳定运行。

主存通过控制芯片与 CPU 进行相连，由可读写的元素构成，每个字节（1 byte = 8 bits）都带有一个地址编号，注意是一个字节，而不是一个位。CPU 通过地址从主存中读取数据和指令，也可以根据地址写入数据。注意一点：当计算机关机时，内存中的指令和数据也会被清除。

CPU 是寄存器的集合体

在 CPU 的四个结构中，我们程序员只需要了解寄存器就可以了，其余三个不用过多关注，为什么这么说？因为程序是把寄存器作为对象来描述的。

说到寄存器，就不得不说到汇编语言，我大学是学信息管理与信息系统的，我就没有学过汇编这门课（就算有这门课也不会好好学hhhh），出来混总是要还的，要想作为一个硬核程序员，不能不了解这些概念。说到汇编语言，就不得不说到高级语言，说到高级语言就不得不牵扯出语言这个概念。

计算机语言

我们生而为人最明显的一个特征是我们能通过讲话来实现彼此的交流，但是计算机听不懂你说的话，你要想和他交流必须按照计算机指令来交换，这就涉及到语言的问题，计算机是由二进制构成的，它只能听的懂二进制也就是机器语言，但是普通人是无法看懂机器语言的，这个时候就需要一种电脑既能识别，人又能理解的语言，最先出现的就是汇编语言。但是汇编语言晦涩难懂，所以又出现了像是 C，C++，Java 的这种高级语言。

所以计算机语言一般分为两种：低级语言（机器语言，汇编语言）和高级语言。使用高级语言编写的程序，经过编译转换成机器语言后才能运行，而汇编语言经过汇编器才能转换为机器语言。

汇编语言

首先来看一段用汇编语言表示的代码清单

mov eax, dword ptr [ebp-8]   /* 把数值从内存复制到 eax */add eax, dword ptr [ebp-0Ch] /* 把 eax 的数值和内存的数值相加 */mov dword ptr [ebp-4], eax /* 把 eax 的数值（上一步的结果）存储在内存中*/

这是采用汇编语言（assembly）编写程序的一部分。汇编语言采用 助记符(memonic) 来编写程序，每一个原本是电信号的机器语言指令会有一个与其对应的助记符，例如 mov,add 分别是数据的存储（move）和相加（addition）的简写。汇编语言和机器语言是一一对应的。这一点和高级语言有很大的不同，通常我们将汇编语言编写的程序转换为机器语言的过程称为 汇编；反之，机器语言转化为汇编语言的过程称为 反汇编。

汇编语言能够帮助你理解计算机做了什么工作，机器语言级别的程序是通过寄存器来处理的，上面代码中的 eax,ebp 都是表示的寄存器，是 CPU 内部寄存器的名称，所以可以说 CPU 是一系列寄存器的集合体。在内存中的存储通过地址编号来表示，而寄存器的种类则通过名字来区分。

不同类型的 CPU ，其内部寄存器的种类，数量以及寄存器存储的数值范围都是不同的。不过，根据功能的不同，可以将寄存器划分为下面这几类

种类功能累加寄存器存储运行的数据和运算后的数据。标志寄存器用于反应处理器的状态和运算结果的某些特征以及控制指令的执行。程序计数器程序计数器是用于存放下一条指令所在单元的地址的地方。基址寄存器存储数据内存的起始位置变址寄存器存储基址寄存器的相对地址通用寄存器存储任意数据指令寄存器储存正在被运行的指令，CPU内部使用，程序员无法对该寄存器进行读写栈寄存器存储栈区域的起始位置

其中程序计数器、累加寄存器、标志寄存器、指令寄存器和栈寄存器都只有一个，其他寄存器一般有多个。

程序计数器

程序计数器(Program Counter)是用来存储下一条指令所在单元的地址。

程序执行时，PC的初值为程序第一条指令的地址，在顺序执行程序时，控制器首先按程序计数器所指出的指令地址从内存中取出一条指令，然后分析和执行该指令，同时将PC的值加1指向下一条要执行的指令。

我们还是以一个事例为准来详细的看一下程序计数器的执行过程

这是一段进行相加的操作，程序启动，在经过编译解析后会由操作系统把硬盘中的程序复制到内存中，示例中的程序是将 123 和 456 执行相加操作，并将结果输出到显示器上。由于使用机器语言难以描述，所以这是经过翻译后的结果，实际上每个指令和数据都可能分布在不同的地址上，但为了方便说明，把组成一条指令的内存和数据放在了一个内存地址上。

地址 0100 是程序运行的起始位置。Windows 等操作系统把程序从硬盘复制到内存后，会将程序计数器作为设定为起始位置 0100，然后执行程序，每执行一条指令后，程序计数器的数值会增加1（或者直接指向下一条指令的地址），然后，CPU 就会根据程序计数器的数值，从内存中读取命令并执行，也就是说，程序计数器控制着程序的流程。

条件分支和循环机制

我们都学过高级语言，高级语言中的条件控制流程主要分为三种：顺序执行、条件分支、循环判断三种，顺序执行是按照地址的内容顺序的执行指令。条件分支是根据条件执行任意地址的指令。循环是重复执行同一地址的指令。

顺序执行的情况比较简单，每执行一条指令程序计数器的值就是 + 1。条件和循环分支会使程序计数器的值指向任意的地址，这样一来，程序便可以返回到上一个地址来重复执行同一个指令，或者跳转到任意指令。

下面以条件分支为例来说明程序的执行过程（循环也很相似）

程序的开始过程和顺序流程是一样的，CPU 从0100处开始执行命令，在0100和0101都是顺序执行，PC 的值顺序+1，执行到0102地址的指令时，判断0106寄存器的数值大于0，跳转（jump）到0104地址的指令，将数值输出到显示器中，然后结束程序，0103 的指令被跳过了，这就和我们程序中的 if() 判断是一样的，在不满足条件的情况下，指令会直接跳过。所以 PC 的执行过程也就没有直接+1，而是下一条指令的地址。

标志寄存器

条件和循环分支会使用到 jump（跳转指令），会根据当前的指令来判断是否跳转，上面我们提到了标志寄存器，无论当前累加寄存器的运算结果是正数、负数还是零，标志寄存器都会将其保存（也负责溢出和奇偶校验）

溢出（overflow）：是指运算的结果超过了寄存器的长度范围

奇偶校验（parity check）：是指检查运算结果的值是偶数还是奇数

CPU 在进行运算时，标志寄存器的数值会根据当前运算的结果自动设定，运算结果的正、负和零三种状态由标志寄存器的三个位表示。标志寄存器的第一个字节位、第二个字节位、第三个字节位各自的结果都为1时，分别代表着正数、零和负数。

CPU 的执行机制比较有意思，假设累加寄存器中存储的 XXX 和通用寄存器中存储的 YYY 做比较，执行比较的背后，CPU 的运算机制就会做减法运算。而无论减法运算的结果是正数、零还是负数，都会保存到标志寄存器中。结果为正表示 XXX 比 YYY 大，结果为零表示 XXX 和 YYY 相等，结果为负表示 XXX 比 YYY 小。程序比较的指令，实际上是在 CPU 内部做减法运算。

函数调用机制

接下来，我们继续介绍函数调用机制，哪怕是高级语言编写的程序，函数调用处理也是通过把程序计数器的值设定成函数的存储地址来实现的。函数执行跳转指令后，必须进行返回处理，单纯的指令跳转没有意义，下面是一个实现函数跳转的例子

图中将变量 a 和 b 分别赋值为 123 和 456 ，调用 MyFun(a,b) 方法，进行指令跳转。图中的地址是将 C 语言编译成机器语言后运行时的地址，由于1行 C 程序在编译后通常会变为多行机器语言，所以图中的地址是分散的。在执行完 MyFun(a,b)指令后，程序会返回到 MyFun(a,b) 的下一条指令，CPU 继续执行下面的指令。

函数的调用和返回很重要的两个指令是 call 和 return 指令，再将函数的入口地址设定到程序计数器之前，call 指令会把调用函数后要执行的指令地址存储在名为栈的主存内。函数处理完毕后，再通过函数的出口来执行 return 指令。return 指令的功能是把保存在栈中的地址设定到程序计数器。MyFun 函数在被调用之前，0154 地址保存在栈中，MyFun 函数处理完成后，会把0154的地址保存在程序计数器中。这个调用过程如下

在一些高级语言的条件或者循环语句中，函数调用的处理会转换成 call 指令，函数结束后的处理则会转换成 return 指令。

通过地址和索引实现数组

接下来我们看一下基址寄存器和变址寄存器，通过这两个寄存器，我们可以对主存上的特定区域进行划分，来实现类似数组的操作，首先，我们用十六进制数将计算机内存上的 00000000 - FFFFFFFF 的地址划分出来。那么，凡是该范围的内存地址，只要有一个 32 位的寄存器，便可查看全部地址。但如果想要想数组那样分割特定的内存区域以达到连续查看的目的的话，使用两个寄存器会更加方便。

例如，我们用两个寄存器（基址寄存器和变址寄存器）来表示内存的值

这种表示方式很类似数组的构造，数组是指同样长度的数据在内存中进行连续排列的数据构造。用数组名表示数组全部的值，通过索引来区分数组的各个数据元素，例如: a[0] - a[4]，[]内的 0 - 4 就是数组的下标。

CPU 指令执行过程

那么 CPU 是如何执行一条条的指令的呢？

几乎所有的冯·诺伊曼型计算机的CPU，其工作都可以分为5个阶段：取指令、指令译码、执行指令、访存取数、结果写回。

取指令阶段是将内存中的指令读取到 CPU 中寄存器的过程，程序寄存器用于存储下一条指令所在的地址指令译码阶段，在取指令完成后，立马进入指令译码阶段，在指令译码阶段，指令译码器按照预定的指令格式，对取回的指令进行拆分和解释，识别区分出不同的指令类别以及各种获取操作数的方法。执行指令阶段，译码完成后，就需要执行这一条指令了，此阶段的任务是完成指令所规定的各种操作，具体实现指令的功能。访问取数阶段，根据指令的需要，有可能需要从内存中提取数据，此阶段的任务是：根据指令地址码，得到操作数在主存中的地址，并从主存中读取该操作数用于运算。结果写回阶段，作为最后一个阶段，结果写回（Write Back，WB）阶段把执行指令阶段的运行结果数据“写回”到某种存储形式：结果数据经常被写到CPU的内部寄存器中，以便被后续的指令快速地存取；总结

本篇文章我们主要讲述了

CPU 是什么，CPU 的重要性，CPU 执行程序的过程还讲述了 CPU 的内部结构，它的组成部分提到了汇编语言和高级语言提到了CPU 与 寄存器的关系提到了主要的寄存器的功能，程序计数器，标志寄存器，基址寄存器和变址寄存器还提到了函数调用机制是怎样的。CPU 指令的执行过程

二、硬核知识之内存

我们都知道，计算机是处理数据的设备，而数据的主要存储位置就是磁盘和内存，并且对于程序员来讲，CPU 和内存是我们必须了解的两个物理结构，它是你通向高阶程序员很重要的桥梁，那么本篇文章我们就来介绍一下基本的内存知识。

什么是内存

内存（Memory）是计算机中最重要的部件之一，它是程序与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存对计算机的影响非常大，内存又被称为主存，其作用是存放 CPU 中的运算数据，以及与硬盘等外部存储设备交换的数据。只要计算机在运行中，CPU 就会把需要运算的数据调到主存中进行运算，当运算完成后CPU再将结果传送出来，主存的运行也决定了计算机的稳定运行。

内存的物理结构

在了解一个事物之前，你首先得先需要见过它，你才会有印象，才会有想要了解的兴趣，所以我们首先需要先看一下什么是内存以及它的物理结构是怎样的。

内存的内部是由各种IC电路组成的，它的种类很庞大，但是其主要分为三种存储器

随机存储器（RAM）： 内存中最重要的一种，表示既可以从中读取数据，也可以写入数据。当机器关闭时，内存中的信息会 丢失。只读存储器（ROM）：ROM 一般只能用于数据的读取，不能写入数据，但是当机器停电时，这些数据不会丢失。高速缓存（Cache）：Cache 也是我们经常见到的，它分为一级缓存（L1 Cache）、二级缓存（L2 Cache）、三级缓存（L3 Cache）这些数据，它位于内存和 CPU 之间，是一个读写速度比内存更快的存储器。当 CPU 向内存写入数据时，这些数据也会被写入高速缓存中。当 CPU 需要读取数据时，会直接从高速缓存中直接读取，当然，如需要的数据在Cache中没有，CPU会再去读取内存中的数据。

内存 IC 是一个完整的结构，它内部也有电源、地址信号、数据信号、控制信号和用于寻址的 IC 引脚来进行数据的读写。下面是一个虚拟的 IC 引脚示意图

图中 VCC 和 GND 表示电源，A0 - A9 是地址信号的引脚，D0 - D7 表示的是数据信号、RD 和 WR 都是控制信号，我用不同的颜色进行了区分，将电源连接到 VCC 和 GND 后，就可以对其他引脚传递 0 和 1 的信号，大多数情况下，+5V 表示1，0V 表示 0。

我们都知道内存是用来存储数据，那么这个内存 IC 中能存储多少数据呢？D0 - D7 表示的是数据信号，也就是说，一次可以输入输出 8 bit = 1 byte 的数据。A0 - A9 是地址信号共十个，表示可以指定 00000 00000 - 11111 11111 共 2 的 10次方 = 1024个地址。每个地址都会存放 1 byte 的数据，因此我们可以得出内存 IC 的容量就是 1 KB。

如果我们使用的是 512 MB 的内存，这就相当于是 512000（512 * 1000） 个内存 IC。当然，一台计算机不太可能有这么多个内存 IC ，然而，通常情况下，一个内存 IC 会有更多的引脚，也就能存储更多数据。

内存的读写过程

让我们把关注点放在内存 IC 对数据的读写过程上来吧！我们来看一个对内存IC 进行数据写入和读取的模型

来详细描述一下这个过程，假设我们要向内存 IC 中写入 1byte 的数据的话，它的过程是这样的：

首先给 VCC 接通 +5V 的电源，给 GND 接通 0V 的电源，使用 A0 - A9 来指定数据的存储场所，然后再把数据的值输入给 D0 - D7 的数据信号，并把 WR（write）的值置为 1，执行完这些操作后，即可以向内存 IC 写入数据读出数据时，只需要通过 A0 - A9 的地址信号指定数据的存储场所，然后再将 RD 的值置为 1 即可。图中的 RD 和 WR 又被称为控制信号。其中当WR 和 RD 都为 0 时，无法进行写入和读取操作。内存的现实模型

为了便于记忆，我们把内存模型映射成为我们现实世界的模型，在现实世界中，内存的模型很想我们生活的楼房。在这个楼房中，1层可以存储一个字节的数据，楼层号就是地址，下面是内存和楼层整合的模型图

我们知道，程序中的数据不仅只有数值，还有数据类型的概念，从内存上来看，就是占用内存大小（占用楼层数）的意思。即使物理上强制以 1 个字节为单位来逐一读写数据的内存，在程序中，通过指定其数据类型，也能实现以特定字节数为单位来进行读写。

下面是一个以特定字节数为例来读写指令字节的程序的示例

// 定义变量char a;short b;long c;// 变量赋值a = 123;b = 123;c = 123;

我们分别声明了三个变量 a,b,c ，并给每个变量赋上了相同的 123，这三个变量表示内存的特定区域。通过变量，即使不指定物理地址，也可以直接完成读写操作，操作系统会自动为变量分配内存地址。

这三个变量分别表示 1 个字节长度的 char，2 个字节长度的 short，表示4 个字节的 long。因此，虽然数据都表示的是 123，但是其存储时所占的内存大小是不一样的。如下所示

这里的 123 都没有超过每个类型的最大长度，所以 short 和 long 类型为所占用的其他内存空间分配的数值是0，这里我们采用的是低字节序列的方式存储

低字节序列：将数据低位存储在内存低位地址。

高字节序列：将数据的高位存储在内存地位的方式称为高字节序列。

内存的使用指针

指针是 C 语言非常重要的特征，指针也是一种变量，只不过它所表示的不是数据的值，而是内存的地址。通过使用指针，可以对任意内存地址的数据进行读写。

在了解指针读写的过程前，我们先需要了解如何定义一个指针，和普通的变量不同，在定义指针时，我们通常会在变量名前加一个 * 号。例如我们可以用指针定义如下的变量

char *d; // char类型的指针 d 定义short *e; // short类型的指针 e 定义long *f; // long类型的指针 f 定义

我们以32位计算机为例，32位计算机的内存地址是 4 字节，在这种情况下，指针的长度也是 32 位。然而，变量 d e f 却代表了不同的字节长度，这是为什么呢？

实际上，这些数据表示的是从内存中一次读取的字节数，比如 d e f 的值都为 100，那么使用 char 类型时就能够从内存中读写 1 byte 的数据，使用 short 类型就能够从内存读写 2 字节的数据， 使用 long 就能够读写 4 字节的数据，下面是一个完整的类型字节表

我们可以用图来描述一下这个读写过程

数组是内存的实现

数组是指多个相同的数据类型在内存中连续排列的一种形式。作为数组元素的各个数据会通过下标编号来区分，这个编号也叫做索引，如此一来，就可以对指定索引的元素进行读写操作。

首先先来认识一下数组，我们还是用 char、short、long 三种元素来定义数组，数组的元素用[value] 扩起来，里面的值代表的是数组的长度，就像下面的定义

char g[100];short h[100];long i[100];

数组定义的数据类型，也表示一次能够读写的内存大小，char 、short 、long 分别以 1 、2 、4 个字节为例进行内存的读写。

数组是内存的实现，数组和内存的物理结构完全一致，尤其是在读写1个字节的时候，当字节数超过 1 时，只能通过逐个字节来读取，下面是内存的读写过程

数组是我们学习的第一个数据结构，我们都知道数组的检索效率是比较快的，至于数组的检索效率为什么这么快并不是我们这篇文章讨论的重点。

栈和队列

我们上面提到数组是内存的一种实现，使用数组能够使编程更加高效，下面我们就来认识一下其他数据结构，通过这些数据结构也可以操作内存的读写。

栈

栈（stack）是一种很重要的数据结构，栈采用 LIFO（Last In First Out）即后入先出的方式对内存进行操作。它就像一个大的收纳箱，你可以往里面放相同类型的东西，比如书，最先放进收纳箱的书在最下面，最后放进收纳箱的书在最上面，如果你想拿书的话， 必须从最上面开始取，否则是无法取出最下面的书籍的。

栈的数据结构就是这样，你把书籍压入收纳箱的操作叫做压入（push），你把书籍从收纳箱取出的操作叫做弹出（pop），它的模型图大概是这样

入栈相当于是增加操作，出栈相当于是删除操作，只不过叫法不一样。栈和内存不同，它不需要指定元素的地址。它的大概使用如下

// 压入数据Push(123);Push(456);Push(789);// 弹出数据j = Pop();k = Pop();l = Pop();

在栈中，LIFO 方式表示栈的数组中所保存的最后面的数据（Last In）会被最先读取出来（First On）。

队列

队列和栈很相似但又不同，相同之处在于队列也不需要指定元素的地址，不同之处在于队列是一种 先入先出(First In First Out) 的数据结构。队列在我们生活中的使用很像是我们去景区排队买票一样，第一个排队的人最先买到票，以此类推，俗话说: 先到先得。它的使用如下

// 往队列中写入数据EnQueue(123);EnQueue(456);EnQueue(789);// 从队列中读出数据m = DeQueue();n = DeQueue();o = DeQueue();

向队列中写入数据称为 EnQueue()入列，从队列中读出数据称为DeQueue()。

与栈相对，FIFO 的方式表示队列中最先所保存的数据会优先被读取出来。

队列的实现一般有两种：顺序队列 和 循环队列，我们上面的事例使用的是顺序队列，那么下面我们看一下循环队列的实现方式

环形缓冲区

循环队列一般是以环状缓冲区(ring buffer)的方式实现的，它是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。假如我们要用 6 个元素的数组来实现一个环形缓冲区，这时可以从起始位置开始有序的存储数据，然后再按照存储时的顺序把数据读出。在数组的末尾写入数据后，后一个数据就会从缓冲区的头开始写。这样，数组的末尾和开头就连接了起来。

链表

下面我们来介绍一下链表和 二叉树，它们都是可以不用考虑索引的顺序就可以对元素进行读写的方式。通过使用链表，可以高效的对数据元素进行添加 和 删除操作。而通过使用二叉树，则可以更高效的对数据进行检索。

在实现数组的基础上，除了数据的值之外，通过为其附带上下一个元素的索引，即可实现链表。数据的值和下一个元素的地址（索引）就构成了一个链表元素，如下所示

对链表的添加和删除都是非常高效的，我们来叙述一下这个添加和删除的过程，假如我们要删除地址为 p[2] 的元素，链表该如何变化呢？

我们可以看到，删除地址为 p[2] 的元素后，直接将链表剔除，并把 p[2] 前一个位置的元素 p[1] 的指针域指向 p[2] 下一个链表元素的数据区即可。

那么对于新添加进来的链表，需要确定插入位置，比如要在 p[2] 和 p[3] 之间插入地址为 p[6] 的元素，需要将 p[6] 的前一个位置 p[2] 的指针域改为 p[6] 的地址，然后将 p[6] 的指针域改为 p[3] 的地址即可。

链表的添加不涉及到数据的移动，所以链表的添加和删除很快，而数组的添加设计到数据的移动，所以比较慢，通常情况下，使用数组来检索数据，使用链表来进行添加和删除操作。

二叉树

二叉树也是一种检索效率非常高的数据结构，二叉树是指在链表的基础上往数组追加元素时，考虑到数组的大小关系，将其分成左右两个方向的表现形式。假如我们把 50 这个值保存到了数组中，那么，如果接下来要进行值写入的话，就需要和50比较，确定谁大谁小，比50数值大的放右边，小的放左边，下图是二叉树的比较示例

二叉树是由链表发展而来，因此二叉树在追加和删除元素方面也是同样有效的。

这一切的演变都是以内存为基础的。

三、硬核知识之磁盘

我们大家知道，计算机的五大基础部件是 存储器、控制器、运算器、输入和输出设备，其中从存储功能的角度来看，可以把存储器分为内存和 磁盘，内存我们上面的文章已经介绍过了，那么此篇文章我们来介绍一下磁盘以及内存和磁盘的关系。

认识磁盘

首先，磁盘和内存都具有存储功能，它们都是存储设备。区别在于，内存是通过电流 来实现存储；磁盘则是通过磁记录技术来实现存储。内存是一种高速，造假昂贵的存储设备；而磁盘则是速度较慢、造假低廉的存储设备；电脑断电后，内存中的数据会丢失，而磁盘中的数据可以长久保留。内存是属于内部存储设备，硬盘是属于 外部存储设备。一般在我们的计算机中，磁盘和内存是相互配合共同作业的。

一般内存指的就是主存（负责存储CPU中运行的程序和数据）；早起的磁盘指的是软磁盘（soft disk，简称软盘），就是下面这个

（2000年的时候我曾经我姑姑家最早的计算机中见到过这个，当时还不知道这是啥，现在知道了。）

如今常用的磁盘是硬磁盘（hard disk，简称硬盘），就是下面这个

程序不读入内存就无法运行

在了解磁盘前，还需要了解一下内存的运行机制是怎样的，我们的程序被保存在存储设备中，通过使用 CPU 读入来实现程序指令的执行。这种机制称为存储程序方式，现在看来这种方式是理所当然的，但在以前程序的运行都是通过改变计算机的布线来读写指令的。

计算机最主要的存储部件是内存和磁盘。磁盘中存储的程序必须加载到内存中才能运行，在磁盘中保存的程序是无法直接运行的，这是因为负责解析和运行程序内容的 CPU 是需要通过程序计数器来指定内存地址从而读出程序指令的。

磁盘构件磁盘缓存

我们上面提到，磁盘往往和内存是互利共生的关系，相互协作，彼此持有良好的合作关系。每次内存都需要从磁盘中读取数据，必然会读到相同的内容，所以一定会有一个角色负责存储我们经常需要读到的内容。 我们大家做软件的时候经常会用到缓存技术，那么硬件层面也不例外，磁盘也有缓存，磁盘的缓存叫做磁盘缓存。

磁盘缓存指的是把从磁盘中读出的数据存储到内存的方式，这样一来，当接下来需要读取相同的内容时，就不会再通过实际的磁盘，而是通过磁盘缓存来读取。某一种技术或者框架的出现势必要解决某种问题的，那么磁盘缓存就大大改善了磁盘访问的速度。

Windows 操作系统提供了磁盘缓存技术，不过，对于大部分用户来说是感受不到磁盘缓存的，并且随着计算机的演进，对硬盘的访问速度也在不断演进，实际上磁盘缓存到 Windows 95/98 就已经不怎么使用了。

把低速设备的数据保存在高速设备中，需要时可以直接将其从高速设备中读出，这种缓存方式在web中应用比较广泛，web 浏览器是通过网络来获取远程 web 服务器的数据并将其显示出来。因此，在读取较大的图片的时候，会耗费不少时间，这时 web 浏览器可以把获取的数据保存在磁盘中，然后根据需要显示数据，再次读取的时候就不用重新加载了。

虚拟内存

虚拟内存是内存和磁盘交互的第二个媒介。虚拟内存是指把磁盘的一部分作为假想内存来使用。这与磁盘缓存是假想的磁盘（实际上是内存）相对，虚拟内存是假想的内存（实际上是磁盘）。

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个完整的地址空间），但是实际上，它通常被分割成多个物理碎片，还有部分存储在外部磁盘管理器上，必要时进行数据交换。

计算机中的程序都要通过内存来运行，如果程序占用内存很大，就会将内存空间消耗殆尽。为了解决这个问题，WINDOWS 操作系统运用了虚拟内存技术，通过拿出一部分硬盘来当作内存使用，来保证程序耗尽内存仍然有可以存储的空间。虚拟内存在硬盘上的存在形式就是PAGEFILE.SYS 这个页面文件。

通过借助虚拟内存，在内存不足时仍然可以运行程序。例如，在只剩 5MB 内存空间的情况下仍然可以运行 10MB 的程序。由于 CPU 只能执行加载到内存中的程序，因此，虚拟内存的空间就需要和内存中的空间进行置换（swap），然后运行程序。

虚拟内存与内存的交换方式

刚才我们提到虚拟内存需要和内存中的部分内容做置换才可让 CPU 继续执行程序，那么做置换的方式是怎样的呢？又分为哪几种方式呢？

虚拟内存的方法有分页式 和 分段式 两种。Windows 采用的是分页式。该方式是指在不考虑程序构造的情况下，把运行的程序按照一定大小的页进行分割，并以页为单位进行置换。在分页式中，我们把磁盘的内容读到内存中称为 Page In，把内存的内容写入磁盘称为 Page Out。Windows 计算机的页大小为 4KB ，也就是说，需要把应用程序按照 4KB 的页来进行切分，以页（page）为单位放到磁盘中，然后进行置换。

为了实现内存功能，Windows 在磁盘上提供了虚拟内存使用的文件（page file，页文件）。该文件由 Windows 生成和管理，文件的大小和虚拟内存大小相同，通常大小是内存的 1 - 2 倍。

节约内存

Windows 是以图形界面为基础的操作系统。它的前身是 MS-DOC，最初的版本可以在 128kb 的内存上运行程序，但是现在想要 Windows 运行流畅的花至少要需要 512MB 的内存，但通常往往是不够的。

也许许多人认为可以使用虚拟内存来解决内存不足的情况，而虚拟内存确实能够在内存不足的时候提供补充，但是使用虚拟内存的 Page In 和 Page Out 通常伴随着低速的磁盘访问，这是一种得不偿失的表现。所以虚拟内存无法从根本上解决内存不足的情况。

为了从根本上解决内存不足的情况，要么是增加内存的容量，加内存条；要么是优化应用程序，使其尽可能变小。第一种建议往往需要衡量口袋的银子，所以我们只关注第二种情况。

注意：以下的篇幅会涉及到 C 语言的介绍，是每个程序员（不限语言）都需要知道和了解的知识。

通过 DLL 文件实现函数共有

DLL（Dynamic Link Library）文件，是一种动态链接库 文件，顾名思义，是在程序运行时可以动态加载 Library（函数和数据的集合）的文件。此外，多个应用可以共有同一个 DLL 文件。而通过共有一个 DLL 文件则可以达到节约内存的效果。

例如，假设我们编写了一个具有某些处理功能的函数 MyFunc()。应用 A 和 应用 B 都需要用到这个函数，然后在各自的应用程序中内置 MyFunc()（这个称为Static Link，静态链接）后同时运行两个应用，内存中就存在了同一个函数的两个程序，这会造成资源浪费。

为了改变这一点，使用 DLL 文件而不是应用程序的执行文件（EXE文件）。因为同一个 DLL 文件内容在运行时可以被多个应用共有，因此内存中存在函数 MyFunc（）的程序就只有一个

Windows 操作系统其实就是无数个 DLL 文件的集合体。有些应用在安装时，DLL文件也会被追加。应用程序通过这些 DLL 文件来运行，既可以节约内存，也可以在不升级 EXE 文件的情况下，通过升级 DLL 文件就可以完成更新。

通过调用 _stdcall 来减少程序文件的大小

通过调用 _stdcall 来减小程序文件的方法，是用 C 语言编写应用时可以利用的高级技巧。我们来认识一下什么是 _stdcall。

_stdcall 是 standard call(标准调用)的缩写。Windows 提供的 DLL 文件内的函数，基本上都是通过 _stdcall 调用方式来完成的，这主要是为了节约内存。另一方面，用 C 语言编写的程序默认都不是 _stdcall 。C 语言特有的调用方式称为 C 调用。C 语言默认不使用 _stdcall 的原因是因为 C 语言所对应的函数传入参数是可变的，只有函数调用方才能知道到底有多少个参数，在这种情况下，栈的清理作业便无法进行。不过，在 C 语言中，如果函数的参数和数量固定的话，指定 _stdcall 是没有任何问题的。

C 语言和 Java 最主要的区别之一在于 C 语言需要人为控制释放内存空间

C 语言中，在调用函数后，需要人为执行栈清理指令。把不需要的数据从接收和传递函数的参数时使用的内存上的栈区域中清理出去的操作叫做 栈清理处理。

例如如下代码

// 函数调用方void main(){  int a;  a = MyFunc(123,456);}// 被调用方int MyFunc(int a,int b){  ...}

代码中，从 main 主函数调用到 MyFunc() 方法，按照默认的设定，栈的清理处理会附加在 main 主函数这一方。在同一个程序中，有可能会多次调用，导致 MyFunc() 会进行多次清理，这就会造成内存的浪费。

汇编之后的代码如下

push 1C8h								// 将参数 456( = 1C8h) 存入栈中push 7Bh								// 将参数 123( = 7Bh) 存入栈中call @LTD+15 (MyFunc)(00401014)			// 调用 MyFunc 函数add esp,8								// 运行栈清理

C 语言通过栈来传递函数的参数，使用 push 是往栈中存入数据的指令，pop 是从栈中取出数据的指令。32 位 CPU 中，1次 push 指令可以存储 4 个字节（32 位）的数据。上述代码由于进行了两次 push 操作，所以存储了 8 字节的数据。通过 call 指令来调用函数，调用完成后，栈中存储的数据就不再需要了。于是就通过 add esp,8 这个指令，使存储着栈数据的 esp 寄存器前进 8 位（设定为指向高 8 位字节的地址），来进行数据清理。由于栈是在各种情况下都可以利用的内存领域，因此使用完毕后有必要将其恢复到原始状态。上述操作就是执行栈的清理工作。另外，在 C 语言中，函数的返回值，是通过寄存器而非栈来返回的。

栈执行清理工作，在调用方法处执行清理工作和在反复调用方法处执行清理工作不同，使用 _stdcall 标准调用的方式称为反复调用方法，在这种情况下执行栈清理开销比较小。

磁盘的物理结构

之前我们介绍了CPU、内存的物理结构，现在我们来介绍一下磁盘的物理结构。磁盘的物理结构指的是磁盘存储数据的形式。

磁盘是通过其物理表面划分成多个空间来使用的。划分的方式有两种：可变长方式 和 扇区方式。前者是将物理结构划分成长度可变的空间，后者是将磁盘结构划分为固定长度的空间。一般 Windows 所使用的硬盘和软盘都是使用扇区这种方式。扇区中，把磁盘表面分成若干个同心圆的空间就是 磁道，把磁道按照固定大小的存储空间划分而成的就是 扇区

扇区是对磁盘进行物理读写的最小单位。Windows 中使用的磁盘，一般是一个扇区 512 个字节。不过，Windows 在逻辑方面对磁盘进行读写的单位是扇区整数倍簇。根据磁盘容量不同功能，1簇可以是 512 字节（1 簇 = 1扇区）、1KB（1簇 = 2扇区）、2KB、4KB、8KB、16KB、32KB( 1 簇 = 64 扇区)。簇和扇区的大小是相等的。

不管是硬盘还是软盘，不同的文件是不能存储在同一簇中的，否则就会导致只有一方的文件不能删除。所以，不管多小的文件，都会占用 1 簇的空间。这样一来，所有的文件都会占用 1 簇的整数倍的空间。

我们使用软盘做实验会比较简单一些，我们先对软盘进行格式化，格式化后的软盘空间如下

接下来，我们保存一个 txt 文件，并在文件输入一个字符，这时候文件其实只占用了一个字节，但是我们看一下磁盘的属性却占用了 512 字节

然后我们继续写入一些东西，当文件大小到达 512 个字节时，已用空间也是 512 字节，但是当我们继续写入一个字符时，我们点开属性会发现磁盘空间会变为 1024 个字节（= 2 簇），通过这个实验我们可以证明磁盘是以簇为单位来保存的。

四、硬核知识之二进制

我们都知道，计算机的底层都是使用二进制数据进行数据流传输的，那么为什么会使用二进制表示计算机呢？或者说，什么是二进制数呢？在拓展一步，如何使用二进制进行加减乘除？二进制数如何表示负数呢？本文将一一为你揭晓。

为什么用二进制表示

我们大家知道，计算机内部是由IC电子元件组成的，其中 CPU 和 内存 也是 IC 电子元件的一种，CPU和内存图如下

CPU 和 内存使用IC电子元件作为基本单元，IC电子元件有不同种形状，但是其内部的组成单元称为一个个的引脚。有人说CPU 和 内存内部都是超大规模集成电路，其实IC 就是集成电路(Integrated Circuit)。

IC元件两侧排列的四方形块就是引脚，IC的所有引脚，只有两种电压: 0V 和 5V，IC的这种特性，也就决定了计算机的信息处理只能用 0 和 1 表示，也就是二进制来处理。一个引脚可以表示一个 0 或 1 ，所以二进制的表示方式就变成 0、1、10、11、100、101等，虽然二进制数并不是专门为 引脚 来设计的，但是和 IC引脚的特性非常吻合。

计算机的最小集成单位为 位，也就是 比特(bit)，二进制数的位数一般为 8位、16位、32位、64位，也就是 8 的倍数，为什么要跟 8 扯上关系呢？ 因为在计算机中，把 8 位二进制数称为 一个字节， 一个字节有 8 位，也就是由 8个bit构成。

为什么1个字节等于8位呢？因为 8 位能够涵盖所有的字符编码，这个记住就可以了。

字节是最基本的计量单位，位是最小单位。

用字节处理数据时，如果数字小于存储数据的字节数 ( = 二进制的位数)，那么高位就用 0 填补，高位和数学的数字表示是一样的，左侧表示高位，右侧表示低位。比如 这个六位数用二进制数来表示就是 100111，只有6位，高位需要用 0 填充，填充完后是 00100111，占一个字节，如果用 16 位表示 就是 0000 0000 0010 0111占用两个字节。

我们一般口述的 32 位和 64位的计算机一般就指的是处理位数，32 位一次可以表示 4个字节，64位一次可以表示8个字节的二进制数。

我们一般在软件开发中用十进制数表示的逻辑运算等，也会被计算机转换为二进制数处理。对于二进制数，计算机不会区分他是 图片、音频文件还是数字，这些都是一些数据的结合体。

什么是二进制数

那么什么是二进制数呢？为了说明这个问题，我们先把 00100111 这个数转换为十进制数看一下，二进制数转换为十进制数，直接将各位置上的值 * 位权即可，那么我们将上面的数值进行转换

也就是说，二进制数代表的 00100111 转换成十进制就是 39，这个 39 并不是 3 和 9 两个数字连着写，而是 3 * 10 + 9 * 1，这里面的 10 , 1 就是位权，以此类推，上述例子中的位权从高位到低位依次就是 7 6 5 4 3 2 1 0。这个位权也叫做次幂，那么最高位就是2的7次幂，2的6次幂 等等。二进制数的运算每次都会以2为底，这个2 指得就是基数，那么十进制数的基数也就是 10 。在任何情况下位权的值都是 数的位数 - 1，那么第一位的位权就是 1 - 1 = 0， 第二位的位权就睡 2 - 1 = 1，以此类推。

那么我们所说的二进制数其实就是 用0和1两个数字来表示的数，它的基数为2，它的数值就是每个数的位数 * 位权再求和得到的结果，我们一般来说数值指的就是十进制数，那么它的数值就是 3 * 10 + 9 * 1 = 39。

移位运算和乘除的关系

在了解过二进制之后，下面我们来看一下二进制的运算，和十进制数一样，加减乘除也适用于二进制数，只要注意逢 2 进位即可。二进制数的运算，也是计算机程序所特有的运算，因此了解二进制的运算是必须要掌握的。

首先我们来介绍移位 运算，移位运算是指将二进制的数值的各个位置上的元素坐左移和右移操作，见下图

上述例子中还是以 39 为例，我们先把十进制的39 转换为二进制的 0010 0111，然后向左移位 <<一个字节，也就变成了 0100 1110，那么再把此二进制数转换为十进制数就是上面的78， 十进制的78 竟然是 十进制39 的2倍关系。我们在让 0010 0111 左移两位，也就是 1001 1100，得出来的值是 156，相当于扩大了四倍！

因此你可以得出来此结论，左移相当于是数值扩大的操作，那么右移 >>呢？按理说右移应该是缩小 1/2，1/4 倍，但是39 缩小二倍和四倍不就变成小数了吗？这个怎么表示呢？请看下一节

便于计算机处理的补数

刚才我们没有介绍右移的情况，是因为右移之后空出来的高位数值，有 0 和 1 两种形式。要想区分什么时候补0什么时候补1，首先就需要掌握二进制数表示负数的方法。

二进制数中表示负数值时，一般会把最高位作为符号来使用，因此我们把这个最高位当作符号位。 符号位是 0 时表示正数，是 1 时表示 负数。那么 -1 用二进制数该如何表示呢？可能很多人会这么认为： 因为 1 的二进制数是 0000 0001，最高位是符号位，所以正确的表示 -1 应该是 1000 0001，但是这个答案真的对吗？

计算机世界中是没有减法的，计算机在做减法的时候其实就是在做加法，也就是用加法来实现的减法运算。比如 100 - 50 ，其实计算机来看的时候应该是 100 + (-50)，为此，在表示负数的时候就要用到二进制补数，补数就是用正数来表示的负数。

为了获得补数，我们需要将二进制的各数位的数值全部取反，然后再将结果 + 1 即可，先记住这个结论，下面我们来演示一下。

具体来说，就是需要先获取某个数值的二进制数，然后对二进制数的每一位做取反操作(0 ---> 1 , 1 ---> 0)，最后再对取反后的数 +1 ，这样就完成了补数的获取。

补数的获取，虽然直观上不易理解，但是逻辑上却非常严谨，比如我们来看一下 1 - 1 的这个过程，我们先用上面的这个 1000 0001(它是1的补数，不知道的请看上文，正确性先不管，只是用来做一下计算)来表示一下

奇怪，1 - 1 会变成 130 ，而不是0，所以可以得出结论 1000 0001 表示 -1 是完全错误的。

那么正确的该如何表示呢？其实我们上面已经给出结果了，那就是 1111 1111，来论证一下它的正确性

我们可以看到 1 - 1 其实实际上就是 1 + (-1)，对 -1 进行上面的取反 + 1 后变为 1111 1111, 然后与 1 进行加法运算，得到的结果是九位的 1 0000 0000，结果发生了溢出，计算机会直接忽略掉溢出位，也就是直接抛掉 最高位 1 ，变为 0000 0000。也就是 0，结果正确，所以 1111 1111 表示的就是 -1 。

所以负数的二进制表示就是先求其补数，补数的求解过程就是对原始数值的二进制数各位取反，然后将结果 + 1，

当然，结果不为 0 的运算同样也可以通过补数求得正确的结果。不过，有一点需要注意，当运算结果为负的时候，计算结果的值也是以补数的形式出现的，比如 3 - 5 这个运算，来看一下解析过程

3 - 5 的运算，我们按着上面的思路来过一遍，计算出来的结果是 1111 1110，我们知道，这个数值肯定表示负数，但是负数无法直接用十进制表示，需要对其取反+ 1，算出来的结果是 2，因为 1111 1110的高位是 1，所以最终的结果是 -2。

编程语言的数据类型中，有的可以处理负数，有的不可以。比如 C语言中不能处理负数的 unsigned short类型，也有能处理负数的short类型 ，都是两个字节的变量，它们都有 2 的十六次幂种值，但是取值范围不一样，short 类型的取值范围是 -32768 - 32767 ， unsigned short 的取值范围是 0 - 65536。

仔细思考一下补数的机制，就能明白 -32768 比 32767 多一个数的原因了，最高位是 0 的正数有 0 ~ 32767 共 32768 个，其中包括0。最高位是 1 的负数，有 -1 ~ -32768 共 32768 个，其中不包含0。0 虽然既不是正数也不是负数，但是考虑到其符号位，就将其归为了正数。

算数右移和逻辑右移的区别

在了解完补数后，我们重新考虑一下右移这个议题，右移在移位后空出来的最高位有两种情况 0 和 1。当二进制数的值表示图形模式而非数值时，移位后需要在最高位补0，类似于霓虹灯向右平移的效果，这就被称为逻辑右移。

将二进制数作为带符号的数值进行右移运算时，移位后需要在最高位填充移位前符号位的值( 0 或 1)。这就被称为算数右移。如果数值使用补数表示的负数值，那么右移后在空出来的最高位补 1，就可以正确的表示 1/2,1/4,1/8等的数值运算。如果是正数，那么直接在空出来的位置补 0 即可。

下面来看一个右移的例子。将 -4 右移两位，来各自看一下移位示意图

如上图所示，在逻辑右移的情况下， -4 右移两位会变成 63， 显然不是它的 1/4，所以不能使用逻辑右移，那么算数右移的情况下，右移两位会变为 -1，显然是它的 1/4，故而采用算数右移。

那么我们可以得出来一个结论：左移时，无论是图形还是数值，移位后，只需要将低位补 0 即可；右移时，需要根据情况判断是逻辑右移还是算数右移。

下面介绍一下符号扩展：将数据进行符号扩展是为了产生一个位数加倍、但数值大小不变的结果，以满足有些指令对操作数位数的要求，例如倍长于除数的被除数，再如将数据位数加长以减少计算过程中的误差。

以8位二进制为例，符号扩展就是指在保持值不变的前提下将其转换成为16位和32位的二进制数。将0111 1111这个正的 8位二进制数转换成为 16位二进制数时，很容易就能够得出0000 0000 0111 1111这个正确的结果，但是像 1111 1111这样的补数来表示的数值，该如何处理？直接将其表示成为1111 1111 1111 1111就可以了。也就是说，不管正数还是补数表示的负数，只需要将 0 和 1 填充高位即可。

逻辑运算的窍门

掌握逻辑和运算的区别是：将二进制数表示的信息作为四则运算的数值来处理就是算数，像图形那样，将数值处理为单纯的 0 和 1 的罗列就是逻辑

计算机能够处理的运算，大体可分为逻辑运算和算数运算，算数运算指的是加减乘除四则运算；逻辑运算指的是对二进制各个数位的 0 和 1分别进行处理的运算，包括逻辑非(NOT运算)、逻辑与(AND运算)、逻辑或(OR运算)和逻辑异或(XOR运算)四种。

逻辑非 指的是将 0 变成 1，1 变成 0 的取反操作逻辑与 指的是"两个都是 1 时，运算结果才是 1，其他情况下是 0"逻辑或 指的是"至少有一方是 1 时，运算结果为 1，其他情况下运算结果都是 0"逻辑异或 指的是 "其中一方是 1，另一方是 0时运算结果才是 1，其他情况下是 0"

掌握逻辑运算的窍门，就是要摒弃二进制数表示数值这一个想法。大家不要把二进制数表示的值当作数值，应该把它看成是 开关上的 ON/OFF。

五、硬核知识之压缩算法

认识压缩算法

我们想必都有过压缩和 解压缩文件的经历，当文件太大时，我们会使用文件压缩来降低文件的占用空间。比如微信上传文件的限制是100 MB，我这里有个文件夹无法上传，但是我解压完成后的文件一定会小于 100 MB，那么我的文件就可以上传了。

此外，我们把相机拍完的照片保存到计算机上的时候，也会使用压缩算法进行文件压缩，文件压缩的格式一般是JPEG。

那么什么是压缩算法呢？压缩算法又是怎么定义的呢？在认识算法之前我们需要先了解一下文件是如何存储的

文件存储

文件是将数据存储在磁盘等存储媒介的一种形式。程序文件中最基本的存储数据单位是字节。文件的大小不管是 xxxKB、xxxMB等来表示，就是因为文件是以字节 B = Byte 为单位来存储的。

文件就是字节数据的集合。用 1 字节（8 位）表示的字节数据有 256 种，用二进制表示的话就是 0000 0000 - 1111 1111 。如果文件中存储的数据是文字，那么该文件就是文本文件。如果是图形，那么该文件就是图像文件。在任何情况下，文件中的字节数都是连续存储的。

压缩算法的定义

上面介绍了文件的集合体其实就是一堆字节数据的集合，那么我们就可以来给压缩算法下一个定义。

压缩算法（compaction algorithm）指的就是数据压缩的算法，主要包括压缩和还原（解压缩）的两个步骤。

其实就是在不改变原有文件属性的前提下，降低文件字节空间和占用空间的一种算法。

根据压缩算法的定义，我们可将其分成不同的类型：

有损和无损

无损压缩：能够无失真地从压缩后的数据重构，准确地还原原始数据。可用于对数据的准确性要求严格的场合，如可执行文件和普通文件的压缩、磁盘的压缩，也可用于多媒体数据的压缩。该方法的压缩比较小。如差分编码、RLE、Huffman编码、LZW编码、算术编码。

有损压缩：有失真，不能完全准确地恢复原始数据，重构的数据只是原始数据的一个近似。可用于对数据的准确性要求不高的场合，如多媒体数据的压缩。该方法的压缩比较大。例如预测编码、音感编码、分形压缩、小波压缩、JPEG/MPEG。

对称性

如果编解码算法的复杂性和所需时间差不多，则为对称的编码方法，多数压缩算法都是对称的。但也有不对称的，一般是编码难而解码容易，如 Huffman 编码和分形编码。但用于密码学的编码方法则相反，是编码容易，而解码则非常难。

帧间与帧内

在视频编码中会同时用到帧内与帧间的编码方法，帧内编码是指在一帧图像内独立完成的编码方法，同静态图像的编码，如 JPEG；而帧间编码则需要参照前后帧才能进行编解码，并在编码过程中考虑对帧之间的时间冗余的压缩，如 MPEG。

实时性

在有些多媒体的应用场合，需要实时处理或传输数据（如现场的数字录音和录影、播放MP3/RM/VCD/DVD、视频/音频点播、网络现场直播、可视电话、视频会议），编解码一般要求延时 ≤50 ms。这就需要简单/快速/高效的算法和高速/复杂的CPU/DSP芯片。

分级处理

有些压缩算法可以同时处理不同分辨率、不同传输速率、不同质量水平的多媒体数据，如JPEG2000、MPEG-2/4。

这些概念有些抽象，主要是为了让大家了解一下压缩算法的分类，下面我们就对具体的几种常用的压缩算法来分析一下它的特点和优劣

几种常用压缩算法的理解RLE 算法的机制

接下来就让我们正式看一下文件的压缩机制。首先让我们来尝试对 AAAAAABBCDDEEEEEF 这 17 个半角字符的文件（文本文件）进行压缩。虽然这些文字没有什么实际意义，但是很适合用来描述 RLE 的压缩机制。

由于半角字符（其实就是英文字符）是作为 1 个字节保存在文件中的，所以上述的文件的大小就是 17 字节。如图

（这里有个问题需要读者思考一下：为什么 17 个字符的大小是 17 字节，而占用空间却很大呢？ 这个问题此篇文章暂不讨论）

那么，如何才能压缩该文件呢？大家不妨也考虑一下，只要是能够使文件小于 17 字节，我们可以使用任何压缩算法。

最显而易见的一种压缩方式我觉得你已经想到了，就是把相同的字符去重化，也就是 字符 * 重复次数 的方式进行压缩。所以上面文件压缩后就会变成下面这样

从图中我们可以看出，AAAAAABBCDDEEEEEF 的17个字符成功被压缩成了 A6B2C1D2E5F1 的12个字符，也就是 12 / 17 = 70%，压缩比为 70%，压缩成功了。

像这样，把文件内容用 数据 * 重复次数 的形式来表示的压缩方法成为 RLE(Run Length Encoding, 行程长度编码) 算法。RLE 算法是一种很好的压缩方法，经常用于压缩传真的图像等。因为图像文件的本质也是字节数据的集合体，所以可以用 RLE 算法进行压缩

RLE 算法的缺点

RLE 的压缩机制比较简单，所以 RLE 算法的程序也比较容易编写，所以使用 RLE 的这种方式更能让你体会到压缩思想，但是 RLE 只针对特定序列的数据管用，下面是 RLE 算法压缩汇总

文件类型压缩前文件大小压缩后文件大小压缩比率文本文件14862字节29065字节199%图像文件96062字节38328字节40%EXE文件24576字节15198字节62%

通过上表可以看出，使用 RLE 对文本文件进行压缩后的数据不但没有减小反而增大了！几乎是压缩前的两倍！因为文本字符种连续的字符并不多见。

就像上面我们探讨的这样，RLE 算法只针对连续的字节序列压缩效果比较好，假如有一连串不相同的字符该怎么压缩呢？比如说ABCDEFGHIJKLMNOPQRSTUVWXYZ，26个英文字母所占空间应该是 26 个字节，我们用 RLE 压缩算法压缩后的结果为 A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1 ，所占用 52 个字节，压缩完成后的容量没有减少反而增大了！这显然不是我们想要的结果，所以这种情况下就不能再使用 RLE 进行压缩。

哈夫曼算法和莫尔斯编码

下面我们来介绍另外一种压缩算法，即哈夫曼算法。在了解哈夫曼算法之前，你必须舍弃半角英文数字的1个字符是1个字节(8位)的数据。下面我们就来认识一下哈夫曼算法的基本思想。

文本文件是由不同类型的字符组合而成的，而且不同字符出现的次数也是不一样的。例如，在某个文本文件中，A 出现了 100次左右，Q仅仅用到了 3 次，类似这样的情况很常见。哈夫曼算法的关键就在于 多次出现的数据用小于 8 位的字节数表示，不常用的数据则可以使用超过 8 位的字节数表示。A 和 Q 都用 8 位来表示时，原文件的大小就是 100次 * 8 位 + 3次 * 8 位 = 824位，假设 A 用 2 位，Q 用 10 位来表示就是 2 * 100 + 3 * 10 = 230 位。

不过要注意一点，最终磁盘的存储都是以8位为一个字节来保存文件的。

哈夫曼算法比较复杂，在深入了解之前我们先吃点甜品，了解一下 莫尔斯编码，你一定看过美剧或者战争片的电影，在战争中的通信经常采用莫尔斯编码来传递信息，例如下面

接下来我们来讲解一下莫尔斯编码，下面是莫尔斯编码的示例，大家把 1 看作是短点(嘀)，把 11 看作是长点(嗒)即可。

莫尔斯编码一般把文本中出现最高频率的字符用短编码 来表示。如表所示，假如表示短点的位是 1，表示长点的位是 11 的话，那么 E（嘀）这一数据的字符就可以用 1 来表示，C（滴答滴答）就可以用 9 位的 110101101来表示。在实际的莫尔斯编码中，如果短点的长度是 1 ，长点的长度就是 3，短点和长点的间隔就是1。这里的长度指的就是声音的长度。比如我们想用上面的 AAAAAABBCDDEEEEEF 例子来用莫尔斯编码重写，在莫尔斯曼编码中，各个字符之间需要加入表示时间间隔的符号。这里我们用 00 加以区分。

所以，AAAAAABBCDDEEEEEF 这个文本就变为了 A * 6 次 + B * 2次 + C * 1次 + D * 2次 + E * 5次 + F * 1次 + 字符间隔 * 16 = 4 位 * 6次 + 8 位 * 2次 + 9 位 * 1 次 + 6位 * 2次 + 1位 * 5次 + 8 位 * 1次 + 2位 * 16次 = 106位 = 14字节。

所以使用莫尔斯电码的压缩比为 14 / 17 = 82%。效率并不太突出。

用二叉树实现哈夫曼算法

刚才已经提到，莫尔斯编码是根据日常文本中各字符的出现频率来决定表示各字符的编码数据长度的。不过，在该编码体系中，对 AAAAAABBCDDEEEEEF 这种文本来说并不是效率最高的。

下面我们来看一下哈夫曼算法。哈夫曼算法是指，为各压缩对象文件分别构造最佳的编码体系，并以该编码体系为基础来进行压缩。因此，用什么样的编码（哈夫曼编码）对数据进行分割，就要由各个文件而定。用哈夫曼算法压缩过的文件中，存储着哈夫曼编码信息和压缩过的数据。

接下来，我们在对 AAAAAABBCDDEEEEEF 中的 A - F 这些字符，按照出现频率高的字符用尽量少的位数编码来表示这一原则进行整理。按照出现频率从高到低的顺序整理后，结果如下，同时也列出了编码方案。

字符出现频率编码（方案）位数

A601E511B2102D2112C11003F11013

在上表的编码方案中，随着出现频率的降低，字符编码信息的数据位数也在逐渐增加，从最开始的 1位、2位依次增加到3位。不过这个编码体系是存在问题的，你不知道100这个3位的编码，它的意思是用 1、0、0这三个编码来表示 E、A、A 呢？还是用10、0来表示 B、A 呢？还是用100来表示 C 呢。

而在哈夫曼算法中，通过借助哈夫曼树的构造编码体系，即使在不使用字符区分符号的情况下，也可以构建能够明确进行区分的编码体系。不过哈夫曼树的算法要比较复杂，下面是一个哈夫曼树的构造过程。

自然界树的从根开始生叶的，而哈夫曼树则是叶生枝

哈夫曼树能够提升压缩比率

使用哈夫曼树之后，出现频率越高的数据所占用的位数越少，这也是哈夫曼树的核心思想。通过上图的步骤二可以看出，枝条连接数据时，我们是从出现频率较低的数据开始的。这就意味着出现频率低的数据到达根部的枝条也越多。而枝条越多则意味着编码的位数随之增加。

接下来我们来看一下哈夫曼树的压缩比率，用上图得到的数据表示 AAAAAABBCDDEEEEEF 为 000000000000 100100 110 101101 0101010101 111，40位 = 5 字节。压缩前的数据是 17 字节，压缩后的数据竟然达到了惊人的5 字节，也就是压缩比率 = 5 / 17 = 29% 如此高的压缩率，简直是太惊艳了。

大家可以参考一下，无论哪种类型的数据，都可以用哈夫曼树作为压缩算法

文件类型压缩前压缩后压缩比率文本文件14862字节4119字节28%图像文件96062字节9456字节10%EXE文件24576字节4652字节19%

可逆压缩和非可逆压缩

最后，我们来看一下图像文件的数据形式。图像文件的使用目的通常是把图像数据输出到显示器、打印机等设备上。常用的图像格式有 : BMP、JPEG、TIFF、GIF 格式等。

BMP ： 是使用 Windows 自带的画笔来做成的一种图像形式JPEG：是数码相机等常用的一种图像数据形式TIFF: 是一种通过在文件中包含"标签"就能够快速显示出数据性质的图像形式GIF： 是由美国开发的一种数据形式，要求色数不超过 256个

图像文件可以使用前面介绍的 RLE 算法和哈夫曼算法，因为图像文件在多数情况下并不要求数据需要还原到和压缩之前一摸一样的状态，允许丢失一部分数据。我们把能还原到压缩前状态的压缩称为 可逆压缩，无法还原到压缩前状态的压缩称为非可逆压缩。

一般来说，JPEG格式的文件是非可逆压缩，因此还原后有部分图像信息比较模糊。GIF 是可逆压缩

转自：cxuan