当前位置 : 首页 » 文章分类 :  开发  »  Java面试准备-(11)计算机基础

Java面试准备-(11)计算机基础

Java面试准备之计算机基础


算法

树和二叉树

完全二叉树(Complete Binary Tree)

完全二叉树(Complete Binary Tree)
在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。

完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉搜索树(二叉排序树)(BST)

二叉查找树(也叫二叉搜索树)(Binary Search Tree)就是二叉排序树(Binary Sort Tree)

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点,那么会有y.key<=x.key;如果y是x右子树中的一个节点,那么有y.key>=x.key。

查找与性能分析O(logn)->O(n)

若假设树的高度是h,那么查找过程的时间复杂度就是O(h)。
若n个结点的二叉搜索树是平衡的,查找复杂度为O(logn),最坏情况下(比如用有序数组创建BST),二叉查找树退化成了一棵具有n个结点的线性链(单边树),查找复杂度为O(n)。

递归实现:

//递归实现
Tree_Search(x, k):
if x == NIL or x.key == k :
    return x
if k < x.key
    return Tree_Search(x.left, k)
else return Tree_Search(x.right, k)

非递归迭代实现:

//非递归迭代实现
Tree_Search(x, k) :
while x!=NIL and k!=x.key:
    if k < x.key
        x = x.left
    else x = x.right
return x

深入理解二叉搜索树(BST)
https://blog.csdn.net/u013405574/article/details/51058133


平衡二叉树(AVL)

AVL树是根据它的发明者G. M. Adelson-Velskii和E. M. Landis命名的。AVL树本质上还是一棵二叉搜索树,它的特点是:
本身首先是一棵二叉查找树。带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1

平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡(通过旋转实现)。

平衡二叉树很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

平衡二叉树详解
https://blog.csdn.net/u010442302/article/details/52713585


红黑树(RBT)

R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树是一种近似平衡的二叉查找树,它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。

红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树的插入

将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。

1、把红黑树当做BST插入结点

第一步: 将红黑树当作一颗二叉查找树,将节点插入。
红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
好吧?那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树!

2、把插入结点染为红色

第二步:将插入的节点着色为”红色”。
为什么着色成红色,而不是黑色呢?为什么呢?在回答之前,我们需要重新温习一下红黑树的特性:
(1) 每个节点或者是黑色,或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
(4) 如果一个节点是红色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
将插入的节点着色为红色,不会违背”特性(5)”!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。

为什么将插入结点看做红色?

因为要满足红黑树的这五条性质,如果我们插入的是黑色节点,那就违反了性质五,需要进行大规模调整,如果我们插入的是红色节点,那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时,违反性质二,所以,我们把要插入的节点的颜色变成红色。

3、旋转与着色使之再次成为红黑树

在树的结构发生改变时(插入或者删除操作),红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,集改变检索树的结构关系。结构调整过程包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)。

红黑树的应用

红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

1、广泛用于C++的STL中,map和set都是用红黑树实现的.
2、著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.
3、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查.
4、ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
5、java中TreeMap的实现.

红黑树与AVL对比

平衡二叉树是一种严格的平衡树,平衡因子小于等于1。由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.

AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。
结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.
查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。
插入删除对比:

  1. AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。
  2. 如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。
  3. 当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。
  4. AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。
    总体评价:大量数据实践证明,RBT的总体统计性能要好于平衡二叉树。

二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比
https://blog.csdn.net/z702143700/article/details/49079107

浅谈AVL树,红黑树,B树,B+树原理及应用
https://blog.csdn.net/whoamiyang/article/details/51926985

红黑树(一)之 原理和算法详细介绍
http://www.cnblogs.com/skywang12345/p/3245399.html

最容易懂得红黑树
https://blog.csdn.net/sun_tttt/article/details/65445754

史上最清晰的红黑树讲解(上)(结合Java TreeMap讲解)
https://www.cnblogs.com/CarpenterLee/p/5503882.html

漫画:什么是红黑树? - 程序员小灰
http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191832&idx=1&sn=12017161025495c6914b5ab9397baa59


B-树(B树)

B-树就是B树,也就是英文中的B-Tree,中间是横线不是减号,一般直接读作B树(读作B减树不规范,但好多人这么读)

一个m阶的B树具有如下几个特征:
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

为什么数据库索引使用B树?

数据库索引是存储在磁盘上的,索引大小可能有几个G甚至更多。当利用索引查询的时候,不能把整个索引都加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页对应着索引树的结点。每次加载一个结点,都需要进行一次磁盘IO,磁盘IO的次数等于索引树的高度。

为了减少磁盘IO的次数,需要把原本“瘦高”的树结构变得“矮胖”。B树是一种多路平衡查找树,由于是多叉的,对于同样的结点个数n,B树比平衡二叉树的高度更小,这就是B树相对于平衡二叉树的优点。

由于B树每个节点上有多个key值,所以查询时比较次数其实不比平衡二叉树少,但相对于耗时的磁盘IO,内存中的比较耗时几乎可以忽略。只要高度足够低,IO次数足够少,就可以提高查找性能。

漫画:什么是B-树?
http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0


B+树

B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

一个m阶的B+树具有如下几个特征:
1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

B+树与B树对比

B+树相比于B树的优势:
1、IO次数更少(磁盘IO代价低)
相对于B树,B+树每个节点存储的关键字数更多,这就意味着,数据量相同的情况下,B+树的层级更少(高度更低、更矮胖),所以IO次数更少,查询数据更快。
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

2、查询性能稳定
B+树中所有关键字指针都存在叶子节点,所以每次查询都必须最终查到叶子节点上,而B树只要找到匹配元素即停止。所以B树查找性能并不稳定(最好情况只查根节点,最坏情况查到叶子节点),而B+树每次查找都是稳定的。
由于内部结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

3、范围查询方便(顺序遍历)
B树中做范围查询只能先找到边界点(比作左边界),再做中序遍历直到右边界,很繁琐。由于B+树中所有叶子节点形成有序链表,所以B+树中做范围查询只需先找到边界点(比如左边界),然后在链表上顺序遍历到右边界即可。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能。

漫画:什么是B+树?
https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191027&idx=1&sn=4ba22e3ec8bd149f69fc0aba72e4347e

浅谈AVL树,红黑树,B树,B+树原理及应用
https://blog.csdn.net/whoamiyang/article/details/51926985

B树与B+树
https://blog.csdn.net/guoziqing506/article/details/64122287

B树和B+树与索引

B树主要应用于文件系统以及部分数据库索引,比如著名的非关系数据库MongoDB
而大部分关系型数据库,比如mysql,则使用B+树作为索引。

在 MySQL 中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。

不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。

一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引。当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。

B-树和B+树的应用:数据搜索和数据库索引
http://blog.jobbole.com/107800/


排序

快速排序(nlogn不稳定)

思想:首先选取一个枢纽元(pivot),然后将数据划分成左右两部分,左边的大于(或等于)枢纽元,右边的小于(或等于枢纽元),最后递归处理左右两部分。

步骤及实现

步骤:
1、选择枢轴
2、按枢轴分割
3、递归对左右两个子序列进行快速排序

按枢轴分割
改进的双向扫描
枢纽元保存在一个临时变量中,这样左端的位置可视为空闲。j从右向左扫描,直到A[j]小于等于枢纽元,检查i、j是否相交并将A[j]赋给空闲位 置A[i],这时A[j]变成空闲位置;i从左向右扫描,直到A[i]大于等于枢纽元,检查i、j是否相交并将A[i]赋给空闲位置A[j],然后 A[i]变成空闲位置。重复上述过程,最后直到i、j相交跳出循环。最后把枢纽元放到空闲位置上。

代码实现

public static void quickSort(int[] arr){
    qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
    if (low < high){
        int pivot=partition(arr, low, high);        //将数组分为两部分
        qsort(arr, low, pivot-1);                  //递归排序左子数组
        qsort(arr, pivot+1, high);                  //递归排序右子数组
    }
}
private static int partition(int[] arr, int low, int high){
    int pivot = arr[low];    //枢轴记录
    while (low<high){
        while (low<high && arr[high]>=pivot) --high;
        arr[low]=arr[high];            //交换比枢轴小的记录到左端
        while (low<high && arr[low]<=pivot) ++low;
        arr[high] = arr[low];          //交换比枢轴小的记录到右端
    }
    //扫描完成,枢轴到位
    arr[low] = pivot;
    //返回的是枢轴的位置
    return low;
}

时间复杂度

快速排序最佳运行时间O(nlogn),最坏运行时间O(N^2),随机化以后期望运行时间O(nlogn)

可以看出,每一次调用partition()方法都需要扫描一遍数组长度(注意,在递归的时候这个长度并不是原数组的长度n,而是被分隔出来的小数组,即n×(2^(-i))),其中i为调用深度。而在这一层同样长度的数组有2^i个。那么,每层排序大约需要O(n)复杂度。而一个长度为n的数组,调用深度最多为log(n)层。二者相乘,得到快速排序的平均复杂度为O(nlogn)。

通常,快速排序被认为是在所有同数量级的排序方法中,平均性能最好。

快速排序对数组中的数据分布很敏感,当数据分布较随机时,快速排序性能最好,复杂度为O(nlogn),如果数组已基本有序,快排性能最差,复杂度为O(N^2),退化为冒泡排序。


快速排序优化

优化枢轴选取

select_pivot(T A[], int p, int q),该函数从A[p…q]中选取一个枢纽元并返回,且枢纽元放置在左端(A[p]的位置)。
固定选取:取序列的第一个元素为枢轴
随机选取:顾名思义就是从A[p…q]中随机选择一个枢纽元
三数取中:即取三个元素的中间数作为枢纽元,一般是取左端、右断和中间三个数,也可以随机选取。

分割到一定程度后使用插入排序

当待排序序列的长度分割到一定大小后,使用插入排序。
原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排

if (high - low + 1 < 10)
{
    InsertSort(arr,low,high);
    return;
}//else时,正常执行快排
递归栈优化(尾递归优化)

此外,快速排序需要一个递归栈,通常情况下这个栈不会很深,为log(n)级别。但是,如果每次划分的两个数组长度严重失衡,则为最坏情况,栈的深度将增加到O(n)。此时,由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销,这里甚至可能达到恐怖的O(n^2)空间复杂度。所以,快速排序的最差空间复杂度不是一个定值,甚至可能不在一个级别。

为了解决这个问题,我们可以在每次划分后比较两端的长度,并先对短的序列进行排序(目的是先结束这些栈以释放空间),可以将最大深度降回到O(㏒n)级别。

此外,快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化
原因:如果待排序的序列划分极端不平衡,递归的深度将趋近于n,而栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多。优化后,可以缩减堆栈深度,由原来的O(n)缩减为O(logn),将会提高性能。

private static void qsort(int[] arr, int low, int high){
    while (low < high){
        int pivot=partition(arr, low, high);
        qsort(arr, low, pivot-1);
        low = pivot + 1;  //尾递归改为循环
    }
}

其实这种优化编译器会自己优化,相比不使用优化的方法,时间几乎没有减少

快速排序(简介、清晰)
https://www.cnblogs.com/codeskiller/p/6360870.html

三种快速排序以及快速排序的优化
http://blog.csdn.net/insistgogo/article/details/7785038

快速排序 优化 详细分析
http://blog.csdn.net/zuiaituantuan/article/details/5978009


快速排序应用

寻找第k小的数

输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。(剑指offer,面试题30,页数:167)
随机选取枢轴进行一次分割,得到分割后的枢轴位置loc,如果loc=k,则找到第k小的数;如果loc>k,继续在左边找;如果loc<k,继续在右边找

求数组的中位数(出现次数过半的数)

随机选取枢轴进行一次分割,得到分割后枢轴的位置loc,如果loc=mid,则找到中位数;如果loc<mid,在右边子序列中找中位数;如果loc>mid,在左边子序列中找中位数。

//找出 arr 中 第  n/2  大的那个元素
    public static int media_number(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int center = (left + right) / 2;

        int pivot_index = parition(arr, left, right);//枢轴元素的索引

        while(pivot_index != center)
        {
            if(pivot_index > center){
                right = pivot_index - 1;
                pivot_index = parition(arr, left, right);
            }
            else{
                left = pivot_index + 1;
                pivot_index = parition(arr, left, right);
            }
        }
        return arr[center];
    }

