一、Java

Java的优势

平台无关性、垃圾回收

Java有哪些特性，举个多态的例子。

封装、继承、多态

abstract interface区别

含有abstract修饰符的class即为抽象类，abstract类不能创建的实例对象。含有abstract方法的类必须定义为abstract class，abstract class类中的方法不必是抽象的。abstract class类中定义抽象方法必须在具体(Concrete)子类中实现，所以，不能有抽象构造方法或抽象静态方法。如果的子类没有实现抽象父类中的所有抽象方法，那么子类也必须定义为abstract类型。

接口（interface）可以说成是抽象类的一种特例，接口中的所有方法都必须是抽象的。接口中的方法定义默认为public abstract类型，接口中的成员变量类型默认为public static final。

下面比较一下两者的语法区别：

1. 抽象类可以有构造方法，接口中不能有构造方法。
2. 抽象类中可以有普通成员变量，接口中没有普通成员变量
3. 抽象类中可以包含非抽象的普通方法，接口中的可以有非抽象方法，比如deaflut方法
4. 抽象类中的抽象方法的访问类型可以是public，protected和（默认类型,虽然
   eclipse下不报错，但应该也不行），但接口中的抽象方法只能是public类型的，并且默认即为public abstract类型。
5. 抽象类中可以包含静态方法，接口中不能包含静态方法
6. 抽象类和接口中都可以包含静态成员变量，抽象类中的静态成员变量的访问类型可以任意，但接口中定义的变量只能是public static final类型，并且默认即为public static final类型。
7. 一个类可以实现多个接口，但只能继承一个抽象类。

有抽象方法一定是抽象类吗？抽象类一定有抽象方法吗？

有抽象方法不一定是抽象类，也可能是接口。抽象类不一定有抽象方法，可以有非抽象的普通方法。

Java的反射机制

在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为Java语言的反射机制。

反射的核心是JVM在运行时才动态加载类或调用方法/访问属性，它不需要事先知道运行对象是谁。

super()和this()能不能同时使用

不能同时使用，this和super不能同时出现在一个构造函数里面，因为this必然会调用其它的构造函数，其它的构造函数必然也会有super语句的存在，所以在同一个构造函数里面有相同的语句，就失去了语句的意义，编译器也不会通过。

hashcode，equals，Object的这两个方法默认返回什么？描述了一下为什么重写equals方法必须重写hashcode方法

默认的hashCode方法会利用对象的地址来计算hashcode值，不同对象的hashcode值是不一样的。

public boolean equals(Object obj) {
        return (this == obj);
    }

可以看出Object类中的equals方法与“==”是等价的，也就是说判断对象的地址是否相等。Object类中的equals方法进行的是基于内存地址的比较。

一般对于存放到Set集合或者Map中键值对的元素，需要按需要重写hashCode与equals方法，以保证唯一性。

final

1. final关键字可以用于成员变量、本地变量、方法以及类。
2. final成员变量必须在声明的时候初始化或者在构造器中初始化，否则就会报编译错误。
3. 你不能够对final变量再次赋值。
4. 本地变量必须在声明时赋值。
5. 在匿名类中所有变量都必须是final变量。
6. final方法不能被重写。
7. final类不能被继承。
8. 接口中声明的所有变量本身是final的。
9. final和abstract这两个关键字是反相关的，final类就不可能是abstract的。
10. final方法在编译阶段绑定，称为静态绑定(static binding)。
11. 没有在声明时初始化final变量的称为空白final变量(blank final variable)，它们必须在构造器中初始化，或者调用this()初始化。不这么做的话，编译器会报错“final变量(变量名)需要进行初始化”。
12. 将类、方法、变量声明为final能够提高性能，这样JVM就有机会进行估计，然后优化。
13. 按照Java代码惯例，final变量就是常量，而且通常常量名要大写。

String,StringBuffer,StringBuilder区别，String为什么不可变

String，是否可以继承，“+”怎样实现

String不可以继承，因为String被final修饰，而final修饰的类是不能被继承的。

String为不可变的，每次String对象做累加时都会创建StringBuilder对象。

