什么是队列？

先进者先出，这就是典型的 “队列”（Queue）

栈只支持两个基本操作：入栈 push（） 和出栈 pop（）。队列和栈非常相似，支持的操作也有限，最基本的操作也是两个：入队 enqueue（） 放一个数据到队列尾部；出队 dequeue（），从队列头部取一个元素。所以，队列和栈一样，也是一种操作受限的线性表数据结构。

队列数组实现

跟栈一样，可以用是数组实现也可以用链表实现，用数组实现的栈叫做顺序栈，用链表实现的栈叫做链式栈。同样的，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果 tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

对于栈来说一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

• 调用出队操作时，head 指针会往后移，tail 指针指向不变。
• 调用入队操作时，tail 指针会往后移，head 指针指向不变。

当 tail 指针移到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。

可以用数据搬移来解决这个问题，每次进行出队操作时都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。

实际上，在每次出队操作时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据搬移操作。借助这个**，出队函数 dequeue（）保持不变，修改入队方法 enqueue 的实现：

   // 入队操作，将 item 放入队尾
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

队列单链表实现

省略

队列循环链表实现

主要解决数据搬移问题、省略

线程池工作原理

当向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？

一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。

如何处理排队请求？按照公平性原则，先进者先服务，所以队列这种数据结构很适合来存储排队请求。那么用哪种队列的实现方式来处理呢？数组还是链表？两种实现方式又各有什么不同？

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以针对响应时间比较铭感的系统，基于链表实现的无限排队的线程池是不合适的。

而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池排队的请求超过队列大小时，接下来的请求就会被拒绝没这种方式对于响应时间铭感的系统来说，就相对更加合理。不过设置一个合理的队列大小，也是非常讲究的，过大导致等待请求太多，过小导致无法充分利用系统资源，发挥最大性能。

问题

1. 除了线程池会用到队列排队请求，还有哪些类似的池结构或者场景中会用到队列的排队请求？

Java IO 包中还提供了很多关于操作流的对象，如果需要将各种形式的流数据打印，则需要用到打印流。如果输入的数据流有多个，可以使用合并流，合并后统一操作。如果需要将对象流化，则需要用到专门操作对象的流对象，等等场景。

打印流（PrintStream、PrintWriter）

两者都可以直接操作输入流和文件，且都可以指定编码，是否自动刷新。PrintWriter 类常用于 Web 开发。

PrintStream 类除了提供写字节操作以外，还提供了各种打印方法如下，此类打印方法能够将是数据类型完整地打印出去，如 print(int i) 打印的是 4 个字节的数据，而不是 write(int i) 方法，每次都只写出 1 个字节。

void print(boolean b) 
void print(char c) 
void print(char[] s) 
void print(double d) 
void print(float f) 
void print(int i) 
void print(long l) 
void print(Object obj) 
void print(String s) 

其构造方法可接受参数很多如下，且三种构造函数都能指定字符集。默认自带缓冲区，每次写出得刷新才能生效。也可以在构造函数中指定自动刷新。

PrintStream(File file)  
PrintStream(OutputStream out) 
PrintStream(String fileName) 

序列流（SequenceInputStream）

当输入的数据源有多个时，可以使用 SequenceInputStream 对多个输入流进行合并，方便统一操作

Vector<FileInputStream> v = new Vector<FileInputStream>();
v.add(new FileInputStream("c:\\1.txt"));
v.add(new FileInputStream("c:\\2.txt"));
v.add(new FileInputStream("c:\\3.txt"));
SequenceInputStream sis = new SequenceInputStream(v.elements());
FileOutputStream fos = new FileOutputStream("c:\\4.txt");
byte[] buf = new byte[1024];
int len =0;
while ((len=sis.read(buf))!=-1) {
  fos.write(buf,0,len);
}
// .close()

操作对象

ObjectInputStream 与 ObjectOutputStream
被操作的对象需要实现 Serializable （标记接口)

操作基本数据类型

DataInputStream 与 DataOutputStream

操作字节数组

ByteArrayInputStream 与 ByteArrayOutputStream

操作字符数组

CharArrayReader 与 CharArrayWrite

操作字符串

StringReader 与 StringWriter

什么是递归？

递归（Recursive）是一种非常广泛的算法。包含是递归的是算法和数据结构，DFS 深度优先搜索、前后中序二叉树遍历等等。

递归使用场景

1. 一个问题的解可以分为几个子问题的解
2. 此问题与分解之后的子问题，除数据规模之外，思路一致
3. 存在递归终止条件

递归关键 写出递推公式，找到终止条件，

青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路：
如果有一级台阶，则只有一种跳法（1）；
如果有两级台阶，则有两种跳法：（1，1；2）；
如果有三级台阶，则有三种跳法:（1，1，1；1，2；2，1）；
如果有四级台阶，则有五种跳法：（1，1，1，1；1，1，2；1，2，1；2，1，1；2，2；）......
依次类推可以发现如下规律：当 n=1，f（n）=1；当 n=2，f（n）=2；当 n>=3，f（n）=f（n-1）+f（n-2）

思路：先举几个例子，找出 f(n) 的规律，再处理一下边界条件

递归常见问题及解决方案

1. 警惕堆栈溢出：重点是边界条件的检查
2. 警惕重复计算（台阶问题，如果n=5，那么 f(3) 就会被计算两次）：保存结果集，计算过的直接走缓存

字符流：FileWriter 类

用来写入字符文件的便捷类。此类的构造方法假定默认字符编码和默认字节缓冲区大小都是可接受的。要自己指定这些值，可以先在 FileOutputStream 上构造一个 OutputStreamWriter。

文件是否可用或是否可以被创建取决于底层平台。特别是某些平台一次只允许一个 FileWriter（或其他文件写入对象）打开文件进行写入。在这种情况下，如果所涉及的文件已经打开，则此类中的构造方法将失败。

FileWriter 用于写入字符流。要写入原始字节流，请考虑使用 FileOutputStream。

创建一个 FileWriter，用如下方式，假设文件不存在，则会被创建，若文件存在则会被覆盖。当文件文件位不存在的文件夹或者盘符下，该方法会抛出 FileNotFoundException。

FileWriter writer = new FileWriter("D:\\demo.txt");

若文件不想被覆盖，则使用如下构造方法：指定追加模式为 true。此时当文件存在时，写操作会在文件末尾追加内容。

FileWriter writer = new FileWriter("D:\\demo.txt", true);

基本的使用方法如下，需要注意的是，调用 write 方法之后并不会直接将文本内容写入磁盘，会先在内存中滞留，当调用 flush 方法后，才会将内容刷入磁盘。此处能写入磁盘，是因为在 close 方法中，会先调用一次 flush 方法。 关闭流的操作需要在 finnaly 代码块中，且需要判断对象是否为 null，以免出现 NPE。