快速排序及其应用
https://www.2cto.com/kf/201308/235343.html


归并排序(nlogn稳定)

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略

归并排序将待排序数组A[1..n]分成两个各含n/2个元素的子序列,然后对这个两个子序列进行递归排序,最后将这两个已排序的子序列进行合并,即得到最终排好序的序列。

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(NlogN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

图解排序算法(四)之归并排序
http://www.cnblogs.com/chengxiao/p/6194356.html

白话经典算法系列之五 归并排序的实现(讲的真好)
https://blog.csdn.net/yuehailin/article/details/68961304

排序算法(2)——归并排序
https://blog.csdn.net/tmylzq187/article/details/51816084


Timsort(归并加插入)(nlogn稳定)

TimSort排序算法是Python和Java针对对象数组的默认排序算法。TimSort排序算法的本质是归并排序算法,只是在归并排序算法上进行了大量的优化。对于日常生活中我们需要排序的数据通常不是完全随机的,而是部分有序的,或者部分逆序的,所以TimSort充分利用已有序的部分进行归并排序。

TimSort算法的核心在于利用数列中的部分有序。

Timsort是结合了归并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用(TimSort 是 Python 中 list.sort 的默认实现)。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,现在Java SE7和Android也采用Timsort算法对数组排序。

TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退,将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字,而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列,每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run,这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。

综上述过程,Timsort算法的过程包括
(0)如何数组长度小于某个值,直接用二分插入排序算法
(1)找到各个run,并入栈
(2)按规则合并run

run是已经排好序的一块分区。run可能会有不同的长度,每个run最少要有2个元素。Timesort根据run的长度来选择排序的策略。例如如果run的长度小于某一个值,则会选择插入排序算法来排序。

Timesor按照升序和降序划分出各个run:

  • run如果是是升序的,那么run中的后一元素要大于或等于前一元素;
  • 如果run是严格降序的,即run中的前一元素大于后一元素,需要将run 中的元素翻转(这里注意降序的部分必须是“严格”降序才能进行翻转。因为 TimSort 的一个重要目标是保持稳定性stability。如果在 >= 的情况下进行翻转这个算法就不再是 stable)。

Timsort原理介绍
https://blog.csdn.net/yangzhongblog/article/details/8184707

简易版的TimSort排序算法
https://www.cnblogs.com/nullzx/p/6014471.html

深入理解 timsort 算法(1):自适应归并排序
http://blog.jobbole.com/99681/


希尔排序(减少插入排序的移动次数)

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量,到增量为1时,其实多数情况下只需微调即可,不会涉及过多的数据移动。

希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量),其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

图解排序算法(二)之希尔排序
https://www.cnblogs.com/chengxiao/p/6104371.html


堆排序(nlogn不稳定)

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
用简单的公式来描述一下堆的定义就是:
大顶堆:arr[i] >= arr[2i+1] 且 arr[i] >= arr[2i+2]
小顶堆:arr[i] <= arr[2i+1] 且 arr[i] <= arr[2i+2]

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换(或者说将堆顶输出),此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

图解排序算法(三)之堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html


栈和队列

最大栈(最小栈)

用java实现栈,增加getMaxValue()方法(最大栈)
思路分析:在栈中实现一个方法 每一调用该方法可以获得当前栈中的最大值 通过把两个栈封装在一个栈中 其中的一个栈存放正常的元素 另一个栈max只存最大元素

如果push()一个数 如果这个数比 最大栈的栈顶值max.peek()还要大 说明插入的该元素是栈中的最大的元素,将其同时插入max。 否则 在max栈中插入max.peek(),即之前的最大值。出栈时同时将max栈顶pop即可。

实现一个最大栈、最小栈
http://blog.csdn.net/u013078669/article/details/51029935

用两个栈实现一个队列

真正性能较高的,其实是另一个变种。即:
入队时,将元素压入s1。
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。但在实际面试中很少有人说出,可能是时间较少的缘故吧。

用两个栈实现一个队列——我作为面试官的小结
https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

两个栈实现队列 两个队列实现栈
https://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

两个队列实现一个栈

q1是专职进出栈的,q2只是个中转站。元素集中存放在一个栈中,但不是指定(q1 或 q2)。
定义两个指针:pushtmp:指向专门进栈的队列q1; tmp:指向临时作为中转站的另一个栈q2

入栈:直接入pushtmp所指队列即可
出栈:把pushtmp的除最后一个元素外全部转移到队列tmp中,然后把刚才剩下q1中的那个元素出队列

使用两个队列实现一个栈
https://www.cnblogs.com/ming-zi/p/6379697.html

两个栈实现队列 两个队列实现栈
https://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html


用java实现生产者消费者模式


数组/链表

()判断两个单链表是否相交,找出交点?(哗啦啦一面)
分别遍历两个链表,最后一个结点相同(用==比较引用相同)则说明有交点。
同时开始遍历两个链表,其中一个结束后开始计数,得到两个链表长度查m,此时也知道了哪个链表更长。
较长的链表先走m步,然后较短的链表开始,不断比较结点是否相等,遇到的第一个相等结点就是交点。


跳跃表(skiplist)

有时候会被问到链表如果做到二分搜索,可能会有部分的人会去把链表中的值保存到数组来进行二分,但是如果知道跳跃表的话,那么这个数据结构就可以解决这个困惑,它允许快速查询一个有序连续元素的数据链表,它的效率可以做到和二分相同,都是O(logn)的平均时间复杂度,其空间复杂度为O(n)。

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。
像是redis中有序集合就使用到了跳跃表。

跳跃表的性质;
1、由很多层结构组成;
2、每一层都是一个有序的链表,排列顺序为由高层到底层,都至少包含两个链表节点,分别是前面的head节点和后面的nil节点;
3、最底层的链表包含了所有的元素;
4、如果一个元素出现在某一层的链表中,那么在该层之下的链表也全都会出现(上一层的元素是当前层的元素的子集);
5、链表中的每个节点都包含两个指针,一个指向同一层的下一个链表节点,另一个指向下一层的同一个链表节点;


跳跃表

可以看到,这里一共有4层,最上面就是最高层(Level 3),最下面的层就是最底层(Level 0),然后每一列中的链表节点中的值都是相同的,用指针来连接着。跳跃表的层数跟结构中最高节点的高度相同。理想情况下,跳跃表结构中第一层中存在所有的节点,第二层只有一半的节点,而且是均匀间隔,第三层则存在1/4的节点,并且是均匀间隔的,以此类推,这样理想的层数就是logN。

搜索
其基本原理就是从最高层的链表节点开始,如果比当前节点要大和比当前层的下一个节点要小,那么则往下找,也就是和当前层的下一层的节点的下一个节点进行比较,以此类推,一直找到最底层的最后一个节点,如果找到则返回,反之则返回空。
跳跃表查找操作的时间复杂度是O(logN)

插入
既然要插入,首先需要确定插入的层数,这里有不一样的方法。1. 看到一些博客写的是抛硬币,只要是正面就累加,直到遇见反面才停止,最后记录正面的次数并将其作为要添加新元素的层;2. 还有就是一些博客里面写的统计概率,先给定一个概率p,产生一个0到1之间的随机数,如果这个随机数小于p,则将高度加1,直到产生的随机数大于概率p才停止,根据给出的结论,当概率为1/2或者是1/4的时候,整体的性能会比较好(其实当p为1/2的时候,也就是抛硬币的方法)。
当确定好要插入的层数以后,则需要将元素都插入到从最底层到第k层。
跳跃表插入操作的时间复杂度是O(logN)

删除
在各个层中找到包含指定值的节点,然后将节点从链表中删除即可,如果删除以后只剩下头尾两个节点,则删除这一层。
总体上,跳跃表删除操作的时间复杂度是O(logN)

跳跃表原理和实现
https://www.cnblogs.com/George1994/p/7635731.html

漫画算法:什么是跳跃表?
http://blog.jobbole.com/111731/


图的遍历

图的遍历就是从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次,要为每一个顶点设置一个访问标志。通常有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS).这两种算法对有向图与无向图均适用。

数据结构(17)–图的遍历DFS和BFS
http://blog.csdn.net/u010366748/article/details/50792759

算法导论–图的遍历(DFS与BFS)
http://blog.csdn.net/luoshixian099/article/details/51897538

深度优先搜索(DFS)

深度优先搜索(DFS)
1.从图中某个顶点v0出发,首先访问v0;
2.访问结点v0的第一个邻接点,以这个邻接点vt作为一个新节点,访问vt所有邻接点。直到以vt出发的所有节点都被访问到,回溯到v0的下一个未被访问过的邻接点,以这个邻结点为新节点,重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。
3.若此时图中仍有未被访问的结点,则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程,直到图中的所有节点均被访问过。

遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。 当使用二维数组表示邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需时间为O(n^2),其中n为顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图中边的数目或有向图中弧的数目。由此,当以邻接表作存储结构时,深度优先搜遍遍历图的时间复杂度为O(n+e)。

广度优先搜索(BFS)

广度优先搜索(BFS)
BFS类似与树的层次遍历,从源顶点s出发,依照层次结构,逐层访问其他结点。即访问到距离顶点s为k的所有节点之后,才会继续访问距离为k+1的其他结点。
1.从图中某个顶点v0出发,首先访问v0;
2.依次访问v0的各个未被访问的邻接点。
3.依次从上述邻接点出发,访问他们的各个未被访问的邻接点。始终保证一点:如果vi在vk之前被访问,则vi的邻接点应在vk的邻接点之前被访问。重复上述步骤,直到所有顶点都被访问到。
4.如果还有顶点未被访问到,则随机选择一个作为起始点,重复上述过程,直到图中所有顶点都被访问到。

每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程,因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同,两者不同之处仅仅在于对顶点访问的顺序不同。

判断图的连通性(DFS/BFS)

如果一个图是连通的,那么从一个节点开始访问,采用深度优先或者广度优先对它进行遍历,那么必定能够访问完所有的节点。

EOJ 1816 判断图连通的三种方法——dfs,bfs,并查集
http://blog.csdn.net/fangpinlei/article/details/42127055


最短路径

无权图最短路径(BFS)

求从顶点A到B所含边数目最少的路径
只需从顶点A出发对图作广度优先搜索,一旦遇到顶点B就终止,此时得到从A到B的最短路径。

一个无权图G,使用某个顶点s作为输入参数,我们想要找出从s到所有其它顶点的最短路径。
这种搜索图的方法称为广度优先搜索(breadth-first search)。该方法按层处理顶点:距开始点最近的那些顶点首先被求值,而最远的那些顶点最后被求值。这很像对树的层序遍历

最短路径算法–无权最短路径
http://blog.csdn.net/tanga842428/article/details/52582817

赋权图单源最短路径(迪杰斯特拉算法)

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

迪杰斯特拉算法用于求带权有向图G0中从v0到其余各顶点的最短路径。

地杰斯特拉算法也适用于带权无向图,因为带权无向图可以看作是有往返二重边的有向图,只要在顶点vi 与vj 之间存在无向边(vi , vj ),就可以看成是在这两个顶点之间存在权值相同的两条有向边(vi , vj)和(vj , vi)

算法的思路:
Dijkstra算法采用的是一种贪心的策略,声明一个数组dis[]来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

设T是已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为x)或者是边(s,x)(s为起点),或者是中间只经过T中顶点到达x的路径。
反证法:假设此路径上有一个顶点不在T中,则说明存在一条终点不在T中而长度比此路径短的路径。但是,这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的,故长度比此路径短的所有路径均已产生,他们的终点必定在T中,所以假设不成立。

时间复杂度O(n^2)

赋权图多源最短路径(弗洛伊德算法)

依次以图中每个顶点为起点,重复n此迪杰斯特拉算法,可得到每一对顶点间的最短路径,复杂度为O(n^3)
弗洛伊德算法,复杂度也是O(n^3),但形式上更简单。

对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。


LeetCode刷题