// 程序编译期即加载完成对象s1为"ab"
String s1 = "a" + "b";  
// 这种方式，JVM会先创建一个StringBuilder，然后通过其append方法完成累加操作
String s1 = "a";
String s2 = "b"; 
String s3 = s1 + s2; // 等效于 String s3 = (new StringBuilder(s1)).append(s2).toString();

字符串常量池

map、list、set的区别

有没有有序的set？

有，LinkedHashSet和TreeSet

Set如何保证不重复？

HashSet中add()中调用了HashMap的put()，将一个key-value对放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同。如果这个两个key的equals比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。

说一说对Java io的理解

IO，其实意味着：数据不停地搬入搬出缓冲区而已（使用了缓冲区）。

nio与bio的了解以及说一下区别

BIO：同步阻塞式IO，服务器实现模式为一个连接一个线程，即客户端有连接请求时服务器端就需要启动一个线程进行处理，如果这个连接不做任何事情会造成不必要的线程开销，当然可以通过线程池机制改善。

NIO：同步非阻塞式IO，服务器实现模式为一个请求一个线程，即客户端发送的连接请求都会注册到多路复用器上，多路复用器轮询到连接有I/O请求时才启动一个线程进行处理。

Java并发的理解

死锁，死锁原因

两个或者多个线程之间相互等待，导致线程都无法执行，叫做线程死锁。

1. 互斥条件：使用的资源是不能共享的。
2. 不可抢占条件：线程持有一个资源并等待获取一个被其他线程持有的资源。
3. 请求与保持条件：线程持有一个资源并等待获取一个被其他线程持有的资源。
4. 循环等待条件：线程之间形成一种首尾相连的等待资源的关系。

wait和sleep的区别

ArrayList和LinkedList有什么区别？

HashMap 的原理，hashmap的扩容问题，为什么HashMap的初始容量会是16，为什么是2倍扩容，实现简单的 get/put操作；处理哈希冲突用的哪种方法（拉链），还知道什么处理哈希冲突的方法（开放地址检测），开放地址检测怎么实现的

从哈希表中删除一个元素，再加入元素时恰好与原来那个哈希冲突，这个元素会放在哪

HashMap、Hashtable、concurrenthashmap

HashTable为什么是线程安全的？

synchronized锁住了

HashMap，ConcurrentHashMap以及在什么情况下性能会不好

Thread状态有哪些

新建、就绪、运行、阻塞、死亡

多线程实现方法

• 继承Thread类创建线程类，重写run方法，run方法就是代表线程需要完成的任务，调用线程对象的start()来启动该线程，线程类已经继承了Thread类，所以不能再继承其他父类。
• 实现Runnable接口创建线程类，定义Runnable实现类，重写run方法
• 实现Callable接口，重写call()方法，call()作为线程的执行体，具有返回值
• 线程池，使用线程池产生线程对象java.util.concurrent.ExecutorService、java.util.concurrent.Executors;

Java如何实现线程安全

互斥同步：推荐使用 synchronized 关键字进行同步, 在 concurrent包中有ReentrantLock类, 实现效果差不多. 还是推荐原生态的synchronized.

非阻塞同步：需要硬件指令完成.常用的指令有:

Test-and-Set

Fetch-and-Increment

Swap

Compare-and-Swap (CAS)

Load-Linked/Store-Conditional (LL/SC)

典型的应用在 AtomicInteger 中

无同步方案：将变量保存在本地线程中，就不会出现多个线程并发的错误了。

java中主要使用的就是ThreadLocal这个类。

Synchronized和lock区别

• Lock提供了synchronized关键字所不具备的主要特性有：
  • 尝试非阻塞地获取锁boolean tryLock()：当前线程尝试获取锁，如果这一时刻没有被其他线程获取到，则成功获取并持有锁
  • 能被中断地获取锁void lockInterruptibly()：当获取到锁的线程被中断时，中断异常抛出同时会释放锁
  • 超时获取锁boolean trylock(long time, TimeUnit unit)：在指定截止时间之前获取锁，如果在截止时间仍旧无法获取锁，则返回
