01、数据结构与算法 - 基础：简介

第一部分：Java数据结构

要理解Java数据结构，必须能清楚何为数据结构？

数据结构:

1、 Data_Structure，它是储存数据的一种结构体，在此结构中储存一些数据，而这些数据之间有一定的关系。
2、 而各数据元素之间的相互关系，又包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
3、 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

数据结构在Java的语言体系中按逻辑结构可以分为两大类：线性数据结构和非线性数据结构。

一、Java数据结构之：线性数据结构

线性数据结构：常见的有一维数组，线性表，栈，队列，双队列，串。

1、一维数组

在Java里面常用的util有：String [], int [], ArrayList, Vector, CopyOnWriteArrayList等。及可以通过一维 数组[] 自己实现不同逻辑结构的Util类。而ArrayList封装了一些 [] 的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的，方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。

数组这种数据结构典型的操作方法，是根据下标进行操作的，所以insert的的时候可以根据下标插入到具体的某个位置，但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新，删除效率也比较低，而按索引查询效率非常高,查询效率时间复杂度是1。

2、 线性表

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的，链表的每一个节点都知道上一个节点、或者下一个节点是谁，通常用Node表示。常见的有顺序链表(LinkedList、Linked***)，单项链表（里面只有Node类），双向链表(两个Node类)，循环链表(多个Node类)等。

操作方法：插入效率比较高，插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了，如果实现的不好，需要整个链路找下去才能找到应该找的元素。所以常见的方法有：add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常见的Uitil有：LinkedList，LinkedMap等，而这两个JDK底层也做了N多优化，可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

3: 栈Stack

栈,最主要的是要实现先进后出，后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈，pop()出栈。

java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构，就是线程栈，来保证当前线程的执行顺序。

4、队列

队列，队列是一种特殊的线性数据结构，队列只能允许在队头，队尾进行添加和查询等相关操作。队列又有单项有序队列，双向队列，阻塞队列等。

Queue这种数据结构注定了基本操作方法有：add(E e)加入队列，remove(),poll()等方法。

队列在Java语言环境中是使用频率相当高的数据结构，所有其实现的类也很多来满足不同场景。

使用场景也非常多，如线程池，mq，连接池等。

5、串

串：也称字符串，是由N个字符组成的优先序列。在Java里面就是指String, 而String里面是由chat[]来进行储存。

KMP算法： 这个算法一定要牢记，Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是：在字符串比对的时候，主串的比较位置不需要回退的问题。

二、Java数据结构之：非线性数据结构

非线性数据结构：常见的有：多维数组，集合，树，图，散列表(hash).

1、多维数组

一维数组前面咱也提到了，多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类，而java里面tree和图底层的native方法用了多维数组来储存。

2、集合

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

3、树

树形结构，作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成，可以有多个子节点。树，显然是由递归算法组成。

树的特点：

• 在一个树结构中，有且仅有一个结点没有直接父节点，它就是根节点。
• 除了根节点，其他结点有且只有一个直接父节点
• 每个结点可以有任意多个直接子节点。

树的数据结构又分如下几种：

1) 自由树/普通树：对子节点没有任何约束。

2) 二叉树：每个节点最多含有两个子节点的树称为二叉树。

2.1) 一般二叉树：每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

2.2) 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

2.3) 满二叉树：所有的节点都是二叉的二叉树成为满二叉树。

3) 二叉搜索树/BST：binary search tree,又称二叉排序树、二叉查找树。是有序的。要点：如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值。

3.1) 二叉平衡树：二叉搜索树，是有序的排序树，但左右两边包括子节点不一定平衡，而二叉平衡树是排序树的一种，并且加点条件，就是任意一个节点的两个叉的深度差不多（比如差值的绝对值小于某个常数，或者一个不能比另一个深出去一倍之类的）。这样的树可以保证二分搜索任意元素都是O(log n)的，一般还附带带有插入或者删除某个元素也是O(log n)的的性质。

为了实现，二叉平衡树又延伸出来了一些算法，业界常见的有AVL、和红黑算法，所以又有以下两种树：

3.1.1) AVL树：最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

3.1.2) 红黑树：通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。

红黑树的5条性质：

1、 每个结点要么是红的，要么是黑的。
2、 根结点是黑的。
3、 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4、 如果一个结点是红的，那么它的俩个儿子都是黑的。
5、 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

4) B-tree：又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子（m>=2）。它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。

4) B+tree：又称B+。是B-树的变体，也是一种多路搜索树。

树总结：
树在Java里面应用的也比较多。非排序树，主要用来做数据储存和展示。而排序树，主要用来做算法和运算，HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

4、Hash

Hash概念：

1、 Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。
2、 所谓的Hash算法都是散列算法，把任意长度的输入，变换成固定长度的输出，该输出就是散列值.（如：MD5,SHA1,加解密算法等）
3、 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java中的hashCode：

1、 我们都知道所有的class都是Object的子类，既所有的class都会有默认Object.java里面的hashCode的方法，如果自己没有重写，默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。
2、 最大的特性是：不同的对象，不同的值有可能计算出来的hashCode可能是一样的。

Hash表：

1、 Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表。而Hash表就是综合了这两种数据结构。
2、 如：HashTable,HashMap。这个时候就得提一下HashMap的原理了，默认16个数组储存，通过Hash值取模放到不同的桶里面去。（注意：JDK1.8此处算法又做了改进，数组里面的值会演变成树形结构
3、 哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”。

一致性Hash：

1、 我们查看一下HashMap的原理，其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的，所有在分布式环境下，应运而生了一致性Hash算法。
2、 用意和hashCode的用意一样，只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。
3、 而一致性Hash需要注意的就是默认分配的桶比较多些，而当其中一台机器挂了，影响的面比较小一些。
4、 需要注意的是，相同的内容算出来的hash一定是一样的。既：幂等性。