马呆萌-LeetCode标签
http://madaimeng.com/tags/LeetCode/


看之前的面试题

把BST转换为双向链表
http://blog.csdn.net/brucehb/article/details/58381745

尾递归优化(改为循环)

与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。
尾递归:http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-explanation.html


设计模式√

随笔分类 - 设计模式
http://www.cnblogs.com/xiaoxi/category/1004551.html

单例模式

基本的实现思路
单例模式要求类能够有返回对象一个引用(永远是同一个)和一个获得该实例的方法(必须是静态方法,通常使用getInstance这个名称)。

单例的实现主要是通过以下两个步骤:
1、将该类的构造方法定义为私有方法,这样其他处的代码就无法通过调用该类的构造方法来实例化该类的对象,只有通过该类提供的静态方法来得到该类的唯一实例;
2、在该类内提供一个静态方法,当我们调用这个方法时,如果类持有的引用不为空就返回这个引用,如果类保持的引用为空就创建该类的实例并将实例的引用赋予该类保持的引用。

懒汉模式和饿汉模式

单例模式可以分为懒汉式和饿汉式:
懒汉式单例模式:懒汉式就是不在类加载时就创建类的单例,而是在第一次使用实例的时候再创建。
饿汉式单例模式:在类加载时就完成了初始化,所以类加载比较慢,但获取对象的速度快。

单例模式的线程安全性

单例模式在多线程的应用场合下必须小心使用。如果当唯一实例尚未创建时,有两个线程同时调用创建方法,那么它们同时没有检测到唯一实例的存在,从而同时各自创建了一个实例,这样就有两个实例被构造出来,从而违反了单例模式中实例唯一的原则。 解决这个问题的办法是为指示类是否已经实例化的变量提供一个互斥锁(虽然这样会降低效率)。

实现单例模式的8中方法

单例模式的八种写法比较
https://www.cnblogs.com/zhaoyan001/p/6365064.html

1、饿汉式(静态常量)[可用]

public class Singleton {
    private final static Singleton INSTANCE = new Singleton();
    private Singleton(){}
    public static Singleton getInstance(){
        return INSTANCE;
    }
}

优点:这种写法比较简单,就是在类装载的时候就完成实例化。避免了线程同步问题。
缺点:在类装载的时候就完成实例化,没有达到Lazy Loading的效果。如果从始至终从未使用过这个实例,则会造成内存的浪费。

2、饿汉式(静态代码块)[可用]

public class Singleton {
    private static Singleton instance;
    static {
        instance = new Singleton();
    }
    private Singleton() {}
    public Singleton getInstance() {
        return instance;
    }
}

这种方式和上面的方式其实类似,只不过将类实例化的过程放在了静态代码块中,也是在类装载的时候,就执行静态代码块中的代码,初始化类的实例。优缺点和上面是一样的。

3、懒汉式(线程不安全)[不可用]

public class Singleton {
    private static Singleton singleton;
    private Singleton() {}
    public static Singleton getInstance() {
        if (singleton == null) {
            singleton = new Singleton();
        }
        return singleton;
    }
}

这种写法起到了Lazy Loading的效果,但是只能在单线程下使用。如果在多线程下,一个线程进入了if (singleton == null)判断语句块,还未来得及往下执行,另一个线程也通过了这个判断语句,这时便会产生多个实例。所以在多线程环境下不可使用这种方式。

4、懒汉式(线程安全,同步方法)[不推荐用]

public class Singleton {
    private static Singleton singleton;
    private Singleton() {}
    public static synchronized Singleton getInstance() {
        if (singleton == null) {
            singleton = new Singleton();
        }
        return singleton;
    }
}

解决上面第三种实现方式的线程不安全问题,做个线程同步就可以了,于是就对getInstance()方法进行了线程同步。
缺点:效率太低了,每个线程在想获得类的实例时候,执行getInstance()方法都要进行同步。而其实这个方法只执行一次实例化代码就够了,后面的想获得该类实例,直接return就行了。方法进行同步效率太低要改进。

5、懒汉式(线程安全,同步代码块)[不可用]

public class Singleton {
    private static Singleton singleton;
    private Singleton() {}
    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                singleton = new Singleton();
            }
        }
        return singleton;
    }
}

由于第四种实现方式同步效率太低,所以摒弃同步方法,改为同步产生实例化的的代码块。但是这种同步并不能起到线程同步的作用。跟第3种实现方式遇到的情形一致,假如一个线程进入了if (singleton == null)判断语句块,还未来得及往下执行,另一个线程也通过了这个判断语句,这时便会产生多个实例。

6、双重检查[推荐用]

public class Singleton {
    private static volatile Singleton singleton;
    private Singleton() {}
    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null) {
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }
}

Double-Check概念对于多线程开发者来说不会陌生,如代码中所示,我们进行了两次if (singleton == null)检查,这样就可以保证线程安全了。这样,实例化代码只用执行一次,后面再次访问时,判断if (singleton == null),直接return实例化对象。

优点:线程安全;延迟加载;效率较高。

双重检查时的实例对象为什么必须是volatile的?

注意:使用双重检查时实例对象必须是volatile的,否则还会有问题。

这里涉及到了JVM编译器的指令重排。
指令重排是什么意思呢?比如java中简单的一句 instance = new Singleton,会被编译器编译成如下JVM指令:
memory =allocate(); //1:分配对象的内存空间
ctorInstance(memory); //2:初始化对象
instance =memory; //3:设置instance指向刚分配的内存地址

但是这些指令顺序并非一成不变,有可能会经过JVM和CPU的优化,指令重排成下面的顺序:
memory =allocate(); //1:分配对象的内存空间
instance =memory; //3:设置instance指向刚分配的内存地址
ctorInstance(memory); //2:初始化对象

假如singleton不是volatile的,线程A加锁进入代码块准备创建单例对象,当线程A执行完1,3,时,instance对象还未完成初始化,但已经不再指向null。此时如果线程B抢占到CPU资源,执行 if(instance == null)的结果会是false,从而返回一个没有初始化完成的instance对象。

为了避免这一情况呢,我们需要在instance对象前面增加一个修饰符volatile
volatile修饰符阻止了变量访问前后的指令重排,保证了指令执行顺序
如此在线程B看来,instance对象的引用要么指向null,要么指向一个初始化完毕的Instance,而不会出现某个中间态,保证了安全。

漫画:什么是单例模式?(整合版) - 程序员小灰
https://blog.csdn.net/bjweimengshu/article/details/78716839

单例模式与双重检测
http://www.iteye.com/topic/652440

7、静态内部类[推荐用]