• synchronized是JVM提供的加锁，悲观锁；lock是Java语言实现的，而且是乐观锁。
• ReentrantLock是基于AQS实现的,由于AQS是基于FIFO队列的实现

Java中都有什么锁

重量级锁、显式锁、并发容器、并发同步器、CAS、volatile、AQS等

可重入锁的设计思路是什么

可重入公平锁获取流程

在获取锁的时候，如果当前线程之前已经获取到了锁，就会把state加1，在释放锁的时候会先减1，这样就保证了同一个锁可以被同一个线程获取多次，而不会出现死锁的情况。这就是ReentrantLock的可重入性。

对于非公平锁而言，调用lock方法后，会先尝试抢占锁，在各种判断的时候会先忽略等待队列，如果锁可用，就会直接抢占使用。

乐观锁和悲观锁

悲观锁：假定会发生并发冲突，则屏蔽一切可能违反数据完整性的操作

乐观锁：假定不会发生并发冲突，只在数据提交时检查是否违反了数据完整性（不能解决脏读问题）

juc包内有哪些类

CountDownLatch 同步计数器，主要用于线程间的控制，但计数无法被重置，如果需要重置计数，请考虑使用 CyclicBarrier 。

CAS如何实现

BlockQueue见过没？

（线程池的排队策略）

线程池原理

线程池的排队策略和拒绝策略的试用条件和具体内容。

线程池的类型，详细介绍cached和fixed

corePoolSize参数的意义

核心线程数

• 核心线程会一直存活，即使没有任务需要执行
• 当线程数小于核心线程数时，即使有线程空闲，线程池也会优先创建新线程处理
• 设置allowCoreThreadTimeout=true（默认false）时，核心线程会超时关闭

线程池新任务到达时会先使用空闲线程还是加入阻塞队列

Java并发包里面的CountdownLatch怎么使用

这个类是一个同步计数器，主要用于线程间的控制，当CountDownLatch的count计数>0时，await()会造成阻塞，直到count变为0，await()结束阻塞，使用countDown()会让count减1。CountDownLatch的构造函数可以设置count值，当count=1时，它的作用类似于wait()和notify()的作用。如果我想让其他线程执行完指定程序，其他所有程序都执行结束后我再执行，这时可以用CountDownLatch，但计数无法被重置，如果需要重置计数，请考虑使用 CyclicBarrier 。

volatile和synchronized区别

• volatile是变量修饰符，其修饰的变量具有可见性，Java的做法是将该变量的操作放在寄存器或者CPU缓存上进行，之后才会同步到主存，使用volatile修饰符的变量是直接读写主存，volatile不保证原子性，同时volatile禁止指令重排
• synchronized作用于一段代码或者方法，保证可见性，又保证原子性，可见性是synchronized或者Lock能保证通一个时刻只有一个线程获取锁然后执行不同代码，并且在释放锁之前会对变量的修改刷新到主存中去，原子性是指要么不执行，要执行就执行到底

线程池使用时一般要考虑哪些问题

一般线程和守护线程的区别

java中的线程分为两种：守护线程（Daemon）和用户线程（User）。

任何线程都可以设置为守护线程和用户线程，通过方法Thread.setDaemon(bool on)；true则把该线程设置为守护线程，反之则为用户线程。Thread.setDaemon()必须在Thread.start()之前调用，否则运行时会抛出异常。

唯一的区别是判断虚拟机(JVM)何时离开，Daemon是为其他线程提供服务，如果全部的User Thread已经撤离，Daemon 没有可服务的线程，JVM撤离。也可以理解为守护线程是JVM自动创建的线程（但不一定），用户线程是程序创建的线程；比如JVM的垃圾回收线程是一个守护线程，当所有线程已经撤离，不再产生垃圾，守护线程自然就没事可干了，当垃圾回收线程是Java虚拟机上仅剩的线程时，Java虚拟机会自动离开。

一致性Hash原理，实现负载均衡

异常

servlet流程

forward redirect 二次请求

序列化，以及json传输

tomcat均衡方式 ，netty

二、JVM

JVM内存划分

程序计数器:记录正在执行的虚拟机字节码指令的地址（如果正在执行的是本地方法则为空）。

