一、概念

什么是泛型？

泛型：就是一种不确定的数据类型，需要在使用这个类的时候才能够确定出来。

比如：ArrayList<E> E就是泛型

泛型只在编译阶段有效。在编译过程中，正确检验泛型结果后，会将泛型的相关信息擦除，并且在对象进入和离开方法的边界处添加类型检查和类型转换的方法。把运行时的问题提前到编译时期。

什么是接口？

接口(interface)是抽象方法和常量值的定义的集合。

从本质上讲，接口是一种特殊的抽象类，这种抽象类中只包含常量和方法的定义，而没有变量和方法的实现。

如果一个类中，既有抽象方法，又有非抽象方法，那么该类只能定义为抽象类，不能定义为接口

接口中所有的方法，都是抽象方法，接口就是一个特殊的抽象类，方法和属性默认都是public修饰，也可以使用protected，但不能用private。所有的属性都是静态的常量，默认省略了static和final修饰符，属性的值必须实例化（初始化）。

案例 : 蝙蝠会飞,又会用牙齿咬

首先定义一个飞行的接口：

public interface Flyable {
    public final int wingsNumber = 2;
    public abstract void fly();
}

接着定义一个咬人的接口：

public interface Bitable {
    public int teethNumber = 0;
    public abstract void bite();
}

最后定义蝙蝠类去实现这两个接口：

public class Bat implements Flyable,Bitable {
    @Override
    public void bite() {
        System.out.println("吸血");
    }

    @Override
    public void fly() {
        System.out.println("用翅膀飞");
    }

    public static void main(String[] args) {
        System.out.println(Flyable.wingsNumber);
    }
}

在JAVA中，一个类无法继承自多个类，但是可以实现多个接口，使用关键字implements 多个接口之间使用逗号隔开，所继承的多个接口之间，没有先后顺序。这个类叫做实现类，这个类必须实现所有接口的所有方法。

此外，接口还常常被用来当做定义常量的集合：

public interface Power {
    int vol = 220;
    double hz = 50.0;
}

接口的特点

用 interface 来定义。
接口中的所有成员变量都默认是由public static final修饰的。
接口中的所有方法都默认是由public abstract修饰的。
接口没有构造方法，构造方法用于创建对象
实现接口的类中必须提供接口中所有方法的具体实现内容。
多个无关的类可以实现同一个接口
一个类可以实现多个无关的接口
与继承关系类似，接口与实现类之间存在多态性
接口也可以继承另一个接口，使用extends关键字。
如果实现接口的类中没有实现接口中的全部方法，必须将此类定义为抽象类。
定义Java类的语法格式：

< modifier> class < name> [extends < superclass>] [implements < interface>[,<interface>]*{
    < declarations>*
}

什么是集合类？

用来更加灵活地存储对象，可以将任意数量的对象放置到容器中，并且不需要担心容器应该设置为多大。其中基本的类型是List、Set、Queue和Map。这些对象类型也称为集合类。

什么是容器？

解释一：
容器（Container）
Spring 提供容器功能，容器可以管理对象的生命周期、对象与对象之间的依赖关系，您可以使用一个配置文件（通常是XML），在上面定义好对象的名称、如何产生（Prototype 方式或Singleton 方式）、哪个对象产生之后必须设定成为某个对象的属性等，在启动容器之后，所有的对象都可以直接取用，不用编写任何一行程序代码来产生对象，或是建立对象与对象之间的依赖关系。
换个更直白点的说明方式：容器是一个Java 所编写的程序，原先必须自行编写程序以管理对象关系，现在容器都会自动帮您作好。
常用容器：WebSphere，WebLogic，Resin，Tomcat

解释二：
容器类

对于这些集合类，由于Java的类库中使用了Collection这个名字来指代类库中的一个特殊子集。所以（《Java编程思想》中使用范围更广的术语"容器类"（容器）称呼它们，它们可以自动调整自己的尺寸。

==所以终于，我明白了俗称“集合类”“容器类”其实都是指这同一套工具类。==

二、 java 泛型

泛型有三种使用方式，分别为：泛型类、泛型接口、泛型方法

1. 泛型类

泛型类型用于类的定义中，被称为泛型类。通过泛型可以完成对一组类的操作对外开放相同的接口。最典型的就是各种容器类，如：List、Set、Map。

一个最普通的泛型类 :

//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic<T>{ 
    //key这个成员变量的类型为T,T的类型由外部指定  
    private T key;

    public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
        this.key = key;
    }

    public T getKey(){ //泛型方法getKey的返回值类型为T，T的类型由外部指定
        return key;
    }
}