public class Singleton {
    private Singleton() {}
    private static class SingletonInstance {
        private static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getInstance() {
        return SingletonInstance.INSTANCE;
    }
}

这种方式跟饿汉式方式采用的机制类似,但又有不同。两者都是采用了类装载的机制来保证初始化实例时只有一个线程。不同的地方在饿汉式方式是只要Singleton类被装载就会实例化,没有Lazy-Loading的作用,而静态内部类方式在Singleton类被装载时并不会立即实例化,而是在需要实例化时,调用getInstance方法,才会装载SingletonInstance类,从而完成Singleton的实例化。

类的静态属性只会在第一次加载类的时候初始化,所以在这里,JVM帮助我们保证了线程的安全性,在类进行初始化时,别的线程是无法进入的。

优点:避免了线程不安全,延迟加载,效率高。

8、枚举(防止反序列化重建单例)[推荐用]

public enum Singleton {
    INSTANCE;
    public void whateverMethod() {
    }
}

借助JDK1.5中添加的枚举来实现单例模式。不仅能避免多线程同步问题,而且还能防止反序列化重新创建新的对象。可能是因为枚举在JDK1.5中才添加,所以在实际项目开发中,很少见人这么写过。

这种方式是Effective Java作者Josh Bloch提倡的方式,它不仅能避免多线程同步问题,而且还自动支持序列化机制,防止反序列化重新创建新的对象,绝对防止多次实例化。不过,由于 JDK1.5 之后才加入 enum 特性,用这种方式写不免让人感觉生疏,在实际工作中,也很少用。

使用枚举实现的单例模式,不但可以防止利用反射强行构建单例对象,而且可以在枚举类对象被反序列化的时候,保证反序列的返回结果是同一对象。

利用反射构造多个单例对象

代码可以简单归纳为三个步骤:
第一步,获得单例类的构造器。
第二步,把构造器设置为可访问。
第三步,使用newInstance方法构造对象。

//获得构造器
Constructor con = Singleton.class.getDeclaredConstructor();
//设置为可访问
con.setAccessible(true);
//构造两个不同的对象
Singleton singleton1 = (Singleton)con.newInstance();
Singleton singleton2 = (Singleton)con.newInstance();
//验证是否是不同对象
System.out.println(singleton1.equals(singleton2)); //false

反序列化对单例模式的破坏

使用枚举实现的单例模式,不但可以防止利用反射强行构建单例对象,而且可以在枚举类对象被反序列化的时候,保证反序列的返回结果是同一对象。

对于其他方式实现的单例模式,如果既想要做到可序列化,又想要反序列化为同一对象,则必须实现readResolve方法。

漫画:什么是单例模式?(整合版) - 程序员小灰
https://blog.csdn.net/bjweimengshu/article/details/78716839

设计模式:单例模式
http://www.cnblogs.com/xiaoxi/p/7799456.html

常见的几种单例模式
https://www.cnblogs.com/Ycheng/p/7169381.html

面试被问设计模式?不要怕看这里:单例模式
http://blog.jobbole.com/109449/


工厂模式

简单工厂模式(静态工厂模式)

一个工厂类,根据传入的不同参数生成各种不同class的对象。这些对象同属于某一基类或接口。

问题:
增加新产品时要修改工厂类(修改if else或switch case),扩展性不好。不符合开闭原则。
优秀的java代码是符合“开放-封闭”原则(Open-Closed Principe, OCP)的,也就是说对扩展开发,对修改关闭

工厂方法模式

多个工厂类,按需选择一工厂生成对象。这些工厂之间靠拥有同一接口方法关联,所以叫“工厂方法”模式。
不在工厂里直接创建对象,而是直接封装一个一个的小工厂,每个工厂负责创建自己的子类

问题:
符合开闭原则。
但是这还是有缺点的,如果产品类过多,我们就要生成很多的工厂类。

抽象工厂模式

多个工厂类,每个工厂类可以生产不同的产品对象。
抽象工厂是应对产品族概念的。比如说,每个汽车公司可能要同时生产轿车,货车,客车,那么每一个工厂都要有创建轿车,货车和客车的方法。

结合实例分析简单工厂模式&工厂方法模式&抽象工厂模式的区别
https://www.cnblogs.com/zhi-hao/p/4028169.html

为什么使用工厂模式?(优点)

首先,工厂模式是为了解耦:把对象的创建和使用的过程分开。就是Class A 想调用 Class B ,那么A只是调用B的方法,而至于B的实例化,就交给工厂类。

其次,工厂模式可以降低代码重复。如果创建对象B的过程都很复杂,需要一定的代码量,而且很多地方都要用到,那么就会有很多的重复代码。我们可以这些创建对象B的代码放到工厂里统一管理。既减少了重复代码,也方便以后对B的创建过程的修改维护。
由于创建过程都由工厂统一管理,所以发生业务逻辑变化,不需要找到所有需要创建B的地方去逐个修正,只需要在工厂里修改即可,降低维护成本。

举个例子:
一个数据库工厂:可以返回一个数据库实例,可以是mysql,oracle等。
这个工厂就可以把数据库连接需要的用户名,地址,密码等封装好,直接返回对应的数据库对象就好。不需要调用者自己初始化,减少了写错密码等等这些错误。调用者只负责使用,不需要管怎么去创建、初始化对象。


装饰器模式

装饰器模式,顾名思义,就是对已经存在的某些类进行装饰,以此来扩展一些功能。

涉及角色:
Component为统一接口,也是装饰类和被装饰类的基本类型。
ConcreteComponent为具体实现类,也是被装饰类,他本身是个具有一些功能的完整的类。
Decorator是装饰类,实现了Component接口的同时还在内部维护了一个ConcreteComponent的实例,并可以通过构造函数初始化。而Decorator本身,通常采用默认实现,他的存在仅仅是一个声明:我要生产出一些用于装饰的子类了。而其子类才是赋有具体装饰效果的装饰产品类。
ConcreteDecorator是具体的装饰产品类,每一种装饰产品都具有特定的装饰效果。可以通过构造器声明装饰哪种类型的ConcreteComponent,从而对其进行装饰。

装饰器模式实现:
装饰者和被装饰者需要继承同一个接口或者是抽象类,被装饰者作为装饰者的一个变量。程序中原来调用被装饰者某方法func1的地方改成调用装饰者相同的那个方法func1,并且装饰者的该方法func1上添加了一些额外的功能,在方法func1中再调用被装饰着的方法func1。

装饰器的价值在于装饰,他并不影响被装饰类本身的核心功能。装饰器模式在不影响各个ConcreteComponent核心价值的同时,添加了他特有的装饰效果,具备非常好的通用性,这也是他存在的最大价值。

装饰器模式(Decorator)——深入理解与实战应用
https://www.cnblogs.com/jzb-blog/p/6717349.html

Java IO设计模式(装饰模式与适配器模式)
https://www.cnblogs.com/wangrd/p/7152662.html

装饰模式和代理模式区别

一句话,装饰者模式是增强对象功能(穿不同的衣服),代理模式是控制代理的对象,但不对其做功能增加

Java IO中的装饰模式(InputStream-FilterInputStream)

装饰模式在Java语言中的最著名的应用莫过于Java I/O标准库的设计了。

由于Java I/O库需要很多性能的各种组合,如果这些性能都是用继承的方法实现的,那么每一种组合都需要一个类,这样就会造成大量性能重复的类出现。而如果采用装饰模式,那么类的数目就会大大减少,性能的重复也可以减至最少。因此装饰模式是Java I/O库的基本模式。

抽象构件(Component)角色:由InputStream扮演。这是一个抽象类,为各种子类型提供统一的接口。
具体构件(ConcreteComponent)角色:由ByteArrayInputStream、FileInputStream、PipedInputStream、StringBufferInputStream等类扮演。它们实现了抽象构件角色所规定的接口。
抽象装饰(Decorator)角色:由FilterInputStream扮演。它实现了InputStream所规定的接口。
具体装饰(ConcreteDecorator)角色:由几个类扮演,分别是BufferedInputStream、DataInputStream以及两个不常用到的类LineNumberInputStream、PushbackInputStream。

即具体构件角色是节点流,装饰角色是过滤流。

InputStream这个抽象类有一个子类与上述其它子类非常不同,这个子类就是FilterInputStream,可参见上图中的InputStream族谱图。

翻开FilterInputStream的代码,我们可以看到,它内部又维护了一个InputStream的成员对象,并且它的所有方法,都是调用这个成员对象的同名方法。
换句话说,FilterInputStream它什么事都不做。就是把调用委托给内部的InputStream成员对象。

FilterInputStream的又有其子类,分别是:BufferedInputStream, DataInputStream, LineNumberInputStream, PushbackInputStream

虽然从上面代码看FilterInputStream并没有做什么有卵用的事,但是它的子类可不同了,以BufferedInputStream为例,这个类提供了提前读取数据的功能,也就是缓冲的功能。
从这里可以开始感受到,BufferedInputStream就是一个装饰者,它能为一个原本没有缓冲功能的InputStream添加上缓冲的功能。

比如我们常用的FileInputStream,它并没有缓冲功能,我们每次调用read,都会向操作系统发起调用索要数据。假如我们通过BufferedInputStream来装饰它,那么每次调用read,会预先向操作系统多拿一些数据,这样就不知不觉中提高了程序的性能。

同理,对于其它的FilterInputStream的子类,其作用也是一样的,那就是装饰一个InputStream,为它添加它原本不具有的功能。OutputStream以及家属对于装饰器模式的体现,也以此类推。

Java IO : 流,以及装饰器模式在其上的运用
https://segmentfault.com/a/1190000004255439

《java与设计模式》之装饰模式详解&Java IO中的装饰器模式
https://blog.csdn.net/caihuangshi/article/details/51334097


代理模式

代理模式包含如下角色:
ISubject:抽象主题角色,是一个接口。该接口是对象和它的代理共用的接口。
RealSubject:真实主题角色,是实现抽象主题接口的类。
Proxy:代理角色,内部含有对真实对象RealSubject的引用,从而可以操作真实对象。代理对象提供与真实对象相同的接口,以便在任何时刻都能代替真实对象。同时,代理对象可以在执行真实对象操作时,附加其他的操作,相当于对真实对象进行封装。

静态代理

静态代理的实现:
代理类和被代理类实现相同的接口,代理类持有被代理类的引用,代理方法执行时,同步调用被代理类的相同方法。

静态代理是死的,不会在运行时动态创建,相当于在编译期,就给被代理的对象生成了一个不可动态改变的代理类。

Java设计模式——代理模式实现及原理
https://blog.csdn.net/goskalrie/article/details/52458773

设计模式学习之代理模式
https://blog.csdn.net/u012124438/article/details/70184219

JDK动态代理

在java的动态代理机制中,有两个重要的类或接口,一个是 InvocationHandler(Interface)、另一个则是 Proxy(Class),这一个类和接口是实现我们动态代理所必须用到的。

InvocationHandler接口

每一个动态代理类都必须要实现InvocationHandler这个接口,并且每个代理类的实例都关联到了一个handler,当我们通过代理对象调用一个方法的时候,这个方法的调用就会被转发为由InvocationHandler这个接口的 invoke 方法来进行调用。我们来看看InvocationHandler这个接口的唯一一个方法 invoke 方法:
Object invoke(Object proxy, Method method, Object[] args) throws Throwable
proxy:  指代我们所代理的那个真实对象
method:  指代的是我们所要调用真实对象的某个方法的Method对象
args:  指代的是调用真实对象某个方法时接受的参数

Proxy类

Proxy这个类的作用就是用来动态创建一个代理对象的类,它提供了许多的方法,但是我们用的最多的就是 newProxyInstance 这个方法:
public static Object newProxyInstance(ClassLoader loader, Class<?>[] interfaces, InvocationHandler h) throws IllegalArgumentException
这个方法的作用就是得到一个动态的代理对象,其接收三个参数,我们来看看这三个参数所代表的含义:
loader:  一个ClassLoader对象,定义了由哪个ClassLoader对象来对生成的代理对象进行加载
interfaces:  一个Interface对象的数组,表示的是我将要给我需要代理的对象提供一组什么接口,如果我提供了一组接口给它,那么这个代理对象就宣称实现了该接口(多态),这样我就能调用这组接口中的方法了
h:  一个InvocationHandler对象,表示的是当我这个动态代理对象在调用方法的时候,会关联到哪一个InvocationHandler对象上

动态代理实例

首先我们定义了一个Subject类型的接口,为其声明了两个方法:

public interface Subject
{
    public void rent();
    public void hello(String str);
}

接着,定义了一个类来实现这个接口,这个类就是我们的真实对象,RealSubject类:

public class RealSubject implements Subject
{
    @Override
    public void rent()
    {
        System.out.println("I want to rent my house");
    }

    @Override
    public void hello(String str)
    {
        System.out.println("hello: " + str);
    }
}

下一步,我们就要定义一个动态代理类了,前面说个,每一个动态代理类都必须要实现 InvocationHandler 这个接口,因此我们这个动态代理类也不例外:

public class DynamicProxy implements InvocationHandler
{
    // 这个就是我们要代理的真实对象
    private Object subject;

    //    构造方法,给我们要代理的真实对象赋初值
    public DynamicProxy(Object subject)
    {
        this.subject = subject;
    }

    @Override
    public Object invoke(Object object, Method method, Object[] args)
            throws Throwable
    {
        //  在代理真实对象前我们可以添加一些自己的操作
        System.out.println("before rent house");

        System.out.println("Method:" + method);

        //    当代理对象调用真实对象的方法时,其会自动的跳转到代理对象关联的handler对象的invoke方法来进行调用
        method.invoke(subject, args);

        //  在代理真实对象后我们也可以添加一些自己的操作
        System.out.println("after rent house");

        return null;
    }

}

最后,来看看我们的Client类:

public class Client
{
    public static void main(String[] args)
    {
        //    我们要代理的真实对象
        Subject realSubject = new RealSubject();

        //    我们要代理哪个真实对象,就将该对象传进去,最后是通过该真实对象来调用其方法的
        InvocationHandler handler = new DynamicProxy(realSubject);

        /*
        * 通过Proxy的newProxyInstance方法来创建我们的代理对象,我们来看看其三个参数
        * 第一个参数 handler.getClass().getClassLoader() ,我们这里使用handler这个类的ClassLoader对象来加载我们的代理对象
        * 第二个参数realSubject.getClass().getInterfaces(),我们这里为代理对象提供的接口是真实对象所实行的接口,表示我要代理的是该真实对象,这样我就能调用这组接口中的方法了
        * 第三个参数handler, 我们这里将这个代理对象关联到了上方的 InvocationHandler 这个对象上
        */
        Subject subject = (Subject)Proxy.newProxyInstance(handler.getClass().getClassLoader(), realSubject
                .getClass().getInterfaces(), handler);

        System.out.println(subject.getClass().getName());
        subject.rent();
        subject.hello("world");
    }
}

java的动态代理机制详解
http://www.cnblogs.com/xiaoluo501395377/p/3383130.html


策略模式

定义:策略模式定义了一系列的算法,并将每一个算法封装起来,而且使他们可以相互替换,让算法独立于使用它的客户而独立变化。

分析下定义,策略模式定义和封装了一系列的算法,它们是可以相互替换的,也就是说它们具有共性,而它们的共性就体现在策略接口的行为上,另外为了达到最后一句话的目的,也就是说让算法独立于使用它的客户而独立变化,我们需要让客户端依赖于策略接口。

这个模式涉及到三个角色:

  • 抽象策略(Strategy)角色:这是一个抽象角色,通常由一个接口或抽象类实现。此角色给出所有的具体策略类所需的接口。
  • 具体策略(ConcreteStrategy)角色:包装了相关的算法或行为。
  • 环境(Context)角色:持有一个Strategy的引用。

策略模式的优点

  • (1)策略模式提供了管理相关的算法族的办法。策略类的等级结构定义了一个算法或行为族。恰当使用继承可以把公共的代码移到父类里面,从而避免代码重复。
  • (2)使用策略模式可以避免使用多重条件(if-else)语句。多重条件语句不易维护,它把采取哪一种算法或采取哪一种行为的逻辑与算法或行为的逻辑混合在一起,统统列在一个多重条件语句里面,比使用继承的办法还要原始和落后。

策略模式的缺点