Java虚拟机栈:每个 Java 方法在执行的同时会创建一个栈帧用于存储局部变量表、操作数栈、常量池引用等信息。每一个方法从调用直至执行完成的过程，就对应着一个栈帧在 Java 虚拟机栈中入栈和出栈的过程。

本地方法栈:与 Java 虚拟机栈类似，它们之间的区别只不过是本地方法栈为本地方法服务。

Java堆:几乎所有对象实例都在这里分配内存。是垃圾收集的主要区域（"GC 堆"），虚拟机把 Java 堆分成以下三块：

• 新生代
• 老年代
• 永久代

新生代又可细分为Eden空间、From Survivor空间、To Survivor空间，默认比例为8:1:1。

方法区：方法区（Method Area）与Java堆一样，是各个线程共享的内存区域。Object Class Data(类定义数据)是存储在方法区的，此外，常量、静态变量、JIT编译后的代码也存储在方法区。

运行时常量池：运行时常量池是方法区的一部分。Class 文件中的常量池（编译器生成的各种字面量和符号引用）会在类加载后被放入这个区域。除了在编译期生成的常量，还允许动态生成，例如 String 类的 intern()。这部分常量也会被放入运行时常量池。

直接内存：直接内存（Direct Memory）并不是虚拟机运行时数据区的一部分，也不是Java虚拟机规范中定义的内存区域，但是这部分内存也被频繁地使用，而且也可能导致OutOfMemoryError 异常出现。避免在Java堆和Native堆中来回复制数据。

GC

垃圾回收器

Java对象头

HotSpot虚拟机中，对象在内存中的布局分为三块区域：对象头、实例数据和对齐填充。

对象头包括两部分：Mark Word 和 类型指针。

• Mark Word：Mark Word用于存储对象自身的运行时数据，如哈希码（HashCode）、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等等，占用内存大小与虚拟机位长一致。

• 类型指针：类型指针指向对象的类元数据，虚拟机通过这个指针确定该对象是哪个类的实例。

内存泄漏

类加载过程

双亲委派模型，为什么要使用双亲委派模型

Java虚拟机的一些参数配置

为什么jvm调优经常会将-Xms和-Xmx参数设置成一样

三、数据结构与算法

常见的排序算法时间复杂度

快排算法 写代码

堆排序怎么实现

链表，数组的优缺点，应用场景，查找元素的复杂度

入栈出栈的时间复杂度，链表插入和删除的时间复杂度

如何用LinkedList实现堆栈操作

Arraylist如何实现排序

利用数组，实现一个循环队列类

两个有序数组，有相同的元素，找出来

二叉树怎么实现的

二叉树前中后序遍历 深度 广度

二叉树深度

递归

    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(TreeDepth(root.left) + 1, TreeDepth(root.right) + 1);
    }

非递归，层次遍历

    public int TreeDepth_2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue queue = new LinkedList<>();
        queue.offer(root);
        int start = 0;
        int end = 1;
        int depth = 0;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            start++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            if (start == end) {
                start = 0;
                end = queue.size();
                depth++;
            }
        }
        return depth;
    }

层序遍历二叉树

• 思路：
• 访问根节点，并将根节点入队。
• 当队列不空的时候，重复以下操作。
• 1、弹出一个元素。作为当前的根节点。
• 2、如果根节点有左孩子，访问左孩子，并将左孩子入队。

• 3、如果根节点有右孩子，访问右孩子，并将右孩子入队。

  public void levelOrder(TreeNode root) {
      //使用队列，先进先出
      Queue queue = new LinkedList<>();
      queue.add(root);
      while (!queue.isEmpty()) {
          TreeNode temp = queue.poll();
          System.out.print(temp.val + " ");
          if (temp.left != null) {
              queue.offer(temp.left);
          }
          if (temp.right != null) {
              queue.offer(temp.right);
          }
      }
  }

树的中序遍历，除了递归和栈还有什么实现方式

二叉搜索树转换成一个排好序的双向链表

判断平衡二叉树

