1.生存周期不同 全局变量:全局区（静态区）（static）：全局变量和静态变量是存储在一起的，初始化过的全局变量和静态变量在同一块区域，未初始化的全局变量和静态变量存放在一块相邻的区域内。此区域由系统在程序结束后释放 局部变量： 放在堆栈中。由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈

2.作用范围不同 全局变量具有全局作用域。全局变量只需在一个源文件中定义，就可以作用于所有的源文件。当然，其他不包含全局变量定义的源文件需要用extern 关键字再次声明这个全局变量。 局部变量也只有局部作用域，它是自动对象（auto），它在程序运行期间不是一直存在，而是只在函数执行期间存在，函数的一次调用执行结束后，变量被撤销，其所占用的内存也被收回

3.静态变量分为 全局静态变量(常称为全局变量)和局部静态变量(static修饰的变量)

using namespace std;

static int var1 = 0;//局部静态变量,虽然位置在函数体外
static int var2;//同上，局部静态变量
int var3 = 0;//全局静态变量
int main(int argc, char const *argv[])
{
	int var4 = 3;//在text段
	static int var5 = 1;//局部静态变量
    return 0;
}

       内存是计算机中重要的部件之一，它是与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大。内存(Memory)也被称为内存储器，其作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的是否稳定运行决定了计算机的稳定性。再引入虚拟内存之前我们再说说进程与程序的主要区别：

 （1）程序是永存的；进程是暂时的，是程序在数据集上的一次执行，有创建有撤销，存在是暂时的；

 （2）程序是静态的观念，进程是动态的观念；

 （3）进程具有并发性，而程序没有；

 （4）进程是竞争计算机资源的基本单位，程序不是。

 （5）进程和程序不是一一对应的： 一个程序可对应多个进程即多个进程可执行同一程序； 一个进程可以执行一个或几个程序

       我们平常说的每个进程都有自己独立的4G内存空间，但是实际上我们现在作用的个人计算机的内存水平最多也就是4G。那么问题来了，一个进程占据4G内存，一个程序往往分多个进程，首先是内存不够用，其次如果只这样的话，每个进程分开执行，这就存在执行等待的问题，甚至是进程阻塞。如此一来，计算机执行效率低下，显然不可取。由此，引入了虚拟内存，顾名思义，操作系统是给每个进程分配了4G的虚拟内存，而不是内存。也就是说程序运行时操作系统先将相关的文件和数据是先从磁盘上读取，通过地址映射到虚拟内存上，内存通过和虚拟内存和物理内存间的映射关系获取当下进程需要的文件和数据。

        Intel 80386 微处理器的诞生之前，计算机内存采用的是实地址模式，之后才是我们现在所用的保护地址模式。它是 Intel公司80286及以后的x86(80386,80486和80586等)兼容处理器（CPU）的一种操作模式。实模式被特殊定义为20位地址内存可访问空间上，它的容量是2的20次幂（1M）的可访问内存空间（物理内存和BIOS-ROM），软件可通过这些地址直接访问BIOS程序和外围硬件。实模式下处理器没有硬件级的内存保护概念和多道任务的工作模式。但是为了向下兼容，所以80286及以后的x86系列兼容处理器仍然是开机启动时工作在实模式下。1M 地址空间组成是由 16位的段地址和16位的段内偏移地址组成的。用公式表示为：物理地址=左移4位的段地址+偏移地址。286处理器体系结构引入了地址保护模式的概念，处理器能够对内存及一些其他外围设备做硬件级的保护设置（实质上就是屏蔽一些地址的访问）。Intel 80386使用之后保护模式才真正使用，它具有许多特性设计为提高系统的多道任务和系统的稳定性。例如内存的保护，分页机制和硬件虚拟存储的支持。最终的物理计算公式为：物理地址 = 左移 4 位的段地址 + 偏移地址。保护模式下存在着分段地址映射，首先由基地址+逻辑地址/偏移量得到线性地址，当操所系统没有开启分页机制时，这个线性地址就是物理地址，若开启分页机制，得到的是虚拟地址，必须要经过分页地址映射才能得到我们想要的物理地址。

       在保护模式下，段是通过一系列被称之为 “ 描述符表 ” 的表所定义的。段寄存器存储的是指向这些表的指针。用于定义内存段的表有两种：全局描述符表 (GDT) 和局部描述符表 (LDT) 。GDT 是一个段描述符数组，其中包含所有应用程序都可以使用的基本描述符。在实模式中，段长是固定的 ( 为 64KB) ，而在保护模式中，段长是可变的，其最大可达 4GB 。LDT 也是段描述符的一个数组。与 GDT 不同， LDT 是一个段，其中存放的是局部的、不需要全局共享的段描述符。每一个操作系统都必须定义一个 GDT ，而每一个正在运行的任务都会有一个相应的 LDT 。