  • (1)客户端必须知道所有的策略类,并自行决定使用哪一个策略类。这就意味着客户端必须理解这些算法的区别,以便适时选择恰当的算法类。换言之,策略模式只适用于客户端知道算法或行为的情况。
  • (2)由于策略模式把每个具体的策略实现都单独封装成为类,如果备选的策略很多的话,那么对象的数目就会很可观。

《JAVA与模式》之策略模式
http://www.cnblogs.com/java-my-life/archive/2012/05/10/2491891.html

设计模式学习之策略模式
https://blog.csdn.net/u012124438/article/details/70039943


状态模式

状态模式:允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类。

在很多情况下,一个对象的行为取决于一个或多个动态变化的属性,这样的属性叫做状态,这样的对象叫做有状态的(stateful)对象,这样的对象状态是从事先定义好的一系列值中取出的。当一个这样的对象与外部事件产生互动时,其内部状态就会改变,从而使得系统的行为也随之发生变化。

模式的组成
环境类(Context): 定义客户感兴趣的接口。维护一个ConcreteState子类的实例,这个实例定义当前状态。
抽象状态类(State): 定义一个接口以封装与Context的一个特定状态相关的行为。
具体状态类(ConcreteState): 每一子类实现一个与Context的一个状态相关的行为。

状态模式中有什么优点呢?
首先是避免了过多的swith…case 或者if..else 语句的使用,避免了程序的复杂性;其次是很好的使用体现了开闭原则和单一职责原则,每个状态都是一个子类,你要增加状态就增加子类,你要修改状态,你只修改一个子类就可以了;最后一个好处就是封装性非常好,这也是状态模式的基本要求,状态变换放置到了类的内部来实现,外部的调用不用知道类内部如何实现状态和行为的变换。

状态模式既然有优点,那当然有缺点了,只有一个缺点,子类会太多,也就是类膨胀,你想一个事物有七八、十来个状态也不稀奇,如果完全使用状态模式就会有太多的子类,不好管理,这个需要大家在项目自己衡量。

Java设计模式——状态模式(STATE PATTERN)
https://blog.csdn.net/u012401711/article/details/52675873

策略模式和状态模式的区别

应用场景(目的)却不一样,State模式重在强调对象内部状态的变化改变对象的行为,Strategy模式重在外部对策略的选择,策略的选择由外部条件决定,也就是说算法的动态的切换。
但由于它们的结构是如此的相似,我们可以认为“状态模式是完全封装且自修改的策略模式”。即状态模式是封装对象内部的状态的,而策略模式是封装算法族的

设计模式 ( 十七) 状态模式State(对象行为型)
https://blog.csdn.net/hguisu/article/details/7557252


适配器模式

适配器模式把一个类的接口变换成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够在一起工作。

适配器模式的用途
用电器做例子,笔记本电脑的插头一般都是三相的,即除了阳极、阴极外,还有一个地极。而有些地方的电源插座却只有两极,没有地极。电源插座与笔记本电脑的电源插头不匹配使得笔记本电脑无法使用。这时候一个三相到两相的转换器(适配器)就能解决此问题,而这正像是本模式所做的事情。

模式所涉及的角色有:

  • 目标(Target)角色:这就是所期待得到的接口。注意:由于这里讨论的是类适配器模式,因此目标不可以是类。
  • 源(Adaptee)角色:现在需要适配的接口。
  • 适配器(Adaper)角色:适配器类是本模式的核心。适配器把源接口转换成目标接口。显然,这一角色不可以是接口,而必须是具体类。

类适配器

适配器类继承Adaptee类,又实现Target接口,对于Adaptee中已有的方法,默认调用父类(也就是Adaptee类)的方法,对于Adaptee中没有而Target中有的方法,需要额外定义来实现。

对象适配器

对象适配器相当于对源Adaptee的代理,对象适配器内含一个Adaptee的引用,对于Adaptee中已有的方法直接委托给Adaptee对象来调用,对于Adaptee中没有而Target中有的方法,需要额外定义来实现。

建议尽量使用对象适配器的实现方式,多用合成/聚合、少用继承。当然,具体问题具体分析,根据需要来选用实现方式,最适合的才是最好的。

最小接口原则

先来说一下最小接口原则,这个原则所表达的思想是说接口的行为应该尽量的少,如果没做到这个原则,就会出现实现这个接口的子类,很可能出现很多方法是空着的情况,因为你的接口设计的过大,导致接口中原本不该出现的方法出现了,结果现在子类根本用不上这个方法,但由于JAVA语言规则的原因,实现一个接口必须实现它的全部方法,所以我们的子类不得不被迫写一堆空方法在那,只为了编译通过。

缺省适配器

缺省适配(Default Adapter)模式为一个接口提供缺省实现,这样子类型可以从这个缺省实现进行扩展,而不必从原有接口进行扩展。

在很多情况下,必须让一个具体类实现某一个接口,但是这个类又用不到接口所规定的所有的方法。缺省适配模式可以很好的处理这一情况。可以设计一个抽象的适配器类实现接口,此抽象类要给接口所要求的每一种方法都提供一个空的方法。

这种情况其实蛮多的,因为接口设计的最小化只是理想状态,难免会有一些实现类,对其中某些方法不感兴趣,这时候,如果方法过多,子类也很多,并且子类的大部分方法都是空着的,那么就可以采取这种方式了。

使用适配器模式克服观察者模式的缺点

观察者模式的一个缺点,即如果一个现有的类没有实现Observer接口,那么我们就无法将这个类作为观察者加入到被观察者的观察者列表中

举个例子,比如我们希望将HashMap这个类加到观察者列表里,在被观察者产生变化时,假设我们要清空整个map。但是Observable的观察者列表只认识Observer这个接口,它不认识HashMap,这种情况下,我们就可以使用类适配器的方式将我们的HashMap进行改造,类适配器采用继承的方式,那么我们写出如下适配器。

public class HashMapObserverAdapter<K, V> extends HashMap<K, V> implements Observer{
    public void update(Observable o, Object arg) {
        //被观察者变化时,清空Map
        super.clear();
    }
}

即我们继承我们希望复用其功能的类,并且实现我们想适配的接口,在这里就是Observer,那么就会产生一个适配器,这个适配器具有原有类(即HashMap)的功能,又具有观察者接口,所以这个适配器现在可以加入到观察者列表了。

设计模式学习之适配器模式
https://blog.csdn.net/u012124438/article/details/70486083

《JAVA与模式》之适配器模式
http://www.cnblogs.com/java-my-life/archive/2012/04/13/2442795.html


迭代器模式

迭代器模式:提供一种方法顺序的访问一个聚合对象中各个元素,而又不暴露该对象的内部表示。

聚集类:Aggregate(抽象类)和ConcreteAggregate(具体聚集类)表示聚集类,是用来存储迭代器的数据。
在Aggregate(抽象类)中有一个CreateIterator方法,用来获取迭代器
迭代器:迭代器用来为聚集类提供服务,提供了一系列访问聚集类对象元素的方法。

迭代器是可以从前往后,或者从后往前遍历的。
为遍历不同聚集结构提供如:开始,下一个,是否有下一个,是否结束,当前哪一个等等的一个统一接口。

迭代器模式(Iterator)
https://www.cnblogs.com/cxxjohnson/p/6403851.html


观察者模式

观察者向被观察者上注册,当被观察者状态发生改变时(有事件发生时),所有观察者都得到通知。

观察者模式实例

JAVA设计模式之观察者模式
https://www.cnblogs.com/luohanguo/p/7825656.html

实例:有一个微信公众号服务,不定时发布一些消息,关注公众号就可以收到推送消息,取消关注就收不到推送消息。
1、定义一个抽象被观察者接口

package com.jstao.observer;

//抽象被观察者接口,声明了添加、删除、通知观察者方法
public interface Observerable {
    public void registerObserver(Observer o);
    public void removeObserver(Observer o);
    public void notifyObserver();
}

2、定义一个抽象观察者接口

package com.jstao.observer;

//抽象观察者,定义了一个update()方法,当被观察者调用notifyObservers()方法时,观察者的update()方法会被回调。
public interface Observer {
    public void update(String message);
}

3、定义被观察者,实现了Observerable接口,对Observerable接口的三个方法进行了具体实现,同时有一个List集合,用以保存注册的观察者,等需要通知观察者时,遍历该集合即可。

package com.jstao.observer;

import java.util.ArrayList;
import java.util.List;

//被观察者,也就是微信公众号服务,实现了Observerable接口,对Observerable接口的三个方法进行了具体实现
public class WechatServer implements Observerable {
    //注意到这个List集合的泛型参数为Observer接口,设计原则:面向接口编程而不是面向实现编程
    private List<Observer> list;
    private String message;

    public WechatServer() {
        list = new ArrayList<Observer>();
    }

    @Override
    public void registerObserver(Observer o) {
        list.add(o);
    }

    @Override
    public void removeObserver(Observer o) {
        if(!list.isEmpty())
            list.remove(o);
    }

    //遍历
    @Override
    public void notifyObserver() {
        for(int i = 0; i < list.size(); i++) {
            Observer oserver = list.get(i);
            oserver.update(message);
        }
    }

    public void setInfomation(String s) {
        this.message = s;
        System.out.println("微信服务更新消息: " + s);
        //消息更新,通知所有观察者
        notifyObserver();
    }
}

4、定义具体观察者,微信公众号的具体观察者为用户User

package com.jstao.observer;

//观察者,实现了update方法
public class User implements Observer {

    private String name;
    private String message;

    public User(String name) {
        this.name = name;
    }

    @Override
    public void update(String message) {
        this.message = message;
        read();
    }

    public void read() {
        System.out.println(name + " 收到推送消息: " + message);
    }

}

5、编写一个测试类

package com.jstao.observer;

public class Test {
    public static void main(String[] args) {
        WechatServer server = new WechatServer();

        Observer userZhang = new User("ZhangSan");
        Observer userLi = new User("LiSi");
        Observer userWang = new User("WangWu");

        server.registerObserver(userZhang);
        server.registerObserver(userLi);
        server.registerObserver(userWang);
        server.setInfomation("PHP是世界上最好用的语言!");

        System.out.println("----------------------------------------------");
        server.removeObserver(userZhang);
        server.setInfomation("JAVA是世界上最好用的语言!");

    }
}

推模式和拉模式

观察者模式在关于目标角色、观察者角色通信的具体实现中,有两个版本。一种情况便是目标角色在发生变化后,仅仅告诉观察者角色“我变化了”;观察者角色如果想要知道具体的变化细节,则就要自己从目标角色的接口中得到。这种模式被很形象的称为:拉模式——就是说变化的信息是观察者角色主动从目标角色中“拉”出来的。

还有一种方法,那就是我目标角色“服务一条龙”,通知你发生变化的同时,通过一个参数将变化的细节传递到观察者角色中去。这就是“推模式”——管你要不要,先给你啦。

这两种模式的使用,取决于系统设计时的需要。如果目标角色比较复杂,并且观察者角色进行更新时必须得到一些具体变化的信息,则“推模式”比较合适。如果目标角色比较简单,则“拉模式”就很合适啦。

深入浅出观察者模式
https://blog.csdn.net/ai92/article/details/375691

面试被问设计模式?不要怕看这里:观察者模式
http://blog.jobbole.com/109845/

Java内置观察者模式

在JAVA语言的java.util库里面,提供了一个Observable类以及一个Observer接口,构成JAVA语言对观察者模式的支持。

使用javaAPI的观察者模式需要明白这么几件事情:

  • 如何使对象变为观察者?
    实现观察者接口(java.util.Observer),然后调用Observable对象的addObserver()方法.不想再当观察者时,调用deleteObserver()就可以了.

  • 被观察者(主题)如何发出通知?
    第一步:先调用setChanged()方法,标识状态已经改变的事实.
    第二步:调用notifyObservers()方法或者notifyObservers(Object arg),这就牵扯到推(push)和拉(pull)的方式传送数据.如果想用push的方式”推”数据给观察者,可以把数据当做数据对象传送给notifyObservers(Object arg)方法,其中的arg可以为任意对象,意思是你可以将任意对象传送给每一个观察者。如果调用不带参数的notifyObserver()方法,则意味着你要使用pull的方式去主题对象中”拉”来所需要的数据.

  • 观察者如何接收通知?
    观察者只需要实现一个update(Observable o,Object arg)方法,第一个参数o,是指定通知是由哪个主题下达的,第二个参数arg就是上面notifyObserver(Object arg)里传入的数据,如果不传该值,arg为null.

《JAVA与模式》之观察者模式
http://www.cnblogs.com/java-my-life/archive/2012/05/16/2502279.html

设计模式–观察者模式初探和java Observable模式
https://www.cnblogs.com/fingerboy/p/5468994.html


Linux命令与Shell

常用Linux命令

lsof列出当前系统打开文件

lsof (list open files)是一个列出当前系统打开文件的工具。在linux系统环境下,任何事物都可以以文件形式存在,通过文件不仅可以访问常规的数据,还可以访问网络连接和硬件。

-p 进程号:列出指定进程号所打开的文件

top结果中load过高可能原因?

top命令中load average显示的是最近1分钟、5分钟和15分钟的系统平均负载。

系统平均负载被定义为在特定时间间隔内运行队列中(在CPU上运行或者等待运行多少进程)的平均进程数。

cpu load过高问题排查
https://www.cnblogs.com/lddbupt/p/5779655.html

kill -2,-9,-15

默认(缺省)情况下,kill发送的是SIGTERM,即15(SIGTERM)信号,”kill PID”与”kill -15 PID”是一样的。
这个信号通常会要求程序自己正常退出,是一种比较安全的用法。但它是可以被阻塞,处理和忽略的,所以对于有的进程,会中止失败。

另一个常用的信号是9(SIGKILL),这个命令表示立即结束程序,是不能被阻塞,处理和忽略的。在TERM信号失效的情况下,可以尝试使用”kill -9 PID”
事实上,SIGKILL信号是直接发给init进程的,它收到该信号后,负责终止pid指定的进程。

Kill -2 :功能类似于Ctrl + C 是程序在结束之前,能够保存相关数据,然后再退出。

Shell脚本