我们知道List是一个容器，它就是使用了泛型，我们才可以用List来存储任何一种数据类型:

public interface List<E> extends Collection<E> {
    public boolean add(E object);
    public boolean addAll(Collection<? extends E> collection);
    public E get(int location);
}

2. 泛型接口

3. 泛型方法

1. 使用场景

我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)，那么我们就可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现Comparator接口即可。也就是说，我们可以通过实现Comparator来新建一个比较器，然后通过这个比较器对类进行排序。

2. 应用实例

三、 java 容器

1. 容器工具包框架

通过上图，可以把握两个基本主体，即Collection和Map。

Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。Collection包含了List和Set两大分支。

List是一个有序的队列，每一个元素都有它的索引。第一个元素的索引值是0。List的实现类有LinkedList, ArrayList, Vector, Stack；
Set是一个不允许有重复元素的集合。 Set的实现类有HastSet和TreeSet。HashSet依赖于HashMap，它实际上是通过HashMap实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。
Map是一个映射接口，即key-value键值对。Map中的每一个元素包含“一个key”和“key对应的value”。

AbstractMap是个抽象类，它实现了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是继承于AbstractMap。
Hashtable虽然继承于Dictionary，但它实现了Map接口。
Iterator是遍历集合的工具，即我们通常通过Iterator迭代器来遍历集合。我们说Collection依赖于Iterator，是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象。ListIterator是专门为遍历List而存在的。
Enumeration是JDK 1.0引入的抽象类。作用和Iterator一样，也是遍历集合；但是Enumeration的功能要比Iterator少。在上面的框图中，Enumeration只能在Hashtable, Vector, Stack中使用。
Arrays和Collections是操作数组、集合的两个工具类。

有了上面的整体框架之后，我们接下来对每个类分别进行分析。

2. Collection接口

Collection的定义如下：

public interface Collection<E> extends Iterable<E> {}

它是一个接口，是高度抽象出来的集合，它包含了集合的基本操作：添加、删除、清空、遍历(读取)、是否为空、获取大小、是否保护某元素等等。

【在Java中所有实现了Collection接口的类都必须提供两套标准的构造函数，一个是无参，用于创建一个空的Collection，一个是带有Collection参数的有参构造函数，用于创建一个新的Collection，这个新的Collection与传入进来的Collection具备相同的元素。后一个构造函数允许用户复制一个Collection。】

Collection接口中定义的抽象函数：

abstract boolean         add(E object)
abstract boolean         addAll(Collection<? extends E> collection)
abstract void            clear()
abstract boolean         contains(Object object)
abstract boolean         containsAll(Collection<?> collection)
abstract boolean         equals(Object object)
abstract int             hashCode()
abstract boolean         isEmpty()
abstract Iterator<E>     iterator()
abstract boolean         remove(Object object)
abstract boolean         removeAll(Collection<?> collection)
abstract boolean         retainAll(Collection<?> collection)
abstract int             size()
abstract <T> T[]         toArray(T[] array)
abstract Object[]        toArray()

3. List接口

List的定义如下：

public interface List<E> extends Collection<E> {}

List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允许有重复的元素。

官方文档：A List is a collection which maintains an ordering for its elements. Every element in the List has an index. Each element can thus be accessed by its index, with the first index being zero. Normally, Lists allow duplicate elements, as compared to Sets, where elements have to be unique.

关于API方面。既然List是继承于Collection接口，它自然就包含了Collection中的全部函数接口；由于List是有序队列，它也额外的有自己的API接口。主要有“添加、删除、获取、修改指定位置的元素”、“获取List中的子队列”等。

