线性结构

（一）概念

1．基本

线性结构包括表，栈，队列

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
线性结构中存在两种操作受限的使用场景，即队列和栈。栈的操作只能在线性表的一端进行，就是我们常说的先进后出（FILO），队列的插入操作在线性表的一端进行而其他操作在线性表的另一端进行，先进先出（FIFO），由于线性结构存在两种存储结构，因 此队列和栈各存在两个实现方式。

2．顺序表

顺序表（顺序存储）
按照我们的习惯，存放东西时，一般是找一块空间，然后将需要存放的东西依次摆放，这就是顺序存储。计算机中的顺序存储是指在内存中用一块地址连续的空间依次存放数据元素，用这种方式存储的线性表叫顺序表其特点是表中相邻的数据元素在内存中存储位置也相邻，如下图：

 树(Tree)

1．二叉树

（二）红黑树

红黑树是特殊的二叉树.

红黑树:
特点 趋近于平衡树,查询的速度非常快,查询叶子节点最大次数和最小次数不能超过2倍.


二叉树的问题
普通的二叉树作为数据存储工具有很大的又是,可以快速的插入,删除和查找数据项,但是仅仅是相对于插入随机数据,如果插入的数据是有序的,速度就变得特别慢了


平衡树和非平衡树

插入随机的数据,平衡树
插入有序的数据,非平衡树

红黑规则
1. 每个节点不是红色就是黑色的
2. 根总是黑色的
3. 如果节点是红色的,则它的子节点必须是黑色的(不能是红的和红的连在一起)
4. 从根节点到叶节点的每条路径,必须包含相同数目的黑色节点.

纠正违规操作,将不符合红黑规则的树纠正为红黑树
1. 改变节点的颜色
2. 执行旋转操作

左旋
当插入大于E,小于H的时候

1．2 -3 树(最基础的B树)

简单称为三分查找




2-node 二节点就是图中的只有一个字母的节点,
3-node 图中放了两个字母的就是三节点.
4-node

3-node代表可以有三个岔路,三个子节点

左边字母都是在N前面的,右边字母都是在N后面的,A在D前面,所以在最左边,而E F 在D和J的中间,所以在中间节点,而K在J的后面,所以K在右边节点.




2-3树检索效率会比二分查找树效率要高


插入W的时候,此时W比R大,就到右边了,但是右边节点有三个元素,违反了2 - 3 树了, 就会给该节点的中间值元素上移,所以就会成节点装 R W 两个.




添加Z节点,如果发现上移不了的话,层级就会分裂了,比如说Z节点分裂出来了.

2．B树

B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。”

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
根节点至少有两个子节点
每个节点有M-1个key，并且以升序排列
位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:


可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。

B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
的演示动画：
https://files.cnblogs.com/yangecnu/btreebuild.gif

3．B+树

B+树有链表的形式, 用到了计算机的局部性原理

B+树是对B树的一种变形树，它与B树的差异在于：

有k个子结点的结点必然有k个关键码；
非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

如下图，是一个B+树:


下图是B+树的插入动画：
https://files.cnblogs.com/yangecnu/Bplustreebuild.gif

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：


分析
对B树和B+树的分析和对前面讲解的2-3树的分析类似，
对于一颗节点为N度为M的子树，查找和插入需要logM-1N ~ logM/2N次比较。这个很好证明，对于度为M的B树，每一个节点的子节点个数为M/2 到 M-1之间，所以树的高度在logM-1N至logM/2N之间。
这种效率是很高的，对于N=62*1000000000个节点，如果度为1024，则logM/2N <=4，即在620亿个元素中，如果这棵树的度为1024，则只需要小于4次即可定位到该节点，然后再采用二分查找即可找到要找的值。
应用
B树和B+广泛应用于文件存储系统以及数据库系统中，在讲解应用之前，我们看一下常见的存储结构：

我们计算机的主存基本都是随机访问存储器(Random-Access Memory，RAM)，他分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM快，但是也贵的多，一般作为CPU的高速缓存，DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机器操作，所以访问速度非常快，具体的访问原理可以查看CSAPP，另外，他们是易失的，即如果断电，保存DRAM和SRAM保存的信息就会丢失。
我们使用的更多的是使用磁盘，磁盘能够保存大量的数据，从GB一直到TB级，但是 他的读取速度比较慢，因为涉及到机器操作，读取速度为毫秒级，从DRAM读速度比从磁盘度快10万倍，从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构：

如上图，磁盘由盘片构成,每个盘片有两面，又称为盘面(Surface)，这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(spindle)，他使得盘片以固定的旋转速率旋转，通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM。磁盘包含一个多多个这样的盘片并封装在一个密封的容器内。上图左，展示了一个典型的磁盘表面结构。每个表面是由一组成为磁道(track)的同心圆组成的，每个磁道被划分为了一组扇区(sector).每个扇区包含相等数量的数据位，通常是（512）子节。扇区之间由一些间隔(gap)隔开,不存储数据。