  • !!,连续两个英文叹号,表示执行上一条指令

  • $n,n为数字,$n为执行脚本的第一个参数,相当于main函数的argv[n]。例如,$0就是argv[0],即脚本程序自身的名称

  • $#,传递到脚本的参数个数,不包括脚本本身
  • $*,以一个单字符串显示所有向脚本传递的参数,不包括$0
  • $@,与$*类似,从$1开始的所有参数,但每个都作为独立的字符串

$*$@的区别
相同点:都是引用所有参数。
不同点:只有在双引号中体现出来。假设在脚本运行时写了三个参数 1、2、3,,则"$*"等价于 “1 2 3”(单个字符串),而"$@"等价于 “1” “2” “3”(三个字符串)。

  • $?:当前shell进程中,上一个命令的返回值,如果上一个命令成功执行则$?的值为0,否则为其他非零值,常用做if语句条件
  • $$:当前shell进程的pid
  • $!:后台运行的最后一个进程的pid
  • $-:显示Shell使用的当前选项,与set命令功能相同。
  • $_:之前命令的最后一个参数

epoll

epoll是Linux内核为处理大批量文件描述符而作了改进的poll,是Linux下多路复用IO接口select/poll的增强版本,它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统CPU利用率。

epoll可以理解为event poll,不同于忙轮询和无差别轮询,epoll之会把哪个流发生了怎样的I/O事件通知我们。


linux 守护进程

进程组与会话期

进程组(process group):一个或多个进程的集合,每个进程都有一个进程组ID,这个ID就是进程组长的进程ID。且该进程组ID不会因组长进程的退出而受到影响。

会话期(session):会话期是一个或多个进程组的集合。通常,一个会话开始于用户登录,终止于用户退出,在此期间该用户运行的所有进程都属于这个会话期。每个会话有唯一一个会话首进程(session leader),会话ID为会话首进程ID

控制终端(controlling terminal) :每一个会话可以有一个单独的控制终端,与控制终端连接的会话首进程就是控制进程(controlling process)。 这时候,与当前终端交互的就是前台进程组,其他的都是后台进程组。

setsid()

进程调用 setsid()函数会:

首先请注意:只有当该进程不是一个进程组长时,才会成功创建一个新的会话期。
(1)摆脱原会话的控制。该进程变成新会话期的首进程
(2)摆脱原进程组。成为一个新进程组的组长
(3)摆脱终端控制。如果在调用 setsid() 前,该进程有控制终端,那么与该终端的联系被解除。
如果该进程是一个进程组的组长,此函数返回错误。

如何创建守护进程?

创建守护进程的的一般步骤:

1、fork()创建子进程,父进程exit()退出
这是创建守护进程的第一步。由于守护进程是脱离控制终端的,因此,完成第一步后就会在Shell终端里造成程序已经运行完毕的假象。之后的所有工作都在子进程中完成,而用户在Shell终端里则可以执行其他命令,从而在形式上做到了与控制终端的脱离,在后台工作。

2、在子进程中调用 setsid() 函数创建新的会话
在调用了 fork() 函数后,子进程全盘拷贝了父进程的会话期、进程组、控制终端等,虽然父进程退出了,但会话期、进程组、控制终端等并没有改变,因此,这还不是真正意义上的独立开来,而 setsid() 函数能够使进程完全独立出来。

3、再次 fork() 一个子进程并让父进程退出。
现在,进程已经成为无终端的会话组长,但它可以重新申请打开一个控制终端,可以通过 fork() 一个子进程,该子进程不是会话首进程,该进程将不能重新打开控制终端。退出父进程。

4、在子进程中调用 chdir() 函数,让根目录 ”/” 成为子进程的工作目录
这一步也是必要的步骤。使用fork创建的子进程继承了父进程的当前工作目录。由于在进程运行中,当前目录所在的文件系统(如“/mnt/usb”)是不能卸载的,这对以后的使用会造成诸多的麻烦(比如系统由于某种原因要进入单用户模式)。因此,通常的做法是让”/“作为守护进程的当前工作目录,这样就可以避免上述的问题,当然,如有特殊需要,也可以把当前工作目录换成其他的路径,如/tmp。改变工作目录的常见函数是chdir。

5、在子进程中调用 umask() 函数,设置进程的文件权限掩码为0
文件权限掩码是指屏蔽掉文件权限中的对应位。比如,有个文件权限掩码是050,它就屏蔽了文件组拥有者的可读与可执行权限。由于使用fork函数新建的子进程继承了父进程的文件权限掩码,这就给该子进程使用文件带来了诸多的麻烦。因此,把文件权限掩码设置为0,可以大大增强该守护进程的灵活性。设置文件权限掩码的函数是umask。在这里,通常的使用方法为umask(0)。

6、在子进程中关闭任何不需要的文件描述符
同文件权限码一样,用fork函数新建的子进程会从父进程那里继承一些已经打开了的文件。这些被打开的文件可能永远不会被守护进程读写,但它们一样消耗系统资源,而且可能导致所在的文件系统无法卸下。
在上面的第二步之后,守护进程已经与所属的控制终端失去了联系。因此从终端输入的字符不可能达到守护进程,守护进程中用常规方法(如printf)输出的字符也不可能在终端上显示出来。所以,文件描述符为0、1和2 的3个文件(常说的输入、输出和报错)已经失去了存在的价值,也应被关闭。

7、守护进程退出处理
当用户需要外部停止守护进程运行时,往往会使用 kill 命令停止该守护进程。所以,守护进程中需要编码来实现 kill 发出的signal信号处理,达到进程的正常退出。

【Linux编程】守护进程(daemon)详解与创建
http://blog.csdn.net/woxiaohahaa/article/details/53487602


计算机基础

TCP三次握手和四次挥手

三次握手

所谓三次握手(Three-Way Handshake)即建立TCP连接,就是指建立一个TCP连接时,需要客户端和服务端总共发送3个包以确认连接的建立。


跳跃表

(1)第一次握手:
Client将标志位SYN置为1,随机产生一个值seq=J,并将该数据包发送给Server,Client进入SYN_SENT状态,等待Server确认。
(2)第二次握手:
Server收到数据包后由标志位SYN=1知道Client请求建立连接,Server将标志位SYN和ACK都置为1,ack=J+1,随机产生一个值seq=K,并将该数据包发送给Client以确认连接请求,Server进入SYN_RCVD状态。
(3)第三次握手:
Client收到确认后,检查ack是否为J+1,ACK是否为1,如果正确则将标志位ACK置为1,ack=K+1,并将该数据包发送给Server,Server检查ack是否为K+1,ACK是否为1,如果正确则连接建立成功,Client和Server进入ESTABLISHED状态,完成三次握手,随后Client与Server之间可以开始传输数据了。

一个TCP连接必须要经过三次“对话”才能建立起来,其中的过程非常复杂,只简单的 描述下这三次对话的简单过程:主机A向主机B发出连接请求数据包:“我想给你发数据,可以吗?”,这是第一次对话;主机B向主机A发送同意连接和要求同步 (同步就是两台主机一个在发送,一个在接收,协调工作)的数据包:“可以,你什么时候发?”,这是第二次对话;主机A再发出一个数据包确认主机B的要求同 步:“我现在就发,你接着吧!”,这是第三次对话。三次“对话”的目的是使数据包的发送和接收同步,经过三次“对话”之后,主机A才向主机B正式发送数 据。

为什么需要3次握手?

建立三次握手主要是因为A发送了再一次的确认,那么A为什么会再确认一次呢,主要是为了防止已失效的连接请求报文段又突然传送给B,从而产生了错误。
异常情况下,A发送的请求报文连接段并没有丢失,而是在某个网络节点滞留较长时间,以致延误到请求释放后的某个时间到达B,本来是一个早已失效的报文段,但是B收到了此失效连接请求报文段后,就误以为A又重新发送的连接请求报文段,并发送确认报文段给A,同意建立连接,如果没有三次握手,那么B发送确认后,连接就建立了,而此时A没有发送建立连接的请求报文段,于是不理会B的确认,也不会给B发送数据,而B却一直等待A发送数据,因此B的许多资源就浪费了

四次挥手

由于TCP连接时全双工的,因此,每个方向都必须要单独进行关闭,这一原则是当一方完成数据发送任务后,发送一个FIN来终止这一方向的连接,收到一个FIN只是意味着这一方向上没有数据流动了,即不会再收到数据了,但是在这个TCP连接上仍然能够发送数据,直到这一方向也发送了FIN。首先进行关闭的一方将执行主动关闭,而另一方则执行被动关闭


跳跃表

第一次挥手:
Client发送一个FIN,用来关闭Client到Server的数据传送,Client进入FIN_WAIT_1状态。
第二次挥手:
Server收到FIN后,发送一个ACK给Client,确认序号为收到序号+1(与SYN相同,一个FIN占用一个序号),Server进入CLOSE_WAIT状态。
第三次挥手:
Server发送一个FIN,用来关闭Server到Client的数据传送,Server进入LAST_ACK状态。
第四次挥手:
Client收到FIN后,Client进入TIME_WAIT状态,接着发送一个ACK给Server,确认序号为收到序号+1,Server进入CLOSED状态,完成四次挥手。

为什么连接是三次握手而关闭时需要四次握手?

答:因为当Server端收到Client端的SYN连接请求报文后,可以直接发送SYN+ACK报文。其中ACK报文是用来应答的,SYN报文是用来同步的。但是关闭连接时,当Server端收到FIN报文时,很可能并不会立即关闭SOCKET,所以只能先回复一个ACK报文,告诉Client端,”你发的FIN报文我收到了”。只有等到我Server端所有的报文都发送完了,我才能发送FIN报文,因此不能一起发送。故需要四步握手。

理论经典:TCP协议的3次握手与4次挥手过程详解
http://blog.csdn.net/omnispace/article/details/52701752

tcp三次握手四次挥手(及原因)详解
http://blog.csdn.net/xulu_258/article/details/51146489


进程/线程/并发

进程和线程的区别

进程让操作系统的并发性成为可能,而线程让进程的内部并发成为可能。

但是要注意,一个进程虽然包括多个线程,但是这些线程是共同享有进程占有的资源和地址空间的。

进程是操作系统进行资源分配的基本单位,而线程是操作系统进行调度的基本单位。

由于多个线程是共同占有所属进程的资源和地址空间的,那么就会存在一个问题:
如果多个线程要同时访问某个资源,怎么处理?
这就是线程的同步和并发控制问题。

并行(Parallel)与并发(Concurrent)的区别

并发(concurrency)和并行(parallellism)是:
解释一:并行是指两个或者多个事件在同一时刻发生;而并发是指两个或多个事件在同一时间间隔发生。
解释二:并行是在不同实体上的多个事件,并发是在同一实体上的多个事件。
解释三:并发是在一台处理器上“同时”处理多个任务,并行是在多台处理器上同时处理多个任务。如hadoop分布式集群
所以并发编程的目标是充分的利用处理器的每一个核,以达到最高的处理性能。

并发的关键是你有处理多个任务的能力,不一定要同时。
并行的关键是你有同时处理多个任务的能力。

并发是不是一个线程,并行是多个线程?
答:并发和并行都可以是很多个线程,就看这些线程能不能同时被(多个)cpu执行,如果可以就说明是并行,而并发是多个线程被(一个)cpu 轮流切换着执行。

多线程是否一定比单线程快?

那么可能有朋友会问,现在很多时候都采用多线程编程,那么是不是多线程的性能一定就由于单线程呢?

不一定,要看具体的任务以及计算机的配置。比如说:
对于单核CPU,如果是CPU密集型任务,如解压文件,多线程的性能反而不如单线程性能,因为解压文件需要一直占用CPU资源,如果采用多线程,线程切换导致的开销反而会让性能下降。

但是对于比如交互类型的任务,肯定是需要使用多线程的、

而对于多核CPU,对于解压文件来说,多线程肯定优于单线程,因为多个线程能够更加充分利用每个核的资源。

虽然多线程能够提升程序性能,但是相对于单线程来说,它的编程要复杂地多,要考虑线程安全问题。因此,在实际编程过程中,要根据实际情况具体选择。

Java并发编程:进程和线程之由来 - 海子
http://www.cnblogs.com/dolphin0520/p/3910667.html


死锁的四个必要条件

产生死锁的四个必要条件:
(1) 互斥条件:一个资源每次只能被一个进程使用。
(2) 请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3) 不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。
(4) 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之
一不满足,就不会发生死锁。


