(一)局部二值模式LBP的简介
 

          
  LBP(Local Binary Pattern,局部二值模式)是一种描述图像局部纹理的特征算子，该算子是由T.Ojala等人于1994年首次提出来的，后来经过改进，可用于图像特征分析，该算子具有旋转不变性和灰度不变性等显著的优点。
 

        经过改进之后的局部二值模式LBP特征是高效的图像特征分析方法， 已经应用于多个领域之中，特别是在人脸识别、表情识别、行人检测、纹理分类等领域取得了成功。LBP特征将窗口中心点与邻域点的关系进行比较，重新编码已形成新的特征，这样在一定程序上消除了外界场景对图像的影响，因此，在一定程度上解决了复杂场景下(光照变化)的特征描述的问题。
 
（二）经典的LBP特征设计
 

      
  经典的LBP算子定义为3*3的正方形窗口，以窗口的中心像素为阈值，将其相邻的8邻域像素的灰度值与当前窗口的中心点的像素值进行比较，若邻域的像素值小于中心点的像素值，则置该像素点的值为0，反之，则置为1。这样，一个3*3窗口的邻域内的8个像素点和中心像素点进行比较之后，就会产生一个8位的二进制数,即可产生256中LBP码，通过这样计算得到的LBP码值就可以用来反映该窗口的区域纹理特征信息。如下图所示:   
 

 
 
 
 
        
 八位的二进制数组成LBP码值的的规则是：在这个3*3的窗口内，沿着顺时针开始组合成一个8位的二进制数，然后转换成10进制数。
 

       需要说明的是：局部二值模式LBP特征描述的是一种灰度范围内的图像处理技术，针对的输入图像是8位的灰度图像。经典的LBP特征的缺点是无法区分窗口中中心点像素的值到底是等于还是大于邻域上像素点的灰度值，后续的改进引入了LBP+和LBP-因子用来区分上述说的这个缺点。
 
1）灰度不变性
 

      通常，同样的物体具有同样的纹理特征，但是在不同时间段对物体的拍照会因为外界的光照变换，导致同样物体不同时间段或者不同光照条件下的成像，亮度差异比较大。但是LBP具有灰度不变性的特征，可以抑制光照变换所带来的影响。
 

       如下图所示，第一幅图想经过LBP变换后得到的LBP码为11110001.而第二幅图像的每个像素在第一幅图像的基础上增加50，进行LBP变换后，得到的LBP码值仍然是11110001.因此，LBP特征反应了局部亮度的相对变化，所以整体上增加或者减少一个值对于LBP特征没有大的影响。因此得到结论:差分分布对平均光强不敏感。
 

       但是，需要说明的是:LBP特征也仅仅实在一定程度上对于光照具有鲁棒性；例如，阴影对于物体成像的影响，LBP就没有很好的抵抗性能。
 

  
 
 
 
 
 (三)圆形LBP
 
 
       经典的LBP用3*3的正方形窗口的8邻域来描述图像的局部图像纹理特征，其缺点就是难以满足不同尺度和频率的要求。Ojala等人对经典的LBP进行来改进，提出了将3*3的正方形窗口扩展到任意的圆形邻域。如下图所示，所谓圆形邻域，只是采样的点选择不同于八邻域。它是以中心像素为圆心，以R为半径画圆，在圆的边界商均匀的选取P个点作为采样点。而后面的处理方法与前面的八邻域LBP方法一致。
 
 

          需要说明的是:由于圆形LBP采样点在圆形边界点上，那么必然会导致部分计算出来的采样点的坐标不是整数，因此，在这里就需要对得到的坐标点像素值进行处理，常用的方法就是最近邻插值和双线性插值。下图是R=1(pixel)，P=8时的情况。 
 
 
 

        
 
 
 

       我们可以发 ，R的大小就决定了圆的大小，反应了二维空间的尺度；而P的大小就决定了采样点的点数，反应了角度空间的分辨率。同样，我们还可以通过改变R值和P值，实现不同的尺度和角度分辨率(如下图所示)。
 
 
 

   
  
 
 
  
 
 
  
 
 
 
 
1）旋转不变性
 
 

       对于下图的两个模式，其实只有方向不同，在实际中，是同一个模式的不同状态，为了克服旋转带了的变化，引入了“旋转不变性的概念”。
 
 
 

  
 
 
 
 

        处理方法如下所示:两种模式各有一个LBP值。将这个LBP值不断的循环右移，并找到一个右移过程中最小的结果，作为新的LBP。可见，这两种模式得到的新的LBP值相同，属于同一种模式。以此解决方向变化的问题。其中，“循环右移”的实质是对模式图案不断的旋转。“最小化”的过程的实质是“寻找能量最低的位置”。
 
 
 

  
 
 
 
 

        对P=8的LBP，一共有8个采样点，每个采样点可能输出0或者1，所以一共有256种局部二值模式。其中一些仅仅是方向不同，通过旋转之后就可以重合。通过以上的旋转不变性处理之后，256种LBP变味了具有"旋转不变性"的36种模式。如下图所示:特点是，任意两种模式经过任意旋转之后不会重合。  
 
 
 

     
 
 
 
 
2）增强型旋转不变性
 
 

         
    
  在实际应用中，我们通过统计就会发现，上图中第一行的九种模式最为常见，而后面的27中模式并不常见，如果将后面的27种模式单独归类的话，会因为它们出现的概率太小，而具有一定的随机性，因此，分类结果反而不稳定。因此。我们对这种方法进行了改进。
 
 
 

        我们对每个LBP上的数值按顺序读一圈，将0->1和1->0的变化次数记为U。对于上图可以发现,第一行模式的U值均小于2(反映了平坦或者变换区域)，而后面的27中模式的U值大于等于4(变化剧烈，不常见)。如下图所示。这样对于一般的LBP进行处理时，我们将U值小于等于2LBP每个单独跟为一类，而对于U值大于4的LBP全部归为一类。在P=8的情况下，原先分好的36类就变为现在的10类。
 
 
 
 
 
 
 
 
 
 
3）LBP特征直方图
 
 

          
   我们以横坐标X表示LBP的类别，纵坐标Y表示这一类别上的LBP特征的个数，这样我们将会得到一个LBP的特征直方图。如下图所示。
 
 
 
 
 
 
 
 
 
 参考的资料:
 
 
 1)http://blog.csdn.net/ws_20100/
 
 
 2)http://blog.csdn.net/u013207865/article/details/49720509
 
 
 

 
 
转载请注明出处（万分感谢！）： 
 http://blog.csdn.net/javazejian/article/details/52953190 
 出自【zejian的博客】
 
 
关联文章:
 
java数据结构与算法之顺序表与链表设计与实现分析 
 java数据结构与算法之双链表设计与实现 
 java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList（带Iterator迭代器与fast-fail机制） 
 java数据结构与算法之栈（Stack）设计与实现 
 java数据结构与算法之队列(Queue)设计与实现 
 java数据结构与算法之递归思维(让我们更通俗地理解递归) 
 java数据结构与算法之树基本概念及二叉树（BinaryTree）的设计与实现 
 java数据结构与算法之平衡二叉查找树(AVL树)的设计与实现
 
  数据结构与算法这门学科虽然在大学期间就已学习过了，但是到现在确实也忘了不少，因此最近又重新看了本书-《数据结构与算法分析》加上之前看的《java数据结构》也算是对数据结构的进一步深入学习了，于是也就打算写一系列的数据结构的博文以便加深理解，这些博文涵盖了自己对数据结构与算法的理解也包含了这类书籍的基础内容，所以博文中会包含书中的一些概念的引用段落，看到时也不必惊讶，本篇是开篇，主要涵盖顺序表与链表的知识点，关于顺序表与链表将会分两篇博文记录，而本篇将从以下几点出发分析线性表的设计与实现。
 


 
 
  
线性表抽象数据类型概述
线性表的顺序存储设计与实现顺序表
    
1 顺序存储结构的设计原理概要
2 顺序存储结构的实现分析
3 顺序存储结构的效率分析
 
线性表的链式存储设计与实现链表
    
1 链表的链式存储结构设计原理概要
2 单链表的储结构实现分析
3 带头结点的单链表以及循环单链表的实现
      
带头结点的单链表
循环单链表
 
4 单链表的效率分析
 
 
 
 
 
 
1.线性表抽象数据类型概述
 
  首先来说明一下什么是抽象数据类型，我们都知道java在默认情况下，所有的基本数据类型(int,float,boolean等)都支持基本运算，如加减法，这是因为系统已帮我们实现了这些基本数据类型的的基本运算。而对于自定义的数据类型(如类)也需要定义相应的运算，但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算，也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等，所以接下来我们要分析的顺序表和链表也属于ADT范畴。下面引用自java数据结构一书对线性表的定义：
 
 
 
  线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,an-1组成的有限的序列，在数学中记作(a0,a1,…,an-1)，其中ai的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数，也称其为长度(Length)。若n=0，则为空表；若n > 0，则ai(0 < i < n-1)有且仅有一个前驱(Predecessor)元素ai-1和一个后继(Successor)元素ai+1，a0没有前驱元素，ai没有后继元素。
 
 
以上便是对线性表抽象数据类型概述，下面我们开始分别针对顺序表和链表进行深入分析。
 
2.线性表的顺序存储设计与实现（顺序表）
 
2.1 顺序存储结构的设计原理概要
 
  顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址，就如下图所示： 
  
   通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。而顺序表的存储原理正如上图所示，因此顺序表的定义如下（引用）：
 
 
 
  线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0< i <> n-1)存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。
 
 
2.2 顺序存储结构的实现分析
 
  接着我们来分析一下顺序表的实现，先声明一个顺序表接口类ISeqList<T>，然后实现该接口并实现接口方法的代码，ISeqList接口代码如下：
 
package com.zejian.structures.LinkedList;

/**
 * Created by zejian on 2016/10/30.
 * 顺序表顶级接口
 */
public interface ISeqList<T> {

    /**
     * 判断链表是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 链表长度
     * @return
     */
    int length();

    /**
     * 获取元素
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 设置某个元素的值
     * @param index
     * @param data
     * @return
     */
    T set(int index, T data);

    /**
     * 根据index添加元素
     * @param index
     * @param data
     * @return
     */
    boolean add(int index, T data);

    /**
     * 添加元素
     * @param data
     * @return
     */
    boolean add(T data);

    /**
     * 根据index移除元素
     * @param index
     * @return
     */
    T remove(int index);

    /**
     * 根据data移除元素
     * @param data
     * @return
     */
    boolean remove(T data);

    /**
     * 根据data移除元素
     * @param data
     * @return
     */
    boolean removeAll(T data);

    /**
     * 清空链表
     */
    void clear();

    /**
     * 是否包含data元素
     * @param data
     * @return
     */
    boolean contains(T data);

    /**
     * 根据值查询下标
     * @param data
     * @return
     */
    int indexOf(T data);

    /**
     * 根据data值查询最后一个出现在顺序表中的下标
     * @param data
     * @return
     */
    int lastIndexOf(T data);

    /**
     * 输出格式
     * @return
     */
    String toString();
    }
}
 
  代码中声明了一个Object数组，初始化数组大小默认为64，存储的元素类型为泛型T，length则为顺序表的长度，部分方法实现比较简单，这里不过多分析，我们主要分析get(int index)、set(int index, T data)、add(int index, T data)、remove(int index)、removeAll(T data)、indexof(T data)等方法的实现。
 
get(int index) 实现分析 
 从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可，代码实现如下：
 
public T get(int index){
   if (index>=0 && index<this.length)
       return (T) this.table[index];         
   return null;
}
set(int index, T data) 实现分析 
 在顺序表中替换值也是非常高效和简单的，只要根据传递的索引值index找到需要替换的元素，然后把对应元素值替换成传递的data值即可，代码如下：
 
public T set(int index, T data){
   if (index>=0 && index<this.length&& data!=null)
     {
         T old = (T)this.table[index];
         this.table[index] = data;
         return old;
     }
     return null;
 }
add(int index, T data)实现分析 
 在顺序表中执行插入操作时，如果其内部数组的容量尚未达到最大值时，可以归结为两种情况，一种是在头部插入或者中间插入，这种情况下需要移动数组中的数据元素，效率较低，另一种是在尾部插入，无需移动数组中的元素，效率高。但是当顺序表内部数组的容量已达到最大值无法插入时，则需要申请另一个更大容量的数组并复制全部数组元素到新的数组，这样的时间和空间开销是比较大的，也就导致了效率更为糟糕了。因此在插入频繁的场景下，顺序表的插入操作并不是理想的选择。下面是顺序表在数组容量充足下头部或中间插入操作示意图（尾部插入比较简单就不演示了）： 
  
 顺序表在数组容量不充足的情况下头部或中间插入操作示意图： 
  
 理解了以上几种顺序表的插入操作后，我们通过代码来实现这个插入操作如下，注释很清晰就过多分析了：
 
/**
   * 根据index插入元素
   * @param index 插入位置的下标,0作为起始值
   * @param data 插入的数据
   * @return
   */
  public boolean add(int index, T data){                                        
     if (data==null)
         return false;

     //插入下标的容错判断,插入在最前面
     if (index<0)                             
         index=0;

     //插入下标的容错判断,插入在最后面
     if (index>this.length)
         index = this.length;

     //判断内部数组是否已满
     if (this.length==table.length)              
     {
         //把原数组赋值给临时数组
         Object[] temp = this.table;

         //对原来的数组进行成倍拓容,并把原数组的元素复制到新数组
         this.table = new Object[temp.length*2];   

         //先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组
         for (int i=0; i<index; i++) {
             this.table[i] = temp[i];
         }
     }

     //从原数组的最后一个元素开始直到index位置,都往后一个位置
     // 最终腾出来的位置就是新插入元素的位置了
     for (int j=this.length-1; j>=index; j--) {
         this.table[j + 1] = this.table[j];
     }
     //插入新值
     this.table[index] = data;
     //长度加一
     this.length++;
     //插入成功
     return true;
  }
remove(int index) 实现分析 
 顺序表的删除操作和前的插入操作情况是类似的，如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。如下图所示在顺序表中删除元素ai时，ai之后的元素都依次往前移动： 
  
 删除操作的代码实现如下：
 
/**
  * 根据index删除元素
  * @param index 需要删除元素的下标
  * @return
  */
 public T remove(int index)
 {
     if (this.length!=0 && index>=0 && index<this.length)
     {
         //记录删除元素的值并返回
         T old = (T)this.table[index];

         //从被删除的元素位置开,其后的元素都依次往前移动
         for (int j=index; j<this.length-1; j++) {
             this.table[j] = this.table[j + 1];
         }
         //设置数组元素对象为空
         this.table[this.length-1]=null;
         //顺序表长度减1
         this.length--;
         return old;                         
     }
     return null;
 }
removeAll(T data) 实现分析 
 在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理，因此我们只要通过比较找到与data相等的数据元素并获取其下标，然后调用前面实现的remove(int index)方法来移除即可。代码实现如下：
 
@Override
public boolean removeAll(T data) {
    boolean done=false;
    if (this.length!=0 && data!=null)
    {
        int i=0;
        while (i<this.length)
            //找出数据相同的选项
            if (data.equals(this.table[i]))
            {
                this.remove(i);//根据下标删除
                done = true;
            }
            else
                i++;//继续查找
    }
    return done;
}
indexOf(T data) 实现分析 
 要根据data在顺序表中查找第一个出现的数据元素的下标，只需要通过对比数据项是否相等，相等则返回下标，不相等则返回-1，indexOf和lastIndexOf方法实现如下：
 
/**
 * 根据数据查询下标
 * @param data
 * @return
 */
@Override
public int indexOf(T data)
{
    if (data!=null)
        for (int i=0; i<this.length; i++) {
            //相当则返回下标
            if (this.table[i].equals(data))
                return i;
        }
    return -1;
}

/**
 * 根据data查询最后一个出现在顺序表中的下标
 * @param data
 * @return
 */
@Override
public int lastIndexOf(T data)
{
    if (data!=null)
        for (int i=this.length-1; i>=0; i--)
            if (data.equals(this.table[i]))
                return i;
    return -1;
}
 
  以上便是顺序表的主要的操作方法，当然顺序表中还可以实现其他操作，如在初始化构造函数时传入数组来整体初始化顺序表，比较两个信息表是否相等、是否包含某个数据等。这里贴一下传入数据构建顺序表构造方法实现，其他实现代码我们这里就不贴了，稍后实现源码都会上传gitHub提供给大家：
 
/**
* 传入一个数组初始化顺序表
* @param array
*/
public SeqList(T[] array){
  if (array==null){
      throw new NullPointerException("array can\'t be empty!");
  }
  //创建对应容量的数组
  this.table = new Object[array.length];
//复制元素
  for (int i=0;i<array.length;i++){
      this.table[i]=array[i];
  }

  this.length=array.length;
}
 
2.3 顺序存储结构的效率分析
 
  通过上述的分析，我们对顺序表的实现已有了比较清晰的认识，接下来看一下顺序表的执行效率问题，主要针对获取、插入、修改、删除等主要操作。前面分析过，由于顺序表内部采用了数组作为存储容器，而数组又是随机存取结构的容器，也就是说在创建数组时操作系统给数组分配的是一块连续的内存空间，数组中每个存储单元的地址都是连续的，所以在知道数组基地址后可以通过一个简单的乘法和加法运算即可计算出其他存储单元的内存地址(实际上计算机内部也就是这么做的)，这两个运算的执行时间是常数时间，因此可以认为数组的访问操作能在常数时间内完成，即顺序表的访问操作(获取和修改元素值)的时间复杂为O(1)。 
   对于在顺序表中插入或者删除元素，从效率上则显得不太理想了，由于插入或者删除操作是基于位置的，需要移动数组中的其他元素，所以顺序表的插入或删除操作，算法所花费的时间主要是用于移动元素，如在顺序表头部插入或删除时，效率就显得相当糟糕了。若在最前插入或删除，则需要移动n（这里假设长度为n）个元素；若在最后插入或删除，则需要移动的元素为0。这里我们假设插入或删除值为第i(0<i<=n)个元素，其概率为$p_{i}$，则插入或删除一个元素的平均移动次数求和为：
 
 
 

  $$p_{1}*(n-1)+p_{2}*(n-2)+...+p_{i}*(n-i)+...+p_{n-1}*1+p_{n}*0=\sum_{i=1}^{n}(p_{i}*(n-i))$$ 
 
 
 
如果在各个位置插入元素的概率相同即 $p_{i}=\frac{1}{n+1}$ (n+1个插入位置任意选择一个的概率)则有：
 
 
 

  $$\sum_{i=1}^{n}(p_{i}*(n-i))=\frac{1}{n+1}\sum_{i=1}^{n}(n-i)=\frac{1}{n+1} * \frac{n(n+1)}{2}=\frac{n}{2}=O(n)$$ 
 
 
 
  也就是说，在等概率的情况下，插入或者删除一个顺序表的元素平均需要移动顺序表元素总量的一半，其时间复杂度是O(n)。当然如果在插入时，内部数组容量不足时，也会造成其他开销，如复制元素的时间开销和新建数组的空间开销。 
   因此总得来说顺序表有以下优缺点：
 
优点
 
  
使用数组作为内部容器简单且易用
在访问元素方面效率高
数组具有内存空间局部性的特点，由于本身定义为连续的内存块，所以任何元素与其相邻的元素在物理地址上也是相邻的。
缺点
 
  
内部数组大小是静态的，在使用前必须指定大小，如果遇到容量不足时，需动态拓展内部数组的大小，会造成额外的时间和空间开销
在内部创建数组时提供的是一块连续的空间块，当规模较大时可能会无法分配数组所需要的内存空间
顺序表的插入和删除是基于位置的操作，如果需要在数组中的指定位置插入或者删除元素，可能需要移动内部数组中的其他元素，这样会造成较大的时间开销，时间复杂度为O(n)
 
3.线性表的链式存储设计与实现（链表）
 
3.1 链表的链式存储结构设计原理概要
 
  通过前面对线性顺序表的分析，我们知道当创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。鉴于这种种原因，于是链表就出场了，链表在初始化时仅需要分配一个元素的存储空间，并且插入和删除新的元素也相当便捷，同时链表在内存分配上可以是不连续的内存，也不需要做任何内存复制和重新分配的操作，由此看来顺序表的缺点在链表中都变成了优势，实际上也是如此，当然链表也有缺点，主要是在访问单个元素的时间开销上，这个问题留着后面分析，我们先通过一张图来初步认识一下链表的存储结构，如下： 
  
   从图可以看出线性链表的存储结构是用若干个地址分散的存储单元存放数据元素的，逻辑上相邻的数据元素在物理位置上不一定相邻，因此每个存储单元中都会有一个地址指向域，这个地址指向域指明其后继元素的位置。在链表中存储数据的单元称为结点(Node)，从图中可以看出一个结点至少包含了数据域和地址域，其中数据域用于存储数据，而地址域用于存储前驱或后继元素的地址。前面我们说过链表的插入和删除都相当便捷，这是由于链表中的结点的存储空间是在插入或者删除过程中动态申请和释放的，不需要预先给单链表分配存储空间的，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。
 
3.2 单链表的储结构实现分析
 
到此我们已初步了解了链表的概念和存储结构，接下来，开始分析链表的实现，这里先从单链表入手。同样地，先来定义一个顶级的链表接口:ILinkedList和存储数据的结点类Node，该类是代表一个最基本的存储单元，Node代码如下：
 
/**
 * Created by zejian on 2016/10/21.
 * 单向链表节点
 */
public class Node<T> {
    public T data;//数据域
    public Node<T> next;//地址域

    public Node(T data){
        this.data=data;
    }

    public Node(T data,Node<T> next){
        this.data=data;
        this.next=next;
    }
}
 
接着顶级的链表接口ILinkedList，该接口声明了我们所有需要实现的方法。
 
/**
 * Created by zejian on 2016/10/21.
 * 链表顶级接口
 */
public interface ILinkedList<T> {
    /**
     * 判断链表是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 链表长度
     * @return
     */
    int length();

    /**
     * 获取元素
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 设置某个结点的的值
     * @param index
     * @param data
     * @return
     */
    T set(int index, T data);

    /**
     * 根据index添加结点
     * @param index
     * @param data
     * @return
     */
    boolean add(int index, T data);

    /**
     * 添加结点
     * @param data
     * @return
     */
    boolean add(T data);

    /**
     * 根据index移除结点
     * @param index
     * @return
     */
    T remove(int index);

    /**
     * 根据data移除结点
     * @param data
     * @return
     */
    boolean removeAll(T data);

    /**
     * 清空链表
     */
    void clear();

    /**
     * 是否包含data结点
     * @param data
     * @return
     */
    boolean contains(T data);

      /**
     * 输出格式
     * @return
     */
    String toString();
}
 
创建一个单链表SingleILinkedList并实现ILinkedList接口，覆盖其所有方法，声明一个单链表的头结点head，代表链表的开始位置，如下：
 
public class SingleILinkedList<T> implements ILinkedList<T> {
   protected Node<T> headNode; //带数据头结点

   public SingleILinkedList(Node<T> head) {
       this.headNode = head;
   }
   //其他代码先省略
   .....
}
 
boolean isEmpty()实现分析 
 需要判断链表是否为空的依据是头结点head是否为null，当head=null时链表即为空链表，因此我们只需判断头结点是否为空即可，isEmpty方法实现如下：
 
/**
 * 判断链表是否为空
 * @return
 */
@Override
public boolean isEmpty() {
    return this.head==null;
}
int length()实现分析 
 由于单链表的结点数就是其长度，因此我们只要遍历整个链表并获取结点的数量即可获取到链表的长度。遍历链表需要从头结点HeadNode开始，为了不改变头结点的存储单元，声明变量p指向当前头结点和局部变量length，然后p从头结点开始访问，沿着next地址链到达后继结点，逐个访问，直到最后一个结点，每经过一个结点length就加一，最后length的大小就是链表的大小。实现代码如下：
 
@Override
public int length() {
   int length=0;//标记长度的变量
   Node<T> p=head;//变量p指向头结点
   while (p!=null){
       length++;
       p=p.next;//后继结点赋值给p，继续访问
   }
   return length;
}
 T get(int index)实现分析 
 在单链表中获取某个元素的值是一种比较费时间的操作，需要从头结点开始遍历直至传入值index指向的位置，其中需要注意的是index是从0开始计算，也就是说传递的index=3时，查找的是链表中第4个位置的值。其查询获取值的过程如下图所示： 
  
 代码实现如下：
 
/**
 * 根据index索引获取值
 * @param index 下标值起始值为0
 * @return
 */
@Override
public T get(int index) {

    if(this.head!=null&&index>=0){
        int count=0;
        Node<T> p=this.head;
        //找到对应索引的结点
        while (p!=null&&count<index){
            p=p.next;
            count++;
        }

        if(p!=null){
            return p.data;
        }
    }
    return null;
}
 
通过上图和代码，我们就可以很容易理解链表中取值操作的整个过程了。
 T set(int index, T data)实现分析 
 根据传递的index查找某个值并替换其值为data，其实现过程的原理跟get(int index)是基本一样的，先找到对应值所在的位置然后删除即可，不清晰可以看看前面的get方法的图解，这里直接给出代码实现：
 
/**
 * 根据索引替换对应结点的data
 * @param index 下标从0开始
 * @param data
 * @return 返回旧值
 */
@Override
public T set(int index, T data) {

    if(this.head!=null&&index>=0&&data!=null){
        Node<T> pre=this.head;
        int count=0;
        //查找需要替换的结点
        while (pre!=null&&count<index){
            pre=pre.next;
            count++;
        }
        //不为空直接替换
        if (pre!=null){
            T oldData=pre.data;
            pre.data=data;//设置新值
            return oldData;
        }

    }
    return null;
}
 add(int index, T data)实现分析 
 单链表的插入操作分四种情况: 
 a.空表插入一个新结点，插语句如下：
 
head=new Node<T>(x,null);
 
 
b.在链表的表头插入一个新结点(即链表的开始处)，此时表头head!=null，因此head后继指针next应该指向新插入结点p，而p的后继指针应该指向head原来的结点，代码如下：
 
//创建新结点
Node<T> p =new Node<T>(x,null);
//p的后继指针指向head原来的结点
p.next=head;
//更新head
head=p;
 
以上代码可以合并为如下代码：
 
//创建新结点，其后继为head原来的结点，head的新指向为新结点
head=new Node<T>(x,head);
 
执行过程如下图：
 
 
c.在链表的中间插入一个新结点p，需要先找到给定插入位置的前一个结点，假设该结点为front，然后改变front的后继指向为新结点p，同时更新新结点p的后继指向为front原来的后继结点，即front.next，其执行过程如下图所示： 
  
 代码实现如下：
 
//新结点p
Node<T> p =new Node<T>(x,null);
//更新p的后继指向
p.next=front.next;
//更新front的后继指向
front.next=p;
 
以上三句代码合并为一句简洁代码：
 
front.next=new Node<T>(x,front.next);
 