FileWriter fw = null;
try {
    fw = new FileWriter("D:\\demo.txt");
    fw.write("text");
} catch (IOException e) {
    e.printStackTrace();
} finally{
    if (fw!=null) {
        try {
            fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

若想写入换行符，Windows 下用 "\r\n"，Linux 下用 "\n"。使换行具有跨平台性方法很多，这里讲两种，一是使用 BufferWriter 类 newLine() 方法；二是使用 JDK 封装好的换行写入方法，如 PrintWriter 类的 println 方法。

// 法一（省略 flush 操作）
new BufferWriter(new FileWriter("D:\\demo.txt")).newLine();
// 法二（省略 flush 操作）
new PrintWriter("D:\\demo.txt").println("text");

字符流：FileReader 类

用来读取字符文件的便捷类。此类的构造方法假定默认字符编码和默认字节缓冲区大小都是适当的。要自己指定这些值，可以先在 FileInputStream 上构造一个 InputStreamReader。

FileReader 用于读取字符流。要读取原始字节流，请考虑使用 FileInputStream。

创建一个 FileReader，用如下方式，假设文件不存在，该方法会抛出 FileNotFoundException。

FileReader reader = new FileReader("D:\\demo.txt");

读取一个文件的几种方法，单字符读取，字符数组读取

FileReader reader = new FileReader("D:\\demo.txt");
int c = 0;
while ((c = reader.read()) != -1) {
    System.out.println("字符：" + (char) c);
}

FileReader reader = new FileReader("D:\\demo.txt");
char[] buf = new char[1024];
int num = 0;
while ((num = reader.read(buf)) != -1) {
    System.out.println("字符：" + new String(buf, 0, num));
}

拷贝文本文件实例

结合读取文件和写入文件操作，实现简单的文本文件拷贝。

FileReader reader = null;
FileWriter writer = null;
try {
    reader = new FileReader("D://demo.txt");
    writer = new FileWriter("D://demo_copy.txt");

    int length = 0;
    char[] buf = new char[1024];

    while ((length = reader.read(buf)) != -1) {
        writer.write(buf, 0, length);
        writer.flush();
    }
} catch (Exception e) {
    try {
        if (reader != null) {
            reader.close();
        }
        if (writer != null) {
            writer.close();
        }
    } catch (IOException e1) {
        e1.printStackTrace();
    }
}

字符流写缓冲：BufferWriter 类

将文本写入字符输出流，缓冲各个字符，从而提供单个字符、数组和字符串的高效写入。

可以指定缓冲区的大小，或者接受默认的大小。在大多数情况下，默认值就足够大了。

该类提供了 newLine() 方法，它使用平台自己的行分隔符概念，此概念由系统属性 line.separator 定义。并非所有平台都使用新行符 ('\n') > 来终止各行。因此调用此方法来终止每个输出行要优于直接写入新行符。

通常 Writer 将其输出立即发送到底层字符或字节流。除非要求提示输出，否则建议用 BufferedWriter 包装所有其 write() 操作可能开销很高的 Writer（如 FileWriters 和 OutputStreamWriters）。例如，
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("foo.out")));
将缓冲 PrintWriter 对文件的输出。如果没有缓冲，则每次调用 print() 方法会导致将字符转换为字节，然后立即写入到文件，而这是极其低效的

使用实例如下：

FileWriter writer = null;
BufferedWriter bfw = null;
try {
    writer = new FileWriter("D://demo.txt");
    bfw = new BufferedWriter(writer);
    bfw.write("text");
    bfw.newLine(); // 跨平台换行
} catch (Exception e) {
    try {
        if (bfw != null) {
            bfw.close();
        }
        // 可以省略
        if (writer != null) {
            writer.close();
        }
    } catch (IOException e1) {
        e1.printStackTrace();
    }
}

字符流读缓冲：BufferRader 类

从字符输入流中读取文本，缓冲各个字符，从而实现字符、数组和行的高效读取。

可以指定缓冲区的大小，或者可使用默认的大小。大多数情况下，默认值就足够大了。

通常，Reader 所作的每个读取请求都会导致对底层字符或字节流进行相应的读取请求。因此，建议用 BufferedReader 包装所有其 read() 操作可能开销很高的 Reader（如 FileReader 和 InputStreamReader）。例如，
BufferedReader in = new BufferedReader(new FileReader("foo.in"));
将缓冲指定文件的输入。如果没有缓冲，则每次调用 read() 或 readLine() 都会导致从文件中读取字节，并将其转换为字符后返回，而这是极其低效的。
通过用合适的 BufferedReader 替代每个 DataInputStream，可以对将 DataInputStream 用于文字输入的程序进行本地化

注： readLine 方法读取时，只返回换行符之前的内容，不包含文字中的换行符，所以如果需要必须得自己手动添加。
使用实例如下：

FileReader reader = null;
BufferedReader bfr = null;
try {
    reader = new FileReader("D://demo.txt");
    bfr = new BufferedReader(reader);
    String line = "";
    while ((line = bfr.readLine()) != null) {
        System.out.println(line);
    }
} catch (Exception e) {
    try {
        if (bfr != null) {
            bfr.close();
        }
        // 可以省略
        if (reader != null) {
            reader.close();
        }
    } catch (IOException e1) {
        e1.printStackTrace();
    }
}

缓冲区拷贝文本文件实例

结合缓冲读取文件和缓冲写入文件操作，实现简单的文本文件拷贝。

BufferedReader bfr = null;
BufferedWriter bfw = null;
try {
    bfr = new BufferedReader(new FileReader("D://demo.txt"));
    bfw = new BufferedWriter(new FileWriter("D://demo_copy.txt"));

    String line = null;
    while ((line = bfr.readLine()) != null) {
        bfw.write(line);
        bfw.newLine();
        bfw.flush();
    }
} catch (Exception e) {
    try {
        if (bfr != null) {
            bfr.close();
        }
        if (bfw != null) {
            bfw.close();
        }
    } catch (IOException e1) {
        e1.printStackTrace();
    }
}

动手写 BufferReader

在 Windows 下换行符为 "\r\n"，linux 下换行符为 "\n"，两者共同点都是以 "\n" 结尾，可以通过该字符判断是否已经达到行尾，示例代码如下：

class MyBufferReader {
    private FileReader r;
    public MyBufferReader (FileReader r) {
        this.r = r;
    }
    public String myReadLine() throws IOException {
        StringBuilder sb = new StringBuilder();
        int res = 0;
        while ((res = r.read()) != -1) {
            if ('\r' == ((char)res)) {
                continue;
            }
            if ('\n' == ((char)res)) {
                return sb.toString();
            }
            else {
                sb.append((char) res);
            }
        }
        // 若是没有 \n，则把之前读进来的全输出
        if (sb.length() > 0) {
            return sb.toString();
        }
        return null;
    }
    // ... 省略 close 方法
}

参考：
传智播客毕向东

基本概念

并发：多个线程操作相同的资源，保证线程安全，合理使用资源

高并发：服务能同时处理很多请求，提高程序性能

并发编程基础

CPU 多级缓存

为什么需要 CPU 缓存？

CPU 的频率太快，快到主存跟不上，这样在处理器时钟周期内，CPU 常常要等待主存，浪费资源。所以 cache 的出现，是为了缓解 CPU 和主存之间速度不匹配问题（结构：cpu-> cache -> memory）

缓存的容量远远小于主存，不能包含所有的 CPU 所需要的数据。

CPU cache 有什么意义？

1. 时间局部性：如果某个数据被访问，那么在不久将来很可能被再次访问
2. 空间局部性：如果某个数据被访问，那么与他相邻的数据也可能很快被访问

CPU 多级缓存 - 缓存一致性（MESI）

用于保证多个 CPU cache 之间缓存共享数据的一致性

CPU 多级缓存 - 乱序执行优化

处理器为了提高运算速度而做出违背代码原有顺序的优化

单核时代是不会有问题的，但是多核就不一定了

Java 内存模型（Java Memory Model,JMM）

规定了一个线程如何、何时可以看到由其他线程修改过后的共享变量的值。以及在必须时如何同步的访问共享变量。

java 内存模型

硬件内存模型

java 内存模型与硬件内存模型之间的关系

java 内存模型抽象结构图

Java 内存模型 - 同步的八种操作

同步操作图示

• lock（锁定）：作用于主内存的变量，把一个变量标识为一条线程独占
• unlock（解锁）：作用于主内存变量，把一个处于锁定状态的变量释放出来，释放后的变量才可以被其他的线程锁定。
• read（读取）：作用于主内存的变量，把一个变量值从主内存传输到线程的工作内存中，以便随后的 load 动作使用。
• load（载入）：作用于主内存的变量，他把 read 操作从主内存中得到的变量值放入工作内存的副本中
• user（使用）：作用于工作内存的变量，把工作内存中的变量值传递给执行引擎
• assign（赋值）：作用于工作内存的变量，他把一个从执行引擎接收到值，赋值给工作内存的变量
• store（存储）：作用于工作内存的变量，把工作内存中的一个变量的值传送到主内存中，以便于随后的 write 操作
• write（写入）：作用于主内存的变量，他把 store 操作从工作内存中一个变量的值传送到主内存的变量中

Java 内存模型 - 同步规则

1. 如果要把一个变量从主内存中赋值到工作内存，就需要按顺序得执行 read 和 load 操作，如果把变量从工作内存中同步回主内存中，就要按顺序得执行 store 和 write 操作，但 java 内存模型只要求上述操作必须按顺序执行，没有保证必须是连续执行,也就是说 read 和 load、store 和 write 之间是可以插入其他指令的
2. 不允许 read 和 load、store 和write 操作之一单独出现
3. 不允许一个线程丢弃他的最近 assign 的操作，即变量在工作内存中改变了之后必须同步到主内存中
4. 不允许一个线程无原因地（也就是说必须有 assgin 操作）把数据从工作内存同步到主内存中
5. 一个新的变量只能在主内存中诞生，不允许在工作内存中直接使用一个未被初始化（ load 或 assign）的变量。即就是对一个变量实施 use 和 store 操作之前，必须先执行过了 load 和 assign 操作
6. 一个变量在同一时刻只允许一条线程对其进行 lock 操作，但 lock 操作可以同时被一条线程重复执行多次，多次执行 lock 后，只有执行相同次数的 unlock 操作，变量才会解锁，lock 和 unlock 必须成对出现
7. 如果一个变量执行 lock 操作，将会清空工作内存中此变量的值，在执行引擎中使用这个变量前需要重新执行 load 或 assign 操作初始化变量的值
8. 如果一个变量事先没有被lock操作锁定，则不允许他执行 unlock 操作，也不允许去 unlock 一个被其他线程锁定的变量
9. 对一个变量执行 unlock 操作之前，必须先把此变量同步到主内存中（其实就是执行 store 和 write 操作之后）

简介

用来将文件或者文件夹封装成对象，方便对文件与文件夹的属性信息进行操作，File 对象可以作为参数传递给流的构造函数。

基本使用

File 类既能封装文件，又能封装文件夹

// 封装文件
File f = new File("C:\\demo.txt");

// 封装文件夹
File f = new File("C:\\demo");

创建

跟 FileOutputStream 不同的是，FileOutputStream 会在流建立时就默认创建并复写文件。而 File 是需要在调用 createNewFile 方法以后才会创建。
两者的共同点是，文件路径中包含有不存在的文件夹时，会抛出 FileNotFoundException。createNewFile 方法在创建成功时，返回 true。文件存在或者其他原因导致失败，则返回 false。

注：创建的是文件，而不是文件夹，所以当 new File("C:\\demo").createNewFile() 运行结果是，创建不带后缀名的 demo 文件，而不是创建了 demo 文件夹

new File("C:\\demo.txt").createNewFile();

如果需要创建文件夹需要调用 mkdir() | mkdirs() 方法，使用如下：

// 此方法只能创建一级目录
new File("C:\\demo").mkdir();

// 此方法能创建多级目录
new File("C:\\demo\\demo\\demo\\").mkdirs();

删除

删除指定文件，当文件路径中包含有不存在的文件夹，或者所要删除的文件不存在时，返回 false

new File("C:\\demo.txt").delete();

判断

判断文件对象是否是文件或其他时，必须要先判断该文件对象封装的内容是否存在，如果不存在的话，返回都为 false。判断方法得在文件存在时，才会具有意义，如下代码：

File f = new File("C:\\dd\\demo.txt"); // 该文件不存在
f.isFile(); // fasle
f.isDirectory(); // fasle

常用的方法如下：

boolean exists(); // 文件是否存在
boolean isFile(); // 是否是文件
boolean isDirectory(); // 是否是文件夹
boolean isHidden(); // 是否是隐藏文件
boolean isAbsolute(); // 是否是绝对路径

获取

getPath() 该方法返回的是构造函数中指定的路径，若封装的是相对路径则返回相对路径，封装的是绝对路径则返回绝对路径。不同于 getAbsolutePath() 方法，后一个方法返回的永远是绝对路径。

getParent() 该方法返回的是绝对路径中的父目录。如果获取的是相对路径，且含有上层目录，则返回上层目录，否则返回 null。

常用的方法如下：

String getName(); // 获取文件名
long lastModified(); // 获取上次修改时间
long length(); // 获取文件长度

常用功能

获取某个文件下的所有以 .bmp 结尾的文件

使用 listFiles 方法时，File 对象指向的得是一个文件夹，指向文件时，返回的是 null，如果此时对返回的数组进行迭代，会出现 NPE。

File file = new File("D:\\dir");
File[] files = file.listFiles(new FileFilter() {
    @Override
    public boolean accept(File f) {
        return f.getName().endsWith(".bmp");
    }
});

打印某个文件下的所有文件夹和文件名（递归）

使用递归，碰到文件夹时，继续调用自身，进行打印

public static String getLevel(int level) {
    StringBuilder sb = new StringBuilder();
    for (int x = 0; x < level; x++) {
        sb.append("|--");
    }
    return sb.toString();
}

public static void showDir(File dir, int level) {
    System.out.println(getLevel(level) + dir.getName());
    level++;
    File[] files = dir.listFiles();
    for (int x = 0; x < files.length; x++) {
        if (files[x].isDirectory())
            showDir(files[x], level);
        else
            System.out.println(getLevel(level) + files[x]);
    }
}

将指定文件夹下的所有 java 文件的绝对路径写入文件

使用递归，碰到文件夹时，继续调用自身，放文件到集合

public static void fileToList(File dir, List<File> list) {
	File[] files = dir.listFiles();
	for (File file : files) {
		if(file.isDirectory())
			fileToList(file,list);
		else {
			if(file.getName().endsWith(".java"))
				list.add(file);
		}
	}
}
// 省略写入文件方法

1.@value

@Value("${app.name}")
private String projectName;

2.@ConfigurationProperties

@Component
@ConfigurationProperties(locations="classpath:application.properties",prefix="app")
public class AppProperties{

String name;
String version;
}

3.Environment

@Autowired
private Environment env;

env.getProperty("app.name");

4.PropertiesloaderUtils

可以用于具体的方法中，较为灵活

import org.springframework.core.io.support.PropertiesLoaderUtils;
Properties properties=PropertiesLoaderUtils.loadAllProperties("application.properties");

快捷键

查阅官方快捷键说明：Help -> Keymap Reference

常见快捷键，（Windows 下）

小技巧

• 定位语法错误
  按 F2 快速定位到下一个错误和警告处， Shift + F2 定位到上一个错误处

• 在版本控制文件对比窗口时，调到下一处修改的地方
  按 F7 跳到下一处修改，Shift + F7 到上一处修改

• 显示类继承结构图（UML）
  选中类名 -> 右键 Diagram -> 右键 Show Implementations -> 选中添加需要显示的子类

• 快捷方法显示类继承结构图
  选中类名后 Ctrl + H -> 弹出视图中 Ctrl + A -> 右键 Diagram

• 设置鼠标划过显示 javadoc
  File -> Setting -> Editor -> General -> Show quick documentation on mouse move

• 设置代码默认不折叠
  File -> Setting -> Editor -> General -> Code Folding One line method

• 隐藏 .idea 文件夹和 *.iml 文件夹
  setting -> File Type

• 给常用语句设置快捷键
  Settings -> Editor -> Live Templates
  可以新建一个自己的 Template Group，然后里面添加自己模板代码

• 设置自动注释不加在代码行首
  Code Style -> Java -> Code Generation 去掉 Line comment at first column 和 Block comment at first column 复选框的勾

• 使项目脱离 svn 版本管理
  删除隐藏的 .svn 文件夹即可

• 不显示面包屑导航
  Editor - General - Appearance - Show breadcrumbs

• 不显示编辑面板左侧方法折叠和提示小图标

• 方法折叠：Editor - General - Code Floding - Show code floding outline

• 提示小图标：Editor - General - Show gutter icons

• 从接口直接直接跳到实现
  ctrl + alt + 鼠标左键，也可以通过快捷键 Ctrl + Alt + B

• 补全判空、非空：在变量后面输入 . 接着输入 null 回车即可。非空即输入 notnull 或者 nn。

• 快速补全语句：Ctrl + Shift + Enter 补全分号和花括号等

• 选中多行：摁住鼠标滚轮，拖动即可

插件

1. CodeGlance：代码小地图
2. Grep Console：控制台文字高亮输出
3. Lombok plugin：Lombok 插件
4. Maven Helper：分析依赖神器，最为推荐
5. Mybatis：Mybatis 帮助插件，接口与实现之间跳转
6. Rainbow Brackets：在括号上面加上颜色
7. SequenceDiagram：根据代码生成时序图

遇到的问题

• 运行 maven 命令控制台中文乱码

Setting->maven->runner VMoptions:-Dfile.encoding=GB2312

• Idea 输出控制台乱码

http://www.cnblogs.com/vhua/p/idea_1.html

• 搜狗输入法在 Idea 不跟随

https://blog.csdn.net/qq_27905183/article/details/79119237

什么是链表？

数组需要连续的内存空间来存储，对内存的要求比较高。链表恰恰相反，不需要连续的内存空间，通过指针将零散的内存块串联起来。链表（List）常见结构：单链表、双链表、循环链表。

特殊结点：

• 第一个结点：头结点（用来记录链表的基地址）
• 最后一个结点：尾结点（特殊点，指针指向空地址 NULL）

各操作时间复杂度：

• 插入和删除操作，时间复杂度是为 O(1)
• 随机访问第 k 个元素时，需要根据指针依次遍历，直到找到相应的结点，时间复杂度为 O(n)

循环链表 是特殊的单链表，与单链表的唯一区别在于尾结点，循环链表的尾结点指向链表的头结点，首尾相连。单链表只有一个方向，双链表支持两个方向，除 next 指针之外，还有一个前驱指针 prev 指向前面的结点。

双链表比单链表更加高效？

从链表中删除一个数据包含两种情况：

• 删除结点中，“值等于某个给定值”的结点
• 删除给定指针指向的结点

对于第一种情况，不管是单链表还是双链表，为了查找到给定值的结点，都需要从头结点开始依次遍历对比，直到找到值等于给定值的结点，然后通过指针操作将其删除。

单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析加法法则，删除只等于给定值的结点对应的链表操作总时间复杂度为 O(n)。

对于第二种情况，已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表不支持直接获取前驱结点，所以为了找到前驱结点，还是得从头结点开始遍历链表，直到 p->next=q。

但是对于双链表来说，此情况较有优势，因为保存了前驱结点的指针，省去遍历的步骤。所以针对第二种情况，单链表的删除操作需要 O(n) 而双链表只需要 O(1) 时间复杂度内搞定。

同理如果我们希望在链表的指定结点前面插入一个结点，双向链表比单链表有很大的优势，双向链表可以在 O(1) 时间复杂度内搞定，而单向链表需要 O(n) 的时间复杂度。

除了删除、插入有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系决定，决定是往后还是往前查找，所以平均只需要查找一半的数据。

LinkedHashMap 实现原理中包含双向链表这种数据结构

采 用空间换时间 的设计**，当内存充足时，追求代码的执行速度，可以选择空间复杂度较高，但时间复杂度相对较低的算法或者数据结构。相反内存比较吃紧，反过来需要用时间换空间的设计思路。

链表数组性能表

链表数组优势劣势

数组在简单易用，在实现上是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没有办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块的连续内存空间。如果数组生命过大，系统很可能没有连续的内存空间分配给它。导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小限制，天然地支持动态扩容，也是与数组的最大区别。

链表中的每个结点都需要消耗额外的存储空间去存储一份下一个结点的指针，所以内存消耗会翻倍。而且对链表频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能导致频繁的 GC。

使用链表实现 LRU 缓存淘汰算法

维护一个有序的单链表，越靠近链表尾部的节点是越早之前访问的。当有新数据被访问时，从链表头开始顺序遍历链表。

1. 如果此数据之前被缓存在链表中，遍历得到的这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又分为两种情况

• 如果此时缓存未满，则将此节点直接插入到链表的头部
• 如果此时缓存已满，则链表的尾结点删除，将新的数据结点插入链表头部

时间复杂度为 O(n)

问题

1. 数组实现 LRU 缓存淘汰策略
2. 单链表存储字符串如何判断是否是回文

1、线程和进程

进程是程序的副本，进程是程序执行的实例

• 多个进程的内部数据和状态都是完全独立的，而多线程是共享的一块内存空间和一组系统资源，有可能相互影响
• 线程本身的数据通常只有寄存器数据，以及一个程序执行时使用的堆栈，所以线程的切换比进程的负担要小

线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务

2、线程的创建

• 作为 Thread 的子类，并重写 run()
• 实现 Runnable 接口，并实现 run()

总结：

1. 两种方式都需执行线程的 start() 为线程分配必须的系统资源、调度线程运行并执行线程的 run()
2. 在具体应用中，采用哪种方法来构造线程体要视情况而定。通常，当一个线程已继承了另一个类时，就应该用第二种方法来构造
3. 线程的消亡不能调用 stop()，而是让 run() 自然结束

3、线程的结束（停止、中断）

很常见的一个需求就是如何中断正在执行任务的线程？此时又可以分好几种情况

当线程处于正常执行状态时：处于 running() 状态，可以使用中断标记位的方式结束线程的运行。 一般推荐方式是使用中断标记位，每次迭代检查该标记的状态。

private static volatile boolean STOP = false;

**当线程处于可被打断状态：**sleeping（掉用了 Thread.sleep() 方法） 和 waittiing（调用了 Object.wait() 方法） 时，则需要使用 Thread#interrupt() 的方式打断其状态。

对中断操作的正确理解是：它不会真正地中断一个正在运行的线程，而只是发出中断请求，然后由线程在下一个合适的时刻中断自己。
-- 《Java 并发实战》 C7

**当线程处于不可被打断状态：**由于 I/O 操作阻塞或者由于 synchronized 进入锁池阻塞，此时就不能用 interrupt() 方法打断，因为这两种情况并不会去检查线程“已请求去取消”标记而抛出异常，只能设置线程的中断状态，但没有其他任何作用。此时要想终止线程就必须知道线程阻塞的原因：

- 同步的 Socket I/O
当对套接字调用 read() 和 write() 方法而阻塞时，这些方法都不会响应中断，可以调用 close() 方式，使其抛出异常 SocketException

- 同步的 I/O
当关闭一个正在 InterruptibleChannel 上等待的线程时，将抛出 CloseByInterruptException 异常并关闭链路。当关闭一个 InterrptibleChannel 时，将导致所有在链路上的操作的线程都抛出 AsynchronousCloseException

- Selector 的 异步 I/O
如果一个线程在调用 Selector#select() 方法时阻塞了，那么调用 close ()和 wakeUp() 会使线程抛出 ClosedSelectorException 并提前返回。

- 获取某个锁
如果一个线程由于等待某个内置锁而阻塞，那么将无法响应中断，因为线程认为它肯定会获得锁，所以将不会理会中断请求。但是，在 Lock 类中提供了 lockInterruptibly 方法，该方法允许在等待一个锁的同时仍能响应中断。

正常线程使用中断标记位的方式：

class MyThread implements Runnable {
    private boolean flag = true;
    @Override
    public void run() {
        while (flag) {
        }
    }
    public void stopRunning() {
        this.flag = false;
    }
}
class ControlThread {
    private MyThread r = new MyThread();
    private Thread t = new Thread(r); 
    public void startThread() {
        t.start();
    }
    public void stopThread() {
        r.stopRunning();
    }
}

4、线程的生命周期

一个线程从创建到消亡的过程，线程的生命周期分为五个状态：

• 创建状态(new)
  当用 new 操作符创建一个新的线程对象时，该线程出于创建状态（只是一个空的线程对象，系统不为它分配资源）

• 可运行状态(runnable)
  执行线程的 start() 将为线程分配必须的系统资源，安排其运行，并调用线程体的run()，这样就使得该线程处于可运行状态（并不是运行状态，因为线程实际上并未运行，只是具备了运行的能力）

• 运行状态(running)
  可运行状态(runnable)的线程获得了 cpu 时间片（timeslice），执行程序代码。

• 阻塞状态(block)
  当发生下列事件时，会进入阻塞状态：

  • 等待阻塞：线程调用 wait() 等待特定条件满足，放入线程等待队列（waitting queue）
  • 同步阻塞：在获取对象的同步锁时，该同步锁被别的线程占用，jvm 将当前该线程放入锁池(lock pool)
  • 其他阻塞：调用 sleep()、线程 i/o 阻塞

  返回可运行状态：

  • 另一个对象通过 notify() 或者 notifyAll() 通知
  • 等待上一个线程放弃锁
  • 处于睡眠状态的线程在指定时间过去后、等待输入输出完成

• 消亡状态(dead)
  run()，main() 执行结束，或者因异常退出了 run()，则该线程结束生命周期，死亡的线程不可再次复生

线程状态转换图：

加入 synchronized 后的线程状态转换图：（同步的线程状态转换图）

具有 wait() 和 notify() 的线程状态图：

5、线程的调度策略

线程调度器选择优先级最高的线程运行。但是，如果发生一下情况，就会终止线程的运行

• 线程体中调用了 yield()，让出了对 CPU 的占用权
• 线程体中调用了 sleep()，使线程进入睡眠状态
• 线程由于 i/o 操作而阻塞
• 另一个更高优先级的线程出现

6、线程锁

Java 中每个对象都有一个锁（lock）或者叫监视器（monitor），当访问某个对象的 synchronized 方法时，表示将该对象上锁，此时其他任何线程都无法再去访问该 synchronized 方法，直到之前线程执行方法完毕后（或者是抛出异常）。那么将该对象的锁释放掉，其他线程才有可能再去访问该 synchronized 方法

示例代码：

class Example {
    public synchronized void execute() throws Exception {
        for (int i=0; i<20; i++) {
            Thread.sleep(1000);
            System.out.println("hello --" + i);
        }
    }
    public synchronized static void execute2() throws Exception {
        for (int i=0; i<20; i++) {
            Thread.sleep(1000);
            System.out.println("world --" + i);
        }
    }
}
class Thread1 implements Runnable {
    private Example example;
    public Thread1(Example example) {
        this.example = example;
    }
    @Override
    public void run() {
         example.execute();
    }
}
class Thread2 implements Runnable {
    private Example example;
    public Thread2(Example example) {
        this.example = example;
    }
    @Override
    public void run() {
         example.execute2();
    }
}

7、线程死锁

线程间相互等待资源，而又不释放自身的资源，导致无穷无尽的等待，其结果是系统任务永远无法执行完成。死锁问题是在多线程开发中应该坚决避免和杜绝的问题。

示例：

public class DeadLockDemo {
    public void method1() {
        synchronized (Integer.class) {
            System.out.println(Thread.currentThread().getName() + " 获取到 Integer 锁");
            Thread.sleep(1000);
            synchronized (String.class) {
                System.out.println(Thread.currentThread().getName() + " 获取到 String 锁");
            }
        }
    }
    public void method2() {
        synchronized (String.class) {
            System.out.println(Thread.currentThread().getName() + " 获取到 String 锁");
            Thread.sleep(1000);
            synchronized (Integer.class) {
                System.out.println(Thread.currentThread().getName() + " 获取到 Integer 锁");
            }
        }
    }
}

8、多线程目的

多线程编程的目的，就是"最大限度地利用 CPU 资源"，当某一线程的处理不需要占用 CPU 而只和 I/O 等资源打交道时，让需要占用 CPU 资源的其它线程有机会获得 CPU 资源。从根本上说，这就是多线程编程的最终目的

9、线程安全

线程安全是编程中的术语，指某个函数、函数库在多线程环境中被调用时，能够正确地处理多个线程之间的共享变量，使程序功能正确完成

10、问题

1. 当一个线程进入一个对象的一个 synchronized 方法后，其它线程是否可进入此对象的其它方法?

其他方法的几种情况：

• 普通方法（包括静态方法）
  不影响正常访问
• 同步方法
  不能再访问，须等待上个线程释放锁
• 静态同步方法
  不影响正常访问，与同步方法用的不是同一个锁
  同步方法用的是 对象锁
  静态同步方法为用的是 类锁

2. 为什么wait()，notify()方法要和synchronized一起使用？

wait() 作用为通知当前线程等待并释放对象锁，notify() 作用为通知等待此对象锁的线程重新获得对象锁，然而，如果没有获得对象锁，wait() 和 notify() 都是没有意义的，即必须先获得对象锁，才能对对象锁进行操作

参考：
圣思园张龙老师的 Java 视频
开源**某博客

JavaEE 开发中部署网站应用的常见方式总结，本文以 Tomcat 为例，列举三种方式：配置 tomcat 配置文件、打包应用放置特定位置、创建专属配置文件

方法一：在 server.xml 中指定

在 Tomcat 中的 conf 目录中，在 server.xml 中的，<host/>节点中添加：

<Context 
path="/myapp" 
reloadable="true" 
docBase="D:\myapp" 
workDir="D:\myapp\work">
</Context>

在 Tomcat 的配置文件中，一个 Web 应用就是一个特定的 Context，可以通过在 server.xml 中新建 Context 里部署一个 JavaWeb 应用程序。

其中 path 是虚拟路径（外部访问路径），docBase 是应用的物理路径（项目放在硬盘哪个位置），workDir 是这个应用的工作目录（默认是 Tomcat 目录中 work 目录），存放运行时生成的这个应用相关文件

注：

1. 当 path="" 和 path="/" 应用不会被加载（原因不明）
2. docBase 属性中路径的 "" 和 "/" 皆可（在 apache-tomcat-6.0.44 和 apache-tomcat-7.0.68 试验通过）

方法二：放置 webapps 目录下

将 web 项目文件打包成 war 包或者直接将整个文件夹（包括该web的所有内容），拷贝到 Tomcat 的 webapps 目录中。

Tomcat 的 webapps 目录是 Tomcat 默认的应用目录，当服务器启动时，会加载所有这个目录下的应用。也可以将 JavaWeb 应用打成一个 war 包放在目录下，服务器会自动解开这个 war 包，并在这个目录下生成一个同名的文件夹。

一个 war 包就是有特性格式的 jar 包，它是将一个 Web 应用程序的所有内容进行压缩得到。具体如何打包，可以使用许多开发工具的IDE 环境，如 Eclipse、NetBeans、ant、JBuilder 等。也可以用 cmd 命令：

jar -cvf applicationname.war package.*；

方法三：创建一个 Context 文件（xml）

在 Tomcat 的 conf\Catalina\localhost 目录中，新建一个 xml 文件，名字任意，该 xml 文件的内容为：

<Context 
path="/myapp" 
docBase="D:\myapp" 
debug="0" 
privileged="true">
</Context>

可以看出，文件中描述一个应用程序的 Context 信息，其内容和 server.xml 中的 Context 信息格式是一致的，文件名便是虚拟目录名。可以直接建立这样的一个 xml 文件，放在 Tomcat 的 conf\catalina\localhost 目录下

注意：

1. 删除一个 Web 应用同时也要删除 webapps 下相应的文件夹和 server.xml 中相应的 Context，还要将 conf\catalina\localhost 目录下相应的 xml 文件删除。否则 Tomcat 仍会按配置去加载

2. 方法三优点是可以定义别名。服务器端运行的项目名称为 path，外部访问的 URL 则使用 XML 的文件名。两种方式都可以访问到网站。

问题

如何配置有层级关系的两个网站？

效果如下：

// 访问主网站：默认应用
http://localhost:8080/
// 访问二级网站（如：blog）
http://localhost:8080/blog 

在 tomcat 的 conf\catalina\localhost 目录下新建 ROOT.xml 和 blog.xml 文件，内容如下：

<!-- ROOT.xml -->
<?xml version="1.0" encoding="UTF-8"?>
<Context path="/" reloadable="true" docBase="F:\deployDemo01"></Context>

<!-- blog.xml -->
<?xml version="1.0" encoding="UTF-8"?>
<Context path="/blog" reloadable="true" docBase="F:\deployDemo01-blog"></Context>

注：docBase 根据实际情况指定

部署时，资源重复加载

应用已打包成 .war 包，放置在 Tomcat\webapps 路径下：
并在 sever.xml 中配置，如下（错误示例）：

<Context 
docBase="F:\DevelopmentKit\apache-tomcat-6.0.44\webapps\TestTomcatDoubleReload.war" 
path="/ttd" 
reloadable="true">
</Context>	

解决：

1. 删除该 Context 节点
2. 将该 .war 包放置于除 Tomcat\webapps 之外的路径下

参考：
http://lvzhou-31.iteye.com/blog/1898261
http://www.cnblogs.com/hwaggLee/p/5151827.html
http://www.cnblogs.com/xiaoyunxia/p/6307392.html

当调用 FileOutputStream#write(int i) 时，只写 1 个字节取低八位，也就是超过一个字节长度时，将会造成数据丢失，使用时需要注意。

FileOutputStream fos = new FileOutputStream("C:\\text.txt");
// 只将 1 个字节的数据写出去，剩余会被丢失
// 即写出了00100001
fos.write(289); 
fos.close();

字节流：FileOutputStream 类

文件输出流是用于将数据写入 File 或 FileDescriptor 的输出流。文件是否可用或能否可以被创建取决于基础平台。特别是某些平台一次只允许一个 FileOutputStream（或其他文件写入对象）打开文件进行写入。在这种情况下，如果所涉及的文件已经打开，则此类中的构造方法将失败。

FileOutputStream 用于写入诸如图像数据之类的原始字节的流。要写入字符流，请考虑使用 FileWriter。

创建一个 FileOutputStream，用如下方式，假设文件不存在，则会被创建，若文件存在则会被覆盖。当文件路径中包含有不存在的文件夹或者盘符时，该方法会抛出 FileNotFoundException。

FileOutputStream fos = new FileOutputStream("D:\\demo.txt");

若文件不想被覆盖，则使用如下构造方法：指定追加模式为 true。此时当文件存在时，写操作会在文件末尾追加内容。

FileOutputStream fos = new FileOutputStream("D:\\demo.txt", true);

基本的使用方法如下，和 FileWriter 不同是 FileOutputStream 不带缓冲区，调用完 write 方法以后立刻会将内容刷入磁盘。

FileOutputStream fos = null;
try {
    fos = new FileOutputStream("D:\\demo.txt");
    fos.write('t');
} catch (IOException e) {
    e.printStackTrace();
} finally{
    if (fos!=null) {
        try {
            fos.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

此类中常用 write(byte b[], int off, int len) 方法，将指定 byte 数组中从偏移量 off 开始的 len 个字节写入此文件输出流。

字节流：FileInputStream 类

FileInputStream 从文件系统中的某个文件中获得输入字节。哪些文件可用取决于主机环境。

FileInputStream 用于读取诸如图像数据之类的原始字节流。要读取字符流，请考虑使用 FileReader。

创建一个 FileInputStream ，用如下方式，假设文件不存在，该方法会抛出 FileNotFoundException。

FileInputStream fis = new FileInputStream("D:\\demo.txt");

读取一个文件的几种方法，单字符读取，字符数组读取

FileInputStream fis = new FileInputStream("D:\\demo.txt");
int c = 0;
while ((c = fis.read()) != -1) {
    System.out.println("字符：" + (char) c);
}
// .close()

FileInputStream fis = new FileInputStream("D:\\demo.txt");
byte[] buf = new byte[1024];
int num = 0;
while ((num = fis.read(buf)) != -1) {
    System.out.println("字符：" + new String(buf, 0, num));
}
// .close()

拷贝图片文件实例

结合读取文件和写入文件操作，实现简单的文本文件拷贝。

FileInputStream fis = null;
FileOutputStream fos = null;
try {
    fis = new FileInputStream("D:\\pic\\1.jpg");
    fos = new FileOutputStream("D:\\pic\\1_copy.jpg");

    byte[] buf = new byte[1024];
    int length = 0;
    while ((length = fis.read(buf)) != -1) {
        fos.write(buf, 0, length);
    }
} catch (Exception e) {
    try {
        if (fis != null) {
            fis.close();
        }
        if (fos != null) {
            fos.close();
        }
    } catch (IOException e1) {
        e1.printStackTrace();
    }
}

字节流写缓冲：BufferedOutputStream 类

该类实现缓冲的输出流。通过设置这种输出流，应用程序就可以将各个字节写入底层输出流中，而不必针对每次字节写入调用底层系统。

底层有 buf 数组，所以每次写完记得要 flush。使用实例如下：

FileOutputStream fos = new FileOutputStream("D:\\demo.txt");
BufferedOutputStream bfos = new BufferedOutputStream(fos);
bfos.write(new byte[]{'1', '2'});
bfos.flush();
// .close()

字节流读缓冲：BufferedInputStream 类

BufferedInputStream 为另一个输入流添加一些功能，即缓冲输入以及支持 mark 和 reset 方法的能力。
在创建 BufferedInputStream 时，会创建一个内部缓冲区数组。在读取或跳过流中的字节时，可根据需要从包含的输入流再次填充该内部缓冲区，一次填充多个字节。
mark 操作记录输入流中的某个点，reset 操作使得在从包含的输入流中获取新字节之前，再次读取自最后一次 mark 操作后读取的所有字节。

值得注意的是，该类的 available() 方法，解释为返回此输入流可读字节数，需要谨慎调用。当文件过大时，极容易导致内存溢出。
使用实例如下：

FileInputStream fis = new FileInputStream("D:\\demo.txt");
BufferedInputStream bfis = new BufferedInputStream(fis);
int lenght = 0;
byte[] buf = new byte[1024];
while ((lenght = bfis.read(buf)) != -1) {
    // do something
}

缓冲区拷贝图片文件实例

结合缓冲读取文件和缓冲写入文件操作，实现简单的文本文件拷贝。

BufferedInputStream bfis = new BufferedInputStream(new FileInputStream("D:\\pic\\1.jpg"));
BufferedOutputStream bfos = new BufferedOutputStream(new FileOutputStream("D:\\pic\\1_pcopy.jpg"));
int lenght = 0;
byte[] buf = new byte[1024];
while ((lenght = bfis.read(buf)) != -1) {
    bfos.write(buf, 0, lenght);
    bfos.flush();
}
// .close()

参考：
传智播客毕向东

体系概要

Collection 是一个高度抽象的接口，它主要的两个分支是：List 和 Set，两者都是接口，皆继承于 Collection。List 是有序的队列，可以有重复的元素；而 Set 是数学概念中的集合，没有重复元素。

Java 抽象出了 AbstractCollection 抽象类，它实现了 Collection 中的绝大部分函数；这样，在 Collection 的实现类中，我们就可以通过继承 AbstractCollection 省去重复编码。

在 AbstractCollection 基础之上，又衍生出了 AbstractList 和 AbstractSet，具体的 List 实现类继承于 AbstractList，而 Set 的实现类则继承于 AbstractSet。

另外，Collection 中有一个 iterator() 函数，它的作用是返回一个 Iterator 接口。通常，可以通过 Iterator 迭代器来遍历集合。ListIterator 是 List 接口所特有的，可以通过 listIterator() 返回一个ListIterator对象。

Collection 简介

类定义如下：

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

Collection 是一个高度抽象出的接口，是 Collection 层次结构中的根接口，它包含了集合的基本操作：添加、删除、清空、遍历(读取)、是否为空、获取大小、是否保护某元素等等。Collection 表示一组对象，这些对象也称为 collection 的元素

Collection 接口的所有子类(直接子类和间接子类)都必须实现2种构造函数：不带参数的构造函数和参数为 Collection 的构造函数。带参数的构造函数，可以用来转换 Collection 的类型。

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

List 简介

类定义如下：

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

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

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

// 相比与 Collection，List 新增的 API
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator()
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)

Set 简介

类定义如下：

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

Set 继承于 Collection 接口，也是集合中的一种。特性是没有重复元素。没有重复元素怎么判断是依赖于具体实现的，如 ==、equals、hashCode 以及几个接口比如 Comparable 等等的规范下。

关于 API 方面，跟 Collection 完全一样。

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

AbstractCollection 简介

类定义如下：

public abstract class AbstractCollection<E> implements Collection<E> {}

AbstractCollection 是一个抽象类，提供 Collection 接口的骨干实现，以最大限度地减少了实现此接口所需的工作。它实现了 Collection 中除 iterator() 和 size() 之外的函数。比如 ArrayList、LinkedList 等，它们这些类想要实现 Collection 接口，通过继承 AbstractCollection 就已经实现了大部分的接口了

AbstractList 简介

类的定义如下：

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}

AbstractList 是一个继承于 AbstractCollection，并且实现 List 接口的抽象类。此类提供 List 接口的骨干实现，以最大限度地减少实现“随机访问”数据存储（如数组）支持的该接口所需的工作。

它实现了 List 中除 size()、get(int location) 之外的函数。
另外，和 AbstractCollection 相比，AbstractList 抽象类中，实现了 iterator() 接口。

AbstractSet 简介

类定义如下：

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {}

AbstractSet 是一个继承于 AbstractCollection，并且实现 Set 接口的抽象类。此类提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

由于 Set 接口和 Collection 接口中的 API 完全一样，Set 也就没有自己单独的 API。和 AbstractCollection 一样，它实现了 List 中除 iterator() 和 size() 之外的函数。

Iterator 简介

类定义如下：

public interface Iterator<E> {}

Iterator 是一个接口，是集合的迭代器。集合可以通过 Iterator 去遍历集合中的元素。一般从集合中删除指定元素时，可以使用此方法，是线程安全的。

boolean         hasNext() 
E               next() 
void            remove()  

参考文档：
https://blog.csdn.net/u011392897/article/details/54983068

IO 流体系简介

IO 流用来处理设备之间的数据传输，Java 对数据的操作是通过流的方式，用于操作流的对象都在IO包中，基本功能是读写。

• 根据数据流向分：输入流，输出流
• 根据数据传输格式分：字节流、字符流
• 根据数据传输目的分：磁盘流（文件流）、网络流

字节流和字符流的区别

字节流可以处理任何流数据（包括文本、音频、图片等），而字符流只能处理文本文件。字符流的产生是因为文本文件相对常用，故对字节流进行了进一步的封装，在底层加上了查找码表进行编码的功能。

IO 流体系常用基类

• 字节流的抽象基类：InputStream，OutputStream
• 字符流的抽象基类：Reader，Writer

注： 由这四个类派生出来的子类名称都是以其父类名作为子类名的后缀，如：
InputStream 的子类 FileInputStream、Reader 的子类 FileReader

IO 编程中需要注意的点

• 如果文件以 FileOutputStream 或者 FileWriter 方式打开，注意是否会被覆盖！
• 操作完流对象以后，切记需要在 finally 代码块中关闭

什么是栈？

后进者先出，先进者后出，典型的 “栈” 结构（Stack）。栈是一种操作受限的线性表，只允许在一端插入和删除数据。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选栈。

如何实现一个栈？

可以用是数组实现，也可以用链表来实现。用数组实现的栈称为顺序栈，用链表实现的栈称为链式栈。

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组，申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回 false，入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的数组就够了，在入栈和出栈的过程中，只需要一两个临时变量，所以空间复杂度是 O(1)。

不管是顺序栈还是链式栈，只涉及栈顶个别数据的操作，所以时间复杂度为 O(1)

应用场景：函数调用栈

操作系统给每个线程分配了一块独立的内存空间，这块内存组织成 栈 这种结构，用来存储函数调用时的临时变量，每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

应用场景：表达式求值

编译器是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

应用场景：括号匹配

用一个栈来保存未匹配的左括号，从左到右依次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号（弹出）。如果能匹配，则继续扫描剩下的字符串。如果扫描过程中遇到不能配对的右括号，或者栈中没有数据，则说明非法格式。

当所有的括号都扫描完，如果栈为空，则说明字符串为合法格式；否则说明有未匹配的左括号，为非法格式。

浏览器的前进后退功能

当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b、c。但是如果你后退到 b 页面后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

使用两个栈，x 和 y，把首次浏览的页面依次压入栈 x，当点击后退按钮时，再依次从 x 中出栈，并将出栈的数据依次放入栈 y。当点击前进按钮时，依次从 y 中取出数据，放入 x 栈中。
当栈 x 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 y 中没有数据，说明当前页不能再前进。

问题

1. 函数调用为什么需要用 栈 来保存临时变量？其他的数据结构不行吗？
2. JVM 内存管理中有个 “堆栈” 的概念，栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 中的 栈 和这边所说的 栈 是不是一回事呢？如果不是，为什么它又叫做 栈

什么是数组？

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

• 线性表

线性表（Linear List），就是数据排成一条线一样的结构。每个线性表上的数据最多只有前后两个方向，除了数组，链表、队列、栈也是线性结构。对立的概念是非线性表，比如二叉树、堆、图等。数据之间并不是简单的前后关系

• 连续的内存空间和相同的数据类型

实现随机访问的原因。弊端：很多操作都非常低效，比如：插入、删除，为保证数据的连续性，需要做大量的数据搬移工作

寻址公式

a[i]_address = base_address + i * data_type_size

• data_type_size：表示数组中每个元素的大小
• base_address：首元素地址

面试错误纠正：

数组适合查找，查找时间复杂度为 O (1)

数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，用二分法查找，时间复杂度也是 O(logn)。所以，正确的表述：

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

插入低效原因及改进方法

如果在末尾插入则不需要移动数据，此时时间复杂度为 0(1)，但如果在数组的开头插入元素，那所有的数据都需要搬运最坏的时间复杂度是 O(n)，因为在每个位置插入元素的概率是一样的，所以平均情况的时间复杂度为(1+2+...+n)/n=O(n)。

如果数组中的数据是有序的，在某个位置插入一个新的元素时，必须按照刚才的方法。但如果数组中的数据并没有任何规律，只是被当做一个存储数据的集合。此时需要插入新元素到第 k 个位置，直接将 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 位置。

删除低效原因及改进方法

原因同插入操作。

如果不追求是数组中数据的连续性，将多次删除操作集中在一起执行。当数组中存在 a，b，c，d，e，f，g，h。现在需要依次删除 a，b，c 三个元素。

为了避免 d，e，f，g，h 这几个数据会被搬运三次，可以先记录下已经删除的数据，每次删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再出发一次真正的删除操作，大大减少了删除操作导致的数据搬移。

注：此操作为 JVM 标记清除垃圾回收算法的核心**

警惕数组的访问越界问题

在 C 语言中，数组越界是一种未决行为，并没有规定数据访问越界时编译器该如何处理。因为，访问数组的本质就是访问一段连续内存，只要通过偏移结算得到的内存地址是可用的，那么程序就可能不报任何错误。

Java 语言本身就会做越界检查，当越界时抛出 java.lang.ArrayIndexOutOfBoundsException 异常。

数组存在的意义

1. ArrayList 无法存储基本数据类型，比如 int、long 需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能损耗，所以关注性能时，选用数组较为合适
2. 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 的大部分方法时，也可以用数组。

做非常底层的开发时，网络框架性能需要做到极致，数组就会优先于容器

为什么大多数变成语言中数组需要从 0 开始编号，而不是从 1 开始？

a[k]_address = base_address + k * type_size

如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为

a[k]_address = base_address + (k-1) * type_size

对比两个公式，从 1 开始编号，每次随机访问数组元素都多了一次减法元素，对于 CPU 来说，就是多了一次减法指令。

1. 通过下标随机访问数组元素是非常基础的编程操作，效率优化尽可能做到极致。所以为了减少一次减法操作，选择从 0 开始编号。
2. 沿用 C 语言传统，减少学习成本。

二位数组寻址公式

对于 m * n 的数组，a [i][ j ] (i < m,j < n) 的地址为：

address = base_address + ( i * n + j) * type_size

基本性质

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

ArrayList 是 List 接口的大小可变数组的实现。特点是其容量能在进行 add 操作时动态增长。它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, Serializable 这些接口。

随机访问

ArrayList 实现了 RandmoAccess 接口，即提供了随机访问功能。指的是下标索引操作 index(i) 的时间复杂度是 O(1)。size、isEmpty、get、set、iterator、listIterator 操作在 O(1) 内完成，add(e) 操作平均在 O(1) 内完成，即添加 n 个元素需要 O(n) 时间。

自动扩容

底层是数组实现其容量是不能改变的，所以容量不够时，需要更大的数组，这个过程叫作扩容。每次扩容时，会拷贝一份新的内容，是个耗时的操作，避免频繁扩容影响性能。

线程不同步

ArrayList 是未同步的，多线程并发读写时需要外部同步，如果不外部同步，那么可以使用 Collections.synchronizedList 方法对 ArrayList 的实例进行一次封装，或者使用 Vector 类或 CopyOnWriteArrayList 类。

允许 null 值

对存储的元素无限制，允许null元素。

快速失败

iterator 和 listIterator 方法返回的迭代器是快速失败的，也就是如果在创建迭代器之后的任何时间被结构性修改，除了通过迭代器自己的 remove 或 add 方法之外，迭代器将直接抛出一个 ConcurrentModificationException，从而达到快速失败 fail-fast 的目的，尽量避免不确定的行为。

ArrayList的迭代器的快速失败行为不能被严格保证，并发修改时它会尽量但不100%保证抛出ConcurrentModificationException。因此，依赖于此异常的代码的正确性是没有保障的，迭代器的快速失败行为应该仅用于检测 bug。

能被克隆、能被序列化

构造函数

// 默认构造函数
ArrayList()
// 指定初始化容量
ArrayList(int capacity)
// 构造一个包含指定 collection 的元素的列表
ArrayList(Collection<? extends E> collection)

对于此处要注意的是，无参构造函数在 1.6 和 1.7 中的实现是有差别的，
1.6 的实现方式是底层数组 大小默认为10；从 1.7 开始，无参构造方法构造的底层数组大小默认为0。

1.7 以后版本使用的是懒初始化方式。指的是默认构造方法构造的集合类，占据尽可能少的内存空间，在第一次进行包含有添加语义的操作时，才进行真正的初始化工作。

即在进行第一次 add/addAll 等操作时才会真正给底层数组赋非 empty 的值。如果 add/addAll 添加的元素小于 10，则把 elementData 数组扩容为 10 个元素大小，否则使用刚好合适的大小。

确保容量方法（扩容方法）

ArrayList 中使用私有方法 ：ensureCapacity、ensureCapacityInternal 方法来确保数组容量。

一: XmlBeanFactory 引用资源

Resource resource = new ClassPathResource("appcontext.xml"); 
BeanFactory factory = new XmlBeanFactory(resource); 

二: ClassPathXmlApplicationContext 编译路径

ApplicationContext factory = new ClassPathXmlApplicationContext("classpath:appcontext.xml"); 
// src目录下的 
ApplicationContext factory = new ClassPathXmlApplicationContext("appcontext.xml"); 
ApplicationContext factory = new ClassPathXmlApplicationContext(new String[] {"bean1.xml","bean2.xml"}); 
// src/conf 目录下的 
ApplicationContext factory = new ClassPathXmlApplicationContext("conf/appcontext.xml"); 
ApplicationContext factory = new ClassPathXmlApplicationContext("file:G:/Test/src/appcontext.xml"); 

三: 用文件系统的路径

ApplicationContext factory = new FileSystemXmlApplicationContext("src/appcontext.xml"); 
//使用了 classpath: 前缀 FileSystemXmlApplicationContext 也能够读入classpath下 的相对路径 
ApplicationContext factory = new FileSystemXmlApplicationContext("classpath:appcontext.xml"); 
ApplicationContext factory = new FileSystemXmlApplicationContext("file:G:/Test/src/appcontext.xml"); 
ApplicationContext factory = new FileSystemXmlApplicationContext("G:/Test/src/appcontext.xml"); 

四: XmlWebApplicationContext

该方法只可用于 web 工程

ServletContext servletContext = request.getSession().getServletContext(); 
ApplicationContext ctx = WebApplicationContextUtils.getWebApplicationContext(servletContext); 

五: 使用BeanFactory

BeanDefinitionRegistry reg = new DefaultListableBeanFactory(); 
XmlBeanDefinitionReader reader = new XmlBeanDefinitionReader(reg); 
reader.loadBeanDefinitions(new ClassPathResource("bean1.xml")); 
reader.loadBeanDefinitions(new ClassPathResource("bean2.xml")); 
BeanFactory bf=(BeanFactory)reg; 

六：Web 应用启动时加载多个配置文件

通过 ContextLoaderListener 也可加载多个配置文件，在web.xml文件中利用 元素来指定多个配置文件位置，其配置如下:

<context-param>   
    <!-- Context Configuration locations for Spring XML files -->   
   <param-name>contextConfigLocation</param-name>   
   <param-value>   
   ./WEB-INF/**/applicationContext.xml,   
   classpath:config/aer/applicationContext.xml,   
   classpath:org/codehaus/xfire/spring/xfire.xml,   
   ./WEB-INF/**/*.spring.xml   
   </param-value>   
</context-param>  

并发模拟

Postman

Apache Bench

JMeter

代码模拟

Semaphore、CountDownLatch

public class ConcurrencyTest {

    // 请求总数
    public static int clientTotal = 5000;

    // 同时并发执行的线程数
    public static int threadTotal = 200;

    public static int count = 0;

    public static void main(String[] args) throws Exception {
        ExecutorService executorService = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(threadTotal);
        final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
        for (int i = 0; i < clientTotal ; i++) {
            executorService.execute(() -> {
                try {
                    semaphore.acquire();
                    add();
                    semaphore.release();
                } catch (Exception e) {
                    log.error("exception", e);
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        executorService.shutdown();
        log.info("count:{}", count);
    }

    private static void add() {
        count++;
    }
}

转换流中可以使用指定编码读取某个文件中的数据或使用指定编码将数据写入某个文件中

读取转换流（InputStreamReader）

InputStreamReader 是字节流通向字符流的桥梁：它使用指定的 charset 读取字节并将其解码为字符。它使用的字符集可以由名称指定或显式给定，或者可以接受平台默认的字符集。

每次调用 InputStreamReader 中的一个 read() 方法都会导致从底层输入流读取一个或多个字节。要启用从字节到字符的有效转换，可以提前从底层流读取更多的字节，使其超过满足当前读取操作所需的字节。

为了达到最高效率，可要考虑在 BufferedReader 内包装 InputStreamReader。例如：
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

应用场景： 通过键盘录入数据。当录入一行数据后，就将该行数据进行打印。如果录入的数据是over，那么停止录入。对标准输出流（System.in）进行转换，包装成能够以字符形式操纵。

InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(isr);
String line = "";
while ((line = reader.readLine()) != null) {
    if ("over".equals(line)) {
        break;
    }
    System.out.println(line);
}

写入转换流（OutputStreamWriter）

应用场景： 同上。对标准输出流（System.out）进行转换，包装成能够以字符形式操纵。

InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(isr);
String line = "";

OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter bw = new BufferedWriter(osw);
while ((line = reader.readLine()) != null) {
    if ("over".equals(line)) {
        break;
    }
    bw.write(line);
    bw.newLine();
    bw.flush();
}

简单练习

练习一

把键盘录入的数据存储到一个文件

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = "";
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("D://demo.txt")));
while ((line = reader.readLine()) != null) {
    if ("over".equals(line)) {
        break;
    }
    bw.write(line);
    bw.newLine();
    bw.flush();
}

练习二

将一个文件的数据打印在控制台

BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("D://demo.txt")));
String line = "";

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while ((line = reader.readLine()) != null) {
    if ("over".equals(line)) {
        break;
    }
    bw.write(line);
    bw.newLine();
    bw.flush();
}

小结

流操作的基本规律：最痛苦的就是流对象有很多，不知道该用哪一个。通过三个明确来完成。

1. 明确源和目的。

• 源：输入流。InputStream Reader
• 目的：输出流。OutputStream Writer。

2. 操作的数据是否是纯文本。

• 是：字符流。
• 不是：字节流。

3. 当体系明确后，在明确要使用哪个具体的对象。通过设备来进行区分：

• 源设备：内存，硬盘。键盘
• 目的设备：内存，硬盘，控制台。

集合体系简介

集合 Java Collections Framework（JCF），就是可以容纳其他 Java 对象的对象，是 Java 提供的工具包，位于 java.util.* 系列包中，始于 JDK 1.2，以下是其优点：

• 降低编程难度、学习难度
• 提高程序性能、 API 间的互操作性
• 降低设计和实现相关 API 的难度
• 增加程序的重用性

集合只能存放对象，所以对于基本数据类型，需要将其转成对应的包装类型后，才能放入。

Java 集合主要可以划分为4个部分：List 列表、Set 集合、Map 映射、工具类(Iterator 迭代器、Enumeration 枚举类、Arrays 和 Collections )。Java 集合工具包框架图如下：

集合基类

图的最顶层有三个类，分别是 Collection、Map、Iterator，三者的共同点是都是接口。
Collection 和 Map 大致没有什么关联，因为 Map 表示的是关联式容器而不是集合，但也有将 Map 中的键值转化成集合视图的方法。
Collection 依赖于 Iterator，是因为 Collection 的实现类都要实现 iterator() 函数，返回一个 Iterator 对象。

Collection 接口

Collection 层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。
一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。
此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。

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

• List 是一个有序的队列，每一个元素都有它的索引。第一个元素的索引值是0。
  List的实现类有 LinkedList, ArrayList, Vector, Stack。
• Set 是一个不允许有重复元素的集合。
  Set的实现类有 HastSet 和 TreeSet。HashSet依赖于 HashMap，它实际上是通过 HashMap 实现的；TreeSet 依赖于 TreeMap，它实际上是通过 TreeMap 实现的。

Map 接口

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。
Map 是一个映射接口，即 key-value 键值对。Map 中的每一个元素包含一个 Key 和这个 Key 对应的 Value

• AbstractMap 是个抽象类，它实现了 Map 接口中的大部分 API。而 HashMap，TreeMap，WeakHashMap 都是继承于 AbstractMap。
• Hashtable 虽然继承于 Dictionary，但它实现了 Map 接口。

Iterator 接口

对 collection 进行迭代的迭代器。迭代器取代了 Java Collections Framework 中的 Enumeration。迭代器与枚举有两点不同：

• 迭代器允许调用者利用定义良好的语义在迭代期间从迭代器所指向的 collection 移除元素。
• 方法名称得到了改进。

Iterator 是遍历集合的工具，说 Collection 依赖于 Iterator，是因为 Collection 的实现类都要实现 iterator() 函数，返回一个 Iterator 对象。

• ListIterator 是专门为遍历 List 而存在的。

Enumeration 接口

实现 Enumeration 接口的对象，它生成一系列元素，一次生成一个。连续调用 nextElement 方法将返回一系列的连续元素。
例如，要输出 Vector v 的所有元素，可使用以下方法：

   for (Enumeration<E> e = v.elements(); e.hasMoreElements();)
       System.out.println(e.nextElement());

这些方法主要通过向量的元素、哈希表的键以及哈希表中的值进行枚举。枚举也用于将输入流指定到 SequenceInputStream 中。
注：此接口的功能与 Iterator 接口的功能是重复的。此外，Iterator 接口添加了一个可选的移除操作，并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。

Enumeration 是 JDK 1.0 引入的抽象类。作用和 Iterator 一样，也是遍历集合；但是 Enumeration 的功能要比 Iterator 少。在上面的框图中，Enumeration 只能在 Hashtable, Vector, Stack 中使用。

连带知识

Iterable

此接口是1.5新增的，目的就是为了 for-each 循环（增强型for循环）。除了数组外，其他类想要使用 for-each 循环必须实现这个接口。

RandomAccess 标记接口

此接口无方法，用于标记 List 接口的实现类，表明它能在O(1)的时间内进行通过下标获取对应的元素的操作，从而能支持一些特别的算法/操作来加速代码执行。

equals、hashCod、==

老生长谈

Comparable、Comparator

自然排序指的是类实现了 Comparable。SortedXXX/NavigableXXX 以及很多 Arrays.sort 方法都依赖这个。

a > b    <--->    a.compareTo(b) > 0
a = b    <--->    a.compareTo(b) = 0
a < b    <--->    a.compareTo(b) < 0

Comparator 接口是在一个类没有实现 Comparable 接口时，提供一个外部比较方法，方便程序实现以及程序变更，其他的和 Comparable 一样。

工具类

java.util.Collections、java.util.Arrays、apache commons collections、guava commom collect。集合类框架很好的扩展，同时封装了很多工具方法与新功能的集合类。

参考：
http://www.cnblogs.com/skywang12345/p/3323085.html
http://www.cnblogs.com/CarpenterLee/p/5414253.html
https://blog.csdn.net/u011392897/article/details/54983068