// Collection的API
abstract boolean         add(E object)
abstract boolean         addAll(Collection<? extends E> collection)
abstract void            clear()
abstract boolean         contains(Object object)
abstract boolean         containsAll(Collection<?> collection)
abstract boolean         equals(Object object)
abstract int             hashCode()
abstract boolean         isEmpty()
abstract Iterator<E>     iterator()
abstract boolean         remove(Object object)
abstract boolean         removeAll(Collection<?> collection)
abstract boolean         retainAll(Collection<?> collection)
abstract int             size()
abstract <T> T[]         toArray(T[] array)
abstract Object[]        toArray()
// 相比与Collection，List新增的API：
abstract void                add(int location, E object)
abstract boolean             addAll(int location, Collection<? extends E> collection)
abstract E                   get(int location)
abstract int                 indexOf(Object object)
abstract int                 lastIndexOf(Object object) 
                            //如果列表含有该对象，则返回它在列表中最后一次出现的索引，否则返回-1
abstract ListIterator<E>     listIterator(int location) 
                            //返回一个列表迭代器，从location开始
abstract ListIterator<E>     listIterator()
abstract E                   remove(int location)
                                //删除index处的元素，将后继元素全部左移，返回被删除的元素
abstract E                   set(int location, E object)
abstract List<E>             subList(int start, int end)

实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

(1) ArrayList

四、工具类

1. Arrays

Arrays.sort()

JDK 1.8 java.util.Arrays.class(rt.jar)

Collections.sort方法底层就是调用的Arrays.sort方法。
Java Arrays中提供了对所有类型的排序。其中主要分为Primitive(8种基本类型)和Object两大类。

　　基本类型：插入排序、调优的快速排序和归并排序相结合的排序方法
　　对象类型：改进的归并排序和插入排序相结合的方法

　　以int[]数组为例：<47 插入排序；>=47 && <286 快排； >286 归并排序。

双轴快排：

　　快速排序使用的是分治思想，将原问题分成若干个子问题进行递归解决。选择一个元素作为轴(pivot)，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比轴元素小，另外一部分的所有数据都比轴元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
　　双轴快排(DualPivotQuicksort) 顾名思义有两个轴元素pivot1，pivot2，且pivot ≤ pivot2，将序列分成三段：x < pivot1、pivot1 ≤ x ≤ pivot2、x >pivot2，然后分别对三段进行递归。这个算法通常会比传统的快排效率更高，也因此被作为Arrays.java中给基本类型的数据排序的具体实现。

Arrays.sort对升序数组、降序数组和重复数组的排序效率有了很大的提升，这里面有几个重大的优化。

对于小数组来说，插入排序效率更高，每次递归到小于47的大小时，用插入排序代替快排，明显提升性能。
双轴快排使用两个pivot，每轮把数组分成3段，在没有明显增加比较次数的情况下巧妙地减少了递归次数。
pivot的选择上增加了随机性，却没有带来随机数的开销。
对重复数据进行了优化处理，避免了不必要交换和递归。

==自定义Compare函数实现降序排序（使用匿名内部类）==

Arrays.sort(int[] a, Comparator<Integer>() {
    public int compare(int a, int b){
         return a - b;   升序
        // return b - a;   降序
        /* a-b>0 交换ab位置，反之不变， 即返回值为正数时，交换数组中正在比较
        的两个元素的位置，返回值为负数时，不交换。 记住第一个参数去比较第二个
        参数就是升序，第二个参数比较第一个参数就是降序就OK了。
        */
    }
})

==给多维数组排序==

利用第二维中的第6个元素的大小关系，给第一维排序

Arrays.sort(a, new Comparator<int[]>()
{
        @Override
        public int compare(int[] o1, int[] o2) {
        // TODO Auto-generated method stub
            return o1[5]-o2[5];
        }
});

先按照第2个元素的降序排列，当第2个元素相等，就按第一个的升序

Arrays.sort(a, new Comparator<int[]>()
{
    @Override
    public int compare(int[] o1, int[] o2) {
        // TODO Auto-generated method stub
        if(o1[1]==o2[1]) return o1[0]-o2[0];//升序
        else return o2[1]-o1[1];//降序
    }
});

lambda

Arrays.sort(nums, (event1, event2) -> {
            return event1[1] == event2[1] ? event1[0]-event2[0] : event1[1]-event2[1];
});

更简洁的lambda

 Arrays.sort(nums, (o1, o2) -> o1[1] - o2[1]);

在题目中用到，根据 edges[i] [0] 排序 edges：

Arrays.sort(edges, (a, b) -> Integer.compare(b[0], a[0]));
//由于是integer也可以写成
Arrays.sort(edges, (a, b) -> b[0]-a[0]);

lambda形式真是美，以后要好好用，同时把注释写好。

java 泛型 & 接口

一、 概念