虚拟内存

接下来我们细说一下4G虚拟内存具体存放的是什么，我们所写的代码中的头文件，定义的变量他们归谁管。下面是我所画的虚拟内存的布局：

                                 

        虚拟内存的划分比例为3:1，用户可用的空间为3G,系统空间为1G。此图的地址是从上往下一次增大，顶部的128M是保留区空间，用户不能访问，访问系统就会报错。.txt段存放的是指令，.data段存放的是初始化过且不为0的全局变量和静态全局变量，.bss段存放的是未初始化的或者初始化为0的全局变量和静态全局变量（.bss段实际上是不存在的，系统采用预留的方式以节省空间，因为它的值为0，给它分配空间没有实际意义）。紧接着会预留一小部分空间放置越界访问，然后是堆栈分区，堆区地址由低地址向高地址分配（堆区（Heap）用于动态内存的开辟，需要注意的是动态内存的开辟并不是用户一次申请多少空间堆区就会减少多大空间，而是系统根据当前用户使用的实时空间进行分配，以免让开辟出来的空间处于空闲状态。），栈区（Stack）地址由高地址向低地址分配空间，在堆区和栈区之间是共享库的存储区域。在栈之后是程序的命令行参数和环境变量的存放区域。从0xc000 0000到0xFFFF FFFF的系统区域是直接内存访问区，常用部分区域和高端内存区域。

内存分配方式

（1） 从静态存储区域分配 。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量， static 变量 。

（2） 在栈上创建 。在执行函数时，函数内局部变量的存储单元都可以在栈上创建 ，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集。

（3）从堆上分配 ， 亦称动态内存分配 。程序在运行的时候用 malloc 或 new 申请任意多少的内存，程序员自己负责在何时用 free 或 delete 释放内存。

 

相信大家在开发过程中，经常会遇到判断一个字符串（或其他类型的变量值）是否已经出现过的需求，这个时候一般使用HashMap可以解决，先将出现过的字符串存于HashMap对象的keySet中，下次只要判断HashMap对象的keySet是否含有该字符串，就能知道是否其已经出现过。
但是，当我们HashMap存放的数据越多，查询速度就会越慢，而且占用内存也会越大。

为什么查询速度会变慢呢？

知道HashMap底层原理的就不难想到，key的hashcode分布不均匀，可能很多key的hashcode被分配到同一个位置的链表中，就算jdk1.8之后引入红黑树，当数据很多的时候，对树进行遍历的速度也不会很理想。
布隆过滤器
这种情况下，布隆过滤器就可以上场了：占用内存非常小，查询速度快，但是存在很低的误判率。

它的原理其实很简单：如下图，

我们创建一个长度为m的bit数组即位数组（bit占用内存较小），初设值为0；
设计k个散列函数即hash函数；
通过散列函数将字符串映射到0至n-1的k个数值；
将这个k个数值作为索引，如果bit数组在这个k个索引位置上的值都为1的话，则该字符串已经出现过，反之，则未出现过；
最后，更新bit数组，将bit数组对应的k个索引位置上将其修改为1。



误判率
布隆过滤器的误判率是指，当一个元素没有出现过时，会存在一定的概率将其误判为已经出现过。

（以下摘自维基百科）


java实现
import java.io.Serializable;
import java.util.BitSet;