d.在链表的表尾插入一个新结点(链表的结尾)在尾部插入时，同样需要查找到插入结点P的前一个位置的结点front（假设为front），该结点front为尾部结点，更改尾部结点的next指针指向新结点P，新结点P的后继指针设置为null，执行过程如下： 
  
 其代码语句如下：
 
//front的next指针指向新结点，新结点的next指针设置为null
front.next=new Node<T>(x,null);
 
  到此我们也就可以发现单向链表中的中间插入和尾部插入其实可以合并为一种情况。最后这里给出该方法整体代码实现，从代码实现上来看中间插入和尾部插入确实也视为同种情况处理了。
 
  /**
     * 根据下标添加结点
     * 1.头部插入
     * 2.中间插入
     * 3.末尾插入
     * @param index 下标值从0开始
     * @param data
     * @return
     */
    @Override
    public boolean add(int index, T data) {

        if (data==null){
            return false;
        }
        //在头部插入
        if (this.head==null||index<=1){
            this.head = new Node<T>(data, this.head);
        }else {
            //在尾部或中间插入
            int count=0;
            Node<T> front=this.head;
            //找到要插入结点位置的前一个结点
            while (front.next!=null&&count<index-1){
                front=front.next;
                count++;
            }
            //尾部添加和中间插入属于同种情况,毕竟当front为尾部结点时front.next=null
            front.next=new Node<T>(data,front.next);
        }
        return true;
    }
 T remove(int index) 删除结点实现分析 
 在单向链表中，根据传递index位置删除结点的操作分3种情况，并且删除后返回被删除结点的数据： 
 a.删除链表头部（第一个）结点，此时需要删除头部head指向的结点，并更新head的结点指向，执行图示如下： 
  
 代码实现如下：
 
//头部删除，更新head指向
head=head.next;
 
b.删除链表的中间结点，与添加是同样的道理，需要先找到要删除结点r（假设要删除的结点为r）位置的前一个结点front(假设为front)，然后把front.next指向r.next即要删除结点的下一个结点，执行过程如下： 
  
 代码语句如下：
 
Node<T> r =front.next;
//更新结点指针指向
front.next=r.next;
r=null;
 
c.删除链表的最后一个结点，通过遍历操作找到最后一个结点r的前一个结点front，并把front.next设置为null，即可。执行过程如下： 
  
 代码如下：
 
front.next=null;
r=null;
 
我们把中间删除和尾部删除合并为如下代码：
 
Node<T> r =front.next;
//如果不是尾部结点，更新结点front指针指向
if(r=!null){
    front.next=r.next;
    r=null;
}
 
该方法整体代码实现如下：
 
/**
     * 根据索引删除结点
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {

        T old=null;

        if (this.head!=null&&index>=0){

            //直接删除的是头结点
            if(index==0){
                old=this.head.data;
                this.head=this.head.next;
            }else {

                Node<T> front = this.head;
                int count = 0;
                //查找需要删除结点的前一个结点
                while (front.next != null && count < index - 1) {
                    front = front.next;
                    count++;
                }

                //获取到要删除的结点
                Node<T> r = front.next;

                if ( r!= null) {
                    //获取旧值
                    old =r.data;
                    //更改指针指向
                    front.next=r.next;
                    //释放
                    r=null;
                }
            }
        }
        return old;
    }
 
当然还有如下更简洁的代码写法：
 
@Override
  public T remove(int index) {

      T old=null;

      if (this.head!=null&&index>=0){

          //直接删除的是头结点
          if(index==0){
              old=this.head.data;
              this.head=this.head.next;
          }else {

              Node<T> front = this.head;
              int count = 0;
              //查找需要删除结点的前一个结点
              while (front.next != null && count < index - 1) {
                  front = front.next;
                  count++;
              }

              if ( front.next!= null) {
                  //获取旧值
                  old =front.next.data;
                  //更改指针指向
                  front.next=front.next.next;
              }
          }
      }
      return old;
  }
void clear() 实现分析 
 清空链表是一件非常简单的事，只需让head=null即可；代码如下：
 
/**
 * 清空链表
 */
@Override
public void clear() {
    this.head=null;
}
 
  ok~,到此单链表主要的添加、删除、获取值、设置替换值、获取长度等方法已分析完毕，其他未分析的方法都比较简单这里就不一一分析了，单链表的整体代码最后会分享到github给大家。
 
3.3 带头结点的单链表以及循环单链表的实现
 
带头结点的单链表
 
前面分析的单链表是不带特殊头结点的，所谓的特殊头结点就是一个没有值的结点即：
 
//没有带值的头结点
Node<T> head= new Node<T>(null,null);
 
此时空链表的情况如下： 
  
 那么多了头结点的单向链表有什么好处呢？通过对没有带头结点的单链表的分析，我们可以知道，在链表插入和删除时都需要区分操作位，比如插入操作就分头部插入和中间或尾部插入两种情况（中间或尾部插入视为一种情况对待即可），如果现在有不带数据的头结点，那么对于单链表的插入和删除不再区分操作的位置，也就是说头部、中间、尾部插入都可以视为一种情况处理了，这是因为此时头部插入和头部删除无需改变head的指向了，头部插入如下所示： 
  
 接着再看看在头部删除的情况： 
  
 带头结点遍历从head.next开始： 
  
 因此无论是插入还是删除，在有了不带数据的头结点后，在插入或者删除时都无需区分操作位了，好~，到此我们来小结一下带头结点的单链表特点：
 
a.空单链表只有一个结点，head.next=null。
b.遍历的起点为p=head.next。
c.头部插入和头部删除无需改变head的指向。
 
  同时为了使链表在尾部插入时达到更加高效，我们可在链表内增加一个尾部指向的结点rear，如果我们是在尾部添加结点，那么此时只要通过尾部结点rear进行直接操作即可，无需从表头遍历到表尾，带尾部结点的单链表如下所示： 
  
 从尾部直接插入的代码实现如下：
 
/**
 * 尾部插入
 * @param data
 * @return
 */
@Override
public boolean add(T data) {
    if (data==null)
        throw new NullPointerException("data can\'t be empty!");

    this.rear.next = new Node<T>(data);
    //更新末尾指针的指向
    this.rear = this.rear.next;
    return true;
}
 
 
   从代码和图示看来确实只要获取当前的尾部指向的结点rear并把新结点赋值给rear.next，最后更新rear结点的值即可，完全不用遍历操作，但是如果是根据index来插入的还，遍历部分结点还是少不了的，下面看看根据index插入的代码实现，由于有了头结点，头部、中间、尾部插入无需区分操作位都视为一种情况处理。
 
/**
 * 根据下标添加结点
 * 1.头部插入
 * 2.中间插入
 * 3.末尾插入
 * @param index 该值从0开始,如传4就代表插入在第5个位置
 * @param data
 * @return
 */
@Override
public boolean add(int index, T data) {

    if (data==null){
        throw new NullPointerException("data can\'t be empty!");
    }

    if(index<0)
        throw new NullPointerException("index can\'t less than 0");

    //无需区分位置操作,中间/头部/尾部插入
    int j=0;
    Node<T> pre=this.headNode;
    //查找到插入位置即index的前一个结点
    while (pre.next!=null&&j<index){
        pre=pre.next;
        j++;
    }

    //将新插入的结点的后继指针指向pre.next
    Node<T> q=new Node<T>(data,pre.next);
    //更改指针指向
    pre.next=q;

    //如果是尾部指针
    if (pre==this.rear)
        this.rear=q;

    return true;
}
 
  最后在看看删除的代码实现，由于删除和插入的逻辑和之前不带头结点的单链表分析过的原理的是一样的，因此我们这里不重复了，主要注意遍历的起始结点变化就行。
 
 /**
     * 根据索引删除结点
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        T old=null;

        //无需区分头删除或中间删除或尾部删除的情况
        if (index>=0){
            Node<T> pre = this.headNode;
            int j = 0;
            //查找需要删除位置的前一个结点
            while (pre.next != null && j < index) {
                pre = pre.next;
                j++;
            }

            //获取到要删除的结点
            Node<T> r = pre.next;

            if (r != null) {
                //获取旧值
                old =r.data;
                //如果恰好是尾部结点,则更新rear的指向
                if (r==this.rear){
                    this.rear=pre;
                }
                //更改指针指向
                pre.next=r.next;
            }

        }
        return old;
    }
 
ok~，关于带头结点的单向链表就分析到这，这里贴出实现源码，同样地，稍后在github上也会提供：
 
package com.zejian.structures.LinkedList.singleLinked;

import com.zejian.structures.LinkedList.ILinkedList;

/**
* Created by zejian on 2016/10/22.
* 带头结点并含有尾指针的链表
*/
public class HeadSingleILinkedList<T> implements ILinkedList<T> {

   protected Node<T> headNode; //不带数据头结点
   protected Node<T> rear;//指向尾部的指针

   public HeadSingleILinkedList() {
       //初始化头结点与尾指针
       this.headNode =rear= new Node<>(null);
   }

   public HeadSingleILinkedList(Node<T> head) {
       this();
       this.headNode.next =rear.next= head;
       rear=rear.next;//更新末尾指针指向
   }

   /**
    * 传入一个数组,转换成链表
    * @param array
    */
   public HeadSingleILinkedList(T[] array)
   {
       this();
       if (array!=null && array.length>0)
       {
           this.headNode.next = new Node<T>(array[0]);
           rear=this.headNode.next;
           int i=1;
           while (i<array.length)
           {
               rear.next=new Node<T>(array[i++]);
               rear = rear.next;
           }
       }
   }

   /**
    * 通过传入的链表构造新的链表
    * @param list
    */
   public HeadSingleILinkedList(HeadSingleILinkedList<T> list) {
       this();
       if (list!=null && list.headNode.next!=null)
       {
           this.headNode.next = new Node(list.headNode.data);
           Node<T> p = list.headNode.next;
           rear = this.headNode.next;
           while (p!=null)
           {
               rear.next = new Node<T>(p.data);
               rear = rear.next;
               p = p.next;
           }
       }
   }


   /**
    * 判断链表是否为空
    * @return
    */
   @Override
   public boolean isEmpty() {
       return this.headNode.next==null;
   }

   @Override
   public int length() {
       int length=0;
       Node<T> currentNode=headNode.next;
       while (currentNode!=null){
           length++;
           currentNode=currentNode.next;
       }
       return length;
   }

   /**
    * 根据index索引获取值
    * @param index 下标值起始值为0
    * @return
    */
   @Override
   public T get(int index) {

       if(index>=0){
           int j=0;
           Node<T> pre=this.headNode.next;
           //找到对应索引的结点
           while (pre!=null&&j<index){
               pre=pre.next;
               j++;
           }

           if(pre!=null){
               return pre.data;
           }

       }
       return null;
   }

   /**
    * 根据索引替换对应结点的data
    * @param index 下标从0开始
    * @param data
    * @return 返回旧值
    */
   @Override
   public T set(int index, T data) {

       if(index>=0&&data!=null){
           Node<T> pre=this.headNode.next;
           int j=0;
           while (pre!=null&&j<index){
               pre=pre.next;
               j++;
           }

           if (pre!=null){
               T oldData=pre.data;
               pre.data=data;//设置新值
               return oldData;
           }

       }
       return null;
   }

   /**
    * 根据下标添加结点
    * 1.头部插入
    * 2.中间插入
    * 3.末尾插入
    * @param index 该值从0开始,如传4就代表插入在第5个位置
    * @param data
    * @return
    */
   @Override
   public boolean add(int index, T data) {

       if (data==null){
           throw new NullPointerException("data can\'t be empty!");
       }

       if(index<0)
           throw new NullPointerException("index can\'t less than 0");

       //无需区分位置操作,中间/头部/尾部插入
       int j=0;
       Node<T> pre=this.headNode;
       while (pre.next!=null&&j<index){
           pre=pre.next;
           j++;
       }

       //将新插入的结点的后继指针指向pre.next
       Node<T> q=new Node<T>(data,pre.next);
       //更改指针指向
       pre.next=q;

       //如果是未指针
       if (pre==this.rear)
           this.rear=q;

       return true;
   }

   /**
    * 尾部插入
    * @param data
    * @return
    */
   @Override
   public boolean add(T data) {
       if (data==null)
           throw new NullPointerException("data can\'t be empty!");

       this.rear.next = new Node<T>(data);
       //更新末尾指针的指向
       this.rear = this.rear.next;
       return true;
   }

   /**
    * 根据索引删除结点
    * @param index
    * @return
    */
   @Override
   public T remove(int index) {
       T old=null;

       //包含了头删除或中间删除或尾部删除的情况
       if (index>=0){

           Node<T> pre = this.headNode;
           int j = 0;
           //查找需要删除位置的前一个结点
           while (pre.next != null && j < index) {
               pre = pre.next;
               j++;
           }

           //获取到要删除的结点
           Node<T> r = pre.next;

           if (r != null) {
               //获取旧值
               old =r.data;
               //如果恰好是尾部结点,则更新rear的指向
               if (r==this.rear){
                   this.rear=pre;
               }
               //更改指针指向
               pre.next=r.next;
           }

       }
       return old;
   }

   /**
    * 根据data移除所有数据相同的结点
    * @param data
    * @return
    */
   @Override
   public boolean removeAll(T data) {

       boolean isRemove=false;

       if(data!=null){
           //用于记录要删除结点的前一个结点
           Node<T> front=this.headNode;
           //当前遍历的结点
           Node<T> pre=front.next;
           //查找所有数据相同的结点并删除
           while (pre!=null){
               if(data.equals(pre.data)){
                   //如果恰好是尾部结点,则更新rear的指向
                   if(data.equals(rear.data)){
                       this.rear=front;
                   }
                   //相等则删除pre并更改指针指向
                   front.next=pre.next;
                   pre =front.next;
                   isRemove=true;
               }else {
                   front=pre;
                   pre=pre.next;
               }
           }
       }
       return isRemove;
   }

   /**
    * 清空链表
    */
   @Override
   public void clear() {
       this.headNode.next=null;
       this.rear=this.headNode;
   }

   /**
    * 判断是否包含某个值
    * @param data
    * @return
    */
   @Override
   public boolean contains(T data) {

       if(data!=null){
           Node<T> pre=this.headNode.next;
           while (pre!=null){
               if(data.equals(pre.data)){
                   return true;
               }
               pre=pre.next;
           }
       }
       return false;
   }

   /**
    * 从末尾连接两个链表
    * @param list
    */
   public void concat(HeadSingleILinkedList<T> list)
   {
       if (this.headNode.next==null) {
           this.headNode.next = list.headNode.next;
       } else {
           Node<T> pre=this.headNode.next;
           while (pre.next!=null)
               pre = pre.next;
          pre.next=list.headNode.next;
           //更新尾部指针指向
           this.rear=list.rear;
       }
   }

   @Override
   public String toString() {
       String str="(";
       Node<T> pre = this.headNode.next;
       while (pre!=null)
       {
           str += pre.data;
           pre = pre.next;
           if (pre!=null)
               str += ", ";
       }
       return str+")";
   }

   public static void main(String[] args){

       String[] letters={"A","B","C","D","E","F"};
       HeadSingleILinkedList<String> list=new HeadSingleILinkedList<>(letters);

       System.out.println("list.get(3)->"+list.get(3));
       System.out.println("list:"+list.toString());

       System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
       System.out.println("list:"+list.toString());
       System.out.println("list.add(Z)—>"+list.add("Z"));
       System.out.println("list:"+list.toString());


       System.out.println("list.contains(Z)->"+list.contains("Z"));
       System.out.println("list.set(4,P)-->"+list.set(4,"P"));
       System.out.println("list:"+list.toString());

       System.out.println("list.remove(Z)->"+list.removeAll("Z"));
       System.out.println("list.remove(4)-->"+list.remove(4));
       System.out.println("list:"+list.toString());
   }
}
 
循环单链表
 
  有上述的分析基础，循环单链表(Circular Single Linked List)相对来说就比较简单了，所谓的循环单链表是指链表中的最后一个结点的next域指向了头结点head，形成环形的结构，我们通过图示来理解： 
  
 此时的循环单链表有如下特点： 
 a.当循环链表为空链表时，head指向头结点，head.next=head。 
 b.尾部指向rear代表最后一个结点，则有rear.next=head。 
 在处理循环单链表时，我们只需要注意在遍历循环链表时，避免进入死循环即可，也就是在判断循环链表是否到达结尾时，由之前的如下判断
 
Node<T> p=this.head;
while(p!=null){
     p=p.next;
}
 
在循环单链表中改为如下判断：
 
Node<T> p=this.head;
while(p!=this.head){
     p=p.next;
}
 
因此除了判断条件不同，其他操作算法与单链表基本是一样的，下面我们给出循环单链表的代码实现：
 
package com.zejian.structures.LinkedList.singleLinked;

import com.zejian.structures.LinkedList.ILinkedList;


/**
 * Created by zejian on 2016/10/25.
 * 循环单链表
 */
public class CircularHeadSILinkedList<T> implements ILinkedList<T> {

    protected Node<T> head; //不带数据头结点
    protected Node<T> tail;//指向尾部的指针


    public CircularHeadSILinkedList() {
        //初始化头结点与尾指针
        this.head= new Node<T>(null);
        this.head.next=head;
        this.tail=head;
    }


    public CircularHeadSILinkedList(T[] array)
    {
        this();
        if (array!=null && array.length>0)
        {
            this.head.next = new Node<>(array[0],head);
            tail=this.head.next;
            int i=1;
            while (i<array.length)
            {
                tail.next=new Node<>(array[i++]);
                tail.next.next=head;
                tail = tail.next;
            }
        }
    }


    @Override
    public boolean isEmpty() {
        return this.head.next==head;
    }

    @Override
    public int length() {

        int length=0;
        Node<T> p=this.head.next;
        while (p!=head){
            p=p.next;
            length++;
        }

        return length;
    }

    @Override
    public T get(int index) {

        if (index>=0)
        {
            int j=0;
            Node<T> pre=this.head.next;
            while (pre!=null && j<index)
            {
                j++;
                pre=pre.next;
            }
            if (pre!=null)
                return pre.data;
        }
        return null;
    }

    @Override
    public T set(int index, T data) {

        if (data==null){
            return null;
        }

        if(index>=0){
            int j=0;
            Node<T> p=this.head.next;

            while (p!=head&&j<index){
                j++;
                p=p.next;
            }

            //如果不是头结点
            if(p!=head){
                T old = p.data;
                p.data=data;

                return old;
            }
        }
        return null;
    }

    @Override
    public boolean add(int index, T data) {
        int size=length();
        if(data==null||index<0||index>=size)
            return false;

        int j=0;
        Node<T> p=this.head;
        //寻找插入点的位置的前一个结点
        while (p.next!=head&&j<index){
            p=p.next;
            j++;
        }

        //创建新结点,如果index=3,那么插入的位置就是第4个位置
        Node<T> q=new Node<>(data,p.next);
        p.next=q;
        //更新尾部指向
        if(p==tail){
            this.tail=q;
        }
        return true;
    }

    @Override
    public boolean add(T data) {
        if(data==null){
            return false;
        }

        Node<T> q=new Node<>(data,this.tail.next);
        this.tail.next=q;
        //更新尾部指向
        this.tail=q;

        return true;
    }

    @Override
    public T remove(int index) {
        int size=length();
        if(index<0||index>=size||isEmpty()){
            return null;
        }

        int j=0;
        Node<T> p=this.head.next;

        while (p!=head&&j<index){
            j++;
            p=p.next;
        }

        if(p!=head){
            T old =p.next.data;

            if(tail==p.next){
                tail=p;
            }
            p.next=p.next.next;

            return old;
        }

        return null;
    }

    @Override
    public boolean removeAll(T data) {
        boolean isRemove=false;
        if(data==null){
            return isRemove;
        }

        //用于记录要删除结点的前一个结点
        Node<T> front=this.head;
        //当前遍历的结点
        Node<T> pre=front.next;
        //查找所有数据相同的结点并删除
        while (pre!=head){
            if(data.equals(pre.data)){
                //如果恰好是尾部结点,则更新rear的指向
                if(data.equals(tail.data)){
                    this.tail=front;
                }
                //相等则删除pre并更改指针指向
                front.next=pre.next;
                pre =front.next;
                isRemove=true;
            }else {
                front=pre;
                pre=pre.next;
            }
        }


        return isRemove;
    }

    @Override
    public void clear() {
        this.head.next=head;
        this.tail=head;
    }

    @Override
    public boolean contains(T data) {
        if (data==null){
            return false;
        }

        Node<T> p=this.head.next;

        while (p!=head){
            if(data.equals(p.data)){
                return true;
            }

            p=p.next;
        }

        return false;
    }

    @Override
    public String toString()
    {
        String str="(";
        Node<T> p = this.head.next;
        while (p!=head)
        {
            str += p.data.toString();
            p = p.next;
            if (p!=head)
                str += ", ";
        }
        return str+")";
    }

    public static void main(String[] args){

        String[] letters={"A","B","C","D","E","F"};
        CircularHeadSILinkedList<String> list=new CircularHeadSILinkedList<>(letters);

        System.out.println("list.get(3)->"+list.get(3));
        System.out.println("list:"+list.toString());

        System.out.println("list.add(4,Y)—>"+list.add(4,"Y"));
        System.out.println("list:"+list.toString());
        System.out.println("list.add(Z)—>"+list.add("Z"));
        System.out.println("list:"+list.toString());


        System.out.println("list.contains(Z)->"+list.contains("Z"));
        System.out.println("list.set(4,P)-->"+list.set(4,"P"));
        System.out.println("list:"+list.toString());

        System.out.println("list.removeAll(Z)->"+list.removeAll("Z"));
        System.out.println("list.remove(4)-->"+list.remove(4));
        System.out.println("list:"+list.toString());
    }
}
 
3.4 单链表的效率分析
 
  由于单链表并不是随机存取结构，即使单链表在访问第一个结点时花费的时间为常数时间，但是如果需要访问第i(0<i<n)个结点，需要从头结点head开始遍历部分链表，进行i次的p=p.next操作，这点从上述的图文分析我们也可以看出，这种情况类似于前面计算顺序表需要平均移动元素的总数，因此链表也需要平均进行$\frac{n}{2}$次的p=p.next操作，也就是说get(i)和set(i,x)的时间复杂度都为O(n)。 
   由于链表在插入和删除结点方面十分高效的，因此链表比较适合那些插入删除频繁的场景使用，单纯从插入操作来看，我们假设front指向的是单链表中的一个结点，此时插入front的后继结点所消耗的时间为常数时间O(1),但如果此时需要在front的前面插入一个结点或者删除结点自己时，由于front并没有前驱指针，单凭front根本无法知道前驱结点，所以必须从链表的表头遍历至front的前一个结点再执行插入或者删除操作，而这个查询操作所消耗的时间为O(n),因此在已知front结点需要插入前驱结点或者删除结点自己时，消耗的时间为O(n)。当然这种情况并不是无法解决的，后面我们要分析到的双链表就可以很好解决这个问题，双链表是每个结点都同时拥有前后继结点的链表，这样的话上面的问题就迎刃而解了。上述是从已知单链表中front结点的情况下讨论的单链表的插入删除效率。 
   我们可能会有个疑问，从前面单链表的插入删除的代码实现上来说，我们并不知道front结点的，每次插入和删除结点，都需要从表头开始遍历至要插入或者删除结点的前一个结点，而这个过程所花费的时间和访问结点所花费的时间是一样的，即O(n)， 
 也就是说从实现上来说确实单链表的插入删除操作花费时间也是O(n)，而顺序表插入和删除的时间也是O(n)，那为什么说单链表的插入和删除的效率高呢？这里我们要明白的是链表的插入和删除之所以是O(N)，是因为查询插入点所消耗的，找到插入点后插入操作消耗时间只为O(1)，而顺序表查找插入点的时间为O(1)，但要把后面的元素全部后移一位，消耗时间为O(n)。问题是大部分情况下查找所需时间比移动短多了，还有就是链表不需要连续空间也不需要扩容操作，因此即使时间复杂度都是O(n)，所以相对来说链表更适合插入删除操作。
 
  以上便是本篇对象顺序表与单链表的分析，如有误处，欢迎留言，我们一起探讨学习。下篇会是双链表的知识点，欢迎持续关注，下面丢出github的地址： 
 GITHUB博文源码下载地址
 
关联文章:
 
java数据结构与算法之顺序表与链表设计与实现分析 
 java数据结构与算法之双链表设计与实现 
 java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList（带Iterator迭代器与fast-fail机制） 
 
如果您喜欢我写的博文，读后觉得收获很大，不妨小额赞助我一下，让我有动力继续写出高质量的博文，感谢您的赞赏！支付宝、微信
 

 
 
 
          
  
 
 

 
文章目录
 
Java 基础
Head First Java
Java 核心技术卷一
Java 编程思想
   
设计模式
Head First 设计模式
图解设计模式
设计模式
重学 Java 设计模式
   
Java 进阶
Java 并发编程实战
Java 并发编程艺术
Java 并发编程之美
图解Java多线程设计模式
   
JVM
深入理解 Java 虚拟机
Java 虚拟机规范
HotSpot 实战
自己动手写 Java 虚拟机
   
MySQL
MySQL 基础教程
SQL 基础教程
深入浅出 MySQL
MySQL 必知必会
SQL 必知必会
高性能 MySQL
MySQL 是怎样运行的
数据库索引与优化
MySQL 技术内幕：InnoDB存储引擎
MySQL技术内幕
MySQL 内核
   
Maven
MyBatis
MyBatis 从入门到精通
MyBatis 技术内幕
   
Spring
Spring 揭秘
Spring 源码深度解析
Spring 技术内幕
   
HTTP
Tomcat
深入剖析 Tomcat
Tomcat 架构解析
   
Servlet/JSP 技术
Head First Servlet/JSP
Servlet & JSP 核心编程
   
Spring MVC
SpringMVC 学习指南
看透 SpringMVC
   
SpringBoot
从设计理念谈起
Spring Boot 的 Starter 机制
Spring Boot 的豪华开发团队
有个好干爹
   
Spring Cloud
Dubbo
Redis
Redis 实战
Redis 设计与实现
Redis 开发与运维
Redis 深度历险：核心原理与应用实践
   
Kafka
Kafka 权威指南
Apache Kafka实战
深入理解Kafka：核心设计与实践原理
   
ZooKeeper
ZooKeeper 介绍
设计目标
从 Paxos 到 Zookeeper
ZooKeeper : 分布式过程协同技术详解
   
Nginx
Nginx 基础知识
Nginx 正向代理与反向代理
Nginx 基本配置
Nginx 负载均衡
Nginx常用命令
深入理解 Nginx
   
Netty
Netty 实战
   
ES
Elasticsearch 实战
Elasticsearch 源码解析与优化实战
   
Git
Git 是分布式的，SVN 是集中式的
   
Git是分布式的，SVN是集中式的
Git 复杂概念多，SVN 简单易上手
Git 分支廉价，SVN 分支昂贵
Pro Git
Git 版本控制管理
   
计算机基础
计算机组成原理
操作系统
计算机网络
数据结构和算法
关于学习的意见和建议，可以参考
  
 


 （文末有惊喜哦！！！）
 