内存分页

在基本的分页概念中,我们把程序分成等长的小块。这些小块叫做“页(Page)”,同样内存也被我们分成了和页面同样大小的”页框(Frame)“,一个页可以装到一个页框里。在执行程序的时候我们根据一个页表去查找某个页面在内存的某个页框中,由此完成了逻辑到物理的映射。

为什么要分页?(内存碎片/虚拟内存)

内存的分段和分页管理方式和由此衍生的一堆段页式等都属于内存的不连续分配。什么叫不连续分配?就是把程序分割成一块一块的装入内存,在物理上不用彼此相连,在逻辑上使用段表或者页表将离散分布的这些小块串起来形成逻辑上连续的程序。

(1)解决空间浪费碎片化问题
由于将虚拟内存空间和物理内存空间按照某种规定的大小进行分配,这里我们称之为页(Page),然后按照页进行内存分配,也就克服了外部碎片的问题。

(2)解决程序大小受限问题
程序增长有限是因为一个程序需要全部加载到内存才能运行,因此解决的办法就是使得一个程序无须全部加载就可以运行。使用分页也可以解决这个问题,只需将当前需要的页面放在内存里,其他暂时不用的页面放在磁盘上,这样一个程序同时占用内存和磁盘,其增长空间就大大增加了。而且,分页之后,如果一个程序需要更多的空间,给其分配一个新页即可(而无需将程序倒出倒进从而提高空间增长效率)。

一般一个内存页大小为4KB

在32位操作系统中,一个地址对应32位2进制数,则能寻址到4GB(2^32)的地址.而在linux内存管理中,内存以页为单位进行管理,一般情况下每页4KB大小,4GB内存就有(4GB/4KB=2^20)个页.所以可将一个32位的地址分为20位+12位.前20位可以确定出地址在2^20个页中的哪一页,剩下的12位就可以确定出在这一页中的哪个位置.
反过来,若是知道了页内为12位,那每页大小就肯定为了


网络安全

加密算法

对称加密(DES/AES)

对称加密指的就是加密和解密使用同一个秘钥,所以叫做对称加密。对称加密只有一个秘钥,作为私钥。
常见的对称加密算法:DES(Data Encryption Standard),AES,3DES等等。

非对称加密(RSA)

非对称加密指的是:加密和解密使用不同的秘钥,一把作为公开的公钥,另一把作为私钥。公钥加密的信息,只有私钥才能解密。私钥加密的信息,只有公钥才能解密。

公钥加密,私钥解密,或私钥加密,公钥解密

加密密码和解密密码是相对的,如果用加密密码加密那么只有解密密码才能解密,如果用解密密码加密则只有加密密码能解密,所以它们被称为密码对,其中的一个可以在网络上发送、公布,叫做公钥,而另一个则只有密钥对的所有人才持有,叫做私钥,私钥不以任何形式传播。
非对称加密算法需要两个密钥:公开密钥(public key)和私有密钥(private key)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。

非对称加密算法实现机密信息交换的基本过程是:
甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开;得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方;甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。
另一方面,甲方可以使用自己的私密钥对机密信息进行加密后再发送给乙方;乙方再用甲方的公钥对加密后的信息进行解密。

使用过程:
乙方生成两把密钥(公钥和私钥)
甲方获取乙方的公钥,然后用它对信息加密。
乙方得到加密后的信息,用私钥解密,乙方也可用私钥加密字符串
甲方获取乙方私钥加密数据,用公钥解密

常见的非对称加密算法:RSA,ECC

对称加密和非对称加密对比

1、对称加密算法加密速度快、加密效率高
非对称加密算法速度慢

2、对称加密的密钥管理不安全,尤其是涉及到网络通信时。
在数据传送前,发送方和接收方必须商定好秘钥,然后双方都必须要保存好秘钥,如果一方的秘钥被泄露,那么加密信息也就不安全了。

对称加密和非对称加密结合使用

在实际的网络环境中,会将两者混合使用:
例如针对C/S模型,
1、服务端计算出一对秘钥pub/pri。将私钥保密,将公钥公开。
2、客户端请求服务端时,拿到服务端的公钥pub。
3、客户端通过AES计算出一个对称加密的秘钥X。 然后使用pub将X进行加密。
4、客户端将加密后的密文发送给服务端。服务端通过pri解密获得X。
5、然后两边的通讯内容就通过对称密钥X以对称加密算法来加解密。

对称加密与非对称加密,以及RSA的原理
https://blog.csdn.net/u014079662/article/details/61169607


信息摘要(MD5/SHA)

信息摘要是一个唯一对应一个消息或文本的固定长度的值,它由一个单向Hash加密函数对消息进行作用而产生。如果消息在途中改变了,则接收者通过对收到消息的新产生的摘要与原摘要比较,就可知道消息是否被改变了。因此消息摘要保证了消息的完整性。消息摘要采用单向Hash 函数将需加密的明文”摘要”成一串密文,这一串密文亦称为数字指纹(Finger Print)。它有固定的长度,且不同的明文摘要成密文,其结果总是不同的,而同样的明文其摘要必定一致。这样这串摘要便可成为验证明文是否是”真身”的”指纹”了。

消息摘要,其实就是将需要摘要的数据作为参数,经过哈希函数(Hash)的计算,得到的散列值。

消息摘要具有以下特点:
(1)唯一性:数据只要有一点改变,那么再通过消息摘要算法得到的摘要也会发生变化。虽然理论上有可能会发生碰撞,但是概率极其低。
(2)不可逆:消息摘要算法的密文无法被解密。
(3)不需要密钥,可使用于分布式网络。
(4)无论输入的明文有多长,计算出来的消息摘要的长度总是固定的。

常用算法
消息摘要算法包括MD(Message Digest,消息摘要算法)、SHA(Secure Hash Algorithm,安全散列算法)、MAC(Message AuthenticationCode,消息认证码算法)共3大系列,常用于验证数据的完整性,是数字签名算法的核心算法。

MD5和SHA1分别是MD、SHA算法系列中最有代表性的算法。

如今,MD5已被发现有许多漏洞,从而不再安全。SHA算法比MD算法的摘要长度更长,也更加安全。

Java生成MD5和SHA信息摘要

JDK中使用MD5和SHA这两种消息摘要的方式基本一致,步骤如下:
(1)初始化MessageDigest对象
(2)更新要计算的内容
(3)生成摘要

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

import org.apache.commons.codec.binary.Base64;

public class MsgDigestDemo{
    public static void main(String args[]) throws NoSuchAlgorithmException, UnsupportedEncodingException {
        String msg = "Hello World!";

        MessageDigest md5Digest = MessageDigest.getInstance("MD5");
        // 更新要计算的内容
        md5Digest.update(msg.getBytes());
        // 完成哈希计算,得到摘要
        byte[] md5Encoded = md5Digest.digest();

        MessageDigest shaDigest = MessageDigest.getInstance("SHA");
        // 更新要计算的内容
        shaDigest.update(msg.getBytes());
        // 完成哈希计算,得到摘要
        byte[] shaEncoded = shaDigest.digest();

        System.out.println("原文: " + msg);
        System.out.println("MD5摘要: " + Base64.encodeBase64URLSafeString(md5Encoded));
        System.out.println("SHA摘要: " + Base64.encodeBase64URLSafeString(shaEncoded));
    }
}

[Java 安全]消息摘要与数字签名
https://www.cnblogs.com/jingmoxukong/p/5700906.html


数字签名(摘要加密后就是签名)

数字签名算法可以看做是一种带有密钥的消息摘要算法,并且这种密钥包含了公钥和私钥。也就是说,数字签名算法是非对称加密算法和消息摘要算法的结合体。

数字签名是由信本身的内容经过hash算法计算得到digest摘要,然后用A的私钥加密而来的。

签名,使用私钥对需要传输的文本的摘要进行加密,得到的密文即被称为该次传输过程的签名。

特点
数字签名算法要求能够验证数据完整性、认证数据来源,并起到抗否认的作用。

原理
数字签名算法包含签名和验证两项操作,遵循私钥签名,公钥验证的方式。

签名时要使用私钥和待签名数据,验证时则需要公钥、签名值和待签名数据,其核心算法主要是消息摘要算法。


跳跃表

常用算法
RSA、DSA、ECDSA

Java实现数字签名和验证

签名
用私钥为消息计算签名
验证
用公钥验证摘要

import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.Signature;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;

import org.apache.commons.codec.binary.Base64;

public class DsaCoder{
    public static final String KEY_ALGORITHM = "DSA";

    public enum DsaTypeEn {
        MD5withDSA, SHA1withDSA
    }

    /**
    * DSA密钥长度默认1024位。 密钥长度必须是64的整数倍,范围在512~1024之间
    */
    private static final int KEY_SIZE = 1024;

    private KeyPair keyPair;

    public DsaCoder() throws Exception {
        keyPair = initKey();
    }

    public byte[] signature(byte[] data, byte[] privateKey) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey key =keyFactory.generatePrivate(keySpec);

        Signature signature = Signature.getInstance(DsaTypeEn.SHA1withDSA.name());
        signature.initSign(key);
        signature.update(data);
        return signature.sign();
    }

    public boolean verify(byte[] data, byte[] publicKey, byte[] sign) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(publicKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey key =keyFactory.generatePublic(keySpec);

        Signature signature = Signature.getInstance(DsaTypeEn.SHA1withDSA.name());
        signature.initVerify(key);
        signature.update(data);
        return signature.verify(sign);
    }

    private KeyPair initKey() throws Exception {
        // 初始化密钥对生成器
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
        // 实例化密钥对生成器
        keyPairGen.initialize(KEY_SIZE);
        // 实例化密钥对
        return keyPairGen.genKeyPair();
    }

    public byte[] getPublicKey() {
        return keyPair.getPublic().getEncoded();
    }

    public byte[] getPrivateKey() {
        return keyPair.getPrivate().getEncoded();
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World";
        DsaCoder dsa = new DsaCoder();
        byte[] sign = dsa.signature(msg.getBytes(), dsa.getPrivateKey());
        boolean flag = dsa.verify(msg.getBytes(), dsa.getPublicKey(), sign);
        String result = flag ? "数字签名匹配" : "数字签名不匹配";
        System.out.println("数字签名:" + Base64.encodeBase64URLSafeString(sign));
        System.out.println("验证结果:" + result);
    }
}

[Java 安全]消息摘要与数字签名
https://www.cnblogs.com/jingmoxukong/p/5700906.html


数字证书(经过CA认证的加密的公钥)

数字签名是由信本身的内容经过hash算法计算得到digest摘要,然后用A的私钥加密而来的。
数字证书是A向数字证书中心(CA)申请的,是由A的个人信息,公钥等经过CA的私钥加密而来的。

什么是数字证书?
经CA认证加密后的公钥,即是证书,又称为CA证书,证书中包含了很多信息,最重要的是申请者的公钥。

假设A给B写一份信。那么这封将包含如下三部分内容:
1.信本身的内容(直接可以看到,未加密)
2.A的数字签名
3.A的数字证书