public class BloomFilter implements Serializable{
	 private static final int BIT_SIZE = 2 << 28 ;//二进制向量的位数，相当于能存储1000万条url左右，误报率为千万分之一
	    private static final int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};//用于生成信息指纹的8个随机数，最好选取质数

	    private BitSet bits = new BitSet(BIT_SIZE);
	    private Hash[] func = new Hash[seeds.length];//用于存储8个随机哈希值对象

	    public BloomFilter(){
	        for(int i = 0; i < seeds.length; i++){
	            func[i] = new Hash(BIT_SIZE, seeds[i]);
	        }
	    }

	    /**
	     * 像过滤器中添加字符串
	     */
	    public void addValue(String value)  
	    {  
	        //将字符串value哈希为8个或多个整数，然后在这些整数的bit上变为1
	        if(value != null){
	            for(Hash f : func) 
	                bits.set(f.hash(value), true); 
	        }

	    }  

	    /**
	     * 判断字符串是否包含在布隆过滤器中
	     */
	    public boolean contains(String value)  
	    {  
	        if(value == null) 
	            return false;  

	        boolean ret = true;  

	        //将要比较的字符串重新以上述方法计算hash值，再与布隆过滤器比对
	        for(Hash f : func)
	            ret = ret && bits.get(f.hash(value));  
	        return ret;  
	    }  

	    /**
	     * 随机哈希值对象
	     */

	    public static class Hash implements Serializable{
	        private int size;//二进制向量数组大小
	        private int seed;//随机数种子

	        public Hash(int cap, int seed){
	            this.size = cap;
	            this.seed = seed;
	        }

	        /**
	         * 计算哈希值(也可以选用别的恰当的哈希函数)
	         */
	        public int hash(String value){
	            int result = 0;
	            int len = value.length();
	            for(int i = 0; i < len; i++){
	                result = seed * result + value.charAt(i);
	            }

	            return (size - 1) & result;
	        }
	    }
}

如果是想对字符串以外的变量值使用，那么只要先将其转化为字符串即可。

链表实现LRU
在操作系统中常见的缓存淘汰策略有：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
使用链表实现LRU如下：

创建一个链表来维护CPU缓存，链表中的每一个结点距离头结点的距离用于衡量该结点中存放的数据被访问的时间点距离当前时间点的时长，所以链表的表尾表示最早访问的数据。这样一来需要分几种情况来讨论：

遍历链表，如果找到了当前需要访问的数据，就将该结点移到链表的表头。
遍历链表，如果没有找到当前需要访问的数据，就需要将该数据插入链表的表头，但是可能CPU缓存在此时已经满了，所以需要分情况考虑： 

如果CPU缓存没有满，将该数据插入链表即可。
如果CPU缓存满了，将链表的表尾结点删除（最早访问到的数据），然后将新数据插入链表的表头。



这样就实现了LRU缓存。因为不管缓存有没有满，都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 $O(n)$。
数组实现LRU

将数组的首元素作为最新访问的数据，数组末尾元素作为最早访问的数据。这样每一次需要遍历数组寻找数据，时间复杂度为O(n)，如果找到了，需要将该数据移到数组首部，最坏的情况是O(n)，最好的情况是O(1);如果不在数组中，当CPU缓存满的时候需要删除数组末尾的数据，这里删除可以采用直接覆盖的方式，移动前面n-1个数据，然后在数组首部插入新数据，时间复杂度为O(n);如果在数组中，移动数据，插入新数据，时间复杂度为O(n)。根据加法原则，时间复杂度为O(2n+1)=O(n)； 
将数组的尾部元素作为最新访问的数据，数组首部为最早访问的数据。这样每一次需要遍历数组寻找数据，时间复杂度为O(n)，如果找到了，需要将该数据移到数组尾部，最坏的情况是O(n)，最好的情况是O(1);如果不在数组中，当CPU缓存满的时候需要删除数组首部的数据，这里删除可以采用直接覆盖的方式，移动后面n-1个数据，然后在数组尾部插入新数据，时间复杂度为O(n);如果在数组中，移动数据，插入新数据，时间复杂度为O(n)。根据加法原则，时间复杂度还是O(2n+1)=O(n)； 
前两种方法其实思路差不多，只是头部和尾部谁用来存放最早访问的数据。这两种方法都有比较大的缺点，即存在大量移动数组元素的情况，这样的效率很低，为了减少移动的次数，可以使用两个指针new，old来分别指向最新访问的数据、最早访问的数据，一开始数组内元素不断扩充，也就是CPU缓存使用率不断上升的过程，此过程中old指针不断往下标大的方向移动，当CPU缓存满的时候，再次访问数据且恰好不在缓存中时，需要删除元素，删除可以采用直接覆盖的方式，old指针向左移动，指向下标为n-2的位置，然后插入新元素，由于此时只有下标为n-1的位置是空的，所以new指针指向n-1的位置，当再有新元素需要存入缓存时，使用同样的方式来避免大量移动数组中的数据。使用这种方法同样需要先遍历数组，确定是否需要插入数据，时间复杂度为O(n)，而插入删除的时间复杂度为O(1)，总的来说时间复杂度为O(n+1)=O(n)。 

