数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性 ：代表最多只有左右两个方向。相对应的就是查找的方式很单一。
数组在内存层面来看，最大的特点在于它的空间地址的确定性。 空间地址的确定性也就是
1.起始地址的确定性（起始指针位置）
2.每个元素的位置确定（地址连续）
3.空间大小的确定性
所以 在使用层面，数组的特征必须满足以下条件
1.定义大小（长度）
2.定义类型 （单个数据节点的大小）
那么 空间地址的确定，就带来了指针可以根据偏移量来获取元素信息（寻址公式）。在使用层面也就能支持随机访问。
所以在确定角标的情况下，访问的时间复杂度为O(1)
确定性的空间，在带来访问方便的同时，也就丧失了整体变动的灵活性。对节点数据进行增删操作的时候，需要对整个内存数据进行维护。
譬如： 数组里本来是 1 2 3 5 6 7 null null 需要插入 4 到 3 后面，也就需要把5 6 7 向后挪动。 1 2 3 null 5 6 7 null ---> 1 2 3 4 5 6 7 null ，面对插入和删除的情况 平均时间复杂度就是O(n)
那么 ，为什么数组的起始角标为0呢？
其实起始角标，对应的是数组指针的偏移量。指针是指向第一个元素的起始位置。当需要读取指定元素的时候，只需要 p -> X*index 就好了。如果从1开始，那么在获取元素的时候就变成了 p -> X *(index-1) 这样CPU需要多进行一次减法运算。
链表
链表与数组的本质区别，就是链表的节点包含两部分内容：数据＋下一个节点的地址。这样设计的好处
1.碎片化空间得到充分利用，大小不用受限于连续空间的大小限制。
2.在进行增删操作的时候，将变得非常容易。如下图：
可以看出，增删操作的时间复杂度为O(1)
当然，缺点就是不支持随机访问。只有访问到上一个节点才能知道下一个节点的地址。 所以访问的时间复杂度为O(n)。
链表种类
1.单链表
最后一个元素指向null。这样的好处就是 扩容变得相当简单。
2.循环链表
循环链表就是单链表最后一个元素指向首元素，这样的好处就是读取到最后一个元素的时候，可以快速回到首位。在处理环型结构特点的数据时，能发挥其优势，譬如：哈希环
3.双向链表
双向链表的就是多了一个前置地址，这样的好处就是可以左右两边查找数据，不像上面两种，只能查找下一个节点的数据。这样在实际使用中，如果我需要在某个节点之前插入一个值的时候，时间复杂度就是O(1)，如果是上述两种列表则为O(n)。因为找到这个值之后，还需要重新找它的上一个节点，然后进行插入。
4.双向循环列表
就是循环列表＋双向列表
JAVA开发中数组和链表的选择
通常情况下：
1.当业务数据大部分操作都是读取操作时，数组是比链表更合适。
2.当业务数据会经常进行增删的时候，链表比数组更合适。
特殊情况下：
3.当业务数据非常大，也许读取操作比增删操作多，但是数据量大，每一次增删的数据移动将会异常耗时，此时也需要根据具体情况来选择数据类型，根据业务量和操作类型的权重来求时间复杂度，（链表的空间复杂度大致是数组的两倍），最后在时间和空间上权衡用哪种数据结构。
栈
后进者先出，先进者后出，这就是典型的“栈”结构。
栈和数据、链表的本质区别在于 栈考虑的是实际使用过程中的场景问题，而不仅限于数据的存储方式。
仔细思考一下栈的结构特点，会发现其实数组和链表就已经支持了这种操作，那为什么还会需要栈呢？ 因为数据结构的灵活性会导致实际操作中面临更大的风险和不可控，设计栈这种数据结构，可以把这场景下的的操作风险用数据结构来规避。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
简单来说，顺序栈在入栈和出栈时栈针随数组角标变化就行，当角标用完进行数组扩容。链式栈在入栈时把数据插入头部或者尾部，出栈出栈针指向的数据。
既然栈是建立在数组或链表上的，所以不同类型的栈对面不同场景下，也有不一样的性能差距。
在顺序栈中，将面临数组的扩容带来的系统开销(主要是时间复杂度)。在链式栈中，将面临比数组更大的空间消耗(空间复杂度)。
java中对栈的使用场景
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。栈最经典的场景莫过于方法的调用，方法栈。
队列
先进者先出，这就是典型的“队列”。
刚好跟栈的设计场景相反。
那么实现也是跟栈一样，同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
简单来说，维护两个指针，入队指针，出队指针（对头指针、队尾指针），然后对数组或者链表进行操作。为空时，对头指针与队尾指针位置一样，入队时，队尾指针加一，出队时，出对头指针位置数据，并且对头加一。所以：
顺序队列
在队尾指针到数组最后一个元素的位置之后，再进行入队，则需要进行数据迁移（出了很多数据）或扩容（不够用）
链式队列
链式队列结合几种链表，就会有很多种实现
单链表的情况很好理解，循环链表的情况可以把队列首尾相接，就可以成功避免了数据搬移操作
阻塞队列
阻塞队列就是当调用出队操作的时候，队列里面没有元素，调用操作将被阻塞，直到有新元素入队，则返回。 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
可以预见，像生产者-消费者模型，就可以用阻塞队列来实现。当队列满了，生产者阻塞等待。队列空，消费者阻塞等待。相反情况下生产者消费者才会被唤醒。
java中对队列的使用场景与选择
在一些性能优化中，把同步改异步并且需要把请求先来后到时，便可以使用队列来存储请求。
选择问题：
顺序队列和链式队列的性能比较跟栈其实是大同小异的。顺序队列中将面临数组的扩容带来的系统开销。在链式队列中，将面临比数组更大的内存消耗。在实际开发中选择那种，需要根据实际业务请求情况 在时间和空间上分析之后做取舍。结合数组和链表的选择问题，可以很好的理解具体开发中要如何选择。
跳表
我们来思考一下这种情况，有一个数据有序的链表（上一个数据总比下一个数据小），要你在空间上对链表进行优化，已达到更快速的检索数据。如何实现？
我们可以建立索引，来优化查询速率。如下图：
此时我们会发现，查找的时间复杂度变成了 O(logn)。相比与之前的O(n)，有了很大的提升。但是对于插入操作，需要进一步维护索引，复杂度从O(1)变成了O(logn)。
如果此时再在索引上加索引，能进一步降低时间复杂度。
这就是跳表的思想：链表加多级索引的结构。（空间换时间）
跳表的应用，最典型的就是redis的有序集合。为了支持更快的查询操作，舍弃了空间和插入操作的最佳化。
这里，可以想一下mysql的数据表+索引 用这种方式来设计数据库的数据存储 这两者的本质其实是一样的
散列表
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。数据经过散列函数（hash（）），得到散列值（哈希值），然后以哈希值作为角标把数据存入数组。
在这里 ，可以对其进行优化，用hash表＋链表，就实现了hashMap。
在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的[MD5]、[SHA]、[CRC]等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。
所以我们几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。
【散列函数不是hash，hash只是一种散列算法，散列函数是说的是数据分散的函数，可以是hash算法，也可以是其他自定义的内容】
散列冲突
- 开放寻址法
开放寻址法的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。那么就可以直接往下面找一个空闲的位置，这个方法叫 线性探测 。
那么来想一个问题，很多在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。
二次探测（Quadratic probing）和双重散列（Double hashing）
双重散列： hash1()，hash2()... 第一次hash位置被占，则进行第二次hash。。。
二次探测： 线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1²，hash(key)+2²……
装载因子
我们在初始化数组的时候，数组的长度是固定的，但是当插入的数据越来越大的时候，长度不够使，那么必定要扩容。 那么什么时候扩容呢？
也就是当已占的位置/总长度达到某个比例的时候，就可以扩容，不一定得等到全部占用完才扩容。 这个比例 就是装载因子。
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
动态扩容策略
扩容可以等满了的时候一次性扩容，在扩容的时候一次性进行数据迁移，但是这种一次性数据迁移，会让当前插入操作变得异常的慢。此处可以优化成扩容后，里面进行数据插入，然后返回。等下次操作的时候我再迁移一个数据，再返回。每次操作都迁移一个数据。把数据迁移的工作分摊到每次操作中。但是这样需要对数据迁移的事情进行协调。
2.链表法
就是数组位置加个链表 hashMap就这么实现的
当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？
实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。
散列表碰撞攻击
攻击者故意制造散列值一样的数据，链表法的散列表 这时候散列表退化成了链表，此时查询速度从O(1)变成了O(n) ，如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。
如何设计的一个工业级的散列函数？
结合已经学习过的散列知识，我觉得应该有这样几点要求：
支持快速的查询、插入、删除操作；
内存占用合理，不能浪费过多的内存空间；
性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。
如何实现这样一个散列表呢？根据前面讲到的知识，我会从这三个方面来考虑设计思路：
设计一个合适的散列函数；
定义装载因子阈值，并且设计动态扩容策略；
选择合适的散列冲突解决方法。
关于散列函数、装载因子、动态扩容策略，还有散列冲突的解决办法，具体如何选择，还要结合具体的业务场景、具体的业务数据来具体分析。
二叉树
链式实现：
顺序（数组）实现：
当树是一颗完全二叉树（最底层的叶子节点都靠左，且上层节点都是满的）或者满二叉树（所有父节点都有两个子节点）的时候，数组仅仅浪费了第一个空间，但是当二叉树的节点不完全充分时，就会使得存储情况变成数组很多位置空闲，如下：
这种情况会浪费存储空间。
从上面两种结构来看，当树符合完全二叉树的时候，用数组存储实际上会节省更多的空间。
二叉树的遍历
前序遍历
对于任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
static tree qianxuTrue(tree t){
System.out.print(t.getData().data +":");
if(t.getLeftdata()!=null){
qianxuTrue(t.getLeftdata());
}
if(t.getReatedata()!=null){
qianxuTrue(t.getReatedata());
}
return t;
}
前序遍历可以把链式树，转为数组树。
前序可以很方便地形成一条搜索路径，
中序遍历
对于任意节点，先打印左子树，再打印本身，再打印左子树。
static tree zhongxuTrue(tree t){
if(t.getLeftdata()!=null){
zhongxuTrue(t.getLeftdata());
}
System.out.print(t.getData().data +":");
if(t.getReatedata()!=null){
zhongxuTrue(t.getReatedata());
}
return t;
}
中序遍历可以把动态插入的树，进行排序。
中序遍历二叉搜索树的时候可以得到一个有序序列，
后序遍历
对于任意节点，先打印左子树，再打印右子树，最后打印这个节点本身。
static tree houxuTrue(tree t){
if(t.getLeftdata()!=null){
houxuTrue(t.getLeftdata());
}
if(t.getReatedata()!=null){
houxuTrue(t.getReatedata());
}
System.out.print(t.getData().data +":");
return t;
}
后序遍历就是先输出从最下层开始，从下往上 从左往右 输出，这样能进行数据的累加。
后序通常从从下往上归并数据用，非常实用！
二叉查找树（Binary Search Tree）
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。
二叉搜索树的增删查的时间复杂度为O(logN) 。
我们在散列表那节中讲过，散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？
我认为有下面几个原因：
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。
平衡二叉查找树AVL
二叉树中任意一个节点的左右子树的高度相差不能大于 1。
发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。
红黑树
红黑树是一种不严格符合平衡二叉树要求的平衡二叉树。因为严格的平衡二叉树实现非常复杂，且为了在增删操作中维持它的绝对平衡，需要花费大量时间。所以就设计了红黑树这种不完全的平衡二叉树，来满足工业需求。红黑树的条件如下：
1.根节点是黑色的；
2.每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
3.任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4.每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
红黑树的颜色着色目的是利用颜色值作为二叉树的平衡对称性的检查,只要插入的节点“着色”满足红黑二色的规定，最短路径与最长路径不会相差的太远，红黑树的节点分布就能大体上达至均衡。
AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。它解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。
所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。
堆
上面说到二叉树是可以用数组来实现的，那么，当二叉树是平衡二叉树的时候，并且最后一层所有叶子节点都是靠左，这时候在数组中其实就没有空间浪费。如下图：
那么，我们再设定一个规则，所有的父节点都大于子节点（所有的父节点都小于子节点）【大根堆、小根堆】 。那么，我们就把这种结构叫做堆。
可以预见的是，每一个元素i， 它的叶子节点就为2i、2i＋1。
堆的操作
我们把一个满足最后一层叶子节点都靠左的平衡二叉树调整为父节点都大于子节点，这一过程叫堆化。
1.插入
2.删除
堆的应用
因为堆的特性，父节点总比叶子节点大，所以适合于一些需要最值的场景。譬如：
优先级队列：
队列是先进先出，优先级队列是根据优先级来出元素。
TopK问题 ：
我们维系一个K大小的小根堆，当新来的元素比次堆顶元素大的时候，则删除此堆顶，然后再把新元素插入堆。（这里注意，是先删除堆顶元素，堆化后再插入元素。两次堆化。）
利用堆求中位数（百分之多少位置的数）：
形象一点讲，就是一个数组，分成两部分，前一部分的数据必须比后一部分的最小数大，所以后一部分是小根堆，得出最小数。新进来一个数可以对其进行判断。前面一个为啥是大根堆呢？因为要维持两个堆的大小的比例，需要对数据进行动态调整，所以前一个堆是大根堆就可以得出它的最大数，方便数据迁移。
图
图的元素称为顶点，图的连线称为边，顶点的边数称为度。
边可以有方向，没有方向的图叫无向图，有方向的叫有向图。
对于顶点来说，有方向的边数，指向自己的叫入度，指向别人的叫出度。
每条边都可以有权重，边有权重的图叫权重图。
图的存储
邻接矩阵
图可以用二维数组来存储，i 和 j 之间有关系的话，则把A[i][j]记为1，反正则为0。如果带有权重，则可以记为权重值。入下图:
这里我们会发现一个问题，无向图把矩阵反转之后，其实还是一样的，也就是A[j][i]等于A[i][j]。 这样的话，其实我们只需要取一半的空间就好了，可以对其进行压缩。
用二维数组存储有一个很大的弊端，就是非常浪费内存，如果图的顶点很多，且关系不密切的话，就会有很多空数组节点。 但是有一个好处就是搜索关系特别快，根据角标可以直接获取，而且可以进行矩阵计算。
邻接表
数组存储所有顶点，然后接链表用来存储 度（出度-邻接表）（入度-逆邻接表）。
这样存储的好处就是，节省空间，缺点就是数据查找比邻接矩阵慢。
如何存储微博、微信等社交网络中的好友关系？
针对微博用户关系，假设我们需要支持下面这样几个操作：
- 判断用户 A 是否关注了用户 B；
- 判断用户 A 是否是用户 B 的粉丝；
- 用户 A 关注用户 B；
- 用户 A 取消关注用户 B；
- 根据用户名称的首字母排序，分页获取用户的粉丝列表；
- 根据用户名称的首字母排序，分页获取用户的关注列表。
关于如何存储一个图，前面我们讲到两种主要的存储方法，邻接矩阵和邻接表。因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间。所以，这里我们采用邻接表来存储。
不过，用一个邻接表来存储这种有向图是不够的。我们去查找某个用户关注了哪些用户非常容易，但是如果要想知道某个用户都被哪些用户关注了，也就是用户的粉丝列表，是非常困难的。
基于此，我们需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找某个用户关注了哪些用户，我们可以在邻接表中查找；如果要查找某个用户被哪些用户关注了，我们从逆邻接表中查找。
基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系，所以我们选择改进版本，将邻接表中的链表改为支持快速查找的动态数据结构。选择哪种动态数据结构呢？红黑树、跳表、有序动态数组还是散列表呢？
因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。
如果对于小规模的数据，比如社交网络中只有几万、几十万个用户，我们可以将整个社交关系存储在内存中，上面的解决思路是没有问题的。但是如果像微博那样有上亿的用户，数据规模太大，我们就无法全部存储在内存中了。这个时候该怎么办呢？
我们可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。你可以看下面这幅图，我们在机器 1 上存储顶点 1，2，3 的邻接表，在机器 2 上，存储顶点 4，5 的邻接表。逆邻接表的处理方式也一样。当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。
除此之外，我们还有另外一种解决思路，就是利用外部存储（比如硬盘），因为外部存储的存储空间要比内存会宽裕很多。数据库是我们经常用来持久化存储关系数据的，所以我这里介绍一种数据库的存储方式。
我用下面这张表来存储这样一个图。为了高效地支持前面定义的操作，我们可以在表上建立多个索引，比如第一列、第二列，给这两列都建立索引。