其实学习 Java 学到什么程度算是精通，这个其实没有盖棺定论的，也不是说你拿个年薪几十万的 offer 就可以自诩精通了。另外，每当面试的时候简历上填个精通 offer 的家伙我就觉得很搞笑，没有几个熬得过开出门左拐的命运。但是我认为，如果市面上这些资料、书籍你都啃的差不多，你能在所有的 Java 程序员中跻身前 0.1% 的话，你就可以达到"精通" 这个阶段了，因为没人比你强了，你当然是精通了。
 
所以，我还是选择罗列一些知识点推荐给大家，如果你都能够掌握并且真正理解这些东西的话，那你就可以到了精通这个阶段了。
 
首先要学的是计算机基础知识，因为 Java 不是像 Python 那样简单，它是需要一定基础的，如果你上来直接硬肝 Java，那么 90% 的几率你会放弃。
 
因为要想学好 Java ，你就得理解什么是面向对象的设计思想，而面向对象的这种设计思想又不是刚开始学习编程的新人能够熟练掌握呢？那怎么办呢？这不是死局了吗？
 
其实，如果要想真正理解这种设计思想的话，你要首先学的不是 Java，而是 C 语言。
 
为什么呢？因为 C 语言是面向过程的，什么是面向过程和面向对象的设计思想呢？我给你举个例子你就知道了。
 
面向过程与面向对象的区别，由“如何把大象装进冰箱”来看：
 
一、面向过程
 
为了把大象装进冰箱，需要3个过程。
 
思路：
 
1、把冰箱门打开（得到打开门的冰箱）。
 
2、把大象装进去（打开门后，得到里面装着大象的冰箱）。
 
3、把冰箱门关上（打开门、装好大象后，获得关好门的冰箱)。
 
根据上面的思路，可以看到，每个过程都有一个阶段性的目标，依次完成这些过程，就能把大象装进冰箱。
 
二、面向对象
 
为了把大象装进冰箱，需要做三个动作（或者叫行为）。每个动作有一个执行者，它就是对象。
 
思路：
 
1、冰箱，你给我把门打开。
 
2、冰箱，你给我把大象装进去（或者说，大象，你给我钻到冰箱里去）。
 
3、冰箱，你给我把门关上。
 
依次完成这些动作，你就可以把大象装进去。
 
这里我只是举个例子，可能大家还是很懵逼，这里我就要给你推荐几本入门 C 语言的视频和书籍了。
 
关于书籍推荐，可以看看这篇回答
 
初学C语言，有什么好书推荐？
 
书一般是能够静下心来的人看的，一般初学者最大的问题就是很难静下心来编程，如果你觉得难以看得下去书的话，你可以看看这篇回答，里面的视频可以说很全了
 
有哪些优秀的c语言课程视频？
 
初学 C 语言周期大概是3 - 6 个月，学编程的捷径就是每天敲代码，比如 C primer plus 上面就有很多代码示例，你要对着敲，课后练习要跟着做，坚持 3 - 6 个月，你会感谢你自己的坚持。
 
学到这里，你就可以说 C 语言基本入门了。
 
如果 C 语言你能够坚持下来的话，那么 Java 入门，那会非常容易了，其原因有两点
 
C 语言基本上可以说是高级语言的鼻祖，如果你 C 学得好，那么学其他语言都会非常容易。
C 语言比 Java 稍微难点，而且有很多特性非常像，从一门比较难的语言 -> 一门难度中等的语言，那会变得很容易。
 
好了，那么从现在开始，我们就要进入 Java 的学习环节了。
 
学习 Java，我将会从三个阶段来介绍，分为初级、中级和高级
 
Java 基础
 
什么是初级 Java 的水平呢？我认为就是理解 Java 的语法规则、语言特性，这么说有点干瘪，直接上思维导图！
 
 
就这一张图，如果你能把图中内容都理解的差不多，那你就可以说是入门 Java 了，但是这里要注意一个概念，这并不等于说你是一个合格的初级 Java 程序员了，因为要想达到初级 Java 程序员的水平，你要会能干活，能干活的标准是你要懂框架，不要急，我们后面会说。
 
有人问图中为什么没有并发或者 Java 虚拟机这些，这些属于中高级内容，刚开始学 Java 不用懂什么并发和 JVM！！！有一些人或者培训班都喜欢秀自己懂 xxx ，懂 xxx ，这不就是误导小白么。
 
那么话又说回来了，如何才能学习并了解到上面这些内容呢？接下来重点来了！！！
 
如果你能看到这里，我就认为你养成了每日编程的习惯，此时的你能够静下心来编程了。
 
那么我首先给你推荐一本初学 Java 非常合适的一本书
 
Head First Java
 
《Head First Java》是本完整的面向对象（object-oriented，OO）程序设计和Java的学习指导。此书是根据学习理论所设计的，让你可以从学习程序语言的基础开始一直到包括线程、网络与分布式程序等项目。最重要的，你会学会如何像个面向对象开发者一样去思考。
 
 
书中涉及的 Swing 图形化接口和 GUI 这部分可以不用学习，或者作为简单了解，因为现在几乎很少有人 拿 Swing 开发桌面化程序。
 
这本书可以说是非常适合小白的一本了，零基础就可以看，Head First 系列的书籍一般都是语言诙谐幽默，读起来不累，而且书中有非常多锻炼思维的游戏/方法，对于有经验的人来说，看这本书感觉非常弱智，但是对于零基础或者 Java 新手来说，这是一本非常适合系统学习 Java 和查漏补缺的一本书。
 
Java 核心技术卷一
 
有人把 Java 核心技术卷一作为入门书籍推荐，其实我觉得并不友好，虽然这也是一门基础书籍，但是对不同的人来说，这本书的接收程度不同，我推荐看完上面的 Head First Java 再看这本。
 
 
Java 编程思想
 
Java 编程思想就是一本神书了，不管你是初、中还是高级程序员，你每次看这本书的时候都会有新的收获
 
 
这本书同样不适合刚开始入门 Java 的同学看，甚至前三章并不友好，因为 Java 编程思想只是讲面向对象过程的设计思想就用了很大篇幅，这本书包含很多示例代码，我强烈推荐你要学习里面的代码思想，到工作中，这些编码思想和代码规范会非常有用！！！
 
所以综上所述，入门 Java 你需要掌握的基础知识有
 
Java 基本介绍
Java 有哪些特点
什么是 Java 开发环境
Java 开发环境配置（初学者建议 Eclipse）
 
这里就需要区分不同的电脑类型了，一种是 Mac ，一种是 Windows，很少有直接拿 Linux 进行开发的，所以我们这里不探讨 Linux 的方式
 
Mac 上的相关配置可以看这篇
 
Windows 上的相关配置可以看这篇
 
编写入门 Java 程序
 
这里你需要使用集成开发工具，一种是 Eclipse 、一种是 IDE，初学者建议使用 Eclipse，因为 IDE 对新手并不友好。
 
Eclipse下载与安装
 
Java 入门程序编写
 
好了，如果你能按照上面的步骤一步步走下来，那么恭喜你，你能够成功编写一个 Java 入门程序了。
 
现在，你就可以进入到 Java 相关知识点的学习了。
 
了解面向对象的设计思想
 
首先，你需要先认识到什么是面向对象的设计思想。
 
这里我推荐你看一下 《Java编程思想》 的第一章和二章
 
知乎的这个回答也能帮助你理解 什么是面向对象编程思想？
 
Java 基础语法（Java标识符、Java 修饰符、Java 变量、关键字、Java 注释）
 
关于 Java 变量，可以参考这篇文章
 
Java 中的变量有很多，很容易让初学者不知所措，这里我写了一篇 Java 变量解惑的相关文章
 
Java 中到底有哪几种变量
 
 
Java 控制流程
 
 
Java 访问控制权限
 
 
面向对象
 
 
  
继承
封装
多态
面向对象最主要有三大特征：继承、封装和多态，你可以参考这篇博客 面向对象的三大基本特征和五大基本原则
 
 
Java 抽象类和接口 ，也可以参考这篇文章 深入理解Java接口和抽象类
 
 
Java 异常 Exception 和 Error ，这里我也写了一篇文章 看完这篇Exception 和 Error，和面试官扯皮就没问题了
 
 
Java 集合
 
 
泛型 ，深入理解泛型可以参考这篇文章 java 泛型详解-绝对是对泛型方法讲解最详细的，没有之一
 
 
内部类，系统化的了解内部类，可以参考这篇文章 Java内部类详解 - Matrix海子 - 博客园
 
 
Java IO ，深入理解 Java IO ，可以参考这篇文章 为什么一个还没毕业的大学生能够把 IO 讲的这么好？
 
 
Java 枚举 Enum ，全面理解 Enum，就这一篇文章
 
 
反射 ，这篇文章简直太好了 学会反射后，我被录取了！（干货）
 
 
Java 注解
 
 
上面所有的内容和思维导图，都可以在这篇文中获取
 
Java技术核心总结 PDF 下载
 
上面都是以文章方向为主的自学流程，下面是视频方向的自学流程。
 
一、Java基础 1、尚硅谷宋红康（强力推荐）：
 
尚硅谷宋红康Java基础教程(java入门神器、配套资料齐全)_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
2、黑马Java基础+就业班+各种项目idea版本（推荐）：
 
黑马Java基础+就业班+各种项目idea版本（正在更新）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
3、动力节点Java零基础教程视频：
 
Java零基础教程视频（适合Java 0基础，Java初学入门）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
4、北京尚学堂高琪（推荐）：
 
高淇老师应各位网友要求又更新了JAVA300集_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
5、求知讲堂：2019求知讲堂零基础Java入门编程视频教程 高口碑 无废话 无尿点 ：
 
2019求知讲堂零基础Java入门编程视频教程 高口碑 无废话 无尿点_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
6、尚硅谷Java8新特性+JUC+NIO：
 
尚硅谷Java8新特性+JUC+NIO_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
 
如果你能掌握上面的基础内容部分，我觉得你应该花至少 3 - 6 个月，如果你能坚持下来的话，这里我需要鼓励一下你，但是不要自满，因为这才只是最最最最基础的部分，但是现在你可以说是一只脚踏入 Java 大门了。
 
设计模式
 
 
设计模式放在这里不是让你马上就要学习的（当然你也可以学习，没有人能阻碍你学习），因为设计模式涉及到你工作的方方面面。有些设计模式你可能这辈子都用不到，但是你需要了解其思想，以便写出思路严谨，条理清晰的代码。
 
设计模式我给你推荐几本书，你看哪个都行。
 
Head First 设计模式
 
 
这本书虽然只有 14 章，但是却介绍到了所有的二十三种设计模式，每一种设计模式都有对应的应用案例，以风趣幽默的语言描述来一步一步为你揭开设计模式的面纱，告诉你设计模式的演进过程。
 
读这本书不仅仅是学习知识，而是在学习一种思考的方法，学习一种认知的技巧，学习一种成长的阶梯。总之，用你闲暇的时间来读这本书，并不亚于你专注的工作或学习。
 
图解设计模式
 
 
设计模式更多是一种思想，而不是一种固定的代码编写方式，千万不要局限于这些条条框框。日本人的书写的就是非常通俗易懂，适合小白。194张图表 ＋ Java示例代码 = 轻松理解 GoF 的23种设计模式。
 
本书以浅显易懂的语言逐一说明了 GoF 的 23 种设计模式。在讲解过程中，不仅搭配了丰富的图片，而且理论结合实例，用 Java 语言编写代码实现了设计模式的程序，让程序真正地运行起来，并提供了运用模式解决具体问题的练习题和答案。除此以外，本书在必要时还对 Java 语言的功能进行补充说明，以加深读者对 Java 的理解，在学习设计模式的同时也在复习 Java。
 
上面这两本书非常适合初学者学习设计模式
 
设计模式
 
 
这本书结合设计实作例从面向对象的设计中精选出23个设计模式，总结了面向对象设计中最有价值的经验，并且用简洁可复用的形式表达出来。书中分类描述了一组设计良好、表达清楚的软件设计模式，这些模式在实用环境下特别有用。此书适合大学计算机专业的学生、研究生及相关人员参考。
 
这本书并不适合初学者，因为这本书是用C++ 写的，如果你没有对 C++ 语法有了解的话，不容易看懂。下面这段评价我觉得非常合适。
 
 
重学 Java 设计模式
 
 
给大家推荐一下我的朋友 小傅哥 写的重学 Java 设计模式，这本书是彩印的，作者写设计模式大概花了两年的时间，非常用心。书中包含大量的图示和例子。
 
本书从六大设计原则入手，警示我们在日常开发过程中需要注意代码的编写原则。同时，本书列举了大量生动形象的例子，在遇到相关业务场景时可以把代码写得非常漂亮。原则既是规范，也是日常开发过程中要遵守的约定；设计模式是在业务场景下能够使用的工具。遵守原则并在合适的场景下用合适的工具，你的代码将无懈可击！
 
设计模式不用看视频，就研读上面这几本就够了。
 
设计模式并不适合一口气读完，因为你看完几个设计模式就会容易混，相信我，你可以一周熟悉一个设计模式，这样在工作中你也可以使用。一口气看完所有，就会记住最后一个设计模式，相信我，亲身实践。。。。。。
 
Java 进阶
 
Java 进阶需要学习的东西就有很多了，内容涉及许多方面，我们接下来就来和你聊聊
 
 
 
注意：当你学会这些 Java 进阶的内容后，不代表你就是一个中级程序员了，恰恰相反，你需要把这些知识融会贯通并运用到项目/实践中去。掌握多少就看你自己了。
 
 
首先是 Java 多线程，这里我先列出来多线程应该掌握知识的大纲
 
 
这里有个我小伙伴整理的一个多线程思维导图，不知道对你有没有帮助，获取地址如下
 
搞懂这 10 张脑图后，我膨胀了。
 
或者微信搜索「程序员cxuan」，回复「秋招」有很多更优质的思维脑图。
 
 
那么先抛开这张脑图不看，我先给你推荐几本关于 Java 并发方面的书。
 
Java 并发编程实战
 
不要犹豫了，这本书就是并发编程界的王者，也是你必看的一本书。
 
 
外版书籍不会和你讨论什么源码啥的，他们只看思想，思想有了，实现也就轻而易举。所以并发编程实战讨论更多的是思想，这本书同时也罗列了很多伪代码和应用场景来验证这些思想。
 
这本书并不完全适合国内互联网现状，因为在八股文、背书如此盛行的今天，想要进大厂，成为"高级程序员"，你还要懂一些八股文。
 
Java 并发编程艺术
 
所以如果你想要在国内找工作的话，那么下面这本书，更适合你。不要为我为什么，阿里人写的。
 
 
这些书罗列出来的一些知识点，其实都是大厂所经常问到的，所以这本书值得你仔细研读。
 
Java 并发编程之美
 
这本书比较适合初学者，我虽然没有系统看过，但是也翻了一下，这也是学习 Java 并发编程一本不错的书，可以当作查漏补缺或者巩固的一本。
 
 
图解Java多线程设计模式
 
不得不说，日本人写的书就是通俗易懂，充满趣味性，这点不得不佩服，这本 Java 多线程设计模式，就是了解多线程中使用设计模式一本非常好的书籍。本书通过具体的Java 程序，以浅显易懂的语言逐一说明了多线程和并发处理中常用的12 种设计模式，帮助读者加深对多线程和并发处理的理解，并掌握其使用技巧。
 
 
书籍看这几本就差不多了，而且 Java 并发这块我不推荐你看视频，最好是亲自验证，视频这个东西毕竟也是别人吃过的剩下的，最主要的还是要穿一手鞋，亲自验证。
 
说到这里，那么 Java 并发这块你应该掌握的知识点都有哪些呢？划重点划重点了！！！
 
进程和线程的概念，阮一峰老师有一个通俗易懂的解释 进程与线程的一个简单解释 - 阮一峰的网络日志，从操作系统角度理解进程和线程，可以看一下我写的这篇文章
Java 多线程基础， 可以看下我写的这篇文章，介绍了基本的 Java 多线程方法和操作2w字 + 40张图带你参透并发编程！
Java 线程状态以及线程状态的转换，Java线程的6种状态及切换(透彻讲解)_
Java 线程间的通信机制
理解 Java 内存模型
happens-before 原则 或者阅读 Java 并发编程艺术的第三章
volatile 关键字解析
Synchronized 关键字解析
CAS 与原子操作 这个我写了一篇解析原子类的文章 一场 Atomic XXX 的魔幻之旅，为什么要有 AtomicReference ？
AQS 大厂面试必问的 AQS ，这篇文章简直太好了 ，我画了35张图就是为了让你深入 AQS
线程池相关原理 肝完这篇线程池，我咳血了
 
线程池这部分内容的思维导图
 
 
Java 中的锁，这篇文章简直太全了 不懂什么是锁？看看这篇你就明白了
 
锁这部分内容我也汇总了一个思维导图
 
 
 
多线程工具类
 
 
  
CountDownLatch
Semaphore
CyclicBarrier
Exchanger
 
 
Fork/Join 框架
 
 
面试必问的 ConcurrentHashMap ，这里推荐两篇文章 HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！，ConcurrentHashMap实现原理及源码分析 - dreamcatcher-cx - 博客园
 
 
CopyOnWriteArrayList
 
 
Java并发系列 - 阻塞队列（BlockingQueue）
 
 
对了，我这里也总结了一本 《深入浅出 Java 多线程》，你可以在 太赞了！阿里几位工程师重写了 《Java 并发编程》 下载
 
上面的内容如果你能理解，那么你 Java 这部分已经可以算是高级水平了，你去大厂面试问一些八股文，多线程这块问题不大了。
 
JVM
 
Java 虚拟机也叫做 JVM ，这部分是判断一个 Java 程序员分水岭的关键，如果你想要达到中高级 Java 程序员的层次，那么 JVM 是你必须要突破和提高的一个点。下面我就来和大家聊一下 JVM 都需要了解哪些内容。
 
还是照例先给大家介绍几本了解 JVM 非常优秀的书籍
 
深入理解 Java 虚拟机
 
这本书是你必看的一本，而且作者是我们国内的周志明，国内作者一般讲实现比较多，专业术语比较少，这本书讲的更是通俗易懂，虽然有许多概念，不过周志明大佬都给出了示例和解释
 
 
豆瓣能给出国内作者 9.5 的评分，可知这本书写的有多好了，这本书是了解 JVM 非常经典的一本书，五星强烈推荐。
 
Java 虚拟机规范
 
 
Java 虚拟机规范同样也是周志明大佬参与翻译的一本，这本书的权威性不容置疑，其实就是按照 Java 官方文档来写的，可以说看完这一本在面试的时候聊到 JVM 你都能够给出 “官方” 回答，大大增加你的面试通过几率。
 
按理说学习 JVM 掌握上面两本书就 OK 了，但是这里我还是给喜欢学习的小伙伴们一些拓展书籍推荐。
 
HotSpot 实战
 
 
深入浅出地讲解了 HotSpot 虚拟机的工作原理，将隐藏在它内部的本质内容逐一呈现在读者面前。本书适合于已具有一定 Java 编程基础的读者，以及在 Java 或基于 JVM 的编程语言平台下进行各类软件开发的开发人员、测试人员和运维人员。对于 JVM 和编程语言爱好者来说，《HotSpot 实战》也具有一定的学习参考价值。
 
自己动手写 Java 虚拟机
 
我们大家都知道，学习编程最好的方式就是动手实践，幸好 JVM 我们也能自己写了。
 
 
自己动手写 Java 虚拟机是《自己动手系列》中的一本，这个系列有很多硬核的书籍，给大家看一下。
 
 
如果大家有时间的话，我推荐大家按着书中的内容写一个虚拟机，对于掌握理解其运行原理有非常大的帮助。
 
学习 JVM 我同样也不推荐大家看视频，看书就够了，学习 JVM 在于让你去想去思考，你如果非要让我推荐一个视频的话，那我也愿意双手奉上
 
尚硅谷JVM全套教程，百万播放，全网巅峰（宋红康详解java虚拟机）
 
JVM 所涉及到的一些内容
 
 
获取地址如下
 
搞懂这 10 张脑图后，我膨胀了。
 
主要涉及内容
 
Java 内存划分与内存管理
JVM 中的垃圾收集器，这里推荐两篇文章 搞定JVM垃圾回收就是这么简单，或者是这一篇 JVM的垃圾回收机制 总结(垃圾收集、回收算法、垃圾回收器)
JVM 性能监控，这里推荐两篇文章 噜噜呀：必须掌握的JVM性能监控工具 和 别再说你不会 JVM 性能监控和调优了，看完这篇再发言！
JVM 调优，或者是这一篇 JVM性能调优（4） – 性能调优工具
JVM 中的类文件结构
JVM 类加载机制，或者这一篇 零壹技术栈：JVM系列(五) - JVM类加载机制详解
JVM 字节码，JVM 字节码这部分内容，我建议看一本书，这本书就是
 
 
这是一本揭示 JVM 字节码“黑科技”的著作，它从原理和应用两个维度深入剖析了 JVM 字节码。书中内容涉及 JVM 字节码的大部分应用场景，如 Java 性能优化、软件防护与破解、APM 等，通过大量实战案例讲解了它在这些场景中的实操技巧。
 
这里再给大家推荐几篇不错的字节码文章
 
字节码增强技术探索
 
JVM基础系列第5讲：字节码文件结构 - 陈树义 - 博客园
 
轻松看懂Java字节码
 
 
 
到现在为止，Java 语言这条线算是走通了，虽然上面关于并发和 JVM 我列出了学习路线，但是这个学习路线并不是说只能学了并发才学 JVM，其实上这两个掺杂着一起学效果会更好，因为并发会涉及到对于 volatile synchronized 和 内存模型的关系，内存模型又是 JVM 中的内容，所以这两块其实是相辅相成的。而且没必要学并发和 JVM 的时候就要一股脑把东西全看明白，这些内容是中高级的东西，你可以一周看一篇都行。
 
 
上面这些内容真正掌握起码要花 2 - 3 年的时间，也不是说这三年你就学上面这些东西，你可以学习其他的，我下面推荐的这些，就是在这个时间段内你应该掌握的。
 
MySQL
 
MySQL 其实要和 Java 基础以及 Java 并发、JVM 一起学习，甚至要比并发和 JVM 还要早，也就是说，你学完 Java 基础就可以学 MySQL 了。
 
此时的 MySQL 我指的是 MySQL 基础，因为 MySQL 博大精深，想要深入理解 MySQL 不容易，而且我们一般 Java 开发把 MySQL 掌握到中级水平就可以了。
 
MySQL 初级水平就是要求你会写 MySQL ，这里推荐几本书，由初级到高级，大家可以根据自己的水平和能力看对应的书籍。
 
MySQL 基础教程
 
 
这本书是日本公认的 MySQL 入门首选教程，原版长销13年，好评如潮，非常详细。
 
SQL 基础教程
 
又是日本人写的一本高分书。
 
 
这本书介绍了关系数据库以及用来操作关系数据库的 SQL 语言的使用方法。书中通过丰富的图示、大量示例程序和详实的操作步骤说明，让读者循序渐进地掌握 SQL 的基础知识和使用技巧，切实提高编程能力。每章结尾设置有练习题，帮助读者检验对各章内容的理解程度。另外，本书还将重要知识点总结为“法则”，方便读者随时查阅。
 
深入浅出 MySQL
 
这本书是零基础学习 MySQL 非常好的一本书，由浅入深，文字通俗易懂。
 
 
但是这本书非常厚，涵盖的内容非常多，不容易把握重点。
 
MySQL 必知必会
 
相对来说，这本书就比较薄了。
 
 
同样也是入门 MySQL 非常值得看的一本。书中从介绍简单的数据检索开始，逐步深入一些复杂的内容，包括联结的使用、子查询、正则表达式和基于全文本的搜索、存储过程、游标、触发器、表约束，等等。通过重点突出的章节，条理清晰、系统而扼要地讲述了读者应该掌握的知识，使他们不经意间立刻功力大增。
 
SQL 必知必会
 
SQL 语法简洁，使用方式灵活，功能强大，已经成为当今程序员不可或缺的技能。
 
 
这本书是深受世界各地读者欢迎的 SQL 经典畅销书，内容丰富，文字简洁明快，针对 Oracle、SQL Server、MySQL、DB2、PostgreSQL、SQLite 等各种主流数据库提供了大量简明的实例。与其他同类图书不同，它没有过多阐述数据库基础理论，而是专门针对一线软件开发人员，直接从SQL SELECT 开始，讲述实际工作环境中最常用和最必需的 SQL 知识，实用性极强。通过本书，读者能够从没有多少SQL经验的新手，迅速编写出世界级的 SQL！
 
 
 
上面推荐了一些 MySQL 的基础书籍，把上面任意 1 - 2 本啃会了之后，那么你的 CRUD 的功力就初步具备了。恭喜你离初级 Java 程序员又近了一步。
 
 
下面我会推荐一些中高级内容，这些内容会一直伴随着你的整个开发生涯，是的你没听错，如果你做开发，那么下面这些书中的内容，真的会伴随着你整个开发生涯，不论任何语言。
 
高性能 MySQL
 
 
这本书太优秀了！这本书是 MySQL 领域的经典之作，拥有广泛的影响力。我之前和出版社联系给读者送了 20 本书，超过一半的人都要的是 高性能MySQL，由此可见这个影响力！
 
原文链接：cxuan 给大家送 20 本书！！！
 
 
MySQL 是怎样运行的
 
 
这本书是去年刚出的，小孩子大佬非常牛批，之前在掘金写了一篇小册，好像是购买人数最多的课程，这本书就是小册的汇总，非常硬核。
 
本书采用诙谐幽默、通俗易懂的写作风格，针对上面这些问题给出了相应的解答方案。尽管本书的表达方式与司空见惯的学术派、理论派IT图书有显著区别，但本书的确是相当正经的专业技术图书，内容涵盖了使用 MySQL 的同学在求职面试和工作中常见的一些核心概念。无论是身居 MySQL专家身份的技术人员，还是技术有待进一步提升的 DBA，甚至是刚投身于数据库行业的“萌新”人员，本书都是他们彻底了解 MySQL 运行原理的优秀图书。
 
数据库索引与优化
 
这本书大家可能听的比较少，但这是很好的关于索引介绍的书，提供了估计查询支行时间和方法，并解释了索引对于查询效率的影响方式，对实践和指导意义。而且数据库的索引和优化是 MySQL必问的重点。
 
 
 
 
上面推荐的这些算是进阶篇，而我们下面推荐的这几本就算是 MySQL 的高级内容了。
 
 
MySQL 技术内幕：InnoDB存储引擎
 
 
作为 MySQL 5.5 之后的首选存储引擎，InnoDB 存储引擎到底有哪些特别之处？这本书会给你详细介绍一波。这本书从源代码的角度深度解析了 InnoDB 的体系结构、实现原理、工作机制，并给出了大量最佳实践，能帮助你系统而深入地掌握 InnoDB，更重要的是，它能为你设计管理高性能、高可用的数据库系统提供绝佳的指导
 