以上是磁盘的物理结构，现在来看下磁盘的读写操作：


如上图，磁盘用读/写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值。对磁盘的访问时间分为 寻道时间，旋转时间，以及传送时间。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建一个节点的同时，直接申请一个页的空间( 512或者1024)，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。如，将B树的度M设置为1024，这样在前面的例子中，600亿个元素中只需要小于4次查找即可定位到某一存储位置。

同时在B+树中，内节点只存储导航用到的key，并不存储具体值，这样内节点个数较少，能够全部读取到主存中，外接点存储key及值，并且顺序排列，具有良好的空间局部性。所以B及B+树比较适合与文件系统的数据结构。下面是一颗B树，用来进行内容存储。

另外B/B+树也经常用做数据库的索引，这方面推荐您直接看张洋的MySQL索引背后的数据结构及算法原理 这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。

总结
在前面两篇文章介绍了平衡查找树中的2-3树，红黑树之后，本文介绍了文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

Windows：HPFS文件系统
Mac：HFS，HFS+文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
数据库：ORACLE，MYSQL，SQLSERVER等中

 数据结构

1．什么是数据结构

就是数据之间的关系,提高程序的效率,
1. 逻辑关系: 人为认为
a) 集合: 在一个范围内有多个数据,数据之间没有关系
b) 线性: 1对1的关系
c) 树形: 一对多(一个节点下面有多个节点,下面的一个节点又对应多个节点)
d) 图: 多对多
2. 物理关系: 在内存存储
a) 顺序存储 : 在内存中存放数据是连续的内存空间存放的(数组,数组的效率非常高,但是长度是固定的)
b) 链式存储 : 链表

（二）hash(哈希,也叫散列)

hash算法就是把任意长度值(key)通过散列算法变成固定长度的key地址,通过这个地址进行访问的数据结构

它通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度

这个映射函数叫做散列函数,存放记录的数组叫散列表.


hash的key不能重复, hash不支持范围查询 和排序查询

优点: 时间复杂度高, 只需要查询一次就可以查询出来数据,精确查找快.

（三）堆(Heap)

关于内存可以说是Java中的重要概念，而栈和堆又是内存中的两个重要部分。怎样理解栈和堆？栈可以理解为内存中一片连续的区域，而堆可以理解为内存中一片分散的区域。可以说，栈是用来运行程序的区域，当在栈里应用一个值的时候，这个值就会指向堆中的一个位置。其实可以理解为一种函数关系。在进一步理解堆和栈的关系，则要先理解一下Java虚拟机。
在学Java的过程中，有些人会写代码，但对数据的来源并不清楚，代码是怎样运行和实现的，和JVM也有着密切的关系。
一个Java程序需要在Java虚拟机（JVM）上运行才能得以实现，当java程序启动时，java虚拟机也会自动地开启，当java程序的所有线程都结束的时候，自然而然的，载体也会停止工作。
jvm在启动时，会开启虚拟机自身的线程，例如垃圾回收线程，还有java程序的线程，创建的线程名，同时创建对象和变量，这些都会放在JVM的栈中，而线程对象字符串，new的对象，变量，都会放在堆中；最后，变量的值，则会放在方法中，方法区和堆都是共享的，通过以上的叙述，就可以看出一些JVM的运行机制。

如果从数据的调用方面和对象的创建方面来说的话，堆，栈，方法区，是一个整体存在的东西，例如，一个String b=new String(“test”); 我现在new了一个对象b这个对象名放在栈中，b这个对象值（对象字符串）放在堆中，”test”就会放到方法区中，这样的分工机制有效提升了程序运行的速度。
由此可见，堆是java应用程序最密切的内存空间。可以说所有的对象都存在堆中。而且堆的管理是自动化的，通过GC回收机制，垃圾对象会自动清理，不需要显式释放。
因为垃圾回收机制各不相同，所以java堆可能有不同的结构。最常见的是将整个java堆分为新生代和老年代。尚学堂陈老师指出，老年代的数据最终要被消除，新生代存放新对象或者年龄不大的对象，老年代存放老年对象。新生代有可能分为eden区、s0区和s1区，s0区和s1区也被称之为 from 到to区域。
一般情况下，对象首先被分配在eden区，再一次新生代回收后，如果对象还存在，则会进入s0或者s1，而当对象年龄达到一定条件后，就会老龄化进入老年代。
以上就是对Java中堆与栈的理解，希望对正在学Java的朋友有所帮助。