从下往上遍历，如果子树是平衡二叉树，则返回子树高度，否则返回-1

    public boolean IsBalanced_Solution(TreeNode root) {
        return MaxDepth(root) != -1;
    }
    
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = MaxDepth(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = MaxDepth(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        return Math.abs(leftHeight - rightHeight) > 1 ? -1 : 1 + Math.max(leftHeight, rightHeight);
    }

给定一个2叉树，打印每一层最右边的结点

一棵普通树（非二叉搜索树），找出一条路径和最大

一棵树，求所有路径之和

最长公共子序列

反转链表

将当前节点和下一节点保存起来，然后将当前节点反转。

    public ListNode ReverseList(ListNode head) {
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null
        ListNode pre = null;//pre为当前节点的前一节点
        ListNode next = null;//next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre.head.next1.next2变成pre<-head next1.next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1.2.3.4.5
        //1<-2<-3 4.5
        //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
        while (head != null) {
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }

利用递归走到链表的末端，然后再更新每一个节点的next值 ，实现链表的反转。

    public ListNode ReverseList(ListNode head) {
        //如果链表为空或者链表中只有一个元素 
        if (head == null || head.next == null) return head;
        //先递归找到到链表的末端结点，从后依次反转整个链表
        ListNode reverseHead = ReverseList(head.next);
        //再将当前节点设置为后面节点的后续节点 
        head.next.next = head;
        head.next = null;
        return reverseHead;
    }

判断一个数是不是丑数

找出一个字符串中字符连续相同的最长子串，如aabbccc，结果就是ccc

蓄水池抽样算法

寻找一个字符串中第一个只出现一次的字符

用LinkedHashMap记录字符出现的次数

    public Character firstNotRepeating(String str){
        if(str == null)
            return null;
        char[] strChar = str.toCharArray();
        LinkedHashMap hash = new LinkedHashMap();
        for(char item:strChar){
            if(hash.containsKey(item))
                hash.put(item, hash.get(item)+1);
            else
                hash.put(item, 1);
        }
        for(char key:hash.keySet())
        {
            if(hash.get(key)== 1)
                return key;
        }
        return null;
    }

给定一个数组，里面只有一个数出现了一次，其他都出现了两次。怎么得到这个出现了一次的数？

利用HashSet的元素不能重复，如果有重复的元素，则删除重复元素，如果没有则添加，最后剩下的就是只出现一次的元素

    public void FindNumsAppearOnce(int[] array, int num[]) {
        HashSet set = new HashSet<>();
        for (int i = 0; i length; i++) {
            if (!set.add(array[i])) {
                set.remove(array[i]);
            }
        }
        Iterator iterator = set.iterator();
        num[0] = iterator.next();
    }

用HashMap 保存数组的值，key为数组值，value为布尔型表示是否有重复

    public void FindNumsAppearOnce_2(int[] array, int num[]) {
        HashMap map = new HashMap<>();
        for (int i = 0; i length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i], true);
            } else {
                map.put(array[i], false);
            }
        }
        for (int i = 0; i length; i++) {
            if (map.get(array[i])) {
                num[0] = array[i];
            }
        }
    }

给定一个数组，如果有两个不同数的出现了一次，其他出现了两次，怎么得到这两个数？

利用HashSet的元素不能重复，如果有重复的元素，则删除重复元素，如果没有则添加，最后剩下的就是只出现一次的元素

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        HashSet set = new HashSet<>();
        for (int i = 0; i length; i++) {
            if (!set.add(array[i])) {
                set.remove(array[i]);
            }
        }
        Iterator iterator = set.iterator();
        num1[0] = iterator.next();
        num2[0] = iterator.next();
    }

用HashMap 保存数组的值，key为数组值，value为布尔型表示是否有重复

    public void FindNumsAppearOnce_2(int[] array, int num1[], int num2[]) {
        HashMap map = new HashMap<>();
        for (int i = 0; i 

    public void FindNumsAppearOnce_3(int[] array, int num1[], int num2[]) {
        int diff = 0;
        for (int num : array) diff ^= num;
        // 得到最右一位
        diff &= -diff;
        for (int num : array) {
            if ((num & diff) == 0) num1[0] ^= num;
            else num2[0] ^= num;
        }
    }