MySQL技术内幕
 
 
《MySQL技术内幕（第5版）》是MySQL方面名副其实的经典著作，全面介绍MySQL的基础知识以及MySQL有别于其他数据库系统的独特功能，书中特别关注如何高效地使用和管理MySQL。 《MySQL技术内幕（第5版）》由4个部分组成：第一部分集中介绍与数据库使用相关的一些基本概念，第二部分重点关注的是自己如何动手编写和使用 MySQL 的程序，第三部分主要是面向那些负责数据库管理的读者，第四部分提供了一些参考附录。书中包含大量示例，详尽地演示了MySQL的各项功能特性。此外，本书还为使用C语言、PHP语言和Perl语言开发数据库应用的读者提供了相关内容。 《MySQL技术内幕（第5版）》不仅适合MySQL初学者阅读，也适合想要深入了解 MySQL 的数据库管理人员和开发人员参考。
 
MySQL 内核
 
 
非常优秀的一本书，这本书在 InnoDB 介绍性图书的基础之上，更深入地介绍InnoDB存储引擎的内核，例如latch、B+树索引、事务、锁等，从源代码的角度深度解析了InnoDB的体系结构、实现原理、工作机制，并给出了大量最佳实践，希望通过《MySQL内核：InnoDB存储引擎 卷1》帮助用户真正了解一个数据库存储引擎的开发。
 
好了，推荐了这么多本 MySQL 的书籍，那么有没有 MySQL 的视频推荐呢？啊？MySQL 还用看视频吗？MySQL 不好讲呀，初级的直接对着命令敲就可以了，高级的内容，很多讲师也讲不清楚，更别提内核这块了，所以大家还是看书把，看书就够了！
 
那么关于 MySQL ，内容其实是很多的，不过为了这个回答能作为一个标准回答来解释，我耐着性子给大家把所要学习的内容罗列一下，读者朋友们如果觉得我的付出是值得的，不妨给这篇文章点个赞哟！
 
 
那么 MySQL ，走你！
 
 
MySQL 基础入门
 
 
  
 
SQL 基础使用
 
 
查询语言分类
 
 
    
DDL 语句
DML 语句
DQL 语句
DCL 语句
 
 
如何使用 MySQL 帮助文档
 
 
    
按层次查询
快速查阅
 
 
 
MySQl 数据类型
 
 
  
 
数值类型
 
 
    
整数
小数
位类型
 
 
日期类型
 
 
    
YEAR
TIME
DATE
DATETIME
TIMESTAMP
 
 
字符串类型
 
 
    
CHAR 和 VARCHAR
BINARY 和 VARBINARY
BLOB
TEXT
ENUM
SET
 
 
 
MySQL 运算符
 
 
  
算数运算符
比较运算符
逻辑运算符
位运算符
 
 
MySQL 常用函数
 
 
  
字符串函数
数值函数
日期和时间函数
流程函数
其他函数
 
 
上面这些内容都可以在这篇文章中找到，我自己写的关于 MySQL 的实战入门总结
 
138 张图带你 MySQL 入门
 
MySQL 开发中应该掌握哪些知识点
 
 
MySQL 存储引擎
 
 
  
 
存储引擎概述
 
 
存储引擎特性
 
 
    
MyISAM
InnoDB
MEMORY
MERGE
 
 
选择合适的存储引擎
 
 
 
MySQL 字符集
 
 
索引的设计和使用
 
 
  
索引概述
索引设计原则
 
 
视图
 
 
  
 
什么是视图
 
 
对视图的操作
 
 
    
创建或者修改视图
 
 
 
存储过程
 
 
  
 
存储过程使用
 
 
    
创建存储过程
删除存储过程
查看存储过程
 
 
变量的使用
 
 
    
用户变量
全局变量
会话变量
局部变量
 
 
MySQL 流程介绍
 
 
 
触发器
 
 
  
创建触发器
删除触发器
查看触发器
触发器的作用
 
 
上面这些内容，可以在我自己写的 MySQL 开发中找到
 
47 张图带你 MySQL 进阶！！！
 
MySQL 高级内容，主要包括
 
 
事务控制和锁定语句
 
 
  
锁定语句
解锁语句
 
 
事务控制
 
 
  
 
自动提交
 
 
手动提交
 
 
    
事务表和非事务表
 
 
 
SQL 安全问题
 
 
  
SQL Mode 解决问题
SQL Mode 三种作用域
 
 
SQL 正则表达式
 
 
常见 SQL 技巧
 
 
  
RAND 函数
GROUD BY + WITH ROLLUP 语句
数据库名、表名大小写问题
外键问题
 
 
MySQL 常用函数
 
 
  
字符串函数
数值函数
日期和时间函数
流程函数
其他函数
 
 
上面这些内容，你可以在我自己写的关于 MySQL 高级部分找到
 
炸裂！MySQL 82 张图带你飞！
 
以上这些 MySQL 内容都是偏重日常开发和使用，没有深入到 MySQL 架构和底层，所以下面我们介绍的这些内容，会涉及到 MySQL 架构和底层的相关内容，这些内容，也是你在 CRUD 的背后，需要下的功夫。
 
MySQL 架构，这篇文章不错
深入理解Mysql——锁、事务与并发控制
MySQL 隔离级别和实现原理
Innodb 中的事务隔离级别和锁的关系
详细分析MySQL事务日志(redo log和undo log)
MySQL的多版本并发控制(MVCC)是什么？
深入MySQL存储引擎分析锁和排序的
深入了解MySQL存储引擎-------InnoDB
详解MySQL基准测试和sysbench工具
深入理解 MySQL 索引原理
深入理解MySQL索引
腾讯技术工程：深入理解 Mysql 索引底层原理
MySQL索引原理及慢查询优化
万字总结：学习MySQL优化原理，这一篇就够了！
MySQL优化/面试，看这一篇就够了
在MySQL中实现二分查找的详细教程
二叉查找树与平衡二叉树详解
为什么 MySQL 使用 B+ 树
为什么MySQL数据库索引选择使用B+树？
删库不跑路-详解MySQL备份策略
MySQL 备份和恢复机制
搞懂MySQL分区
 
这些内容我也在学习，因为我是 MySQL 新手，所以这部分内容应该不是特别全，大家可以追更这个答案，我会在后面更新这个回答。
 
 
 
这里再提醒大家一点，MySQL 高级内容是你在工作中慢慢掌握的，如果你想要成为初级 Java 程序员，当下不需要掌握这些内容，把我写的几篇文章看完，并且跟着敲下来，那么就可以说你的 MySQL 已经达到入门水准了，可以进行下面的学习了！！
 
 
138 张图带你 MySQL 入门
 
47 张图带你 MySQL 进阶！！！
 
炸裂！MySQL 82 张图带你飞！
 
Maven
 
在学习框架前，我建议你先了解一下什么是 Maven，以及项目为什么要使用 Maven，狼哥的这个 Maven 系列可以了解下。
 
Maven学习总结
 
市面上关于 maven 的书不多，你可以看下这本
 
 
Maven 对于初学者来说，只做为了解即可，但是 Maven 这个优秀的架构是如何简化代码的，如何让我们更方便的使用，以及 Maven 中的一些不为人知的秘密，你都可以在这本书中找到。
 
下面该学啥了？终于到了框架了！！！ 作为一门开发，框架就是你的武器！！！就是玩儿！在抗美援朝的时候，志愿军使用轻武器加迫击炮照样干翻米国骑兵第一师和陆战第一师这种王牌军队。
 
框架要学习的就是 SpringMVC 、Spring 、MyBatis，SSH 框架已经不行了，至于为什么不行，可以看一下这篇回答
 
JAVA的三大框架是什么？
 
框架首先要学的就是 MyBatis
 
MyBatis
 
MyBatis 入门，看一本书就够了。
 
MyBatis 从入门到精通
 
 
这本书是我刚开始学 MyBatis 的时候看的，书中的内容我对照着都敲了一遍，可以说是非常有参考价值的一本。
 
 
 
《MyBatis从入门到精通》中从一个简单的MyBatis查询入手，搭建起学习MyBatis的基础开发环境。通过全面的示例代码和测试讲解了在MyBatis XML方式和注解方式中进行增、删、改、查操作的基本用法，介绍了动态SQL在不同方面的应用以及在使用过程中的最佳实践方案。针对MyBatis高级映射、存储过程和类型处理器提供了丰富的示例，通过自下而上的方法使读者更好地理解和掌握MyBatis的高级用法，同时针对MyBatis的代码生成器提供了详细的配置介绍。
 
 
深入理解 MyBatis ，你可以参考
 
MyBatis 技术内幕
 
 
嗯，这本书其实可以说是把 MyBatis 的一些核心特性和核心组件说完了，《MyBatis 技术内幕》旨在为读者理解 MyBatis 的设计原理、阅读 MyBatis 源码、扩展 MyBatis 功能提供帮助和指导，让读者更加深入地了解 MyBatis 的运行原理、设计理念。希望《MyBatis 技术内幕》能够帮助读者全面提升自身的技术能力，让读者在设计业务系统时，可以参考 MyBatis的 优秀设计，更好地应用MyBatis。
 
这本书我还是强烈推荐给大家的。
 
另外，你也可以去看 MyBatis 官方文档 mybatis - MyBatis 3
 
英文版的看不懂，汉化的也给你安排了。mybatis - MyBatis 3
 
MyBatis 这部分内容可以去看一些视频
 
【狂神说Java】Mybatis最新完整教程IDEA版通俗易懂
 
2020最新MyBatis教程【IDEA版】-MyBatis从入门到精通
 
那么 MyBatis 都应该掌握哪些内容呢？当然你要会用 MyBatis 了，用法直接参见官网或者 MyBatis 从入门到精通这本书就可以了。
 
MyBatis 基础架构
MyBatis 核心配置之 Executor
MyBatis 核心配置之StatementHandler
MyBatis 核心配置之 ParameterHandlers
MyBatis 核心配置之 ResultSetHandler
MyBatis一级缓存详解
MyBatis 二级缓存详解
Mybatis源码分析-解析器模块
面试官问你MyBatis SQL是如何执行的？把这篇文章甩给他
MyBatis源码解析-类型转换篇
MyBatis源码解析 - 资源加载模块
Mybatis源码解读-设计模式总结
【MyBatis源码分析】Configuration加载（上篇）
【MyBatis源码分析】Configuration加载（下篇）
 
 
 
我上面给出的这些连接，都是让你在工作中逐步掌握的，MyBatis 要是达到能够开发的程度，你只需要看完 MyBatis 从入门到精通或者一门视频课程就可以了。
 
 
Spring
 
在学完 MyBatis ，就该学习我们的核心框架 Spring 了，Spring 能风靡到现在一定有他的道理，等你到工作中再慢慢体会它的精髓。
 
学习 Spring ，我首先给你推荐的一本书就是 Spring 实战，也就是 Spring In Action，这本书我认为即使学习 Spring 最好的一本，没有之一了。
 
 
这个评价我认为是有些低了，还有评价说是什么不注重思想的，这只是一本实战书诶，又不是讲思想的，不能要求一本书能够涵盖所有的内容吧，只要这本书能够给出实战案例，代码示例，清楚的讲明白逻辑，我觉得就是好的。
 
Spring 揭秘
 
 
这本书和上面的 Spring 实战一起学习，那么 Spring 你就能击败大部分选手了，这两本书是绝配。这本书更多讲解的是方案和思想。这本书没有教程似的训导，更多的是说故事般的娓娓道来，本书是作者在多年的工作中积累的第一手 Spring 框架使用经验的总结，深入剖析了 Spring 框架各个模块的功能、出现的背景、设计理念和设计原理，揭开了 Spring 框架的神秘面纱，使你“知其然，更知其所以然”。每部分的扩展篇帮助读者活学活用 Spring 框架的方方面面，同时可以触类旁通，衍生出新的思路和解决方案。
 
关于 Spring 基础的视频，我推荐下面几个
 
【狂神说Java】Spring5最新完整教程IDEA版通俗易懂
 
尚硅谷-Spring5框架最新版教程（idea版）
 
作为进阶学习，我推荐宁看看官网
 
Core Technologies
 
Spring 官网的权威性不用我多说了吧，但是官网有个特点，这个不只是 Spring 特有的，几乎所有的外国官网都不会带你分析源码，所以如果你想要了解设计思想和理论精髓，还是要撸源码。
 
撸源码当然很费劲了，这里推荐给你两本书可以搭配着看下，网上对这两本书的褒贬不一，我不强烈推荐任何一本。。。。。。
 
Spring 源码深度解析
 
 
这本书我看了一些，以我目前的能力水平可能还无法完全看懂这本书，里面的内容非常深奥，不过如果你对 Spring 源码有一些研究的话，可以看看。
 
Spring 技术内幕
 
 
这本书和上面一样，代码比较多，但是解释相对较少，适合对 Spring 源码有一些了解的同学看。
 
推荐给你几个 Spring 源码的视频
 
这可能是B站讲的最好的SPRING源码教程（2021年最新版）
 
尚硅谷Spring注解驱动教程(雷丰阳源码级讲解)
 
当然，Spring 你终究还是要看源码的，所以还是硬着头皮啃源码吧，骚年们～
 
关于 Spring，有哪些需要学习的东西呢？
 
Spring学习(1)——快速入门
Spring学习笔记（二）：Spring Bean装配
【Spring实战】高级装配 谢随安
谈谈对Spring IOC的理解
详解Spring IOC
Spring系列之beanFactory与ApplicationContext
BeanFactory 简介以及它 和FactoryBean的区别(阿里面试)
Spring(4)——面向切面编程（AOP模块）
Spring AOP 扫盲
Spring注解？啥玩意？
精进Spring—Spring常用注解【经典总结】
关于 Spring 的文章，可以看下 Spring 系列目录 查漏补缺
使用spring validation完成数据后端校验
Spring进阶 - 验证、数据绑定和类型转换
浅谈Spring的Resources体系
 
 
 
Spring 单独拿来使用的场景非常少，更多是作为框架的整合来用，Spring 最主要的特点就是两个：IOC 容器和 Aop，IOC 容器就是 Spring 和 各种资源整合的基础，可以说有了 IOC 的这个特点，才会有 bean 的装配，自动装配等等特性，而 Aop 就是减少业务耦合性的一种技术，让我们能够以"切面"的方式来看到业务关联性。最主要的就是这两项技术，把这两项技术弄懂了 Spring 就差不多了。
 
 
HTTP
 
再继续往下学习之前，我们先聊聊 HTTP 协议，HTTP 协议可以说是我们 Java 开发打交道最多的协议了，关于 HTTP 协议，我们这里不讲述太多，大家可以参考一下我的这篇文章，里面有详细的 HTTP 教程。
 
想深入了解 HTTP 协议，有哪些值得推荐的书籍？
 
Tomcat
 
我刚开始接触 Tomcat 之前也有这个疑问，这个 Tomcat 是啥。。。。。。听起来很别扭，但是你可以通过这篇文章了解一下什么是 Tomcat
 
Tomcat(一) Tomcat是什么：Tomcat与Java技术 Tomcat与Web应用 以及 Tomcat基本框架及相关配置
 
牧酱：什么是TOMCAT
 
Tomcat 我推荐你看看这几本书
 
 
这本书是一本万能工具，其主题涵盖了Apache Tomcat这一广受欢迎的开源servlet、JSP容器和高性能的web server。《Tomcat权威指南》对管理员和web站点管理员而言，具有较强的参考价值；对在开发或产品中要使用 Tomcat 作为 web 应用程序服务器的开发者而言，这是一本有用的指南书；对 Tomcat 感兴趣的人而言，这是一本优秀的介绍工具。
 
但是这本书翻译好像比较糟糕，大家可以看看英文版
 
http://index-of.co.uk/Misc/O’Reilly%20Tomcat%20The%20Definitive%20Guide%20(2nd%20Edition).pdf
 
深入剖析 Tomcat
 
另外一本就是深入剖析 Tomcat
 
 
这本书会揭示 Tomcat 的工作原理，通过学习本书，你将可以自行开发 Tomcat 组件，或者扩展已有的组件，甚至可以让你自制一个 Tomcat 服务器。
 
关于 Tomcat 学习有多深，这个没有一个明确的定论，对于初级 Java 开发而言，你知道 Tomcat 是干什么的，能够起到什么作用就可以了，如果你想要达到中高级 Java 程序员的水平，那么任何深入的学习都是不为过的。
 
Tomcat 架构解析
 
 
本书全面介绍了Tomcat的架构、各组件的实现方案以及使用方式。包括Tomcat的基础组件架构以及工作原理，Tomcat各组件的实现方案、使用方式以及详细配置说明，Tomcat与Web服务器集成以及性能优化，Tomcat部分扩展特性介绍等。读者可以了解应用服务器的架构以及工作原理，学习Tomcat的使用、优化以及详细配置。
 
这本书和深入剖析 Tomcat 差不多，都是带你深入理解 Tomcat 的一本书，我认为你看哪本都可。
 
Servlet/JSP 技术
 
下面要聊的不是框架了，而是一项非常古老的技术：Servlet 和 JSP 技术，这两项技术很多人说不用在学习了，说这话的人有两点考量：1. 他认为老的技术都不用学了；2. 他自己根本就不懂。
 
在没有前后端分离前，我们的项目架构都是单体，也就是各种 JSP 页面直接耦合进去，Servlet 负责前端和后端的交互，这个时候项目非常冗余，很多文件都扔在一个项目中，导致逻辑混乱，文件类型庞杂。后来随着技术的发展，出现了 SpringMVC ，封装了 Servlet，让我们不用再管理 HttpServletRequest 和 HttpServletResponse，直接让 SpringMVC 把这事干了，我们只用遵照其要求的风格 — restFul 格式，我们就能够把前后端的接口"标准化"，随着 HTML5 等动态页面的发展，从而出现了后面我们说的前后端分离的项目架构，也就是前端是一个项目，后端是一个项目。
 
但是他们的核心还是 Servlet 和 JSP。
 
这里我又开始推荐书了
 
Head First Servlet/JSP
 
 
Head First 系列的书就是幽默，通俗易懂，用轻松愉快的语言，通过做游戏的方式就把知识点给你讲明白了。讲述了关于如何编写 servlets 和 JSP 代码，如何使用 JSP 表达式语言，如何部署 Web 应用，如何开发定制标记，以及会话状态、包装器、过滤器、企业设计模式等方面的知识，以一种轻松、幽默而又形象的方式让你了解、掌握 servlets 和 JSP，并将其运用到你的项目中去。
 
这本书 cxuan 强烈推荐
 
这里给大家推荐一个学习 Servlet 的网站
 
Servlet/JSP Gossip
 
这同时也是一本书
 
 
作者是台湾人，除了语言有点没有那么痛快之外，其他技术点的讲解还不错。
 
Servlet & JSP 核心编程
 
 
这也是一本基础书籍，条理清晰。对于初学者来说是一本不可多得的入门书籍。
 
Servlet 和 JSP 的视频，我给你推荐
 
尚硅谷最新版JavaWeb全套教程,java web零基础入门完整版
 
这个其实也包括了前端 HTML CSS JavaScript Servlet JSP 部分
 
JavaWeb视频教程（JSP/Servlet/上传/下载/分页/MVC/三层架构/Ajax）
 
这两个视频都是 Web 整合的，单独的 Servlet 可以看看
 
【千锋】Servlet教程-Servlet入门
 
2020最新servlet教程-Servlet全解和案例实操_
 
Spring MVC
 
SpringMVC 终于来了！！！！为什么最后再说 SpringMVC，因为Spring MVC 其实就是 Servlet 的一种封装，而且 Spring MVC 打交道的对象是 HTTP 协议，所以你需要先掌握上面知识再学 Spring MVC。
 
学习 SpringMVC，我推荐你看
 
SpringMVC 学习指南
 
 
本书重在讲述如何通过 Spring MVC 来开发基于 Java 的 Web 应用。全书共计12章，分别从 Spring框架、模型2和 MVC模式、Spring MVC 介绍、控制器、数据绑定和表单标签库、传唤器和格式化、验证器、表达式语言、JSTL、国际化、上传文件、下载文件多个角度介绍了Spring MVC。除此之外，本书还配有丰富的示例以供读者练习和参考。
 
看透 SpringMVC
 
 
全面介绍 Spring MVC 的架构、原理、核心概念和操作，通过案例完整呈现 Tomcat 的实现，系统总结 Spring MVC 九大组件的处理以及常用的技巧和实践。
 
这两本书看完，SpringMVC 就差不多了，如果觉得还有遗漏的话，不妨看看官网。
 
Web on Servlet Stack
 
视频可以看看这个
 
2020最新SpringMVC教程【IDEA版】
 
那么关于 SpringMVC 都需要掌握哪些内容呢？
 
Spring MVC【入门】就这一篇！
Spring MVC 解析之 DispatcherServlet
Spring Web MVC-09-springmvc 过滤器与拦截器 Handler and Filter
SpringMVC全局异常处理
SpringMVC 单文件上传与多文件上传
SpringMVC上传文件的三种方式
一文读懂SpringMVC中的文件上传与下载
Spring MVC打印@RequestBody、@Response日志
Spring MVC拦截器实现用户登录权限验证案例
Spring MVC框架原理分析
SpringMVC - 视图解析过程详解
RestTemplate 最详解
Spring MVC中使用RestTemplate访问REST服务详解
SpringMVC之Controller常用注解功能全解析
MVC设计模式介绍 & SpringMVC实现
 
Stop. Stop. Stop
 
当你从 Java 基础 -> MySQL基础 -> MyBatis -> Spring -> HTML/CSS -> Servlert/JSP -> SpringMVC 学完之后，我觉得你应该需要花 1 - 2 年左右的时间，此时的你应该能够具备完成一个小型 SSM 项目的能力了，现在先不忘下面继续学习了，你应该把你的知识进行整合，你可以按照书中的内容搭建小型项目，或者完成一些 SSM 项目等，很多 Java 方向的毕业设计也就到这里就能完事儿了。
 
这里给你推荐一些整合资源
 
Java SSM练手小项目-手把手带你搭建一个基于SSM框架的人力资源管理后台系统
 
liddhome/yosebook-ssm
 
ZhongFuCheng3y/910convenienceSite
 
学生管理系统（SSM简易版）总结
 
https://github.com/saysky/ForestBlog
 
或者看一下尚硅谷的整合教程
 
尚硅谷SSM框架实战，ssm整合教程
 
此时的你，可以说能够具备一个初级 Java 开发的基本素质了，但是你可能还找不到工作，为什么？因为现阶段最最最流行的框架你还没有接触，下面有请大名鼎鼎的 SpringBoot 大佬登场。
 
SpringBoot
 
SpringBoot 可以说是当今 Java 领域最火的框架了，那么 SpringBoot 为什么这么火呢？
 
从设计理念谈起
 
要说到 Spring Boot 为什么这么火，就必须得聊聊 Spring Boot 的设计理念，正是此设计理念奠基了Spring Boot 开发设计的基准，让 Spring Boot 走到了今天。
 
那 Spring Boot 的设计理念是什么呢？它就是约定优于配置（convention over configuration）。
 
约定优于配置并不是一个新概念，它是一种软件设计范式，很早就应用在软件架构设计中，它的作用是减少软件开发人员需做决定的数量，获得简单的好处，而又不失灵活性。
 
只是 Spring Boot 让这个设计理念上升了一个层次，Spring Boot 不止在某个功能上实现此设计理念，而是整个软件体系都在践行约定优于配置。
 
Spring Boot 体系将约定优于配置的思想展现得淋淋尽致，小到配置文件，中间件的默认配置，大到内置容器、生态中的各种 Starters 无不遵循此设计规则。
 
Spring Boot Jpa 80% 大部分查询功能都以约定的方式给与提供，另外 20% 复杂的场景，提供另外的技术手段来解决，典型的约定优于配置的实现。
 
Spring Boot Starter ，在项目启动的时候，根据约定信息对组件进行加载、初始化。因此项目中引入了对于的 Starter 之后，就可以到达开箱即用的效果。
 
甚至 Spring Cloud 的设计，也借鉴了约定优于配置的思想，很多组件都是在启动时，默认提供了其相关的功能，可以让我们的使用到达很少配置或者零配置。
 
Spring Boot 的 Starter 机制
 
Spring Boot Starter 是 Spring Boot 的 星辰大海。
 
正是因为丰富的 Spring Boot Starter ，让 Spring Boot 征服了使用各个开源软件的开发者，只要 Spring Boot Starter 指向哪个开源软件，就会让某个开源软件变得异常好用。
 
这真的是这样，有一种神笔马良的感觉（夸张了一点）。
 
那什么是 Spring Boot Starter 呢？
 
在 Spring Boot 中，Starter 是为快速应用开发提供“一站式服务”的依赖（Dependency）。Starter 使得开发人员在开始编写新的模块时不需要拷贝样板式的配置文件、编写样板式的代码，只需要提供最简单的配置即可开始编程。
 
Spring Boot Starter 有两个核心组件：自动配置代码和提供自动配置模块及其它有用的依赖。也就意味着当我们项目中引入某个 Starter ，即拥有了此软件的默认使用能力，除非我们需要特定的配置，一般情况下我仅需要少量的配置或者不配置即可使用组件对应的功能。
 
Spring Boot 由众多 Starter 组成，随着版本的推移 Starter 家族成员也与日俱增。在传统 Maven 项目中通常将一些层、组件拆分为模块来管理，以便相互依赖复用，在 Spring Boot 项目中我们则可以创建自定义 Spring Boot Starter 来达成该目的。
 
Spring Boot Starter 统一了使用不同软件的编程体验。
 
在没有使用 Spring Boot Starter 之前，我们需要按照每个开源软件的特性，将对应的组件包集成到我们的开发项目中，因为每个组件的设计理念和开发团队都不一致，因此会有很多不同的调用风格在我们的项目中。
 
Spring Boot 强大到很多技术社区都主动提供了对应的 Starter 组件，比如 MyBatis 、Apache Camel、Apache CXF 等等。随着 Spring Boot 的发展 Starter 组件会越来越多。
 
Spring Boot 非常强大的原因之一就是提供了大量的 Spring Boot Starter ，如此多的“开箱即用” 的依赖模块，让我们在日常开发中“拿来即用”，以便更加快速和高效专注于业务开发。
 
Spring Boot 的豪华开发团队
 
我们经常会看到在介绍 Spring Boot 的时候有这么一句：Spring Boot 是由 Pivotal 团队提供的全新框架。由此我们得知 Spring Boot 是由 Pivotal 团队所研发，那么 Pivotal 团队到底是一个什么样的团队呢？其实这里的 Pivotal 团队是指 Pivotal 公司。
 
Pivotal 公司介绍：致力于“改变世界构造软件的方式（We are transforming how the world builds software）”，提供云原生应用开发 PaaS 平台及服务，帮助企业客户采用敏捷软件开发方法论，从而提高软件开发人员工作效率、减少运维成本，实现数字化转型、IT 创新，并最终实现业务创新。
 