于大多数应用来说，Java堆（Java Heap）是Java虚拟机所管理的内存中最大的一块。Java堆是被所有线程共享的一块内存区域，在虚拟机启动时创建。此内存区域的唯一目的就是存放对象实例，几乎所有的对象实例都在这里分配内存。这一点在Java虚拟机规范中的描述是：所有的对象实例以及数组都要在对上分配内存，但是随着JIT编译器的发展与逃逸分析技术逐渐成熟，栈上分配、标量替换优化技术将会导致一些微妙的变化发生，所有的对象都分配在堆上也渐渐变得不是那么“绝对”了。
Java堆是垃圾收集器管理的主要区域，因此很多时候也被称作“GC堆”（Garbage Collected heap）。从内存回收的角度来看，由于现在收集器基本都采用分代收集算法，所以Java 堆中还可以细分为：新生代和老年代；在细致一点的有Eden空间、From Survivor空间、To Survivor空间等。从内存分配的角度看，线程共享的Java 堆中可能划分出多个线程私有的分配缓冲区。不过无论如何划分，都与存放内容无关，无论哪个区域，存储的都仍然是对象实例，进一步划分的目的是为了更好地回收内存，或者更快地分配内存。
根据Java虚拟机规范的规定，Java堆可以处于物理上不连续的内存空间中，只要逻辑上是连续的即可，就像我们的磁盘空间一样。在实现时，既可以实现固定大小的，也可以是扩展的，不过当前主流的虚拟机都是按照可扩展来实现的。如果在堆中没有内存完成实例分配，并且堆也无法再扩展时，将会抛出OutOfMemoryError异常。

（四）数组(Array)

1．概念

一维数组概念

二维数组概念

2．一维数组的使用

3．二维数组的使用

4．数组的基本操作

遍历数组

填充替换数组元素

对数组排序

复制数组

数组查询

（五）栈(stack)

后进先出,先进后出(类似一个箱子,放在箱子底下最后一个出来)

栈底层是一个数组

不能随机访问(不能搜索操作)
其实成功完成顺序表和链表之后，栈已经没太多可说的了，主要是逻辑上的不同，毕竟栈也是一种特殊的线性结构。栈是一种操作限定在表尾部进行的线性表，表尾称为栈顶（Top），另一端固定不动，称为栈底（Bottom）。进栈、出栈示意图如下：

（六）链表(Linked List)

　假如我们现在要存放一些物品，但是没有足够大的空间将所有的物品一次性放下（电脑中使用链式存储不是因为内存不够先事先说明一下…，具体原因后续会说到），同时设定我们因为脑容量很小，为了节省空间，只能记住一件物品位置。此时我们很机智的找到了解决方案：存放物品时每放置一件物品就在物品上贴一个小纸条，标明下一件物品放在那里，只记住第一件物品的位置，寻找的时候从第一件物品开始寻找，通过小纸条我们可以找到所有的物品，这就是链式存储。链表实现的时候不再像线性表一样只存储数据即可，还有下一个数据元素的地址，因此先定义一个节点类(Node)，记录物品信息和下一件物品的位置，我们把物品本身叫做数据域，存储下一件物品地址信息的小纸条称为引用域。链表结构示意图如下：
　　寻找物品的时候发现了一个问题，我们从一件物品找下一件物品的时候很容易，但是如果要找上一件物品就得从头开始找，真的很麻烦。为了解决这个问题我们又机智了一把，模仿之前的做法，在存放物品的时候多放置一个小纸条记录上一件物品的位置，这样就可以很快的找到上一件物品了。我们把这种方式我们称为双向链表，前面只放置一张小纸条的方式称为单向链表。

　由于数据存储结构不同导致使用场景上的巨大差异，顺序表由于元素连续具有随机存储的特点，所以查找数据很方便效率很高，但是插入、删除操作为了确保数据元素连续，需要移动大量的数据导致效率很低。而链表由于存储空间不要求连续，插入、删除只需修改相邻元素的引用域地址即可，所以效率很高，但查询需要从头引用开始遍历链表，效率很低。因此，如果只是进行查找操作而不经常插入、删除线性表中的数据元素，则使用顺序存储结构，反之，使用链式存储结构。

（七）图(Graph)

 算法

（一）Java中的hash算法

· Object.hashCode 直接获取内存地址
· Integer.hashCode 直接返回intValue
· String.hashCode 根据字符串内容生成hashCode,字符串内容一样则hashCode也相同
· 其它场景中的hash算法
· MD5 MD4
· SHA

1．hash算法的用途

· 哈希查找,哈希表
· 秒传(百度网盘,我们上传一个电影,它把影片hash出来一个字符串,再用字符流去数据库里面查找,如果有相同的字符串就说明这个影片已经存在了,其实就不需要传了.其实hash可以当一个唯一签名,两个内容相等的话,它的签名一定是一样的.)
· HashMap
· 加解密,MD5 , SHA
· Git
· 比特币,区块链
· Redis MongoDB