然后B收到了这封信。B会想这封确定是A发过来的吗?这封信在发送过程中有被篡改,还是完整的吗?只有当B确认清楚,才能判断出信的内容是否可靠。

然后B先用CA提供的公钥解开数字证书,根据得到的内容如A的个人信息,确定是A发过来的,然后拿到了A的公钥。

接着,用A的公钥解开A的数字签名就能得到,信本身内容的摘要。然后将信的第一部分即信的本身内容经hash计算得到又一个摘要,将两个摘要比较,如果相同说明信的内容没有被篡改。

最后,便能确定信的可靠性了。

公钥,私钥,数字签名,数字证书个人总结
https://blog.csdn.net/sum_rain/article/details/36897095

为什么需要数字证书?

首先要知道数字签名的验证过程:
签名验证,数据接收端,拿到传输文本,但是需要确认该文本是否就是发送发出的内容,中途是否曾经被篡改。因此拿自己持有的发送方公钥对签名进行解密,得到了文本的摘要,然后使用与发送方同样的HASH算法计算摘要值,再与解密得到的摘要做对比,发现二 者完全一致,则说明文本没有被篡改过

1、在签名验证的过程中,有一点很关键,收到数据的一方,需要自己保管好公钥,但是要知道每一个发送方都有一个公钥,那么接收数据的人需要保存非常多的公钥,这根本 就管理不过来。
2、并且本地保存的公钥有可能被篡改替换,无从发现。

怎么解决这一问题了?
由一个统一的证书管理机构来管理所有需要发送数据方的公钥,对公钥进 行认证和加密。这个机构也就是我们常说的CA。认证加密后的公钥,即是证书,又称为CA证书,证书中包含了很多信息,最重要的是申请者的公钥。

CA 机构在给公钥加密时,用的是一个统一的密钥对,在加密公钥时,用的是其中的私钥。这样,申请者拿到证书后,在发送数据时,用自己的私钥生成签名,将签名、 证书和发送内容一起发给对方,对方拿到了证书后,需要对证书解密以获取到证书中的公钥,解密需要用到CA机构的”统一密钥对“中的公钥,这个公钥也就是我 们常说的CA根证书,通常需要我们到证书颁发机构去下载并安装到相应的收取数据的客户端,如浏览器上面。这个公钥只需要安装一次。有了这个公钥之后,就可 以解密证书,拿到发送方的公钥,然后解密发送方发过来的签名,获取摘要,重新计算摘要,作对比,以验证数据内容的完整性。

公钥私钥加密解密数字证书数字签名详解
https://www.cnblogs.com/kex1n/p/5582530.html


Base64编码

为什么要使用Base64(任意数据转换为asc字符)

Base64编码的作用:由于某些系统中只能使用ASCII字符。Base64就是用来将非ASCII字符的数据转换成ASCII字符的一种方法。

Base64是一种很常见的编码规范,其作用是将二进制序列转换为人类可读的ASCII字符序列,常用在需用通过文本协议(比如HTTP和SMTP)来传输二进制数据的情况下。Base64并不是加密解密算法,尽管我们有时也听到使用Base64来加密解密的说法,但这里所说的加密与解密实际是指编码(encode)和解码(decode)的过程,其变换是非常简单的,仅仅能够避免信息被直接识别。

[Java 安全]加密算法
http://www.cnblogs.com/jingmoxukong/p/5688306.html

Base64编码原理

那么Base64到底是怎样编码的呢?

简单来说,任何一个数据无非可以看作一个比特流,如01000100010011101100111010111100011001010……那么我们取6个比特为一组,计算它的ascii值,得到一个字符,这个字符肯定是可见字符,好,把它对应的字符写出来,再取6个比特,计算…,如此下去,直到最后,就完成了编码。

1、标准base64只有64个字符(英文大小写、数字和+、/)以及用作后缀等号;
2、base64是把3个字节变成4个可打印字符,所以base64编码后的字符串一定能被4整除(不算用作后缀的等号);
3、等号一定用作后缀,且数目一定是0个、1个或2个。这是因为如果原文长度不能被3整除,base64要在后面添加\0凑齐3n位。为了正确还原,添加了几个\0就加上几个等号。显然添加等号的数目只能是0、1或2;
4、严格来说base64不能算是一种加密,只能说是编码转换。使用base64的初衷。是为了方便把含有不可见字符串的信息用可见字符串表示出来,以便复制粘贴;Base64是一种可逆的编码方式。

为什么要使用base64编码,有哪些情景需求? - 郭无心的回答 - 知乎
https://www.zhihu.com/question/36306744/answer/71626823

Base64使用场景

它的使用场景有很多,比如:
1、将图片等资源文件以Base64编码形式直接放于代码中,使用的时候反Base64后转换成Image对象使用;
2、有些文本协议不支持不可见字符的传递,只能转换成可见字符来传递信息。
3、有时在一些特殊的场合,大多数消息是纯文本的,偶尔需要用这条纯文本通道传一张图片之类的情况发生的时候,就会用到Base64,比如多功能Internet 邮件扩充服务(MIME)就是用Base64对邮件的附件进行编码的。
4、base64 最早就是用来邮件传输协议中的,原因是邮件传输协议只支持 ascii 字符传递,因此如果要传输二进制文件,如:图片、视频是无法实现的。因此 base64 就可以用来将二进制文件内容编码为只包含 ascii 字符的内容,这样就可以传输了

Java中使用Base64编码

1、在JDK1.6之前,JDK核心类一直没有Base64的实现类,有人建议用JDK里面的【sun.misc.BASE64Encoder】和 【sun.misc.BASE64Decoder】,使用它们的优点就是不需要依赖第三方类库,缺点就是可能在未来版本会被删除(用maven编译会发出警告),而且性能不佳。

2、JDK1.6中添加了另一个Base64的实现【javax.xml.bind.DatatypeConverter】两个静态方法【parseBase64Binary】和【printBase64Binary】,隐藏在javax.xml.bind包下面,不被很多开发者知道。

3、在Java8在java.util包下面实现了BASE64编解码API,而且性能不俗,API也简单易懂
该类提供了一套静态方法获取下面三种BASE64编解码器:
Basic编码:是标准的BASE64编码,用于处理常规的需求
URL编码:使用下划线替换URL里面的反斜线“/”
MIME编码:使用基本的字母数字产生BASE64输出,而且对MIME格式友好:每一行输出不超过76个字符,而且每行以“\r\n”符结束。

4、第三方实现Base64的API
常用的是Apache Commons Codec library里面的【org.apache.commons.codec.binary.Base64】

Base64编码
http://www.cnblogs.com/baiqiantao/p/d0bbba14f1b942af618226893ee83f1b.html


上一篇 Java面试准备-(12)智力题

下一篇 Java面试准备-(10)JMS和MQ

阅读
31,694
阅读预计116分钟
创建日期 2018-05-28
修改日期 2018-12-13
类别
标签
目录
  1. 算法
    1. 树和二叉树
      1. 完全二叉树(Complete Binary Tree)
      2. 二叉搜索树(二叉排序树)(BST)
        1. 查找与性能分析O(logn)->O(n)
      3. 平衡二叉树(AVL)
      4. 红黑树(RBT)
        1. 红黑树的插入
          1. 1、把红黑树当做BST插入结点
          2. 2、把插入结点染为红色
            1. 为什么将插入结点看做红色?
          3. 3、旋转与着色使之再次成为红黑树
        2. 红黑树的应用
        3. 红黑树与AVL对比
      5. B-树(B树)
        1. 为什么数据库索引使用B树?
      6. B+树
        1. B+树与B树对比
        2. B树和B+树与索引
    2. 排序
      1. 快速排序(nlogn不稳定)
        1. 步骤及实现
        2. 时间复杂度
        3. 快速排序优化
          1. 优化枢轴选取
          2. 分割到一定程度后使用插入排序
          3. 递归栈优化(尾递归优化)
        4. 快速排序应用
          1. 寻找第k小的数
          2. 求数组的中位数(出现次数过半的数)
      2. 归并排序(nlogn稳定)
      3. Timsort(归并加插入)(nlogn稳定)
      4. 希尔排序(减少插入排序的移动次数)
      5. 堆排序(nlogn不稳定)
    3. 栈和队列
      1. 最大栈(最小栈)
      2. 用两个栈实现一个队列
      3. 两个队列实现一个栈
      4. 用java实现生产者消费者模式
    4. 数组/链表
      1. 跳跃表(skiplist)
      1. 图的遍历
        1. 深度优先搜索(DFS)
        2. 广度优先搜索(BFS)
        3. 判断图的连通性(DFS/BFS)
      2. 最短路径
        1. 无权图最短路径(BFS)
        2. 赋权图单源最短路径(迪杰斯特拉算法)
        3. 赋权图多源最短路径(弗洛伊德算法)
    5. LeetCode刷题
    6. 看之前的面试题
    7. 尾递归优化(改为循环)
  2. 设计模式√
    1. 单例模式
      1. 懒汉模式和饿汉模式
      2. 单例模式的线程安全性
      3. 实现单例模式的8中方法
        1. 1、饿汉式(静态常量)[可用]
        2. 2、饿汉式(静态代码块)[可用]
        3. 3、懒汉式(线程不安全)[不可用]
        4. 4、懒汉式(线程安全,同步方法)[不推荐用]
        5. 5、懒汉式(线程安全,同步代码块)[不可用]
        6. 6、双重检查[推荐用]
          1. 双重检查时的实例对象为什么必须是volatile的?
        7. 7、静态内部类[推荐用]
        8. 8、枚举(防止反序列化重建单例)[推荐用]
      4. 利用反射构造多个单例对象
      5. 反序列化对单例模式的破坏
    2. 工厂模式
      1. 简单工厂模式(静态工厂模式)
      2. 工厂方法模式
      3. 抽象工厂模式
      4. 为什么使用工厂模式?(优点)
    3. 装饰器模式
      1. 装饰模式和代理模式区别
      2. Java IO中的装饰模式(InputStream-FilterInputStream)
    4. 代理模式
      1. 静态代理
      2. JDK动态代理
        1. InvocationHandler接口
        2. Proxy类
        3. 动态代理实例
    5. 策略模式
    6. 状态模式
      1. 策略模式和状态模式的区别
    7. 适配器模式
      1. 类适配器
      2. 对象适配器
      3. 最小接口原则
      4. 缺省适配器
      5. 使用适配器模式克服观察者模式的缺点
    8. 迭代器模式
    9. 观察者模式
      1. 观察者模式实例
      2. 推模式和拉模式
      3. Java内置观察者模式
  3. Linux命令与Shell
    1. 常用Linux命令
      1. lsof列出当前系统打开文件
      2. top结果中load过高可能原因?
      3. kill -2,-9,-15
    2. Shell脚本
    3. epoll
    4. linux 守护进程
      1. 进程组与会话期
      2. setsid()
      3. 如何创建守护进程?
  4. 计算机基础
    1. TCP三次握手和四次挥手
      1. 三次握手
        1. 为什么需要3次握手?
      2. 四次挥手
        1. 为什么连接是三次握手而关闭时需要四次握手?
    2. 进程/线程/并发
      1. 进程和线程的区别
      2. 并行(Parallel)与并发(Concurrent)的区别
      3. 多线程是否一定比单线程快?
      4. 死锁的四个必要条件
    3. 内存分页
      1. 为什么要分页?(内存碎片/虚拟内存)
      2. 一般一个内存页大小为4KB
    4. 网络安全
      1. 加密算法
        1. 对称加密(DES/AES)
        2. 非对称加密(RSA)
        3. 对称加密和非对称加密对比
        4. 对称加密和非对称加密结合使用
      2. 信息摘要(MD5/SHA)
        1. Java生成MD5和SHA信息摘要
      3. 数字签名(摘要加密后就是签名)
        1. Java实现数字签名和验证
      4. 数字证书(经过CA认证的加密的公钥)
        1. 为什么需要数字证书?
      5. Base64编码
        1. 为什么要使用Base64(任意数据转换为asc字符)
        2. Base64编码原理
        3. Base64使用场景
        4. Java中使用Base64编码
百度推荐