Pivotal 公司可谓是大牛云集，公司研发的产品有： Spring 以及衍生框架、缓存中间件 Redis、消息队列框架 RabbitMQ、数据引擎产品 Greenplum，还有 Tomcat、Groovy 里的一些顶级开发者，DevOps 理论的提出者都在这个公司。
 
2016 年风靡全球的云原生理念亦是 Pivotal 公司提出，美国硅谷著名的精益化创业书籍的作者 Eric Ries 也加入了 Pivotal公司。Spring Boot 为什么如此的优秀，正是因为背后有这些全球的顶级开发者。
 
Pivotal 公司的背后其实是一场商业并购大片，有很多著名的公司在其身后，戴尔、Spring、EMC、VMware 等等，详情大家开源看这篇文章：《是时候给大家介绍 Spring Boot/Cloud 背后豪华的研发团队了》。
 
有个好干爹
 
Spring Boot 的干爹是谁呢？毫无疑问就是 Spring 了。有图为证，看下面：
 
 
Spring Boot 完全依赖 Spring 来开发，发明 Spring Boot 也是为了让大家更好的使用 Spring，而不是消灭 Spring ，所以说没有 Spring 这个干爹，就没有 Spring Boot 。
 
当然 Spring Boot 不仅是基于 Spring 开发这么简单，Spring Boot 完全继承了 Spring 干爹的声誉，说实话如果没有 Spring 这个老干爹十多年来打拼下来的天气，哪有 Spring Boot 今天来的风光。
 
2002 年的时候， Rod Johnson 可能也没有想到自己开创的一个小开源软件，可以发展到今天这么辉煌的一刻。到了今天，如果一个 Java 程序员说自己不知道 Spring ，那估计会把他当作外星人吧。
 
Spirng 当时以 IoC 和 Aop 开始发家，一开始的目标只是想干掉 EJB 这个庞然大物，但是随着时间的发展，Spring 开始了一路的逆袭之路，在2010年的时候 Spring 还是 SSH 三大框架之一，到了今天 Spring 要说自己是老二，还这没有人敢说自己是第一。
 
正是因为 Spring 在 Java 社区中有如此强大的影响力，所以在 Spring Boot 一出生的时候，就受到了广大社区爱好者的关注、使用、写教程、贡献代码、提 Bug。正是因为庞大的开源爱好者，才一起反铺 Spring Boot ，让 Spring Boot 发展这么快，这么好。
 
 
 
上面这段内容转载自 Spring Boot 为什么这么火？
 
 
所以你只需要再学习完 SpringBoot ，就能够完成一个初级 Java 开发的用人需求了。所以你必须要学好 SpringBoot，之前看很多大咖推荐 SpringBoot 实战这本书，我觉得这本书并不好，反正我看这本书的时候找不到头绪和思路
 
 
很多人认为是基础入门书籍，但是我觉得学习 SpringBoot ，看这几个 github 就行了
 
Github点赞接近 100k 的Spring Boot学习教程+实战项目推荐！
 
推荐以 Spring Boot 教程与 Spring Cloud 教程的详细开源项目 “SpringBoot-Learning” 此项目内容为 Spring Boot 教程程序样例，对于 Spring Boot 的初学者来说非常有用，文末也列出了Spring 相关开源项目，供大家交流学习。
 
1. SpringBoot-Learning 部分样例：
 快速入门
 
chapter1：基本项目构建（可作为工程脚手架），引入web模块，完成一个简单的RESTful API
使用Intellij中的Spring Initializr来快速构建Spring Boot/Cloud工程
 
工程配置
 
chapter2-1-1：配置文件详解：自定义属性、随机数、多环境配置等
 
Web开发
 
chapter3-1-1：构建一个较为复杂的RESTful API以及单元测试
chapter3-1-2：使用Thymeleaf模板引擎渲染web视图
chapter3-1-3：使用Freemarker模板引擎渲染web视图
chapter3-1-4：使用Velocity模板引擎渲染web视图
chapter3-1-5：使用Swagger2构建RESTful API
chapter3-1-6：统一异常处理
 
数据访问、日志管理等等，项目地址：程序猿DD/SpringBoot-Learning - 码云 Gitee.com
 
项目名称：spring boot 实践学习案例 springboot-learning-example
 项目结构：
 a. 『 基础 - 入门篇 』
 
springboot-helloworld
 《Spring Boot 之 HelloWorld 详解》
springboot-properties 《Spring Boot 之配置文件详解》
 
b. 『 基础 - Web 业务开发篇 』
 
springboot-restful 《Springboot 实现 Restful 服务，基于 HTTP / JSON 传输》《Spring Boot 之 RESRful API 权限控制》
springboot-freemarker 《Spring Boot 集成 FreeMarker 详解案例》
springboot-validation-over-json 《Spring Boot HTTP over JSON 的错误码异常处理》
 
c. 『 基础 – 数据存储篇 』
 
springboot-mybatis 《Springboot 整合 Mybatis 的完整 Web 案例》
springboot-mybatis-annotation 《Spring Boot 整合 Mybatis Annotation 注解的完整 Web 案例》
springboot-mybatis-mutil-datasource 《Spring Boot 整合 Mybatis 实现 Druid 多数据源详解》
 
d. 『 基础 – 数据缓存篇 』
 
springboot-mybatis-redis 《Spring Boot 整合 Redis 实现缓存操作》
springboot-mybatis-redis-annotation 《Spring Boot 注解实现整合 Redis 作为缓存》
 
e. 『 其他篇 』
 
springboot-elasticsearch 《Spring Boot 整合 Elasticsearch，实现 function score query 权重分查询》
springboot-dubbo-server
springboot-dubbo-client
 Dubbo 服务提供者工程和 Dubbo 服务消费者工程 《Springboot 整合 Dubbo/ZooKeeper 详解 SOA 案例》《Spring Boot 中如何使用 Dubbo Activate 扩展点》
 
Spring Data ES 篇
 
spring-data-elasticsearch-crud 《Spring Data Elasticsearch - 基本案例》
spring-data-elasticsearch-query
 spring-data-elasticsearch - 实战案例详解
 
项目地址：泥沙砖瓦浆木匠/springboot-learning-example - 码云 Gitee.com
 
Spring 相关项目推荐：
 
项目名称：基于Spring+SpringMVC+Mybatis分布式敏捷开发系统架构
 
 
项目内容：基于Spring+SpringMVC+Mybatis分布式敏捷开发系统架构，提供整套公共微服务服务模块：集中权限管理（单点登录）、内容管理、支付中心、用户管理（支持第三方登录）、微信平台、存储系统、配置中心、日志分析、任务和通知等，支持服务治理、监控和追踪，努力为中小型企业打造全方位J2EE企业级开发解决方案。
 项目地址：shuzheng/zheng - 码云 Gitee.com
 
项目名称：模块化开发系统 ybg-spring-fast
 项目简介：以SpringBoot 为中心，模块化开发系统，用户可以随意删减除权限框架外 任意的系统模块。复用，组装性强主要应用技术：spring Security+Ehcache+quartz+swagger2+Mysql5.6+springjdbc+druid+spring social+spring session + layerui+vue.js等。
 
 
项目地址：YYDeament/ybg-spring-fast - 码云 Gitee.com
 
项目名称：JAVA分布式快速开发平台 iBase4J
 
 
**项目内容：**JAVA分布式快速开发平台：SpringBoot，SpringMVC，Mybatis，mybatis-plus，motan/dubbo分布式，Redis缓存，Shiro权限管理，Spring-Session单点登录，Quartz分布式集群调度，Restful服务，QQ/微信登录，App token登录，微信/支付宝支付；日期转换、数据类型转换、序列化、汉字转拼音、身份证号码验证、数字转人民币、发送短信、发送邮件、加密解密、图片处理、excel导入导出、FTP/SFTP/fastDFS上传下载、二维码、XML读写、高精度计算、系统配置工具类等等。
 项目地址：iBase4J/iBase4J - 码云 Gitee.com
 
**4. 项目名称：**Java EE（J2EE）快速开发框架 ThinkGem
 **项目内容：**Java EE（J2EE）快速开发框架，基于经典技术组合（Spring MVC、Apache Shiro、MyBatis、Bootstrap UI），包括核心模块如：组织机构、角色用户、权限授权、数据权限、内容管理、工作流等。虽说很长时间没有大的更新了，但它的架构精良易于扩展深受大家喜爱，依然是中小企业的首选，它的功能设计、底层架构也非常具有参考意义、是学习入门的首选。关注我ThinkGem开源中国博客了解4.0最新动态。
 项目地址：ThinkGem/JeeSite - 码云 Gitee.com
 
**5. 项目名称：**Java快速开发平台 MCMS
 
 
项目内容：完整开源，Java快速开发平台。基于Spring、SpringMVC、Mybatis架构，MStore提供更多好用的插件与模板（文章、商城、微信、论坛、会员、评论、支付、积分、工作流、任务调度等，同时提供上百套免费模板任意选择），价值源自分享！铭飞系统不仅一套简单好用的开源系统、更是一整套优质的开源生态内容体系。
 项目地址：铭飞/MCMS - Gitee
 
项目名称：基于Spring Cloud微服务化开发平台 AG-Admin
 
 
项目内容：AG-Admin是国内首个基于Spring Cloud微服务化开发平台，具有统一授权、认证后台管理系统，其中包含具备用户管理、资源权限管理、网关API管理等多个模块，支持多业务系统并行开发，可以作为后端服务的开发脚手架。代码简洁，架构清晰，适合学习和直接项目中使用。核心技术采用Eureka、Fegin、Ribbon、Zuul、Hystrix、JWT Token、Mybatis等主要框架和中间件，前端采用vue-element-admin组件。
 项目地址：老A/AG-Admin - 码云 Gitee.com
 
项目名称：轻量级的Spring Boot快速开发平台 renren-fast
 项目简介：renren-fast是一个轻量级的Spring Boot快速开发平台，其设计目标是开发迅速、学习简单、轻量级、易扩展；使用Spring Boot、Shiro、MyBatis、Redis、Bootstrap、Vue2.x等框架，包含：管理员列表、角色管理、菜单管理、定时任务、参数管理、代码生成器、日志管理、云存储、API模块(APP接口开发利器)、前后端分离等。
 项目地址：人人开源/renren-fast - 码云 Gitee.com
 
 
 
作者：Gitee 链接：https://www.zhihu.com/question/53729800/answer/255785661
 
 
其实你学了一段时间就会发现，SpringBoot 就完全是个脚手架，方便我们快速搭建一个项目，简化了配置，不用再让你写繁杂的 XML 表达式，相反的而是用 注解 来实现，他们的原理类似，只不过使用注解能让你的项目更加简洁。
 
最后再推荐一下 SpringBoot 的官网
 
https://docs.spring.io/spring-boot/docs/2.3.10.RELEASE/reference/htmlsingle/
 
Spring Cloud
 
Spring Cloud 是以 SpringBoot 为基础的微服务项目架构，现在大多数互联网公司甚至一些传统行业都开始用 Spring Cloud 为基础架构，有些是因为业务需求，有些是为了装 B，反正不管怎样，面试官问起你会不会 Spring Cloud，你说不会的话，那么你的印象分估计会降低，所以初级程序员，或多或少要了解一下 Spring Cloud ，所以我给你推荐几本书和 Github 作为基础和练习。
 
我刚开始学 Spring Cloud 是看的这本书，当然现在这个书中的版本有些好了，不过作为了解，你也应该看一下这本书
 
 
《Spring Cloud 微服务实战》从时下流行的微服务架构概念出发，详细介绍了 Spring Cloud 针对微服务架构中几大核心要素的解决方案和基础组件。对于各个组件的介绍，《Spring Cloud 微服务实战》主要以示例与源码结合的方式来帮助读者更好地理解这些组件的使用方法以及运行原理。同时，在介绍的过程中，还包含了作者在实践中所遇到的一些问题和解决思路，可供读者在实践中作为参考。
 
这本书的作者翟永超（DD）也建了一个网站
 
https://blog.didispace.com/spring-cloud-learning/
 
反正学习 Spring Cloud 跟着 D 总没错的。
 
可以看下 Spring Cloud 大致都要学习哪些东西
 
Brixton 版本
 
 
Dalston 版本
 
 
Edgware 版本
 
 
Finchley 版本
 
 
还有各种套件的选择
 
 
 
顺便把阿里巴巴开源框架 Spring Cloud Alibaba 学了
 
 
除了上述内容之外，还可以看看到底什么是微服务
 
 
本书全面介绍了微服务的建模、集成、测试、部署和监控，通过一个虚构的公司讲解了如何建立微服务架构。主要内容包括认识微服务在保证系统设计与组织目标统一上的重要性，学会把服务集成到已有系统中，采用递增手段拆分单块大型应用，通过持续集成部署微服务，等等。
 
什么是微服务设计模式，微服务设计模式都有哪些，以及微服务的拆分策略等。
 
 
估计很多人可能会把集群、微服务和分布式搞混了，下面来解惑下
 
集群是个物理形态，分布式是个工作方式。
 1.分布式：一个业务分拆多个子业务，部署在不同的服务器上
 2.集群：同一个业务，部署在多个服务器上
 分布式是指将不同的业务分布在不同的地方。而集群指的是将几台服务器集中在一起，实现同一业务。
 