使用单链表实现回文数的判断
回文数需要首先确定中间的元素，然后判断两边的元素是否都对应相等，在确定链表长度的时候，可以使用快慢指针来实现，慢指针每一次移动一个结点，快指针每一次移动两个结点，当快指针到达链表尾的时候，慢指针就到达中间了，此时仅仅花了遍历全部链表元素的一半的时间。在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等，从而判断是否为回文数。 
这里需要避免一个误区，不是快指针跨度越大越好，比如这里快指针跨度为慢指针的100倍，就容易出现一个问题，快指针从某一步开始就跳出链表了，但是也不清楚到底具体链表尾多远，所以需要一个额外的指针来存储快指针上一次存放的地址，当某一次快指针跳出链表的时候，通过这个额外的指针可以回到链表中。回来了还不然，还没有确定链表中间结点，所以，需要重新移动快指针来确定此时与尾结点的距离，然后还要移动相应倍数的慢指针，最终才能确定中间结点，这一过程是比较繁琐的，而且容易出错，所以快慢指针方法的“快指针”不能太“快”。
双链表和单链表的删除操作
删除给定指针指向的结点: 这种情况是已经找到了要删除的元素,我们只需要执行删除操作即可. 针对单链表而言: 单链表如果要删除一个结点q.必须要知道这个结点的前驱结点是谁,修改前驱结点的指针指向即可.单链表找某个结点的前驱结点,只能从头开始遍历. 临界值 p->next == q;说明p就是q的前驱结点.所以在单链表中,找这个前驱结点的平均时间复杂度为O(n),然后执行删除操作的时间复杂度为O(1). 根据时间复杂度分析的加法法则: 删除给定指针指向的结点 --> 单链表的总的时间复杂度为O(n). 针对双链表而言: 双链表要删除一个结点q.也必须得知道这个结点的前驱结点和后继结点. 修改前驱结点的后继指针next和后继结点的前驱指针prev即可.而针对双链表而言,找q的前驱结点和q的后继结点的时间复杂度都为O(1).而执行删除操作(修改指针指向)的时间复杂度也为O(1). 根据时间复杂度分析的加法法则: 删除给定指针指向的结点 --> 双链表的总的时间复杂度为O(1).

CPU缓存技术
 缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。数据库索引操作、MapReduce，是典型的空间换时间。

数组与链表的区别




时间复杂度
数组
链表




插入|删除
$O(n)$
$O(1)$


随机访问
$O(1)$
$O(n)$



 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。

 如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

 对内存要求方面: 数组对内存的要求更高。因为数组需要一块连续内存空间来存放数据。（可能出现的问题就是:内存总的剩余空间足够，但是申请容量较大的数组时申请失败） 链表对内存的要求较低，是因为链表不需要连续的内存空间，只要内存剩余空间足够，无论是否连续，用链表来申请空间一定会成功。

 链表虽然方便，但是内存开销比数组大了将近一倍，假设存储100个整数，数组400个字节的存储空间足够了。但是如果用链表存储100个整数，链表得需要1200个字节的存储空间(C/C++)，因为链表中的每个节点不止要存储数据，还要存储地址，内存的利用率就比数组低太多了。

 由此还可以得出:如果内存容量本身就很小，要存储的数据也比较多。选择数组来存储数据更好，如果内存空间充足，那我们在存储数据的时候到底选择链表还是数组。这个就视具体的业务场景而定了。