分布式中的每一个节点，都可以做集群。而集群并不一定就是分布式的。
 举例：就比如新浪网，访问的人多了，他可以做一个集群，前面放一个响应服务器，后面几台服务器完成同一业务，如果有业务访问的时候，响应服务器看哪台服务器的负载不是很重，就将给哪一台去完成。
 而分布式，从窄意上理解，也跟集群差不多，但是它的组织比较松散，不像集群，有一个组织性，一台服务器垮了，其它的服务器可以顶上来。
 分布式的每一个节点，都完成不同的业务，一个节点垮了，那这个业务就不可访问了。
 简单说，分布式是以缩短单个任务的执行时间来提升效率的，而集群则是通过提高单位时间内执行的任务数来提升效率。
 例如：如果一个任务由 10 个子任务组成，每个子任务单独执行需 1 小时，则在一台服务器上执行该任务需 10 小时。
 采用分布式方案，提供 10 台服务器，每台服务器只负责处理一个子任务，不考虑子任务间的依赖关系，执行完这个任务只需一个小时。(这种工作模式的一个典型代表就是 Hadoop 的 Map/Reduce 分布式计算模型）
 而采用集群方案，同样提供 10 台服务器，每台服务器都能独立处理这个任务。假设有 10 个任务同时到达，10 个服务器将同时工作，1 小时后，10 个任务同时完成，这样，整体来看，还是 1 小时内完成一个任务！
 好的设计应该是分布式和集群的结合，先分布式再集群，具体实现就是业务拆分成很多子业务，然后针对每个子业务进行集群部署，这样每个子业务如果出了问题，整个系统完全不会受影响。
 另外，还有一个概念和分布式比较相似，那就是微服务。
 **微服务是一种架构风格，一个大型复杂软件应用由一个或多个微服务组成。**系统中的各个微服务可被独立部署，各个微服务之间是松耦合的。每个微服务仅关注于完成一件任务并很好地完成该任务。在所有情况下，每个任务代表着一个小的业务能力。
 
区别:
 1.分布式
 
 
将一个大的系统划分为多个业务模块，业务模块分别部署到不同的机器上，各个业务模块之间通过接口进行数据交互。区别分布式的方式是根据不同机器不同业务。
 上面：service A、B、C、D 分别是业务组件，通过API Geteway进行业务访问。
 注：分布式需要做好事务管理。
 分布式事务可参考：微服务架构的分布式事务解决方案
 
2.集群模式
 
 
集群模式是不同服务器部署同一套服务对外访问，实现服务的负载均衡。区别集群的方式是根据部署多台服务器业务是否相同。
 注：集群模式需要做好session共享，确保在不同服务器切换的过程中不会因为没有获取到session而中止退出服务。
 一般配置Nginx的负载容器实现：静态资源缓存、Session共享可以附带实现，Nginx支持5000个并发量。
 
分布式是否属于微服务？
 答案是肯定的。微服务的意思也就是将模块拆分成一个独立的服务单元通过接口来实现数据的交互。
 
微服务架构
 微服务的设计是为了不因为某个模块的升级和BUG影响现有的系统业务。微服务与分布式的细微差别是，微服务的应用不一定是分散在多个服务器上，他也可以是同一个服务器。
 
 
分布式和微服的架构很相似，只是部署的方式不一样而已。
 
 
 
链接：https://www.jianshu.com/p/1f9455139a31
 作者：mayiwoaini
 
 
然后我就要推荐给你一本分布式方向的神书了
 
 
有些人认为这是数据处理方向的人看的书，但是里面涉及 NoSQL, 大数据，最终一致性，CAP，MapReduce，流处理确实 Java 程序员也需要知道和了解的，这本书讲的比较高深，适合在工作中慢慢研究，不太适合 Java 方向的初学者。
 
 
综上所述，我上面推荐的三本书都适合中高级 Java 程序员来看的，初学者把 D 总的文章搞懂了就行，或者可以做做下面的 github
 
macrozheng/springcloud-learning
 
Dubbo
 
说完了 Spring Cloud，怎能少的了 Dubbo？
 
先来了解一下 Spring Cloud 和 Dubbo 的区别是什么，如何做技术选型？
 
Java 微服务框架选型（Dubbo 和 Spring Cloud？）
 
Dubbo 的书籍感觉一般，我没有看过，不过大家感兴趣可以了解一下
 
 
《深入理解Apache Dubbo与实战》首先介绍Dubbo的简史、后续的规划和整体架构大图；接着介绍Dubbo环境配置，并基于Dubbo开发第一款应用程序；然后介绍Dubbo内置的常用注册中心的实现原理，Dubbo扩展点加载的原理和实现，Dubbo的启动、服务暴露、服务消费和优雅停机的机制，Dubbo中RPC协议细节、编解码和服务调用实现原理，Dubbo集群容错、路由和负载均衡机制，Dubbo的扩展点相关知识，Dubbo高级特性的实现和原理，Dubbo常用的Filter的实现原理，Dubbo中新增etcd3注册中心的实战内容和Dubbo服务治理平台的相关知识；最后介绍Dubbo未来生态和Dubbo Mesh的相关知识。
 
官网文档走起！ Apache Dubbo
 
Dubbo 的 Github apache/dubbo
 
Redis
 
Redis 可以说是最流行的 NoSQL 数据库了，你可能不知道 Redis 是干什么用的，我先给你普及一下。
 
缓存数据库目前最常用的两种就是 Redis 和 Memcached，与 Memcached 相比 Redis 其一大特点是支持丰富的数据类型(Memcached 只能用 string 类型)。Redis 因为其丰富的数据结构因此应用范围不局限于缓存，有很多场景用 Redis 来实现可以大大减少工作量。
 
关于 Redis 的使用场景，可以看一下
 
Redis能用来做什么
 
深入分析Redis特点及应用场景
 
这里给大家推荐两本 Redis 入门的经典书籍
 
Redis 实战
 
 
这本书一共由三个部分组成。第一部分对Redis进行了介 绍，说明了Redis的基本使用方法、它拥有的5种数据结构以及操作这5种数据结构的命令，并讲解了如何使用Redis去构建文章展示网站、cookie、购物车、网页缓存、数据库行缓存等一系列程序。第二部分对Redis命令进行了更详细的介绍，并展示了如何使用Redis去构建更为复杂的辅助工具和应用程序，并在最后展示了如何使用Redis去构建一个简单的社交网站。第三部分对Redis用户经常会遇到的一些问题进行了介绍，讲解了降低Redis内存占用的方法、扩展Redis性能的方法以及使用Lua语言进行脚本编程的方法。这
 
Redis 设计与实现
 
 
这本书强烈推荐，系统而全面地描述了 Redis 内部运行机制，图示丰富，描述清晰，并给出大量参考信息，是 NoSQL 数据库开发人员的案头必备。
 
这本书和上面的 Redis 实战，一个讲实现，一个讲思想，正所谓理论和实践相结合。
 
Redis 开发与运维
 
 
这本书也是学习 Redis 很好的一本，也针对于初学者，适合零基础的童鞋。这本书全面讲解 Redis 基本功能及其应用，并结合线上开发与运维监控中的实际使用案例，深入分析并总结了实际开发运维中遇到的“陷阱”，以及背后的原因， 包含大规模集群开发与管理的场景、应用案例与开发技巧，为高效开发运维提供了大量实际经验和建议。
 
Redis 深度历险：核心原理与应用实践
 
 
Redis 深度历险是老钱写的，老钱最开始在掘金开了一门掘金小册，受到广泛好评，所以这本书也是如此。Redis 深度历险适合对于 Redis 有一定基础了解的程序员阅读，渴望深度掌握 Redis 技术原理的中高级后端开发者；渴望成功进入大型互联网企业研发部的中高级后端开发者；需要支撑公司 Redis 中间件运维工作的初中级运维工程师；对 Redis 中间件技术好奇的中高级前端技术研究者。
 
学习 Redis 基本上上面几本书看完就差不多了，当然官网是必不可少的
 
Redis
 
关于 Redis 相关知识，你需要了解
 
Redis【入门】就这一篇！
Redis 命令【官网】
Redis 命令参考手册
通俗易懂的Redis数据结构基础教程
Redis(1)——5种基本数据结构
Redis持久化
一文看懂Redis的持久化原理
10分钟彻底理解Redis的持久化机制：RDB和AOF
基于Redis的分布式锁实现
[Redis] 你了解 Redis 的三种集群模式吗？
分布式锁的实现之 redis 篇
Redis集群的原理和搭建
深入剖析Redis系列(二) - Redis哨兵模式与高可用集群
Redis 事务详解
Redis Lua实战
Redis Lua脚本完全入门
 
Kafka
 
我刚开始听到 Kafka 的时候，还以为是写《变形记》的那位呢 哈哈哈，其实不是，Kafka 是一个优秀的消息流平台。
 
 
Kafka学习之路 （一）Kafka的简介
 
就介绍一些 kafka 的基本内容显然不够，更多内容你可以参考
 
Kafka 权威指南
 
 
我当时入门看的是这本书，所以强烈推荐一下。这本书是 O’ RELLY 出版的，作者为 LinkedIn 的 Kafka 核心作者和一线技术人员共同执笔写成的，可以说是非常权威。
 
这本书详细介绍了如何部署Kafka集群、开发可靠的基于事件驱动的微服务，以及基于 Kafka 平台构建可伸缩的流式应用程序。通过详尽示例，你将会了解到 Kafka 的设计原则、可靠性保证、关键API，以及复制协议、控制器和存储层等架构细节。
 
Apache Kafka实战
 
 
这本书的作者是胡夕老师，胡夕老师对 Kafka 有非常深入的理解，他也在极客时间开了一门 Kafka 的课程，我是通过课程认识他的，胡夕老师对 Kafka 源码有很深的研究，所以这本 Apache Kafka 实战，是一本涵盖 Apache Kafka 各方面的具有实践指导意义的工具书和参考书。作者结合典型的使用场景，对 Kafka 整个技术体系进行了较为全面的讲解，以便读者能够举一反三，直接应用于实践。同时，本书还对 Kafka 的设计原理及其流式处理组件进行了较深入的探讨，并给出了翔实的案例。
 
深入理解Kafka：核心设计与实践原理
 
 
这本书适合对 Kafka 有一定程度了解的童鞋，这本书从基础概念入手，循序渐进地转入对其内部原理的剖析。
 
最后，官网压轴
 
Apache Kafka
 
kafka 的学习视频，大家看看尚硅谷的就可以了。
 
尚硅谷Kafka教程(kafka框架快速入门)
 
Kafka 一般会涉及如下内容
 
Kafka学习之路 （一）Kafka的简介
Kafka学习之路 （二）Kafka的架构
Kafka学习之路 （三）Kafka的高可用
Kafka学习之路 （四）Kafka的安装
Kafka学习之路 （五）Kafka在zookeeper中的存储
真的，关于 Kafka 入门看这一篇就够了
你能说出 Kafka 这些原理吗
Kafka【第一篇】Kafka集群搭建
Kafka监控工具汇总
比Kafka Mangaer更优秀的开源监控工具-Kafka Eagle
Apache Kafka监控与调优
 
ZooKeeper
 
Kafka 的底层是使用 ZooKeeper 来保证可靠性的，那么 ZooKeeper 是什么呢？
 
ZooKeeper 介绍
 
ZooKeeper 一个中心化的服务, 用于维护配置信息, 命名服务(naming), 提供分布式同步和集群服务(group services)。
 
它是一个开源的分布式应用程序协调服务, 作为 Google Chubby 的一个开源实现, 是 Hadoop 和 Hbase 的重要组件。 ZooKeeper 的目标是封装好复杂易出错的关键服务, 暴露简单易用、高效、稳定的接口给用户, 提供 java 和 C 接口。
 
设计目标
 
简单
 ZooKeeper 允许分布式的进程之间通过一个共享的层级命名空间(hierarchinal namespace, 和文件系统类似)进行协调。
 ZK 实现了高性能、高可用和严格顺序访问, 是的它可以用于大规模分布式系统, 无单点故障问题, 和复杂的同步原语。
 复制的(replicated)
 ZooKeeper 和其它的分布式进程一样, 也是一个集群的主机作为一个整体。结构如下图
 
 
组成 ZooKeeper 服务的所有服务器必须指向相互之间的存在, 并在内存中维护一张状态图和事务日志, 以及永久储存的快照。 只要服务器中的一个多数(majority)保持可用, ZooKeeper 就可以继续提供服务。
 客户端连接到一个单一的(single) ZooKeeper 服务器, 通过 TCP 连接来发送请求、获取响应、观察的事件和发送心跳。 如果 TCP 连接断开了, 客户端则连接到其它服务器。
 
有序(ordered)
 ZooKeeper 用一个数字表示每一次的更新, 以反映所有 ZooKeeper 事务的顺序。后续可以利用这个顺序来实现诸如同步原语之类的高级抽象。
 
快速(fast)
 ZK 在读多写少的负载中性能尤其高, 读写比例大概处于 10:1 时表现最好。
 
数据模型和层级命名空间(hierarchinal namespace)
 命名空间
 
 
名字是一个用斜杆(/)分隔的路径元素序列, ZK 中每一个节点(znode)都用路径标识。
 
节点和临时节点(ephemeral nodes)
 和文件系统不同, ZK 中的节点可以拥有数据和子节点。ZK 被设计来存储协调数据: 状态信息、配置、位置信息等, 所以数据通常很小(byte 到 kilobyte 之间)。
 znode 维护了一个状态结构体(stat structure), 结构体包含数据修改的版本, ACL(Access Control List) 变化, 时间戳。 每次数据修改, 版本号加一。
 znode 中的数据读取都是原子的, 读写都是整个节点所有数据进行读写, 并且通过 ACL 进行访问控制。
 临时节点表示只在 session 存续的期间存在的节点, 在实现[tbd]时很有用。
 
条件更新和观察(watches)
 当一个 znode 改变时会触发一个观察, 且删除 watch。客户端可以通过 watch 来接收到通知, 如果客户端和 ZK 的连接断开了会受到一个本地通知。
 
保证(Guarantees)
 
顺序一致性(Sequential Consistency) - 从一个客户端来的更新会按照发送的顺序应用
原子性(atomicity) -
单系统镜像(Signle System Image) - 不管客户端连到的是哪一个 ZK 服务器, 看到的都是同样一个 view
可靠性(Reliability) -
及时性(Timeliness) - 在一定的时间范围内(within a certain time bound), 客户端看到服务器 view 保证是最新的
 
简单 API
 简单的编程接口
 
create
delete
exists
get data
set data
get children
sync
 
实现
 
 
除了 Reqeust Processor 以外, 组成 ZK 服务的每一台服务器拥有所有组件的一份本地拷贝。Replicated Database 是一个内存数据库, 而每一个更新操作都会先序列化到磁盘, 然后才会应用到内存数据库。
 
读请求 - ZK 服务器根据的本地 Replicated Database 响应
写请求 - ZK 服务器会将来自客户端的所有写请求转发到角色为 leader 的 ZK 服务器(leader 只有一个, 其它称为 follower) 来写, 然后同步给 follower
 
ZK 使用一个自定义的原子消息协议。
 
性能
 
 
测试环境
 
ZooKeeper release 3.2
服务器 双核 2GHz Xeon, 两块 15K RPM 的 SATA, 一块作为 ZK 的日志, 快照写到系统盘
读写请求都是 1K
“Servers” 表示提供服务的 ZK 服务器数量
接近 30 台其它服务器用来模拟客户端
leader 配置成不接受客户端连接
 
可靠性
 
 
图中 1-5 表示如下五个事件:
 
一个 follower 失效和恢复
另外一个 follower 失效和恢复
leader 失效
两个 follower 失效和恢复
另外一个 leader 失效
 
ZK 服务器组由 7 台服务器组成, 写请求的比例保持在 30%。
 几个观察到的现象
 
follower 失效和恢复足够快的话, ZK 能够保持高吞吐
leader 失效性能影响较大
花了不到 200ms 来选举一个新的 leader
follower 恢复后, 吞吐能够提升回来
 
更多关于 ZooKeeper 的内容，可以参考下
 
从 Paxos 到 Zookeeper
 
 
这本书从分布式一致性的理论出发，向读者简要介绍几种典型的分布式一致性协议，以及解决分布式一致性问题的思路，其中重点讲解了 Paxos 和 ZAB 协议。同时，本书深入介绍了分布式一致性问题的工业解决方案——ZooKeeper，并着重向读者展示这一分布式协调框架的使用方法、内部实现及运维技巧，旨在帮助读者全面了解 ZooKeeper，并更好地使用和运维 ZooKeeper。
 
ZooKeeper : 分布式过程协同技术详解
 
 
这本书内容非常好，但是翻译属实有些不忍直视了。
 
一般市面上关于 ZooKeeper 的书非常少，只找到了这两本，推荐读者读一下 《从 Paxos 到 ZooKeeper》 这本书，我看过一遍，内容还是写的非常容易理解。
 
关于 ZooKeeper 的视频，我还是推荐你尚硅谷的
 
尚硅谷Zookeeper教程(zookeeper框架精讲)
 
关于 ZooKeeper ，你需要掌握的有
 
一文读懂分布式架构知识体系（内含超全核心知识大图）-阿里云开发者社区
分布式一致性协议概述
zookeeper核心之ZAB协议就这么简单！
ZAB协议选主过程详解
Zookeeper系列一：Zookeeper介绍、Zookeeper安装配置、ZK Shell的使用
ZooKeeper 的应用场景
阿里P8架构师谈：Zookeeper的原理和架构设计，以及应用场景
【分布式】Zookeeper序列化及通信协议
【分布式】Zookeeper会话
【分布式】Zookeeper的Leader选举
深入浅出Zookeeper（七）：Leader选举
【分布式】Zookeeper请求处理
【分布式】Zookeeper数据与存储
Zookeeper 运维实践手册
zookeeper介绍及运维实践
 
Nginx
 
Nginx 基础知识
 
 
 
Nginx 是什么？
 
 
Nginx 是一个 web 服务器，主要处理客户端和服务器的请求分发。
 
 
 
特点和优势
 
 
高并发
热部署
快
低功耗
热部署
 
 
 
使用和扩展
 
 
开源免费的Nginx与商业版Nginx Plus，与之对应的是免费OpenResty与商业版OpenResty
 
开源版 nginx.org
商业版 NGINX Plus
阿里巴巴 Tengine
开源版 OpenResty
商业版 OpenResty
 
Nginx 正向代理与反向代理
 
 
 
为了便于理解，首先先来了解一下一些基础知识，nginx是一个高性能的反向代理服务器那么什么是反向代理呢？
 
 
代理是在服务器和客户端之间假设的一层服务器，代理将接收客户端的请求并将它转发给服务器，然后将服务端的响应转发给客户端。
 
不管是正向代理还是反向代理，实现的都是上面的功能。
 
如果你对OSI 七层模型与 TCP/IP 四层模型不是很熟悉可以再回顾下
 
 
 
 
正向代理
 
 
正向代理（forward）意思是一个位于客户端和原始服务器 (origin server) 之间的服务器，为了从原始服务器取得内容，客户端向代理发送一个请求并指定目标 (原始服务器)，然后代理向原始服务器转交请求并将获得的内容返回给客户端。
 
正向代理是为我们服务的，即为客户端服务的，客户端可以根据正向代理访问到它本身无法访问到的服务器资源。
 
正向代理对我们是透明的，对服务端是非透明的，即服务端并不知道自己收到的是来自代理的访问还是来自真实客户端的访问。
 
 
 
反向代理
 
 
反向代理（Reverse Proxy）方式是指以代理服务器来接受 internet 上的连接请求，然后将请求转发给内部网络上的服务器，并将从服务器上得到的结果返回给 internet 上请求连接的客户端，此时代理服务器对外就表现为一个反向代理服务器。
 
反向代理是为服务端服务的，反向代理可以帮助服务器接收来自客户端的请求，帮助服务器做请求转发，负载均衡等。
 
反向代理对服务端是透明的，对我们是非透明的，即我们并不知道自己访问的是代理服务器，而服务器知道反向代理在为他服务。
 
Nginx 基本配置
 
安装nginx时通常需要编译自己需要的模块，可以使用 rpmbuild 制作 Nginx 的 RPM 包
 
main                                # 全局配置

events {                            # nginx工作模式配置
}

http {                                # http设置
    ....

    server {                        # 服务器主机配置
        ....
        location {                    # 路由配置
            ....
        }

        location path {
            ....
        }

        location otherpath {
            ....
        }
    }

    server {
        ....

        location {
            ....
        }
    }

    upstream name {                    # 负载均衡配置
        ....
    }
}
 
如果想要生成nginx规范配置，可以参考nginxconfig.io
 
下面是 nginx 一些配置中常用的内置全局变量，你可以在配置的任何位置使用它们。
 
| 变量名 | 功能 | | — | — | | $host | 请求信息中的 Host，如果请求中没有 Host 行，则等于设置的服务器名 | | $request_method | 客户端请求类型，如 GET、POST | | $remote_addr | 客户端的 IP 地址 | | $args | 请求中的参数 | | $content_length | 请求头中的 Content-length 字段 | | $http_user_agent | 客户端 agent 信息 | | $http_cookie | 客户端 cookie 信息 | | $remote_addr | 客户端的 IP 地址 | | $remote_port | 客户端的端口 | | $server_protocol | 请求使用的协议，如 HTTP/1.0、HTTP/1.1\ | | $server_addr | 服务器地址 | | $server_name | 服务器名称 | | $server_port | 服务器的端口号 |
 
 
Nginx 负载均衡
 
Upstream 指定后端服务器地址列表，在 server 中拦截响应请求，并将请求转发到 Upstream 中配置的服务器列表。
 
upstream balanceServer {
    server 10.1.22.33:12345;
    server 10.1.22.34:12345;
    server 10.1.22.35:12345;
}

server {
    server_name  fe.server.com;
    listen 80;
    location /api {
        proxy_pass http://balanceServer;
    }
}
 
上面的配置只是指定了 nginx 需要转发的服务端列表，并没有指定分配策略。
 
默认情况下采用的是轮询策略，将所有客户端请求轮询分配给服务端。这种策略是可以正常工作的，但是如果其中某一台服务器压力太大，出现延迟，会影响所有分配在这台服务器下的用户。
 
Nginx常用命令
 
# 快速关闭Nginx，可能不保存相关信息，并迅速终止web服务
nginx -s stop
# 平稳关闭Nginx，保存相关信息，有安排的结束web服务
nginx -s quit
# 因改变了Nginx相关配置，需要重新加载配置而重载
nginx -s reload
# 重新打开日志文件
nginx -s reopen
# 为 Nginx 指定一个配置文件，来代替缺省的
nginx -c filename
# 不运行，而仅仅测试配置文件。nginx 将检查配置文件的语法的正确性，并尝试打开配置文件中所引用到的文件
nginx -t
#  显示 nginx 的版本
nginx -v
# 显示 nginx 的版本，编译器版本和配置参数
nginx -V
# 格式换显示 nginx 配置参数
2>&1 nginx -V | xargs -n1
2>&1 nginx -V | xargs -n1 | grep lua
 
上面只是一些 Nginx 的基础知识，如果想要了解更多的 Nginx 内容，你可以参考
 
深入理解 Nginx
 
 
学习 Nginx ，跟着陶辉老师就够了，这本书首先通过介绍官方 Nginx 的基本用法和配置规则，帮助读者了解一般 Nginx 模块的用法，然后重点介绍了如何开发 HTTP 模块(含 HTTP 过滤模块)来得到定制化的 Nginx，其中包括开发—个功能复杂的模块所需要了解的各种知识，并对内存池的实现细节及 TCP 协议进行了详细介绍；接着，综合 Nginx 框架代码分析了 Nginx 架构的设计理念和技巧，此外，还新增了如何在模块中支持 HTTP变量，以及与 slab 共享内存等相关的内容，相信通过完善，可进一步帮助读者更好地开发出功能丰富、性能—流的 Nginx 模块。
 
如果大家有兴趣，陶辉老哥在极客时间开了一门关于 Nginx 的课程，大家可以详细了解下。
 
Nginx 是需要你在工作中逐渐掌握的，它涉及内容如下
 
8分钟带你深入浅出搞懂Nginx
万字总结，体系化带你全面认识 Nginx ！
就是要让你搞懂 Nginx，这篇就够了！
 
Netty
 
Netty 是一个利用 Java 的高级网络的能力，隐藏其背后的复杂性而提供一个易于使用的 API 的客户端/服务器框架。
 Netty 是一个广泛使用的 Java 网络编程框架（Netty 在 2011 年获得了Duke’s Choice Award，见https://www.java.net/dukeschoice/2011）。它活跃和成长于用户社区，像大型公司 Facebook 和 Instagram 以及流行 开源项目如 Infinispan, HornetQ, Vert.x, Apache Cassandra 和 Elasticsearch 等，都利用其强大的对于网络抽象的核心代码。
 
大家可以看看这篇文章 Netty入门教程——认识Netty
 
Netty 推荐一本书
 
Netty 实战
 
 
这一本书循序渐进的为你介绍了 Netty 各个方面内容，本书共分为4个部分：第一部分详细地介绍Netty 的相关概念以及核心组件，第二部分介绍自定义协议经常用到的编解码器，第三部分介绍Netty 对于应用层高级协议的支持，会覆盖常见的协议及其在实践中的应用，第四部分是几个案例研究。此外，附录部分还会简单地介绍 Maven，以及如何通过使用 Maven编译和运行本书中的示例。
 
ES
 
ES 的全称是 Elasticsearch，这个名字挺难拼写的，关于 ES 是干啥的以及 ES 入门汇总，你可以参考这一篇
 
Elasticsearch入门，这一篇就够了
 
更多关于 ES 的内容，你可以看这本书
 
Elasticsearch 实战
 
 
全书共分两个部分，第一部分解释了核心特性，内容主要涉及 Elasticsearch 的介绍，数据的索引、更新和删除，数据的搜索，数据的分析，使用相关性进行搜索，使用聚集来探索数据，文档间的关系等；第二部分介绍每个特性工作的更多细节及其对性能和可扩展性的影响，以便对核心功能进行产品化，内容主要涉及水平扩展和性能提升等。
 
Elasticsearch 源码解析与优化实战
 
 
《Elasticsearch源码解析与优化实战》介绍了Elasticsearch的系统原理，旨在帮助读者了解其内部原理、设计思想，以及在生产环境中如何正确地部署、优化系统。系统原理分两方面介绍，一方面详细介绍主要流程，例如启动流程、选主流程、恢复流程；另一方面介绍各重要模块的实现，以及模块之间的关系，例如 gateway 模块、allocation 模块等。本书的最后一部分介绍如何优化写入速度、搜索速度等大家关心的实际问题，并提供了一些诊断问题的方法和工具供读者参考。
 
我刚开始学 ES 的时候，竟然不知道 ELK 是什么。。。。。。那么 ELK 是啥，为啥要搞 ELK ？
 
为什么用到ELK：
 一般我们需要进行日志分析场景：直接在日志文件中 grep、awk 就可以获得自己想要的信息。但在规模较大的场景中，此方法效率低下，面临问题包括日志量太大如何归档、文本搜索太慢怎么办、如何多维度查询。需要集中化的日志管理，所有服务器上的日志收集汇总。常见解决思路是建立集中式日志收集系统，将所有节点上的日志统一收集，管理，访问。
 一般大型系统是一个分布式部署的架构，不同的服务模块部署在不同的服务器上，问题出现时，大部分情况需要根据问题暴露的关键信息，定位到具体的服务器和服务模块，构建一套集中式日志系统，可以提高定位问题的效率。
 一个完整的集中式日志系统，需要包含以下几个主要特点：
 
收集－能够采集多种来源的日志数据
传输－能够稳定的把日志数据传输到中央系统
存储－如何存储日志数据
分析－可以支持 UI 分析
警告－能够提供错误报告，监控机制
 
ELK提供了一整套解决方案，并且都是开源软件，之间互相配合使用，完美衔接，高效的满足了很多场合的应用。目前主流的一种日志系统。
 
ELK简介：
 ELK是三个开源软件的缩写，分别表示：Elasticsearch , Logstash, Kibana , 它们都是开源软件。新增了一个FileBeat，它是一个轻量级的日志收集处理工具(Agent)，Filebeat占用资源少，适合于在各个服务器上搜集日志后传输给Logstash，官方也推荐此工具。
 Elasticsearch是个开源分布式搜索引擎，提供搜集、分析、存储数据三大功能。它的特点有：分布式，零配置，自动发现，索引自动分片，索引副本机制，restful风格接口，多数据源，自动搜索负载等。
 Logstash 主要是用来日志的搜集、分析、过滤日志的工具，支持大量的数据获取方式。一般工作方式为c/s架构，client端安装在需要收集日志的主机上，server端负责将收到的各节点日志进行过滤、修改等操作在一并发往elasticsearch上去。
 Kibana 也是一个开源和免费的工具，Kibana可以为 Logstash 和 ElasticSearch 提供的日志分析友好的 Web 界面，可以帮助汇总、分析和搜索重要数据日志。
 Filebeat隶属于Beats。目前Beats包含四种工具：
 
 
  
Packetbeat（搜集网络流量数据）
Topbeat（搜集系统、进程和文件系统级别的 CPU 和内存使用情况等数据）
Filebeat（搜集文件数据）
Winlogbeat（搜集 Windows 事件日志数据）
 
 
官方文档：
 Filebeat：
 https://www.elastic.co/cn/products/beats/filebeat
 https://www.elastic.co/guide/en/beats/filebeat/5.6/index.html
 Logstash：
 https://www.elastic.co/cn/products/logstash
 https://www.elastic.co/guide/en/logstash/5.6/index.html
 Kibana:
 https://www.elastic.co/cn/products/kibana
 https://www.elastic.co/guide/en/kibana/5.5/index.html
 Elasticsearch：
 https://www.elastic.co/cn/products/elasticsearch
 https://www.elastic.co/guide/en/elasticsearch/reference/5.6/index.html
 elasticsearch中文社区：
 https://elasticsearch.cn/
 
ELK架构图：
 架构图一：
 
 
这是最简单的一种ELK架构方式。优点是搭建简单，易于上手。缺点是Logstash耗资源较大，运行占用CPU和内存高。另外没有消息队列缓存，存在数据丢失隐患。
 此架构由Logstash分布于各个节点上搜集相关日志、数据，并经过分析、过滤后发送给远端服务器上的Elasticsearch进行存储。Elasticsearch将数据以分片的形式压缩存储并提供多种API供用户查询，操作。用户亦可以更直观的通过配置Kibana Web方便的对日志查询，并根据数据生成报表。
 
架构图二：
 
 
此种架构引入了消息队列机制，位于各个节点上的Logstash Agent先将数据/日志传递给Kafka（或者Redis），并将队列中消息或数据间接传递给Logstash，Logstash过滤、分析后将数据传递给Elasticsearch存储。最后由Kibana将日志和数据呈现给用户。因为引入了Kafka（或者Redis）,所以即使远端Logstash server因故障停止运行，数据将会先被存储下来，从而避免数据丢失。
 
架构图三：
 
 
此种架构将收集端logstash替换为beats，更灵活，消耗资源更少，扩展性更强。同时可配置Logstash 和Elasticsearch 集群用于支持大集群系统的运维日志数据监控和查询。
 
Filebeat工作原理：
 Filebeat由两个主要组件组成：prospectors 和 harvesters。这两个组件协同工作将文件变动发送到指定的输出中。
 
 
**Harvester（收割机）：**负责读取单个文件内容。每个文件会启动一个Harvester，每个Harvester会逐行读取各个文件，并将文件内容发送到制定输出中。Harvester负责打开和关闭文件，意味在Harvester运行的时候，文件描述符处于打开状态，如果文件在收集中被重命名或者被删除，Filebeat会继续读取此文件。所以在Harvester关闭之前，磁盘不会被释放。默认情况filebeat会保持文件打开的状态，直到达到close_inactive（如果此选项开启，filebeat会在指定时间内将不再更新的文件句柄关闭，时间从harvester读取最后一行的时间开始计时。若文件句柄被关闭后，文件发生变化，则会启动一个新的harvester。关闭文件句柄的时间不取决于文件的修改时间，若此参数配置不当，则可能发生日志不实时的情况，由scan_frequency参数决定，默认10s。Harvester使用内部时间戳来记录文件最后被收集的时间。例如：设置5m，则在Harvester读取文件的最后一行之后，开始倒计时5分钟，若5分钟内文件无变化，则关闭文件句柄。默认5m）。
 
**Prospector（勘测者）：**负责管理Harvester并找到所有读取源。
 filebeat.prospectors: - input_type: log paths: - /apps/logs/*/info.log
 Prospector会找到/apps/logs/*目录下的所有info.log文件，并为每个文件启动一个Harvester。Prospector会检查每个文件，看Harvester是否已经启动，是否需要启动，或者文件是否可以忽略。若Harvester关闭，只有在文件大小发生变化的时候Prospector才会执行检查。只能检测本地的文件。
 
Filebeat如何记录文件状态：
 将文件状态记录在文件中（默认在/var/lib/filebeat/registry）。此状态可以记住Harvester收集文件的偏移量。若连接不上输出设备，如ES等，filebeat会记录发送前的最后一行，并再可以连接的时候继续发送。Filebeat在运行的时候，Prospector状态会被记录在内存中。Filebeat重启的时候，利用registry记录的状态来进行重建，用来还原到重启之前的状态。每个Prospector会为每个找到的文件记录一个状态，对于每个文件，Filebeat存储唯一标识符以检测文件是否先前被收集。
 
Filebeat如何保证事件至少被输出一次：
 Filebeat之所以能保证事件至少被传递到配置的输出一次，没有数据丢失，是因为filebeat将每个事件的传递状态保存在文件中。在未得到输出方确认时，filebeat会尝试一直发送，直到得到回应。若filebeat在传输过程中被关闭，则不会再关闭之前确认所有时事件。任何在filebeat关闭之前为确认的时间，都会在filebeat重启之后重新发送。这可确保至少发送一次，但有可能会重复。可通过设置shutdown_timeout 参数来设置关闭之前的等待事件回应的时间（默认禁用）。
 
Logstash工作原理：
 Logstash事件处理有三个阶段：inputs → filters → outputs。是一个接收，处理，转发日志的工具。支持系统日志，webserver日志，错误日志，应用日志，总之包括所有可以抛出来的日志类型。
 
 
Input：输入数据到logstash。
 一些常用的输入为：
 file：从文件系统的文件中读取，类似于tail -f命令
 syslog：在514端口上监听系统日志消息，并根据RFC3164标准进行解析
 redis：从redis service中读取
 beats：从filebeat中读取
 
Filters：数据中间处理，对数据进行操作。
 一些常用的过滤器为：
 grok：解析任意文本数据，Grok 是 Logstash 最重要的插件。它的主要作用就是将文本格式的字符串，转换成为具体的结构化的数据，配合正则表达式使用。内置120多个解析语法。
 官方提供的grok表达式：https://github.com/logstash-plugins/logstash-patterns-core/tree/master/patterns
 grok在线调试：https://grokdebug.herokuapp.com/
 mutate：对字段进行转换。例如对字段进行删除、替换、修改、重命名等。
 drop：丢弃一部分events不进行处理。
 clone：拷贝 event，这个过程中也可以添加或移除字段。
 geoip：添加地理信息(为前台kibana图形化展示使用)
 
**Outputs：outputs是logstash处理管道的最末端组件。**一个event可以在处理过程中经过多重输出，但是一旦所有的outputs都执行结束，这个event也就完成生命周期。
 一些常见的outputs为：
 elasticsearch：可以高效的保存数据，并且能够方便和简单的进行查询。
 file：将event数据保存到文件中。
 graphite：将event数据发送到图形化组件中，一个很流行的开源存储图形化展示的组件。
 
Codecs：codecs 是基于数据流的过滤器，它可以作为input，output的一部分配置。Codecs可以帮助你轻松的分割发送过来已经被序列化的数据。
 一些常见的codecs：
 json：使用json格式对数据进行编码/解码。
 multiline：将汇多个事件中数据汇总为一个单一的行。比如：java异常信息和堆栈信息。
 
来源：博客园
 作者：Mr.Ares
 原文：https://www.cnblogs.com/aresxin/p/8035137.html
 
关于 ELK 看官网文档就行了，市面上没有什么好的可以借鉴的书籍。
 
Git
 
Git 是一款优秀的分布式版本控制平台，代码协作通常用于团队或者多人共同开发一个项目的情况，刚开始接触代码协作可能无法理解，就是说你和你的同事共同开发一个项目的话，你们的代码也要放在一起，你提交的代码对方能够看到，对方提交的代码你也能够看到。不用在说什么我改了代码我发给你，一方面你知道你改过内容可能会有遗漏，有一些人说那记录好改了哪些文件不就行了吗？但是你这样工作量多大？而且假如你和你同事改的是同一个文件呢？还要记住同一个文件中有多少内容是改没改过的嘛？这太麻烦而且低效了，所以 Git 就是用于解决这种情况的，Git 目前是大多数企业的选择，但是仍旧还有一些传统的软件公司使用 SVN，SVN 也是代码协作平台，下面具体介绍一下 Git
 
Git 是分布式的，SVN 是集中式的
 
Git是分布式的，SVN是集中式的
 
这是 Git 和 SVN 最大的区别。若能掌握这个概念，两者区别基本搞懂大半。因为 Git 是分布式的，所以 Git 支持离线工作，在本地可以进行很多操作，包括接下来将要重磅推出的分支功能。而 SVN 必须联网才能正常工作。
 
Git 复杂概念多，SVN 简单易上手
 
所有同时掌握 Git 和 SVN 的开发者都必须承认，Git 的命令实在太多了，日常工作需要掌握add,commit,status,fetch,push,rebase等，若要熟练掌握，还必须掌握rebase和merge的区别，fetch和pull的区别等，除此之外，还有cherry-pick，submodule，stash等功能，仅是这些名词听着都很绕。
 
在易用性这方面，SVN 会好得多，简单易上手，对新手很友好。但是从另外一方面看，Git 命令多意味着功能多，若我们能掌握大部分 Git 的功能，体会到其中的奥妙，会发现再也回不去 SVN 的时代了。
 
Git 分支廉价，SVN 分支昂贵
 
在版本管理里，分支是很常使用的功能。在发布版本前，需要发布分支，进行大需求开发，需要 feature 分支，大团队还会有开发分支，稳定分支等。在大团队开发过程中，常常存在创建分支，切换分支的需求。
 
Git 分支是指针指向某次提交，而 SVN 分支是拷贝的目录。这个特性使 Git 的分支切换非常迅速，且创建成本非常低。
 
而且 Git 有本地分支，SVN 无本地分支。在实际开发过程中，经常会遇到有些代码没写完，但是需紧急处理其他问题，若我们使用 Git，便可以创建本地分支存储没写完的代码，待问题处理完后，再回到本地分支继续完成代码。
 
学习 Git 的方式有很多种，但是最主要的还是你动手实践，不管是看书也好还是根据教程进行实操，你都需要实践一遍，那么 Git 的使用你就差不多了。
 
Git 也有一些书籍，我推荐给你。
 
Pro Git
 
首推的肯定是大部分程序员入门的《Pro Git》，该书由 GitHub 的两名早期员工 Scott Chacon 和 Ben Straub 编写而成。这本书可以说是最早期，也是现今知名度最高的 Git 入门教程了。
 通过该教程你可以快速了解到 Git 与 GitHub 的基础使用，内容覆盖面广，一些知识点也都讲得较为通透，所以也有不少人拿该这本书当 Git 的使用手册，遇到不懂的问题还会跑回来查阅。
 同时该书还配套了 视频教程 供读者观看。
 
 
或者 Pro Git 中文版 Pro Git（中文版）
 
Git 版本控制管理
 
 
O’Reilly 的一贯风格，清晰明了，特点是讲授了 GIT 的内部原理，而不是简单列举命令操作。使用很多例子和示意图，一目了然。
 
Git 的资料有很多，这里给大家推荐几个口碑非常好的
 
廖雪峰的 Git 教程可以说是做到简单清晰明了了，可以说是最好的 Git 入门指南
 
Git教程
 
Github Docs 的官方文档也是学习 Git 的好方式
 
快速入门 - GitHub Docs
 Git 工作流程（阮一峰）：http://www.ruanyifeng.com/blog/2015/12/git-workflow.html
 菜鸟教程-Git简明教程：http://www.runoob.com/manual/git-guide/
 Git Book：https://git-scm.com/book/zh/v2
 
上面这些内容，如果你能够真正掌握，我觉得你已经可以吊打 95% 以上的程序员了，上面这些内容你真正掌握可能会花 5 - 10 年的时间，不同层次的程序员掌握框架的层次不同，比如对于 Kafka 这个消息中间件来说，初级程序员可能知道 Kafka 是用来干什么的，知道 Kafka 有哪些组件，会安装搭建就可以了，对于中级程序员来说，你可能需要懂一些 Kafka 的配置和参数，知道 Kafka 的架构，Kafka 和其他消息中间件的区别等。如果你是高级程序员，可能要求你会监控 Kafka，Kafka 调优，有没有研究过 Kafka 的源码，某个细节点的内部实现原理等。如果你认真研究某个领域五年以上，那么你可以称之为领域内的专家了，我说的是研究，而不是你知道了某个框架五年以上就是专家了，这个概念是完全不一样的，研究是真正去一行一行看其内部实现源码，了解它的设计思想和痛点。
 
上面的这些内容可以说是针对非科班的程序员的，因为非科班程序员和科班程序员的侧重点不同，非科班程序员侧重点就是能上手干活，解决问题，科班程序员侧重点在于思路，算法等，因为他们在大学期间会仔细研究，认真打磨计算机基础。这也不是说非科班程序员不用学习计算机基础了，你在能上手干活的同时也要打牢基础，这样你才能够和科班的去竞争，去内卷，去弥补差距。
 
计算机基础是内功，内功在任何时期和阶段都是需要修炼的。
 
计算机基础
 
计算机基础都包括哪些呢？
 
计算机组成原理、操作系统、计算机网络、数据结构与算法。
 
计算机组成原理
 
先说计算机组成原理，这部分内容主要涉及
 
计算机系统概述
数据与运算
CPU 概述
存储子系统概述
总线和 IO 概述
 
这些内容可以在 MOOC 大学上找到
 
计算机组成原理_电子科技大学_中国大学MOOC(慕课)
 
大家也可以看一下这本书
 
 
虽然国内教授/专家写的书不及国外，但是在国内来说已经算是不错的了，而且这本书还是颇为具有指导意义的。
 
还有一本
 
 
这本书看的人比较少，但是不失为一本好书，计算机组成原理，了解汇编层的代码运行。计算机是如何执行二进制命令的。本书基于 arm 指令集架构。
 
操作系统
 
关于操作系统，我写了一篇如何学习的文章
 
如何学好操作系统原理这门课？
 
计算机网络
 
关于计算机网络，我也写了一篇关于如何学习的文章，你可以参考
 
计算机网络该怎么学？
 
数据结构和算法
 
算法书籍推荐：市面上有很多关于算法的书籍，最近非常火的《labuladong 的算法小抄》，通俗易懂的《小灰的算法之旅》等等，不过我这里只说两本最经典的算法书：《算法导论》和《算法第四版》
 
关于算法如何学习，可以参考下这个回答
 
如何系统地学习算法？
 
关于学习的意见和建议，可以参考
 
程序员cxuan：编程从入门到精通，2021小白版
 
这篇回答会持续完善下，欢迎读者追更，点赞喜欢关注就是对我的爱。
 
这是第一版内容，部分技术栈和知识点整理的不是很全面，这个我承认，不过如果这篇文章能够对你产生帮助，就是他的价值。
 
我把这篇文章汇总成为了 PDF 版本，链接如下。
 
获取 PDF 链接 密码: atsg

 局部敏感哈希
 
 
 在检索技术中，索引一直需要研究的核心技术。当下，索引技术主要分为三类：基于树的索引技术（tree-based index）、基于哈希的索引技术（hashing-based index）与基于词的倒排索引（visual words based inverted index）[1]。本文主要对哈希索引技术进行介绍。
 
 哈希技术概述
 
 
 在检索中，需要解决的问题是给定一个查询样本query，返回与此query相似的样本，线性搜索耗时耗力，不能承担此等重任，要想快速找到结果，必须有一种方法可以将搜索空间控制到一个可以接受的范围，哈希在检索中就是承担这样的任务，因而，这些哈希方法一般都是局部敏感（Locality-sensitive）的，即样本越相似，经过哈希后的值越有可能一样。所以，本文中介绍的技术都是局部敏感哈希（Locality Sensitive Hashing，LSH），与hashmap、hashtable等数据结构中的哈希函数有所不同。
 
 哈希技术分类
 
 
 
 
 
 

  图 1 LSH分层法使用
 
对于哈希技术，可以按照不同的维度对齐进行划分。 
 
 
 按照其在检索技术中的应用方法来划分，可以分为分层法和哈希码法：
 
分层法即为在数据查询过程中使用哈希技术在中间添加一层，将数据划分到桶中；在查询时，先对query计算桶标号，找到与query处于同一个桶的所有样本，然后按照样本之间的相似度计算方法（比如欧氏距离、余弦距离等）使用原始数据计算相似度，按照相似度的顺序返回结果，在该方法中，通常是一组或一个哈希函数形成一个表，表内有若干个桶，可以使用多个表来提高查询的准确率，但通常这是以时间为代价的。分层法的示意图如图1所示。在图1中，H1、H2等代表哈希表，g1、g2等代表哈希映射函数。 
 分层法的代表算法为E2LSH[2]。
 
哈希码法则是使用哈希码来代替原始数据进行存储，在分层法中，原始数据仍然需要以在第二层被用来计算相似度，而哈希码法不需要，它使用LSH函数直接将原始数据转换为哈希码，在计算相似度的时候使用hamming距离来衡量。转换为哈希码之后的相似度计算非常之快，比如，可以使用64bit整数来存储哈希码，计算相似度只要使用同或操作就可以得到，唰唰唰，非常之快，忍不住用拟声词来表达我对这种速度的难言之喜，还望各位读者海涵。 
 哈希码法的代表算法有很多，比如KLSH[3]、Semantic Hashing[4]、KSH[5]等。
 
 
 以我看来，两者的区别在于如下几点：
 
在对哈希函数的要求上，哈希码方法对哈希函数的要求更高，因为在分层法中，即便哈希没有计算的精确，后面还有原始数据直接计算相似度来保底，得到的结果总不会太差，而哈希码没有后备保底的，胜则胜败则败。
在查询的时间复杂度上，分层法的时间复杂度主要在找到桶后的样本原始数据之间的相似度计算，而哈希码则主要在query的哈希码与所有样本的哈希码之间的hamming距离的相似计算。哈希码法没有太多其他的需要，但分层法中的各个桶之间相对较均衡方能使复杂度降到最低。按照我的经验，在100W的5000维数据中，KSH比E2LSH要快一个数量级。
在哈希函数的使用上，两者使用的哈希函数往往可以互通，E2LSH使用的p-stable LSH函数可以用到哈希码方法上，而KSH等哈希方法也可以用到分层法上去。
 上述的区别分析是我自己分析的，如果有其他意见欢迎讨论。
 
 按照哈希函数来划分，可以分为无监督和有监督两种：
 
无监督，哈希函数是基于某种概率理论的，可以达到局部敏感效果。如E2LSH等。
有监督，哈希函数是从数据中学习出来的，如KSH、Semantic Hashing等。
 
 一般来说，有监督算法比无监督算法更加精确，因而也更常用于哈希码法中。
 本文中，主要对无监督的哈希算法进行介绍。
 
 Origin LSH
 
 
 最原始的LSH算法是1999年提出来的[6]。在本文中称之为Origin LSH。
 
 Embedding
 
 Origin LSH在哈希之前，首先要先将数据从L1准则下的欧几里得空间嵌入到Hamming空间。在做此embedding时，有一个假设就是原始点在L1准则下的效果与在L2准则下的效果相差不大，即欧氏距离和曼哈顿距离的差别不大，因为L2准则下的欧几里得空间没有直接的方法嵌入到hamming空间。
 
 
 
 
  
 
 

  

      

       

        1
       
       

        2
       
      

      

       

        Embedding算法如下：
       
       

         
       
      
 



 
找到所有点的所有坐标值中的最大值C；
对于一个点P来说，P=(x1,x2,…,xd)，d是数据的维度；
将每一维xi转换为一个长度为C的0/1序列，其中序列的前xi个值为1，剩余的为0.
然后将d个长度为C的序列连接起来，形成一个长度为Cd的序列.

这就是embedding方法。注意，在实际运算过程中，通过一些策略可以无需将embedding值预先计算出来。
Algorithm of Origin LSH
在Origin LSH中，每个哈希函数的定义如下：

即输入是一个01序列，输出是该序列中的某一位上的值。于是，hash函数簇内就有Cd个函数。
在将数据映射到桶中时，选择k个上述哈希函数，组成一个哈希映射，如下：


 

  
 
 
 
 
  
 
      
 
       

         1
       
 
       

         2
       
 
      
 
 
      
 
       

         再细化，
        LSH的算法步骤如下：
       
 
       

          
       
 
      
 
 
 
 
 
 
 
 
 
从[0,Cd]内取L个数，形成集合G，即组成了一个桶哈希函数g。
对于一个向量P，得到一个L维哈希值，即P|G，其中L维中的每一维都对应一个哈希函数h。
由于直接以上步中得到的L维哈希值做桶标号不方便，因而再进行第二步哈希，第二步哈希就是普通的哈希，将一个向量映射成一个实数。
 
 
 
 
 其中，a是从[0,M-1]中随机抽选的数字。
 
 这样，就把一个向量映射到一个桶中了。
 
 LSH based on p-stable distribution
 
 
 该方法由[2]提出，E2LSH[7]是它的一种实现。
 
 p-stable分布
 
 
 
 定义：对于一个实数集R上的分布D，如果存在P>=0，对任何n个实数v1,…,vn和n个满足D分布的变量X1,…,Xn，随机变量ΣiviXi和(∑i|vi|p)(1/p)X有相同的分布，其中X是服从D分布的一个随机变量，则称D为一个p稳定分布。
 
 
 对任何p∈(0,2]存在稳定分布。P=1时是柯西分布；p=2时是高斯分布。
 
 当p=2时，两个向量v1和v2的映射距离a·v1-a·v2和||v1-v2||pX的分布是一样的，此时对应的距离计算方式为欧式距离。
 
 利用p-stable分布可以有效的近似高维特征向量，并在保证度量距离的同时，对高维特征向量进行降维，其关键思想是，产生一个d维的随机向量a，随机向量a中的每一维随机的、独立的从p-stable分布中产生。对于一个d维的特征向量v，如定义，随机变量a·v具有和(∑i|vi|p)(1/p)X一样的分布，因此可以用a·v表示向量v来估算||v||p。
 
 E2LSH
 
 基于p-stable分布，并以‘哈希技术分类’中的分层法为使用方法，就产生了E2LSH算法。
 
 E2LSH中的哈希函数定义如下：
 
 
 
 其中，v为d维原始数据，a为随机变量，由正态分布产生; w为宽度值，因为a∙v+b得到的是一个实数，如果不加以处理，那么起不到桶的效果，w是E2LSH中最重要的参数，调得过大，数据就被划分到一个桶中去了，过小就起不到局部敏感的效果。b使用均匀分布随机产生，均匀分布的范围在[0,w]。
 
 与Origin LSH类似，选取k个上述的哈希函数，组成一个哈希映射，效果如图2所示：
 
 
 
 
 

  图 2 E2LSH映射
 
但是这样，得到的结果是(N
1
,N
2
,…,N
k
)，其中N
1
,N
2
,…,N
k
在整数域而不是只有0,1两个值，这样的k元组就代表一个桶。但将k元组直接当做桶标号存入哈希表，占用内存且不便于查找，为了方便存储，设计者又将其分层，使用数组+链表的方式，如图3所示： 
 
 
 
 
 
 

  图 3 E2LSH为存储桶标号而产生的数组+链表二层结构
 
对每个形式为k元组的桶标号，使用如下h1函数和h2函数计算得到两个值，其中h1的结果是数组中的位置，数组的大小也相当于哈希表的大小，h2的结果值作为k元组的代表，链接到对应数组的h1位置上的链表中。在下面的公式中,r
’
为[0,prime-1]中依据均匀分布随机产生。 
 
 
 
 
 
 
 
 
 
  
 
 
 
 
  
 
      
 
       

         1
       
 
       

         2
       
 
      
 
 
      
 
       

         经过上述组织后，查询过程如下：
       
 
       

          
       
 
      
 
 
 
 
 
 
 
 
 
对于查询点query，
使用k个哈希函数计算桶标号的k元组；
对k元组计算h1和h2值，
获取哈希表的h1位置的链表，
在链表中查找h2值，
获取h2值位置上存储的样本
Query与上述样本计算精确的相似度，并排序
按照顺序返回结果。
 
 
 E2LSH方法存在两方面的不足[8]：首先是典型的基于概率模型生成索引编码的结果并不稳定。虽然编码位数增加，但是查询准确率的提高确十分缓慢；其次是需要大量的存储空间，不适合于大规模数据的索引。E2LSH方法的目标是保证查询结果的准确率和查全率，并不关注索引结构需要的存储空间的大小。E2LSH使用多个索引空间以及多次哈希表查询，生成的索引文件的大小是原始数据大小的数十倍甚至数百倍。
 
 Hashcode of p-stable distribution
 
 E2LSH可以说是分层法基于p-stable distribution的应用。另一种当然是转换成hashcode，则定义哈希函数如下：
 
 
 
 其中，a和v都是d维向量，a由正态分布产生。同上，选择k个上述的哈希函数，得到一个k位的hamming码，按照”哈希技术分类”中描述的技术即可使用该算法。
 
 Reference
 
 
 [1]. Ai L, Yu J, He Y, et al. High-dimensional indexing technologies for large scale content-based image retrieval: a review[J]. Journal of Zhejiang University SCIENCE C, 2013, 14(7): 505-520.
 
 [2]. Datar M, Immorlica N, Indyk P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Proceedings of the twentieth annual symposium on Computational geometry. ACM, 2004: 253-262.
 
 [3]. Kulis B, Grauman K. Kernelized locality-sensitive hashing[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012, 34(6): 1092-1104.
 
 [4]. Salakhutdinov R, Hinton G. Semantic hashing[J]. International Journal of Approximate Reasoning, 2009, 50(7): 969-978.
 
 [5]. Liu W, Wang J, Ji R, et al. Supervised hashing with kernels[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 2074-2081.
 
 [6]. Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//VLDB. 1999, 99: 518-529.
 
 [7]. http://web.mit.edu/andoni/www/LSH/
 
 [8]. http://blog.csdn.net/jasonding1354/article/details/38237353
 
 文章出处：http://blog.csdn.net/stdcoutzyx/article/details/44456679
 
 
 
 
 
 
 
 
 
 位置敏感哈希(Locality Sensitive Hashing,LSH)是近似最近邻搜索算法中最流行的一种，它有坚实的理论依据并且在高维数据空间中表现优异。由于网络上相关知识的介绍比较单一，现就LSH的相关算法和技术做一介绍总结，希望能给感兴趣的朋友提供便利，也希望有兴趣的同道中人多交流、多指正。
 
 
 
 
 1、LSH原理
 
 最近邻问题（nearest neighbor problem）可以定义如下：给定n个对象的集合并建立一个数据结构，当给定任意的要查询对象时，该数据结构返回针对查询对象的最相似的数据集对象。LSH的基本思想是利用多个哈希函数把高维空间中的向量映射到低维空间，利用低维空间的编码来表示高维向量。通过对向量对象进行多次哈希映射，高维向量按照其分布以及自身的特性落入不同哈希表的不同桶中。在理想情况下可以认为在高维空间中位置比较接近的向量对象有很大的概率最终落入同一个桶中，而距离比较远的对象则以很大的概率落入不同的桶中。因此在查询的时候，通过对查询向量进行同样的多次哈希操作，综合多个哈希表中的查询操作得到最终的结果。
 
 
 
 
 图1 LSH哈希桶演示
 
 使用哈希函数对整个数据集进行过滤，得到可能满足查询条件的点再计算距离，这样就避免了查询点与数据集中所有点进行距离计算，提高了查询效率。该框架可以被称为过滤-验证框架。
 
 2、LSH函数族定义
 
 为了形式化地描述LSH使用的哈希函数的性质，现定义LSH函数族概念。
 
 令S为d维数据点的数据域，D为相似性度量函数，p和q为S中任意两点。函数族H={h:S->U}被称为(r1,r2,p1,p2)-敏感的，当且仅当：
 
 
 
 通过使用LSH函数族中函数进行哈希，可以保证距离近的点冲突的概率大于距离远的点冲突的概率。
 
 3、通用的LSH算法框架
 
 （1）构建LSH索引（哈希过程，Hashing）
 
 定义一个函数族G={g:S->U}，其中g(v)=(h1(v),...,hk(v))，hi∈H，独立随机地从G中选择L个哈希函数g1,...,gL。对于数据集中任意一点v，将其存储到桶gi(v)中，i=1,...,L。
 
 这种算法是完全索引算法（full-indexing algorithms）,它为每个可能的查询点提供一个查询表，因此，响应一个查询点，该算法只需在特殊构造的哈希表中进行一次查询（look-up）。
 
 （2）LSH搜索算法
 
 对于一个查询点q以及给定的距离阈值r，搜索桶g1(q),...,gL(q)，取出其中的所有点v1,...,vn作为候选近似最近邻点。对于任意的vj，如果D(q,vj)<=r，那么返回vj，其中D为相似性度量函数。
 
 在创建LSH索引时,选取的哈希函数是k个LSH函数的串联函数,这样就相对拉大了距离近的点冲突的概率pn与距离远的点冲突的概率pf之间的差值,但这同时也使这两个值一起减小了,于是需要同时使用L张哈希表来加大pn同时减小pf。通过这样的构造过程,在查询时,与查询点q距离近的点就有很大的概率被取出作为候选近似最近邻点并进行最后的距离计算,而与查询点q距离远的点被当作候选近似最近邻点的概率则很小,从而能够在很短的时间内完成查询。
 
 
 
 
 
 图2 通用LSH策略示意图
 
 
 
 
 转载请注明作者及文章出处：http://blog.csdn.net/jasonding1354/article/details/38227085
 
 
 
 
 参考资料：
 
 1、陈永健.基于内容的大规模图像检索关键技术研究[D].华中科技大学.2011
 
 2、凌康.基于位置敏感哈希的相似性搜索技术研究[D].南京大学.2012
 

 
 
 
 上一节，我们分析了LSH算法的通用框架，主要是建立索引结构和查询近似最近邻。这一小节，我们从p稳定分布LSH（p-Stable LSH）入手，逐渐深入学习LSH的精髓，进而灵活应用到解决大规模数据的检索问题上。
 
 对应海明距离的LSH称为位采样算法（bit sampling），该算法是比较得到的哈希值的海明距离，但是一般距离都是用欧式距离进行度量的，将欧式距离映射到海明空间再比较其的海明距离比较麻烦。于是，研究者提出了基于p-稳定分布的位置敏感哈希算法，可以直接处理欧式距离，并解决(R,c)-近邻问题。
 
 1、p-Stable分布
 
 定义：对于一个实数集R上的分布D，如果存在P>=0，对任何n个实数v1,…,vn和n个满足D分布的变量X1,…,Xn，随机变量ΣiviXi和(Σi|vi|p)1/pX有相同的分布，其中X是服从D分布的一个随机变量，则称D为 一个p稳定分布。
 
 对任何p∈(0,2]存在稳定分布：
 
 p=1是柯西分布，概率密度函数为c(x)=1/[π(1+x2)]；
 
 p=2时是高斯分布，概率密度函数为g(x)=1/(2π)1/2*e-x^2/2。
 
 
 利用p-stable分布可以有效的近似高维特征向量，并在保证度量距离的同时，对高维特征向量进行降维，其关键思想是，产生一个d维的随机向量a，随机向量a中的每一维随机的、独立的从p-stable分布中产生。对于一个d维的特征向量v，如定义，随机变量a·v具有和(Σi|vi|p)1/pX一样的分布，因此可以用a·v表示向量v来估算||v||p 。
 
 2、p-Stable分布LSH中的哈希函数
 
 p-Stable分布的LSH利用p-Stable的思想，使用它对每一个特征向量v赋予一个哈希值。该哈希函数是局部敏感的，因此如果v1和v2距离很近，它们的哈希值将相同，并被哈希到同一个桶中的概率会很大。
 
 根据p-Stable分布，两个向量v1和v2的映射距离a·v1-a·v2和||v1-v2||pX 的分布是一样的。
 
 
 a·v将特征向量v映射到实数集R，如果将实轴以宽度w等分，并对每一段进行标号，则a·v落到那个区间，就将此区间标号作为哈希值赋给它，这种方法构造的哈希函数对于两个向量之间的距离具有局部保护作用。
 
 哈希函数格式定义如下：
 
 ha,b(v):Rd->N，映射一个d维特征向量v到一个整数集。哈希函数中又两个随机变量a和b，其中a为一个d维向量，每一维是一个独立选自满足p-Stable的随机变量，b为[0,w]范围内的随机数，对于一个固定的a，b，则哈希函数ha,b(v)为
 
 
 
 
 
 
 
 图1 p-Stable LSH在二维空间的示例
 
 3、特征向量碰撞概率
 
 随机选取一个哈希函数ha,b(v)，则特征向量v1和v2落在同一桶中的概率该如何计算呢？
 
 首先定义c=||v1-v2||p，fp(t)为p-Stable分布的概率密度函数的绝对值，那么特征向量v1和v2映射到一个随机向量a上的距离是|a·v1-a·v2|<w，即|(v1-v2)·a|<w，根据p-Stable分布的特性,||v1-v2||pX=|cX|<w，其中随机变量X满足p-Stable分布。
 
 可得其碰撞概率p(c):
 
  
 
 根据该式，可以得出两个特征向量的冲突碰撞概率随着距离c的增加而减小。
 
 4、p-Stable分布LSH的相似性搜索算法
 
 经过哈希函数哈希之后，g(v)=(h1(v),...,hk(v))，但将(h1(v),...,hk(v))直接存入哈希表，即占用内存，又不便于查找，为解决此问题，现定义另外两个哈希函数：
 
 
 由于每一个哈希桶（Hash Buckets）gi被映射成Zk，函数h1是普通哈希策略的哈希函数，函数h2用来确定链表中的哈希桶。
 
 （1）要在一个链表中存储一个哈希桶gi(v)=(x1,...,xk)时，实际上存的仅仅是h2(x1,...,xk)构造的指纹,而不是存储向量(x1,...,xk)，因此一个哈希桶gi(v)=(x1,...,xk)在链表中的相关信息仅有标识(identifier)指纹h2(x1,...,xk)和桶中的原始数据点。
 
 （2）利用哈希函数h2，而不是存储gi(v)=(x1,...,xk)的值有两个原因：首先，用h2(x1,...,xk)构造的指纹可以大大减少哈希桶的存储空间；其次，利用指纹值可以更快的检索哈希表中哈希桶。通过选取一个足够大的值以很大的概率来保证任意在一个链表的两个不同的哈希桶有不同的h2指纹值。
 
 
 
 
 图2 桶哈希策略示意图
 
 5、不足与缺陷
 
 LSH方法存在两方面的不足：首先是典型的基于概率模型生成索引编码的结果并不稳定。虽然编码位数增加，但是查询准确率的提高确十分缓慢；其次是需要大量的存储空间，不适合于大规模数据的索引。E2LSH方法的目标是保证查询结果的准确率和查全率，并不关注索引结构需要的存储空间的大小。E2LSH使用多个索引空间以及多次哈希表查询，生成的索引文件的大小是原始数据大小的数十倍甚至数百倍。
 
 
 
 
 转载请注明作者及文章出处：http://blog.csdn.net/jasonding1354/article/details/38237353
 
 
 
 
 参考资料：
 
 1、王旭乐.基于内容的图像检索系统中高维索引技术的研究[D].华中科技大学.2008
 
 
 2、M.Datar,N.Immorlica,P.Indyk,and V.Mirrokni,“Locality-SensitiveHashing Scheme Based on p-Stable Distributions,”Proc.Symp. ComputationalGeometry, 2004.
 
 
 3、A.Andoni,“Nearest Neighbor Search:The Old, theNew, and the Impossible”PhD dissertation,MIT,2009.
 
 4、A.Andoni,P.Indyk.E2lsh:Exact Euclidean locality-sensitive hashing.http://web.mit.edu/andoni/www/LSH/.2004.
 
 
 
 
 
 
 
 
 
 搜集了快一个月的资料，虽然不完全懂，但还是先慢慢写着吧，说不定就有思路了呢。
 
 　　开源的最大好处是会让作者对脏乱臭的代码有羞耻感。
 
 　　当一个做推荐系统的部门开始重视【数据清理，数据标柱，效果评测，数据统计，数据分析】这些所谓的脏活累活，这样的推荐系统才会有救。
 
 　　求教GitHub的使用。
 
 　　简单不等于傻逼。
 
 　　我为什么说累：我又是一个习惯在聊天中思考前因后果的人，所以整个大脑高负荷运转。不过这样真不好，学习学成傻逼了。
 
 　　研一的最大收获是让我明白原来以前仰慕的各种国家自然基金项目，原来都是可以浑水摸鱼忽悠过去的，效率不高不说，还有可能有很多错误，哎，我就不说了。
 
 一、问题来源
 
 　　查找LSH发现的，这个是谷歌现在的网页去重方案。但是simHash和LSH有什么联系呢？提前透漏下，simHash本质上是一种LSH。正因为它的局部敏感性（这段的局部敏感性指的是非常相似的文本，即便只差一个字符，md5后的序列也可能非常不同，但是simHash之后的序列可能只是某几位不同），所以我们可以使用海明距离来衡量simhash值的相似度。
 
 　　simhash是google用来处理海量文本去重的算法。google出品，你懂的。simhash最牛逼的一点就是将一个文档，最后转换成一个64位的字节，暂且称之为特征字，然后判断重复只需要判断他们的特征字的距离是不是<n（根据经验这个n一般取值为3），就可以判断两个文档是否相似。
 
 　　谷歌出品嘛，简单实用。
 
 二、算法解析
 
 2.1 算法伪代码
 
 　　1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
 
 　　2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
 
 　　3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
 
 　　4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
 
 　　5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。
 
 
 
 2.2 simHash和传统哈希的区别
 
 　　大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个 0 1 字符串吗？我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。
 
 　　通过simhash计算结果为：
 
 　　1000010010101101111111100000101011010001001111100001001011001011
 
 　　1000010010101101011111100000101011010001001111100001101010001011
 
 　　通过 hashcode计算为：
 
 　　1111111111111111111111111111111110001000001100110100111011011110
 
 　　1010010001111111110010110011101
 
 　　大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hashcode却不能做到，这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。
 
 　　在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明，“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。
 
 　　现在通过这样的转换，我们把库里的文本都转换为simhash 代码，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两simhash的01有多少个不同吗？对的，其实也就是这样，我们通过海明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。
 
 　　simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复，但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果，而simhash对相似的文本的哈希映射结果也相似。
 
 　　http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html
 
 　　http://blog.sina.com.cn/s/blog_81e6c30b0101cpvu.html
 
 　　权重该如何指派呢？我只知道用TF-IDF算法。
 
 三、算法实现
 
 　　谁有容易理解的java或者matlab代码，可以发短消息给我，一起为大家服务。 
 
 四、对比其他去重算法
 
 4.1 百度
 
 　　百度的去重算法最简单，就是直接找出此文章的最长的n句话，做一遍hash签名。n一般取3。 工程实现巨简单，据说准确率和召回率都能到达80%以上。
 
 　　百度的去重算法没有这么傻瓜吧？据一个百度凤巢出来的同事是这么说的。而且我个人觉得简单不等于傻逼。
 
 4.2 shingle算法
 
 　　shingle原理略复杂，不细说。 shingle算法我认为过于学院派，对于工程实现不够友好，速度太慢，基本上无法处理海量数据。
 
 五、问题扩展
 
 　　问题：一个80亿的64-bit指纹组成的集合Q，对于一个给定64-bit的指纹F，如何在a few millionseconds中找到Q中和f至多只有k(k=3)位差别的指纹。
 　　看文献吧。
 
 　　我想的是能否借鉴AC自动机一类的算法，来做匹配，只不过匹配规则是海明距离小于3。我说的是优化后的精确匹配了。
 
 　　http://grunt1223.iteye.com/blog/964564
 
 　　http://blog.csdn.net/lgnlgn/article/details/6008498
 
 　　http://blog.sina.com.cn/s/blog_81e6c30b0101cpvu.html
 
 六、意外收获
 
 　　1.python的计算能力确实很强，float可以表示任意长度的数字，而对应java、c++只能用其他办法来实现了，比如java的BigIneteger,对应的位操作也只能利用类方法。。。汗。。。
 另外说明，位运算只适合整数哦。。。因为浮点的存储方案决定不能位运算，如果非要位运算，就需要Float.floatToIntBits，运算完，再通过Float.intBitsToFloat转化回去。(java默认的float,double的hashcode其实就是对应的floatToIntBits的int值)。
 
 　　2.百度竞价排名系统：凤巢系统
 
 　　3.大神关于就业读研的感触：http://yanyiwu.com/life/2014/10/11/choices-change-my-life.html
 
 七、编者注
 
 　　参考文献是混合交叉的，也就是说，在第1中的参考文献也可能在第2中引用了，但是第2中未作标注。为什么这么些呢？若是以前把所有的参考文献直接放在最后，这样很不方便日后的查找，不过博客园又不想word那样引用方便，所以就取巧了。
 
 　　以后的博文，未作生命的也按词处理。
 
 
 
 
 
 
 
 
 
 LSH local sensitive hash，来自于 mining of massive datasets
 
 包括lsh的详细介绍以及针对不同距离函数的LSH。
 
 
 作用：
 
 
 解决的问题：相似性计算，避免两两计算，提供一组Hash函数，将相似的pair放在一个bucket里面，降低计算规模。
 
 
 约束：
 
 
 Hash函数的要求:
 
 
 1.相似的pair比不相似的paire更容易成为candidate
 
 
 2.识别candidate paire的效率要比从所有pair中识别candidate pair效率高(利用minhash)
 
 
 3.combinable 技术可以更好的降低false positive/negative
 
 
 4.combinable 技术识别candidate pair时间更少
 
 
 Local sensitive hash function: 是一组hash函数F， 如果f(x) = f(y)，说明x,y是candiadte pair。 如果f(x) != f(y)，x，y不是candidate pair。
 
 
 LSH函数集合将原始的特征规模降低为|F|，也就是Hash函数的个数。
 
 
 LSH需要符合如下约束，d是距离度量函数，d1 < d2, p1 > p2：
 
 
 
 
 
 
 if d(x,y) <= d1, p(f(x) = f(y)) >= p1
 
 
 if d(x,y) >= d2, p(fx) = f(y)) <= p2 
 
 
 
 
 
 
 则称为(d1,d2,p1,p2)-sensitive
 
 
 这两个约束说明两个问题：
 
 
 1.如果x,y的距离小于d1, x,y成为candidate pair的概率要最小为 p1,尽量保证距离小的以大概率成为pair。
 
 
 2.如果x,y的距离大于d2，x,y成为candidate pair概率最大伪p2, 保证距离大的以极小的概率成为pair。
 
 
 这就要求，随着距离正大，成为pair的概率要降低，符合常识。
 
 
 我理解d1,d2的约束是为了概念更严格，因为有的时候d1<d2，p1 不一定大于p2(欧氏距离)，加上d1,d2的约束，在dx ~[0,d1], dy~[d2,无穷]这两个集合里，dx < dy，p1>p2一定成立 
 
 
 
 
 
 
 combining tech:
 
 
 LSH提供hash function，保证candidate pair能在一起，而 combine 技术可以更好的延伸这个概念
 
 
 combine技术有两种： and-construct or-constrauct,其实也就是band tech.
 
 
 F为lsh集合， F'是针对F进行combile技术结果：
 
 
 and-construct：将F中r个hash 函数作为一组，保证fi(x)=fi(y), i=1,2...r，也就是r个hash值都相等才算相等，显然限制更加严格 (d1,d2,p1^r, p2^r)   p1^r  < p1，进一步降低candidate pair的个数
 
 
 or-construct :将F中r和hash函数作为一组，保证fi(x)=fi(y)中有一个为真则为真，i=1,2...r，限制变少(d1,d2,1-(1-p1)^r, 1-(1-p2)^r)，也就是(1-p1)^r表示都不想等的概率。
 
 
 两者结合起来，1-(1-p1^r)^m,  r*m=hash函数个数
 
 
 之前的博文中也提到了类这样的技术，min-hash 和banding技术的集合：
 
 
 先利用and-construct，保证只有极其相似hash值相同概率才高，降低candidate pair的规模，然后利用 or-construct技术，保证整体上相似的pair至少在某个band里面成为candidate pair
 
 
 
 
 
 
 整体来讲，LSH 就是基于距离度量函数提供一组hash函数，满足上面提到的约束，保证越相似的pair hash值相同的概率越高，能够成为candidate pair，同一hash值里面的元素少，降低整体的计算规模，同时利用and/or-construct，一方面降低计算规模，另一方面保证lsh的整体召回率，也就是相似pair至少会在某个band里面成为candidate pair。
 
 
 
 
 
 
 LSH for different distance measure:
 
 
 目前的问题是针对不同的距离度量函数，提供不同local sensitive hash函数，符合上面的条件
 
 
 1.jaccard 距离,见 http://blog.csdn.net/hxxiaopei/article/details/7977248
 
 
 jaccard的距离的LSH之前已经说过不再具体介绍，min-hash
 
 
 2.哈明距离
 
 
 计算x,y里面不同bit的个数。
 
 
 这个也很简单，hash函数集合F中，fi(x) = xi即可。
 
 
 其实这个和simhash的后续处理一致
 
 
 3.cosin 相似性
 
 
 jaccard/哈名距离 主要是基于特征字面值进行处理，相等或者不相等。而cosin计算的是夹角，而非计算两个向量里相同元素的个数。
 
 
 比如[1,2,3,4,5][10,20,30,40,50]的cosin值为1，夹角为0。
 
 
 假定d(x,y)表示向量x,y的相似性，对应cos中的夹角theta.
 
 
 LSH函数这样定义：假定x,y的特征维数为N，random的选择K个N维度向量V={v1,v2...vk}
 
 
 定义 d(v1,x)表示v1,x的夹角，基于V，定义LSH集合 F={f1,f2...fk}，其中 fi(x)=sign, sign= {-1,+1}，如果x与vi的夹角>90,sign=-1； 如果x与vi的夹角<=90,则sign = -1;
 
 
 基于F的定义，
 
 
 d(x,y)=0,表示两个x，y相等，则无论V取值如何fi(x) =fi(y)的概率p = 1.
 
 
 d(x,y)=pi/2，表示x,y夹角为90度，则fi(x)=fi(y)的概率为1-pi/(2*pi) = 1-0.5=0.5
 
 
 d(x,y)=pi，表示x,y的夹角为180，则fi(x)=fi(y)的概率为0
 
 
 上面是三个比较特殊的夹角，针对normal的d(x,y)，则有:
 
 
 fi(x)=fi(y)的概率p1= 1-d(x,y)/pi，符合LSH的约束。
 
 
 (d1,d2,1-d1/pi, 1-d2/pi)-sensitive
 
 
 
 
 
 
 每个特征点，经过LSH处理，生成K维的{-1,+1}的向量，利用and-construct or-construct进一步优化即可
 
 
 这里需要考虑的是如何选择K特征向量V，论文提高考虑要服从高斯分布。
 
 
 
 
 
 
 4.欧式距离
 
 
 欧式距离，L2-norm，计算两个点在欧式空间的距离。这个同cosin相似性一样，不能通过字面的相等不相等来计算。
 
 
 比如[1,1,1]、[2,2,2] 的距离小于[1,1,1]、[10,10,10]的距离。
 
 
 假定d(x,y)表示向量x,y的距离，值越大，相似性越低。
 
 
 LSH的定义为：选择一条直线，水平或者垂直方向(针对多维数据，则取相应的直线)，对直线按照宽度为a等分，利用用户在这个维度上的值，计算应该落在那一块,针对LSH 集合F，
 
 
 fi(x) = (xi, a)~xi/a
 
 
 基于F的定义,我们将情况分成2个部分：
 
 
 1,x,y与直线平行：
 
 
      d(x,y)为x,y的距离，d(x,y)< a，fi(x)=fi(y)的概率至少为p=(a-d(x,y))/a = 1 - d(x,y)/a：
 
 
      d=0, 则p = 1
 
 
      d = a/2，则p=0.5
 
 
      p= 0.1a, 则 p = 0.9
 
 
      p = a, 则p = 0
 
 
 2.x,y与直线有夹角theta
 
 
      如果d > a时，是有可能落在同一bucket中，比如下图的y,m。
 
 
      
 
 
      根据cos法则，落在水平直线上的距离为d*cos(theta)，如果距离刚好是a，可以计算出theta,则落在一个bucket的概率最多为1-theta/90，如果d*cos(theta)<a，则theta变大，概率变低。随着d的变大，概率降低
 
 
      如果d=2a，则theta=60,p=1/3
 
 
      如果d=sqrt(a)，则theta=45,p=1/2
 
 
     
 
 
  则为(a/2, 2a, 1/2,1/3)-sensitive,符合d1>d2, p2< p1的约束。
 
 
 解释一下，如果距离小于a/2，至少以p=1/2的概率落在一起，如果d变小，落在一个bucket的概率曾江；如果d>2a，则最多1/3的概率落在一起，如果d变大，摞在一起的概率一定降低    
 
 
  这说明一个事情，d1<d2,则p1>p2的成立条件是[0,d1][d2,~]，大多数情况下(jaccard,hamming,cos)，如果d1<d2,则p1>p2对任何d1<d2关系都成立。但是在欧式距离不一定。这是因为LSH F集合导致的。
 
 
 
 
 
 
 不过在实际使用中，我们定义LSH 集合F，F = {f1,f2....fk}，fi(x)为x的第i维在对应直线上的bucke id，具体a的大小 依赖于业务，如果d一定，那么越大，落在一起的概率就越高，无论d1还是d2
 
 
 
 
 
 
 如果d(x,y) < d~a/2，则fi(x)=fi(y)的概率p=(a-d)/a = 0.5
 
 
 |
 
 
 |                                                                           
 
 
 |                                                                  m.       z.
 
 
 |
 
 
 |
 
 
 |                                                            x. y.
 
 
 |
 
 
 

  |
 
 
 

  |
 
 
 

  |
 
 
 

  |
 
 
 

  |
 
 
 
 
 |--------------|--------------|--------------|--------------|--------------|--------------|--------------|
 

 
 
 

 
 
 
 
  
 两点之间的距离可以用两种方式来衡量，一是几何距离，二是非几何距离。很显然距离的定义满足下面的条件：
 
  
 d(x,y) > 0.
 d(x,y) = 0 iff x = y.
 d(x,y) = d(y,x).
 d(x,y) < d(x,z) + d(z,y)
 
  
 几何距离包括：
 
  
 L2 norm : d(x,y) 是平方和的开方
 L1 norm : d(x,y) 是每个维度的距离之和
 L∞ norm : d(x,y) 是x和y在每个维度上距离的最大值
 
  
 非几何距离用的就比较多了：
 
  
 Jaccard距离：1减去Jaccad相似度
 余弦距离：两个向量之间的角度
 编辑距离（Edit distance）：将一个串变为另一个串需要的插入或删除次数
 海明距离（Hamming Distance）：Bit向量中不同位置的个数
 
  
 这里有一个重要的公理：三角形公理（Triangle Inequality），也就是距离的第四个性质。编辑距离d(x,y) = |x| + |y| – 2|LCS(x,y)|，其中LCS是longest common subsequence，最长公共子序列。
 
  
 LSH的一个核心思想就是两个元素哈希值相等的概率等于两个元素之间的相似度。
 
  
 下面介绍一个重要概念：Hash Family，哈希家族？不管怎么翻译，它指的是能够判断两个元素是否相等（h(x) = h(y) ）的Hash函数集合。LS Hash Family，局部敏感哈希家族的定义是满足下面两个条件的哈希函数家族：
 
  
 如果d(x,y) < d1，那么哈希家族H中的哈希函数h满足h(x) = h(y)的概率至少是p1.
 如果d(x,y) > d2，那么哈希家族H中的哈希函数h满足h(x) = h(y)的概率至多是p2.
 
  
 就是如果x和y离得越近，Pr[h(p)=h(q)]就越大。如果x和y离得越远，Pr[h(p)=h(q)]就越小。我们把局部敏感哈希家族记为(d1,d2,p1,p2)-sensitive。那什么样的函数满足呢？Jaccard就是。我们令S为一个集合，d是Jaccard距离，有Prob[h(x)=h(y)] = 1-d(x,y)，我们就可以得到一个局部敏感哈希家族：a(1/3, 2/3, 2/3, 1/3)-sensitive。事实上，只要满足d1<d2，就可以得到一个局部敏感的哈希家族：(d1,d2,(1-d1),(1-d2))-sensitive。
 
  
 (d1,d2,p1,p2)-sensitive将整个概率空间分成了三部分：<p1，p1-p2，>p2。为了有更好的区分度，我们想让p1-p2的空间尽可能小，让d2-d1尽可能大。选择合适的参数，能够有类似于下面的S曲线应该就是不错的了。可如何来做呢？
 
  
 
 
  
 定义两种哈希函数的操作：AND和OR。
 
  
 AND操作：在局部敏感哈希家族H中选出r个哈希哈数，构成哈希家族H’。对于H’家族中的h = [h1,…,hr]，h(x)=h(y)当且仅当对所有的i，所有hi(x)=hi(y)都满足。这样得到的H’同样也是一个局部敏感哈希家族。并且若源哈希家族是(d1,d2,p1,p2)-sensitive，新哈希家族H’是(d1,d2,(p1)^r,(p2)^r)-sensitive。
 
  
 OR操作：在局部敏感哈希家族H中选出b个哈希哈数，构成哈希家族H’。对于H’家族中的h = [h1,…,hb]，h(x)=h(y)当且仅当存在i，满足hi(x)=hi(y)。这样得到的H’同样也是一个局部敏感哈希家族。并且若源哈希家族是(d1,d2,p1,p2)-sensitive，新哈希家族H’是(d1,d2,1-(1-p1)^b,1-(1-p2)^b)-sensitive。
 
  
 可以看出AND操作是降低了概率，但如果选取一个合适的r，可以使下限概率接近0，而上限概率没有多大影响。类似的，OR操作是增加了概率，但如果选择一个合适的d，可以使上限概率接近1，而下限概率没有多大影响。
 
  
 我们对AND操作和OR操作做级联：
 
  
 AND-OR，1-(1-p^r)^b
 
  
 OR-AND，(1-(1-p)^b)^r
 
  
 举个例子，1-(1-p^4)^4，当p取不同值时：
 
  
 p
 1-(1-p4)4
 .2
 .0064
 .3
 .0320
 .4
 .0985
 .5
 .2275
 .6
 .4260
 .7
 .6666
 .8
 .8785
 .9
 .9860
 
  
 (1-(1-p)^4)^4，当p取不同值时：
 
  
 
p
 
 
(1-(1-p)4)4
 
 
.1
 
 
.0140
 
 
.2
 
 
.1215
 
 
.3
 
 
.3334
 
 
.4
 
 
.5740
 
 
.5
 
 
.7725
 
 
.6
 
 
.9015
 
 
.7
 
 
.9680
 
 
.8
 
 
.9936
 
 
  
 得到这样的S曲线之后，可以找到一个点t，满足1-(1-t^r)^b = t。在t点之后，概率快速上升，在t点之前，概率快速下降。根据需要的灵敏度，可以选择合适的上限概率和下限概率来满足应用需求。
 
  
 
 
  
 参考上图，如果我们要返回距离中心为r的点，LSH会返回给我们范围更远、更多的点，也就是说，LSH返回的结果会带有一定的false positive。我们或许需要使用linear search进行二次筛选，但这毕竟大大减少了计算的时间。
 
  
 由此可见，LSH与一般的加密型哈希函数有很大的区别，参见下图：
 
  
 
 
  
 一种实现(LSH)的最简单的方式是采用random bits sampling的方式，即将待索引的多维整型向量转化为0或1的字符串；再采用随机选取其中的K位拼接成新的字符串；最后再采用常规的哈希函数（例如MD5）等算法获取带索引向量的LSH Code。这样的Hash Code有一个特点，就是Hamming Distance相近的两个向量，其冲突的概率越大，即结果相等的可能性越大。为了减少增强KNN搜索的能力，与Bloom Filter类似，采用多个Hash Table增加冲突的概率，参见下图：
 
  
 
 
  
 来看一下LSH的复杂度：
 
  
 
 
  
 可见，与各种其它的数据结构相比，基于lsh的索引结构的query时间复杂度，可以做到与向量维度无关，有效地克服了维度灾难的问题，因此更适合高维向量的索引。
 
  
 基于LSH实现的图像近似检索，其原理也很类似，如下图所示：
 
 
  
 
 
 
 This entry was posted in 
 Computing, 
 Theories and tagged 
 Big Data, 
 LSH by 
 Jason KIM. Bookmark the
 permalink. 
 
 Related Posts
 
 

  
 
 
 
 

  
 
 
 
 
 
  
 二.simHash算法简介
 
  
 　　以前写的一个介绍simHash的。
 
  
 　　1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
 
  
 　　2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
 
  
 　　3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
 
  
 　　4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
 
  
 　　5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。
 
  
 三.算法几何意义及原理
 
  
 3.1 几何意义
 
  
 　　这个算法的几何意义非常明了。它首先将每一个特征映射为f维空间的一个向量，这个映射规则具体是怎样并不重要，只要对很多不同的特征来说，它们对所对应的向量是均匀随机分布的，并且对相同的特征来说对应的向量是唯一的就行。比如一个特征的4位hash签名的二进制表示为1010，那么这个特征对应的 4维向量就是(1, -1, 1, -1)T，即hash签名的某一位为1，映射到的向量的对应位就为1，否则为-1。然后，将一个文档中所包含的各个特征对应的向量加权求和，加权的系数等于该特征的权重。得到的和向量即表征了这个文档，我们可以用向量之间的夹角来衡量对应文档之间的相似度。最后，为了得到一个f位的签名，需要进一步将其压缩，如果和向量的某一维大于0，则最终签名的对应位为1，否则为0。这样的压缩相当于只留下了和向量所在的象限这个信息，而64位的签名可以表示多达264个象限，因此只保存所在象限的信息也足够表征一个文档了。
 
  
 3.2 算法原理描述性证明
 
  
 　　明确了算法了几何意义，使这个算法直观上看来是合理的。但是，为何最终得到的签名相近的程度，可以衡量原始文档的相似程度呢？这需要一个清晰的思路和证明。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明，以下列出我自己得出的证明思路。
 　　Simhash是由随机超平面hash算法演变而来的，随机超平面hash算法非常简单，对于一个n维向量v，要得到一个f位的签名(f<<n)，算法如下：
 　　1，随机产生f个n维的向量r1,…rf；
 　　2，对每一个向量ri，如果v与ri的点积大于0，则最终签名的第i位为1，否则为0.
 　　这个算法相当于随机产生了f个n维超平面，每个超平面将向量v所在的空间一分为二，v在这个超平面上方则得到一个1，否则得到一个0，然后将得到的 f个0或1组合起来成为一个f维的签名。如果两个向量u, v的夹角为θ，则一个随机超平面将它们分开的概率为θ/π，因此u, v的签名的对应位不同的概率等于θ/π。所以，我们可以用两个向量的签名的不同的对应位的数量，即汉明距离，来衡量这两个向量的差异程度。
 　　Simhash算法与随机超平面hash是怎么联系起来的呢？在simhash算法中，并没有直接产生用于分割空间的随机向量，而是间接产生的：第 k个特征的hash签名的第i位拿出来，如果为0，则改为-1，如果为1则不变，作为第i个随机向量的第k维。由于hash签名是f位的，因此这样能产生 f个随机向量，对应f个随机超平面。下面举个例子：
 　　假设用5个特征w1,…,w5来表示所有文档，现要得到任意文档的一个3维签名。假设这5个特征对应的3维向量分别为：
 　　h(w1) = (1, -1, 1)T
 　　h(w2) = (-1, 1, 1)T
 　　h(w3) = (1, -1, -1)T
 　　h(w4) = (-1, -1, 1)T
 　　h(w5) = (1, 1, -1)T
 　　按simhash算法，要得到一个文档向量d=(w1=1, w2=2, w3=0, w4=3, w5=0) T的签名，
 先要计算向量m = 1*h(w1) + 2*h(w2) + 0*h(w3) + 3*h(w4) + 0*h(w5) = (-4, -2, 6) T，然后根据simhash算法的步骤3，得到最终的签名s=001。上面的计算步骤其实相当于，先得到3个5维的向量，第1个向量由h(w1),…,h(w5)的第1维组成：r1=(1,-1,1,-1,1) T；第2个5维向量由h(w1),…,h(w5)的第2维组成：r2=(-1,1,-1,-1,1) T；同理，第3个5维向量为：r3=(1,1,-1,1,-1) T.按随机超平面算法的步骤2，分别求向量d与r1,r2,r3的点积:
 
  
 　　d T r1=-4 < 0，所以s1=0;
 　　d T r2=-2 < 0，所以s2=0;
 　　d T r3=6 > 0，所以s3=1.
 　　故最终的签名s=001，与simhash算法产生的结果是一致的。
 　　从上面的计算过程可以看出，simhash算法其实与随机超平面hash算法是相同的，simhash算法得到的两个签名的汉明距离，可以用来衡量原始向量的夹角。这其实是一种降维技术，将高维的向量用较低维度的签名来表征。衡量两个内容相似度，需要计算汉明距离，这对给定签名查找相似内容的应用来说带来了一些计算上的困难；我想，是否存在更为理想的simhash算法，原始内容的差异度，可以直接由签名值的代数差来表示呢？
 
  
 
 
 
  
 
 
 
  
 
 
  
 请先阅读有关图的基本知识，图的拉普拉斯矩阵分析以及谱聚类相关内容，谱哈希基于上述技术基础。
 
  
  
 
  
             谱哈希对图像特征向量的编码过程可看做是图分割问题，借助于对相似图的拉普拉斯矩阵特征值和特征向量的分析可对图分割问题提供一个松弛解。由谱聚类可知，相似图拉普拉斯矩阵的特征向量实际上就是原始特征降维后的向量，但其并不是0-1的二值向量，可通过对特征向量进行阈值化产生spectral hashing的二值编码(The bits in spectral hashing are calculated by thresholding a subset of eigenvectors of Laplacians of the similar graph).
 
  
   
  
 若原始特征向量空间用高斯核度量相似度 ，则令 为二值化后的特征向量矩阵即经Spectral Hashing后的二值特征向量，则在低维Hamming空间的平均Hamming距离可表示为。此外，What makes good code?
 
 
  
 (1) each bit has 50% chance of being 0 or 1;
 
  
 (2) the bits are independent of each other(always relaxed to uncorrelated).
 
  
  
 
  
 因此，spectral hashing的编码过程可描述为下述的优化问题(为了求解问题的方便，将二值中的0表示为-1)：
 
  
 
 
  
 
 
  
                     
 
  
                     
 
  
  
 
  
 用Spectral 理论描述为：
 
  
 
 
  
 
 
  
                      
 
  
                      
 
  
 若没有二值的约束 ，则上述优化问题就简化为 是拉普拉斯矩阵的个最小特征值所对应的特征向量构成的矩阵，通过简单的Thresholding可获取Binary Code。
 
  
  
 
  
 但上述的编码过程仅适用于训练集，而我们需要的是能够泛化到任意给定的out-of-example特征向量，因此引入来描述原始特征空间中数据点的概率分布，则上述的优化问题可表述为：
 
  
  
 
 
  
                      
 
  
                      
 当暂不考虑二值化约束时，上述优化问题的解即是eigenfunctions of weighted Laplace-Beltramician operactor  with  minimal eigenvalue. And with proper normalization, the eigenvectors of the discrete Laplacian defined by  points sampled from  coverges to eigenfunctions of  as .
 
  
  
 
  
 因此，就转化为如何利用服从分布的个离散的数据点求取 的特征方程的问题：
 
  
 当是separable distribution时，即，亦即各维之间相互独立时， 的特征方程具有outer product 形式：
 
  
 即若 是特征值对应的一维空间 的特征方程，则 是特征值 对应的维空间的特征方程。特别的，针对 区间内均匀可分离的分布，一维空间的特征值和特征向量可通过下式求得：
 
  
                                 ----------function (1)
 
  
 ，    ----------function (2)
 
 
  
  
 
  
 Summarize the spectral hashing alogrithm:
 
  
 Input:  data points  and the hashed bits 
 
  
Finding the  principal components of the data using PCA;
Calculating the  smallest single-dimension analytical eigenfunctions of   along every PCA direction. This is done by evaluating the  smallest eigenvalues for each direction using function (2), thus creating a list of  eigenvalues, and then sorting this list to find the  smallest eigenvalues; ???
Thresholding the analytical eigenfunctions at zero, to obtain binary codes.
 
  
 分析:
 
  
 Step1中PCA的主要作用是align the axes for data points, 也就是使数据点各维之间相互独立，符合seperate distribution;
 
  
 Step2个人理解应该是先求取维数据点每一维 均匀分布区间，然后利用方程(2)求取每一维对应的最小的个特征值，因此总计有个特征值。然后在个特征值中选取最小的个，并记录其所对应的向量维度及其特征值序号，即 对；针对选取的各最小特征值，计算其对应的一维特征方程 。
 
  
 Step3是采用符号函数，对选取的特征方程进行二值化，产生二值码 
 
 
  
            由此可见，对图的次分割，每次都是选取维空间的某一维，并没有利用特征方程的outer-product的特性，paper 中的解释是二值化编码采用的是符号函数，且，因此一个bit的取值可由其它bits确定，失了去独立性。但其前提是建立在每一个bit对应的特征方程是由其它bits对应特征方程的outer-product，若bits之间不包含相同的特征方程，则还会继续保留各bits之间的独立性。因此outer-product的特征方程应该也可以利用。这仅是个人理解，具体效果还有待验证。
 
  
 训练集的作用主要是产生每维对应的分布区间，利用记录的个最小特征值对应的维度与特征值序号对 扩展至out-of-example。