java

（一） java基础面试知识点

• java中==和equals和hashCode的区别
  ==是运算符，用于比较两个变量是否相等。equals，是Objec类的方法，用于比较两个对象是否相等，默认Object类的equals方法是比较两个对象的地址;hashcode：对象的初始地址的整数表示，若两个对象hashCode返回相同int数，则equals不一定返回true，若两个对象hashCode返回不同int数，则equals一定返回false。
• int、char、long各占多少字节数
  1字节： byte , boolean，2字节： short , char，4字节： int , float，8字节： long , double 注：1字节(byte)=8位(bits)
• int与integer的区别
  1、Integer是int提供的封装类，而int是Java的基本数据类型； 2、Integer默认值是null，而int默认值是0； 3、声明为Integer的变量需要实例化，而声明为int的变量不需要实例化； 4、Integer是对象，用一个引用指向这个对象，而int是基本类型，直接存储数值。
• 谈谈对java多态的理解
  要有继承,要有重写,父类引用指向子类对象
• String、StringBuffer、StringBuilder区别
  String：适用于少量的字符串操作的情况 StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况 StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况
• 什么是内部类？内部类的作用
  放在一个类的内部的类就叫内部类。 1、内部类可以很好的实现隐藏; 2、内部类拥有外围类的所有元素的访问权限; 3、可实现多重继承； 4、可以避免修改接口而实现同一个类中两种同名方法的调用。
• 抽象类和接口区别
  1、抽象类不能被实例化；2、接口自身不能做任何事情；3、抽象类可以有默认的方法实现，使用extend关键字，子类不是抽象类的话，子类必须实现抽象类所有声明的方法，abstract，可以用public、protected、default；4、接口使用implements关键字，interface，接口方法只能用public
• 抽象类的意义
  捕抓子类共同的特性
• 抽象类是否可以没有方法和属性？
  可以
• 接口的意义
  抽象方法的集合
• 泛型中extends和super的区别
  表示类型的上界，表示参数化类型的可能是T 或是 T的子类 表示类型下界（Java Core中叫超类型限定），表示参数化类型是此类型的超类型（父类型），直至Object
• 父类的静态方法能否被子类重写
  父类的静态方法不能被子类继承，更谈不上重写
• 进程和线程的区别
  一个程序至少一个进程，一个进程至少一个线程。
• final，finally，finalize的区别
  被final修饰的类，就意味着不能再派生出新的子类，不能作为父类而被子类继承。因此一个类不能既被abstract声明，又被final声明。将变量或方法声明为final，可以保证他们在使用的过程中不被修改。被声明为final的变量必须在声明时给出变量的初始值，而在以后的引用中只能读取。被final声明的方法也同样只能使用，不能重载。 finally是在异常处理时提供finally块来执行任何清除操作。不管有没有异常被抛出、捕获，finally块都会被执行。try块中的内容是在无异常时执行到结束。catch块中的内容，是在try块内容发生catch所声明的异常时，跳转到catch块中执行。finally块则是无论异常是否发生，都会执行finally块的内容，所以在代码逻辑中有需要无论发生什么都必须执行的代码，就可以放在finally块中。finalize()是Object里面的一个方法，垃圾回收器在回收某个对象的时候，首先会调用该对象的finalize()方法
• 序列化的方式
  1、Java原生序列化Serializable（Parcelable是android特有的序列化API，它的出现是为了解决Serializable在序列化的过程中消耗资源严重的问题）；2、实现Externalizable接口，继承自Serializable；3、ProtoBuff序列化，语言无关、平台无关、可扩展的序列化
• Serializable 和Parcelable 的区别
  Parcelable需实现序列化、反序列化和描述；Parcelable的性能比Serializable好，在内存开销方面较小，所以在内存间数据传输时推荐使用Parcelable，如activity间传输数据，而Serializable可将数据持久化方便保存，所以在需要保存或网络传输数据时选择Serializable，因为android不同版本Parcelable可能不同，所以不推荐使用Parcelable进行数据持久化
• 静态属性和静态方法是否可以被继承？是否可以被重写？以及原因？
  父类的静态属性和方法可以被子类继承；当父类的引用指向子类时，使用对象调用静态方法或者静态变量，是调用的父类中的方法或者变量。并没有被子类改写；因为静态方法从程序开始运行后就已经分配了内存，所有引用到该方法的对象（父类的对象也好子类的对象也好）所指向的都是同一块内存中的数据，也就是该静态方法。子类中如果定义了相同名称的静态方法，并不会重写，而应该是在内存中又分配了一块给子类的静态方法
• 静态内部类的设计意图；成员内部类、静态内部类、局部内部类和匿名内部类的理解，以及项目中的应用
  1、内部类 内部类，即定义在一个类的内部的类。为什么有内部类呢？ 我们知道，在java中类是单继承的，一个类只能继承另一个具体类或抽象类（可以实现多个接口）。这种设计的目的是因为在多继承中，当多个父类中有重复的属性或者方法时，子类的调用结果会含糊不清，因此用了单继承。而使用内部类的原因是：每个内部类都能独立地继承一个（接口的）实现，所以无论外围类是否已经继承了某个（接口的）实现，对于内部类都没有影响。 在我们程序设计中有时候会存在一些使用接口很难解决的问题，这个时候我们可以利用内部类提供的、可以继承多个具体的或者抽象的类的能力来解决这些程序设计问题。可以这样说，接口只是解决了部分问题，而内部类使得多重继承的解决方案变得更加完整。
2、静态内部类 说静态内部类之前，先了解下成员内部类（非静态的内部类）。 成员内部类 成员内部类也是最普通的内部类，它是外围类的一个成员，所以它可以无限制的访问外围类的所有成员属性和方法，尽管是private的，但是外围类要访问内部类的成员属性和方法则需要通过内部类实例来访问。 在成员内部类中要注意两点： 成员内部类中不能存在任何static的变量和方法； 成员内部类是依附于外围类的，所以只有先创建了外围类才能够创建内部类。 静态内部类 静态内部类与非静态内部类之间存在一个最大的区别：非静态内部类在编译完成之后会隐含地保存着一个引用，该引用是指向创建它的外围内，但是静态内部类却没有。 没有这个引用就意味着： 它的创建是不需要依赖于外围类的。 它不能使用任何外围类的非static成员变量和方法。 其它两种内部类：局部内部类和匿名内部类 局部内部类 局部内部类是嵌套在方法和作用于内的，对于这个类的使用主要是应用与解决比较复杂的问题，想创建一个类来辅助我们的解决方案，到那时又不希望这个类是公共可用的，所以就产生了局部内部类，局部内部类和成员内部类一样被编译，只是它的作用域发生了改变，它只能在该方法和属性中被使用，出了该方法和属性就会失效。 匿名内部类 1、匿名内部类是没有访问修饰符的。 2、new 匿名内部类，这个类首先是要存在的。 3、当所在方法的形参需要被匿名内部类使用，那么这个形参就必须为final。 4、匿名内部类没有明面上的构造方法，编译器会自动生成一个引用外部类的构造方法。
• 闭包和局部内部类的区别
  局部内部类就像是方法里面的一个局部变量一样，是不能有public、protected、private以及static修饰符的。 闭包（Closure）是一种能被调用的对象，它保存了创建它的作用域的信息。JAVA并不能显式地支持闭包，但是在JAVA中，闭包可以通过“接口+内部类”来实现。
• string 转换成 integer的方式及原理
  调用Integer类的parseInt()方法： 1 参数校验，包括字符串和进制；字符串不为null，进制在[2，36]之间. 2 字符串长度不为0，即不为空；否则抛出异常； 3 开始处理字符串 3.1 取字符串第一位字符，根据字符的ASCII码与‘0’的ASCII码比较判断是否是’+'或者‘-’； 3.2 确定正负数后，逐位获得每位字符的int值；（如何实现看下面的分析） 3.3 通过*=和-=对各结果进行拼接； 4 根据是否是负数返回相应的结果。

（二） java深入源码级的面试题（有难度）

• 哪些情况下的对象会被垃圾回收机制处理掉？
  1、虚拟机栈（栈帧中的局部变量区，也叫做局部变量表）中引用的对象） 2、方法区中的类静态属性引用的对象、常量引用的对象。 3、本地方法栈中JNI (Native 方法）引用的对象。
• 讲一下常见编码方式？
  ASCII码、ISO8859-1、GB2312、GBK、UTF-16、UTF-8
• utf-8编码中的中文占几个字节；int型几个字节？
  一个utf8数字占1个字节，一个utf8英文字母占1个字节，少数是汉字每个占用3个字节，多数占用4个字节。
• 静态代理和动态代理的区别，什么场景使用？
• Java的异常体系
• 谈谈你对解析与分派的认识。
• 修改对象A的equals方法的签名，那么使用HashMap存放这个对象实例的时候，会调用哪个equals方法？
  会调用对象的equals方法，如果对象的equals方法没有被重写，equals方法和==都是比较栈内局部变量表中指向堆内存地址值是否相等。
• Java中实现多态的机制是什么？
  Java实现多态有三个必要条件：继承、重定、向上转型，在多态中需要将子类的引用赋值给父类对象，只有这样该引用才能够具备调用父类方法和子类的方法。
• 如何将一个Java对象序列化到文件里？
  ObjectOutputStream.writeObject()负责将指定的流写入，ObjectInputStream.readObject()从指定流读取序列化数据。
• 说说你对Java反射的理解
  开发过程中，经常会遇到某个类的某个成员变量、方法或属性是私有的，或只对系统应用开放，这里就可以利用java的反射机制通过反射来获取所需的私有成员或是方法。 1获取类的Class对象实例 Class clz = Class.forName("com.zhenai.api.Apple"); 2根据Class对象实例获取Constructor对象 Constructor appConstructor = clz.getConstructor(); 3 使用Constructor对象的newInstance方法获取反射类对象 Object appleObj = appConstructor.newInstance(); 4)获取方法的Method对象 Method setPriceMethod = clz.getMethod("setPrice", int.class); 5)利用invoke方法调用方法setPriceMethod.invoke(appleObj, 14); 6)通过getFields()可以获取Class类的属性，但无法获取私有属性，而getDeclaredFields()可以获取到包括私有属性在内的所有属性。带有Declared修饰的方法可以反射到私有的方法，没有Declared修饰的只能用来反射公有的方法，其他如Annotation\Field\Constructor也是如此。
• 说说你对Java注解的理解
  java中的注解类似于生活标签的作用，就是用我们的标签（元数据），对箱标注的物品（对象、方法）进行标注，注入我们定义好的属性值，当我们需要的时候进行获取解析（可以是编译器生成的字节码，或是通过反射获取注解对象）时就可以只得到这个东西代表什么东西，有哪些属性。
• 说说你对依赖注入的理解
  依赖注入：简单来说就是A类中使用了B类的实例时，B对象的构造不是在A类某个方法中初始化的，而是在A类外部初始化之后以B类的对象传进来的。这个过程就是依赖注入。
• 说一下泛型原理，并举例说明
  上界通配符<T extends Integer> 下届通配符<T super String> 方法参数集合通配符List<?>
• Java中String的了解
  1、String类是final型，固String类不能被继承，它的成员方法也都默认为final方法。String对象一旦创建就固定不变了，对String对象的任何改变都不影响到原对象，相关的任何改变操作都会生成新的String对象。 2、String类是通过char数组来保存字符串的，String对equals方法进行了重定，比较的是值相等。 String a = "test"; String b = "test"; String c = new String("test"); a、b和字面上的test都是指向JVM字符串常量池中的"test"对象，他们指向同一个对象。而new关键字一定会产生一个对象test，该对象存储在堆中。所以new String("test")产生了两个对象，保存在栈中的c和保存在堆中的test。而在java中根本就不存在两个完全一模一样的字符串对象，故在堆中的test应该是引用字符串常量池中的test。 String str1 = "abc"; //栈中开辟一块空间存放引用str1，str1指向池中String常量"abc" String str2 = "def"; //栈中开辟一块空间存放引用str2，str2指向池中String常量"def" String str3 = str1 + str2;//栈中开辟一块空间存放引用str3 //str1+str2通过StringBuilder的最后一步toString()方法返回一个新的String对象"abcdef" //会在堆中开辟一块空间存放此对象，引用str3指向堆中的(str1+str2)所返回的新String对象。 System.out.println(str3 == "abcdef");//返回false 因为str3指向堆中的"abcdef"对象，而"abcdef"是字符池中的对象，所以结果为false。JVM对String str="abc"对象放在常量池是在编译时做的，而String str3=str1+str2是在运行时才知道的，new对象也是在运行时才做的。
• String为什么要设计成不可变的？
  1、字符串常量池需要String不可变 因为String设计成不可变，当创建一个String对象时，若此字符串值已经存在于常量池中，则不会创建一个新的对象，而是引用已经存在的对象。如果字符串变量允许必变，会导致各种逻辑错误，如改变一个对象会影响到另一个独立对象。 2、String对象可以缓存hashCode。 字符串的不可变性保证了hash码的唯一性，因此可以缓存String的hashCode，这样不用每次去重新计算哈希码。在进行字符串比较时，可以直接比较hashCode，提高了比较性能； 3、安全性 String被许多java类用来当作参数，如url地址，文件path路径，反射机制所需的Strign参数等，若String可变，将会引起各种安全隐患。
• Object类的equal和hashCode方法重写，为什么？
  因为当把Object对象放到集合中时，通过Equals比较对象，不做处理还是会出现重复的问题，根据hash原则，对象的映射地址是根据算法生成的，因为hash碰撞的存在，即两个不同的对象的hash地址可能一样的情况，这样hash地址一样的情况还需要重写equal方法进行比较。 有两种办法可以解决这种问题，第一个重写Object类中的equals和hashCode方法；第二种就是把对象转换成String再放入到集合中，因为String类源码已经重写了这两个方法。

（三） 数据结构

• 常用数据结构简介
  List子接口
LinkedList
LinkedList实现List接口，允许Null元素。此外，LinkedList提供额外的get、remove、insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用在堆栈（stack）、队列（queue）、或双向队列（deque）中
ArrayList
ArrayList实现了可变大小的数组。它允许所有元素，包括NULL。ArrayList没有同步。 size、isEmpty、get、set方法的运行时间为常数。但add方法开销为分摊的常数，添加n个元素，需要O(n)的时间。其他方法的运行时间为线性。
Vector
Vector非常类似于ArrayList，但Vector是同步的。
Stack
Stack继承自Vector，实现一个后进先出的堆栈。
Set
Set是一种不包含重复元素的Collection，即任意两个元素e1和e2都有e1.equals(e2) = false，Set最多有一个null元素。
Map
Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。
Hashtable
Hashtable继承自Map接口，实现一个key-value的映射的哈希表。任何非空（non-null）的对象都可作为key或者value。Hashtable是同步的。
HashMap
HashMap与Hashtable类似，不同之处在于HashMap是非同步的，并允许null，即null key 和 null value。
WeakHashMap
WeakHashMap是一种改进的HashMap，它对key实行弱引用，如果一个key不再被外部所引用，那么该key就可以被GC回收掉了。

• 并发集合了解哪些？
  oncurrentHashMap：把整个Map划分成几个片段，只对相关的几个片段上锁，同时允许多进程访问其他未上锁的片段。
CopyOnWriteArrayList；允许多个线程以非同步的方式读，当有线程写的时候它会将这个List复制一个副本给它。如果在读多写少这种对并发集合有利的条件下使用并发集合，这会比使用同步集合更具有可伸缩性。
CopyOnWriteHashSet

• 列举java的集合以及集合之间的继承关系

image
从上面的集合框架图可以看出：Java集合框架类主要包含两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值映射。 Collection接口又有3种类型的子类，List、Set、Queue，再下边是一些抽象类，最后是具体的实现类，常用的有ArrayList、LinkedLis、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

• 集合类以及集合框架
  同上

• 容器类介绍以及之间的区别（容器类估计很多人没听这个词，Java容器主要可以划分为4个部分：List列表、Set集合、Map映射、工具类（Iterator迭代器、Enumeration枚举类、Arrays和Collections），具体的可以看看这篇博文 Java容器类）
  Array：效率高，容量固定无法动态改变。并且length只能告诉容量，而不能告诉长度。 Collection、List、Set和Map ![image](https://img.haomeiwen.com/i15843920/1fa6b73e9f241d89.png?imageMogr2/auto-orient/strip|imageView2/2/w/174/format/webp) Collection、List、Set和Map都是接口 List下最主要有链表LinkedList和数组，数组分为ArrayList和Vector，两者的区别是Vector是支持线程同步的，适合多线程使用。

• List,Set,Map的区别
  List集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，例如通过list.get(i)的方式来获取集合中的元素。 Map中每一个元素包含一个键和一个值，成对出现，键对象不可以重复，值对象可以重复。 Set集合中的元素不按照特定的方式排序，并且没有重复对象，但它的实现类能对集合中的对象按照特定的方式进行排序，例如TreeSet类，可以按照默认顺序，也可以通过实现java.util.Comparator<Type>接口来自定义排序顺序。

• List和Map的实现方式以及存储方式

List list = new ArrayList(); Map<Object,Object> map = new HashMap<Object,Object>(); List存储的元素容器是个有序的可以索引到元素的容器，并且里边的元素可以重复。 Map存储的是键值对，键不可以重复。

• HashMap的实现原理

HashMap的存储结构是由数组和链表共同完成的。

image
HashMap基本原理： 1、首先判断key是否为Null，如果为Null，直接查询Entry[0]，如果不是NULL，先计算key的hashcode，然后经过两次Hash。得到hash值，这里的hash特征值是一个int值。 2、根据得到的hash特征值，对Entry[]数组的长度length取于，得到的就是Entry数组的index。 3、找到了对应的数组，就找到了对应的链表，然后按照链表的操作对value进行插入、删除、查询等操作。

• HashMap数据结构？

HashMap是由数组和链表存储数据的。

• HashMap源码理解

image

HashMap里边也包含一些优化的方面，比如：Entry[]的长度一定后，随着map里边的数据越来越长，这样同一个index链会很长，会不会影响性能？HashMap里边设置了一个负载极限，随着map的size越来越大，Entry[]会以一定的规则加长长度。

HashMap默认的负载极限是0.75，表明该hash表的3/4已经被填满时，hash表会发生rehashing。

• HashMap如何put数据（从HashMap源码角度讲解）？

image

首先判断key是否为null，key为null则调用putForNullKey()方法，该方法会直接访问Entry[0]，如果key不为null，则将key进行两次hash算法，得到一个整型值，该值与Entry[]数组的length进行取于，得到的余数即是数组的index，Entry[index] = value

• HashMap怎么手写实现？

https://www.jianshu.com/p/b638f19aeb64

• ConcurrentHashMap的实现原理

JDK1.7分析

ConcurrentHashMap采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构。

其中包含两个静态内部类Segment和HashEntry。

1、Segment继承ReentrantLock用来充当锁的角色，每个Segment对象守护每个散列映射表的若干个桶。

2、HashEntry用来封装映射表的键值对

3、每个桶是由若干个HashEntry对象链接起来的链表。

一个ConcurrentHashMap是由若干个Segment对象组成的数组。

image

JDK1.8分析

1.8的实现已经抛弃了Segment分段锁的机制，利用CAS+Synchronized来保证并发更新的安全，底层采用数组+链表+红黑树的存储结构。

image

• ArrayMap和HashMap的对比

ArrayMap

image

ArrayMap利用两个数组，mHashes用来保存每一个key的hash值，mArray大小为mHashes的两倍，依次存储key和value。

查询的时候使用二分查找。

1、查找效率：

HashMap因为其根据hashcode的值直接计算index，所以其查找效率是随着数组长度的增加而增大。

ArrayMap使用的是二分法查找，所以当数组长度每增加一倍，就需要多进行一次判断，效率下降。

2、扩容数量：

HashMap的初始值16个长度，每次扩容的时候，直接申请双倍的数组空间。

ArrayMap每次扩容的时候，如果size长度大于8时申请size*1.5个长度，大于4，小于8时申请8个，小于4个时，申请4个。

这样比较ArrayMap其实是申请了更少的内存空间，但扩容的频率会更高。因此，如果当数据量比较大时，还是用HashMap比较合适，因为扩容次数要比ArrayMap少很多。
3、扩容效率：

HashMap每次扩容的时候重新计算每个数组成员的位置，然后放到新的位置。

ArrayMap则直接使用System.arrayCopy。

所以效率上肯定是ArrayMap更占优势。

4、内存耗费：

以ArrayMap采用了一种独特的方式，能够重复的利用因为数据扩容而遗留下来的数组空间，方便下一个ArrayMap使用，而HashMap没有这样的设计。

综上所述：数据量较小，并且频繁使用Map的时候可以使用ArrayMap；数据量较大时，使用HashMap。

• HashTable实现原理

HashTable实际与HashMap的结构一样，都是数组和链表共同实现。

• TreeMap具体实现

TreeMap内部实现是红黑树

红黑树是特殊的二叉查找树，又名R-B树，由于红黑树是特殊的二叉查找树，即红黑树具有二叉查找树的特性，而且红黑树还有以下特性：

1、每个节点要么是红色，要么是黑色。

2、根节点是黑色。

3、每个叶子节点是黑色，并且为空节点。

4、如果一个节点是红色，则它的子节点必须是黑色。

5、从一个节点到该节点的子孙节点的所有路径包含相同数目的黑节点。

image

上图：

左旋：以X为节点左旋，则Y为X的父节点，Y的左叶子节点变化为X的右叶子节点。

右旋：以Y为节点右旋，则X为Y的父节点，X的右叶子节点变化为Y的左叶子节点。

• HashMap和HashTable的区别

1、HashMap是非同步的，没有对读写等操作进行锁保护，所以是线程不安全的，在多线程场景下会出现数据不一致的问题。而HashTable是同步的，所有操作都进行了锁（synchronize）保护，在多线程下没有安全访问的问题。但锁保护也是有代价的，会对读写的效率产生较大的影响。

2、HashMap结构中，是允许保存null的，Entry.key和Entry.value都可以为null。但HashTable不允许保存null的。

3、HashMap的迭代器（Iterator）是fail-fast迭代器，但HashTable的迭代器（enumerator）不是fail-fast迭代器。如果其他线程对HashMap进行添加或删除元素，将会抛出ConcurrentModificationException异常，但迭代器本身的remove方法移除元素则不会抛出异常。这同样也是Enumerator和Iterator的区别。

• HashMap与HashSet的区别

HashSet是对HashMap的简单包装，对HashSet函数的调用，都会转化成合适的HashMap。

image

• HashSet与HashMap怎么判断集合元素重复？

HashSet不能添加重复的元素，当调用add方法的时候，首先会调用Object的hashCode方法判断hashCode是否已存在，不存在则直接插入元素；如果一样，则需要调用Object的equals方法，判断是否返回true，如果返回true，则说明元素已存在，如果返回false则插入元素。

HashMap同样判断对象的hashCode和equals方法，不同的是HashMap遇到相同的key，会将value的值替换成新的value值。

• 集合Set实现Hash怎么防止碰撞

对象Hash的前提是实现hashCode()和equals()方法，那么hashCode()的作用是保证对象返回唯一的hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。

1、开放地址法。

2、再哈希法。

3、链地址法。

4、建立一个公共溢出区。

• ArrayList和LinkedList的区别，以及应用场景

1、ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2、对于随机访问的get和set，ArrayList较优于LinkedList，因为LinkedList需要移动指针。

3、对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList需要移动数据。

• 数组和链表的区别

内存存储：

1、数组从栈中分配空间，对程序员方便快速，自由度小。

2、链表从堆中分配内存，自由度大，但申请管理比较麻烦。

逻辑结构：

1、数组必须事先定义固定的长度（元素个数），不能适应数据的增减情况（数据插入、删除比较麻烦）。当数据增加时，可能会超出数组的最大空间（越界）；当数组减少时，造成内存浪费。

2、链表动态的进行存储分配，可以使用数据动态的增减情况（数据插入删除简单）（数组插入、删除数据项时需要移动其他项），但链表查询元素时需要遍历整个链表。

• 二叉树的深度优先遍历和广度优先遍历的具体实现

二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归通用做法是采用队列。

深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。深度优先遍历包含：先序遍历、中序遍历、后续遍历

先序遍历：对任一子树，先访问根，然后遍历其左子树，再遍历右子树。

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。

后续遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

广度优先遍历：又叫层次遍历，从上到下对每一层一次访问，在每一层中，从左往右（也可以从右往左）访问节点，访问完一层就进入下一层，直到没有节点可以终止访问。

• 堆的结构

堆是一个完整的二叉树，在这颗树中，所有父节点都满足大于等于其子节点的堆叫大根堆，所有父节点都满足小于等于其子节点的堆叫小根堆。堆虽然是一棵树，但通常存放在一个数组中，父节点和子节点的父子关系通过数组下标来确定

image

• 堆和树的区别

堆是一类特殊的树，堆的通用特点就是父节点会大于或小于所有的子节点。

image

• 堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？

栈内存：在函数中定义的基本类型的变量和对象的引用变量都是在函数的栈内存中分配。

堆内存：堆内存存放的是由new创建的数组或对象。

堆是用来存放对象的，栈是用来存放执行程序的。

• 什么是深拷贝和浅拷贝

浅拷贝：浅拷贝就是按位拷贝对象，它会创建一个新的对象，这个对象有着原始属性值的一份精确拷贝。如果属性是基本数据类型，拷贝的就是基本数据类型的值；如果属性是内存地址（引用类型），拷贝的就是内存地址，因此，如果其中一个对象改变了这个地址，就会影响到另一个对象。

深拷贝：深拷贝会拷贝所有的属性，并拷贝属性指向的动态分派的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝。深拷贝相比于浅拷贝速度要慢，花销较大。

对象的clone方法默认是浅拷贝，若想实现深拷贝需要重写clone方法实现属性对象的拷贝。

• 手写链表逆序代码

http://blog.csdn.net/u012571415/article/details/46955535

• 讲一下对树，B+树的理解

https://www.jianshu.com/p/db226e0196b4

• 讲一下对图的理解

图由定点的有穷非空集合和定点之间边的集合组成，通常表示为：G(V,E)，其中，G表示图，V是图G中定点的集合，E是图G中边的集合。

图分为有向图和无向图。

• 判断单链表成环与否？

image

• 链表翻转（即：翻转一个单项链表）

image

• 合并多个单有序链表（假设都是递增的）

大体思路：使用递归

1、判断L1、L2是否为空。

2、创建一个头指针。

3、判断当前L1、L2指向的节点值的大小，根据结果，让头指针指向节点值小的节点，并让这个节点往下走一步，作为递归函数的参数传入，返回的就是新的两个值的比较结果，则新的比较结果放入头节点的下一个节点。

4、返回头节点。

image

（四） 线程、多线程和线程池

• 开启线程的三种方式？

Java中创建线程主要有三种方式

继承Thread类创建线程类。

通过Runnable接口创建线程类。

通过Callable和Future创建线程。

• 线程和进程的区别？

（1）、进程是资源分配的最小单位，线程是程序执行的最小单位。

（2）、进程有自己独立的地址空间，每启动一个进程，系统会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段。而线程是共享进程中的数据的，使用相同的地址空间，因此，CPU在切换一个线程的开销比进程要小的多。

（3）、线程之间通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信方式IPC进行。

（4）、多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程就死掉了，而一个进程死掉，不会对其他进程造成影响，因为进程有自己独立的地址空间。

• 为什么要有线程，而不是仅仅用进程？

进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。

进程在执行过程中如果遇到阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖与输入的数据，也将无法执行。

• run()和start()方法区别

start:

用start方法来启动线程，真正实现了多线程运行，这无需等待run方法体代码执行完毕而直接继续执行下面的代码。通过调用Thread类的start()方法来启动一个线程，这时线程就处于就绪（可运行）状态，并没有运行，一旦得到CPU时间片，就开始执行run()方法，这里的run()方法称为线程体，它包含了要执行这个线程的内容，Run方法运行结束，这个线程随即终止。

run:

run()方法只是类的一个普通方法而已，如果直接调用run()方法，程序依然只有一个主线程在运行，其程序执行路径仍然只有一条，还是要顺序执行，还是要等待run方法体执行完毕才能执行下面的代码，这样就没有达到写线程的目的。

总结：

调用start()方法可以启动线程，调用run()方法只是类中的一个普通方法，还是会只在主线程中运行。

start()方法启动线程，会自动调用run()方法，这是由jvm内存机制规定的。并且run()方法必须是public访问权限，返回类型必须是void。

• 如何控制某个方法允许并发访问线程的个数？

信号量（Semaphore），有时也被称为信号灯，在多线程环境下使用的一种设施，它负责协调各个线程，以保证他们能够正确合理的使用公共资源。

image

• 在Java中wait和seelp方法的不同；

seelp()方法属于Thread类，wait()方法属于Object类。

seelp()方法导致了程序暂停执行指定的时间，让出CPU给其他线程，但它的监控状态依然保持着，当指定的时间到了，又会恢复运行状态。

在调用seelp()方法时，线程不会释放对象锁。

而调用wait()方法时，线程会放弃对象锁，进入此对象的等待锁定池，只有针对此对象调用notify()方法后本线程才进入对象锁定池，准备获取对象锁进入运行状态。

• 谈谈wait/notify关键字的理解

wait()该方法将当前线程置入休眠状态，直到接到通知或被中断为止。

notify()方法用来通知可能等待该对象的对象锁的其他线程。如果有多个线程等待，则线程规划器任意挑出其中一个线程的wait()状态的线程来发出通知，并使它等待获取该对象的对象锁。（notify后该线程不会马上释放对象锁，wait所在的线程也不会马上获取到该对象锁，要等到程序退出synchronized代码块后，当前线程才会释放对象锁，wait所在的线程也才可以获取对象锁。）

• 什么导致线程阻塞？

（1）、线程执行了seelp()方法，当前线程放弃CPU，睡眠一段时间，然后再恢复执行。

（2）、线程执行一段同步代码，但是尚且无法获得相关的同步锁，只能进入阻塞状态，等到获得了同步锁，才能回复执行。

（3）、线程执行了一个对象的wait()方法，直接进入阻塞状态，等待其他线程执行notify()或notifyAll()方法。

（4）、线程执行某些IO操作，因等待相关资源而进入等待状态。比如，监听System.in，但是尚且没有收到键盘的输入，则进入阻塞状态。

• 线程如何关闭？

（1）、使用退出标志，使线程正常退出，也就是当run方法完成后线程终止。

（2）、使用stop方法强行终止线程（这个方法不推荐使用，因为stop和suspend、resume一样，也可能发生不可预料的结果）。

（3）、使用interrupt方法中断线程。

• 讲一下java中的同步的方法

（1）、同步方法

即有synchronized关键字修饰的方法。

image

（2）、同步代码块

即有synchronized关键字修饰的代码块。

被该关键字修饰的代码块会自动被加上内置锁，从而实现同步。

image

（3）、使用特殊域变量（volatile）实现线程同步。

a、volatile关键字为域变量提供了一种免锁机制。

b、使用volatile修饰域相当于告诉虚拟机该域可能被其他线程更新。

c、因此每次使用该域变量就需要重新计算，而不是使用寄存器中的值。

d、volatile不会提供任何原子操作，它也不能用来修饰final类型的变量。

（4）、使用重入锁实现线程同步。

image

注：关于Lock对象和synchronized关键字的选择：

a、最好两个都不用，使用一种java.util.concurrent包提供的机制，能够帮助用户处理所有与锁有关的代码。

b、如果synchronized关键字能够满足用户的需求，就用synchronized，因为它能简化代码。

c、如果需要更高级的功能，就用ReentrantLock类，此时需要注意及时释放锁，否则会出现死锁，通常在finally代码释放锁。

（5）、使用局部变量实现线程同步。

image

注：ThreadLocal与同步机制

a、ThreadLocal与同步机制都是为了解决多线程中相同变量的访问冲突问题。

b、前者采用以空间换时间的方法，后者采用以时间换空间的的方法。

• 数据一致性如何保证？

https://www.cnblogs.com/jiumao/p/7136631.html

• 如何保证线程安全？

（1）、互斥同步：同步是指多个线程并发访问共享数据时，保证共享数据在同一个时刻只能被一个线程使用。而互斥是实现同步的一种手段，临界区、互斥量、信号量都是主要的互斥实现方式。互斥是方法，同步是目的。

（2）、非阻塞同步：互斥同步最主要的问题就是进行线程阻塞和唤醒带来的性能问题，因此，这种同步也称为阻塞同步。非阻塞同步是先进行操作，如果没有其他线程争用共享数据，则操作成功；如果数据有争用，产生了冲突，则采取其他的补偿措施。

（3）、无同步方案：对于一个方法本来就不涉及共享数据，那自然不需要同步措施来保证正确性。

a、可重入代码：在代码执行的任何时候中断它，转而去执行另一端代码，控制权返回后，原来的程序不会出现任何错误。

b、线程本地存储：共享数据的代码是否在同一线程中执行，如生产者-消费者的模式。

• 如何实现线程同步？

（1）、同步方法

使用synchronized关键字修饰的方法

（2）、同步代码块

使用synchronized关键字修饰的代码块。

（3）、使用特殊域变量（volatile）。

（4）、使用重用锁实现线程同步。

（5）、使用局部变量实现线程同步。

• 两个进程同时要求写或者读，能不能实现？如何防止进程的同步？

允许多个线程读取操作，不允许读操作和写操作同时执行，不允许多个线程写操作。

控制访问数量即可防止进程同步，java并发库Semaphore可以完成信号量的控制，Semaphore可以控制某个资源可被同时访问的数量，通过acquire()获取一个许可，如果没有就等待，而release()释放一个许可。

• 线程间操作List

（1）、使用Collections.synchronizedList()构建list

（2）、操作list的方法增加同步锁。

因为Collections.synchronizedList()构建的list只针对list的add()、poll()等方法做了线程同步，在多线程中直接使用方法会同步，但是在操作list时，add()、poll()方法之前不能保证obj是否被其他线程操作过。

• Java中对象的生命周期

java对象的生命周期包括：创建阶段、应用阶段、不可见阶段、不可达阶段、收集阶段、终结阶段、对象空间重新分配阶段。

• Synchronized用法

Java中的每个对象都可以作为锁。

普通同步方法，锁是当前实例对象。

静态同步方法，锁是当前类的class对象。

同步代码块，锁是括号中的对象。

• synchronize的原理

每个对象有一个监视器锁（monitor）。当monitor被占用时，就会处于锁定的状态，线程执行monitorenter指令时尝试获取monitor的所有权。

http://www.cnblogs.com/paddix/p/5367116.html

• 谈谈对Synchronized关键字，类锁，方法锁，重入锁的理解

Synchronized关键字作用：让方法或代码块的操作具有原子性，从而解决多线程共享资源的问题。

类锁：类锁是锁住整个类，当多线程声明这个类的对象时将会被阻塞，直到拥有这个类锁的对象被销毁或主动释放了类锁，这个时候在被阻塞的线程中挑选出一个占有该类锁，声明该类的对象。其他线程继续被阻塞住。

方法锁：修饰当前方法，进入同步代码块前需要先获得该实例的锁

重入锁：重进入是指任意线程在获取到锁之后，再次获取该锁而不会被该锁阻塞。

• static synchronized 方法的多线程访问和作用

当synchronized修饰一个静态方法时，多线程下，获取的是类锁（即class本身，注意：不是实例），作用范围是整个静态方法，作用的对象是这个类所有的对象。

注：static说明了该类的一个静态资源，不管new了多少对象，只有一份，所以对该类的所有对象都加了锁。

• 同一个类里面两个synchronized方法，两个线程同时访问的问题

synchronized方法增加了对象锁，当一个线程获取到该对象锁是访问其中一个方法，另外一个线程是获取不到该对象锁的，也就是另外一个线程是没有办法访问synchronized方法的，只有一个线程一个线程的访问。

• volatile的原理

可见性：

（1）、修改volatile变量时会强制将修改后的值刷新主内存中。

（2）、修改volatile变量后会导致其他线程工作内存中对应的变量值失效。因此，再读取该变量值的时候就需要重新从主内存中读取。

有序性：Lock前缀指令相当于一个内存屏障（也叫内存栅栏），它确保指令重排序时不会把其后边的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面。即在执行到内存屏障这句指令时，在它前面的操作已经全部完成。

内存屏障：

• 谈谈volatile关键字的用法

image

• 谈谈volatile关键字的作用

保持内存可见性，防止指令重排序。

• 谈谈NIO的理解

Java NIO是一种新式的IO标准，与之前普通的IO操作的工作方式不同。标准的IO基于字节流，和字符流操作，而NIO是基于通道（Channel）和缓冲区（Buffer）进行操作的，数据总是从通道读取到缓冲区中，或者从缓冲区写入通道也类似。

• synchronized 和volatile 关键字的区别

（1）、volatile本质是在告诉jvm当前变量在寄存器（工作内存）中的值是不确定的，需要从主内存中读取；synchronized则是锁定当前变量 ，只有当前线程可以访问该变量，其他线程被阻塞住。

（2）、volatile仅能使用在变量级别；synchronized则可以使用在变量、方法和类的级别上。

（3）、volatile仅能实现变量的修改可见性，不能保证原子性；synchronized则可以保证变量的修改可见性和原子性。

（4）、volatile不会造成线程阻塞；synchronized可能会造成线程阻塞。

（5）、volatile标记的变量不会被编译器优化；synchronized标记的变量可以被编译器优化。

• synchronized与Lock的区别

image

• ReentrantLock 、synchronized和volatile比较

synchronized互斥锁，即操作互斥，并发线程过来，串行获得锁，串行执行代码。就像一个房间一把钥匙一样，一个人进去后，下个人必须等第一个人出来得到钥匙才能进入。如果代码写的不好容易出现死锁。

ReentrantLock可重入锁，和同步锁功能类似，不过需要显式的创建和销毁。

特点：

（1）、ReentrantLock有tryLock方法，如果锁被其他线程特有，返回false，可避免形成死锁。

（2）、创建时可自定义是否抢占。

（3）、ReentrantReadWriteLock，用于读多，写少，且读不需要互斥的场景，大大提高了性能。

volatile，翻译过来是易变的。只保证同一变量在多线程中的可见性。

（1）、它确保指令重排序时不会把后面的指令排在内存屏障之前，也不会把前面的指令排在内存屏障之后；即在执行到内存屏障这句指令时，前面的指令都已经执行完毕。

（2）、它会强制将对缓存的修改立即写入主内存。

（3）、如果是写操作，它会导致其他CPU中对应的缓存行无效。

• ReentrantLock的内部实现

ReentrantLock支持两种获取锁的方式，一种是公平模型，一种非公平模型。

image

公平模型：

（1）、初始化时，state是0，表示无人抢占了打水权，这个时候村民A打水（线程A请求锁）

image

（2）、线程A获取了锁，把state的原子性+1，这个时候的state是1，A线程继续执行其他任务，然后村民B来打水（线程B请求锁），线程B无法获取锁，生成节点进行排队。

image

（3）、初始化的时候会生成一个空的头结点，然后才是B线程节点，这个时候，如果线程A又请求锁，是不需要排队的，否则就会直接死锁。当A再次请求打水的时候，相当于同一家人来了，是有特权的。

image

（4）、这就是重入锁，就是一个线程获取了锁之后，再次去获取同一个锁，这个时候仅仅把状态值进行累加。如果A释放了一次锁，就变成下图：

image

仅仅是把状态值减一，只有线程A把此锁全部释放了，状态值减为0了，其他线程才有机会获得此锁。当A释放掉此锁，state恢复0，然后通知队列唤醒B线程节点，使B可以再次竞争锁。当然如果B线程后边还有C线程，C线程继续休眠，除非线程B执行完，通知C线程。注意：当一个线程节点被唤醒然后取的锁，对应节点会从队列中删除。

非公平锁模式：

当线程A执行完成，要唤醒B线程是需要时间的，而且线程B醒来后还要再次竞争锁，所以如果在切换过程当中，来了一个线程C，那么线程C是有可能获取到锁的，如果线程C获取到了锁，B只能继续休眠。

• lock原理

实现Lock接口的基本思想，必须满足两个条件。

（1）、一个表示锁状态的变量，（我们假设0表示没有线程获取锁，1表示已有线程占据锁），该变量必须声明为volatile。

（2）、另一个是队列，队列中的节点表示因未能获取锁而阻塞的线程。

• 死锁的四个必要条件？

（1）、互斥条件：一个资源每次只能被一个进程使用。

（2）、请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3）、不剥夺条件：进程已获得资源，在未使用完之前，不能强行剥夺。

（4）、循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

• 怎么避免死锁？

（1）、加锁顺序（线程按照一定的顺序加锁）

（2）、加锁时限（线程尝试获取锁的时候加一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）。

（3）、死锁检测。

• 对象锁和类锁是否会互相影响？

不会相互影响。

类锁和对象锁不是同一个东西，一个是类的class对象的锁，一个是类的实例的锁。也就是说：一个线程访问静态synchronized的时候，允许一个线程访问对象的实例synchronized方法。反过来也是成立的，因为他们需要的锁是不同的。

• 什么是线程池，如何使用?

线程池就是容纳多个线程的容器，其中的线程可以反复使用，省去频繁创建线程对象的操作，无需反复创建线程而消耗过多的资源。

Java四种线程池：

newCacheThreadPool创建一个可缓存线程池，如果线程池长度超过了处理需要，可灵活回收空闲线程，若无可回收，则新建线程。

newFixedThreadPool创建一个定长线程池，可控制线程最大并发数，超出的线程会在队列中等待。

newScheduledThreadPool创建一个定长线程池，支持定时及周期性任务执行。

newSingleThreadExecutor创建一个单线程化的线程池，它只会用唯一的工作线程来执行任务，保证所有的任务按照指定的顺序（FIFO，LIFO，优先级）执行。

• Java的并发、多线程、线程模型

线程和锁的模型是java语言的并发模型。

• 谈谈对多线程的理解

并行：指同一时刻，有多条指令在多个处理器上同时执行。

并发：指在同一时刻，只有一条指令执行，但多个进程指令被快速轮换执行，使得在宏观上具有多个进程同时执行的效果。

从逻辑角度来看，多线程存在于一个应用程序中，让一个应用程序中可以有多个执行部分同时执行，但操作系统无需将多个线程看作多个独立的应用，对多线程实现调度和管理及资源分配。线程的调度和分配由进程本身负责完成。

• 多线程有什么要注意的问题？

并发问题，安全问题，效率问题

• 谈谈你对并发编程的理解并举例说明

编写并发程序会在代码上增加额外的开销。

正确的并发是非常复杂的即使对于很简单的问题。

并发中的缺陷因为不易重现也不容易被发现。

并发往往需要对设计策略从根本上进行修改。

生产者和消费者模型。

• 谈谈你对多线程同步机制的理解？

线程同步是为了线程安全，所谓线程安全是指多个线程访问同一资源时，有可能产生数据不一致问题，导致线程访问的资源并不是安全的。如果多线程程序运行结果和单线程程序运行结果一样，且相关变量的值和预期值一样，则是线程安全的。

Java中与线程同步相关的关键字/类包括：

volatile、synchronized、Lock、Atomiclnteger等concurrent包下的原子类等。

• 如何保证多线程读写文件的安全？

多线程文件并发安全其实就是在考察线程并发安全，最普通的方式就是使用wait/notify、Condition、 synchronized、ReentrantLock等方式，这些方式默认都是排他操作，也就是默认情况下，同一时刻只有一个线程可以对文件进行操作，所以可以保证并发文件操作的安全性，但是并发读数量远多于写数量的情况下，性能却不那么好。因此，推荐使用ReadWriteLock的实现类ReentrantReadWriteLock，它也是lock的一种实现，允许多个读线程同时访问，不允许写线程和读线程、写线程和写线程同时访问。所以相对于排他锁来说提高了并发效率。ReentrantReadWriteLock读写锁里边维护了两个继承自lock的锁，一个用于读操作（ReadLock），一个用于写操作（WriteLock）。

• 多线程断点续传原理

我们要在下载行为出现中断的时候，记录下中断的位置信息，在下次下载的行为中读取该位置信息，有了这个位置信息，直接从记录的这个位置开始下载内容，而不需要从头开始下载。

• 断点续传的实现

下载过程出现中断，抛出异常，记录当前位置，下次下载从该位置开始下载。

• 线程之间的通信

（五）并发编程有关知识点

• java线程安全总结
• 深入理解java内存模型系列文章
• 一张图让你看懂JAVA线程间的状态转换
• 锁机制：synchronized、Lock、Condition
• Java 中的锁
• Java并发编程：Thread类的使用
• Java多线程编程总结
• Java并发编程的总结与思考
• Java并发编程实战-----synchronized
• 深入分析ConcurrentHashMap
• 23种设计模式
  1、工厂模式：pizza产地有两个：伦敦和纽约，三种类型的pizza：chesse,pepper,greak
2、单例模式：预加载、懒加载
3、生成器模式：构建生成一台电脑的步骤
4、原型模式：本质就是clone
5、适配器模式：类适配器模式、对象适配器模式、接口适配器模式
6、装饰者模式：装饰者和被装饰者之间必须是一样的类型,也就是要有共同的超类。在这里应用继承并不是实现方法的复制,而是实现类型的匹配。因为装饰者和被装饰者是同一个类型,因此装饰者可以取代被装饰者,这样就使被装饰者拥有了装饰者独有的行为。
7、代理模式
8、外观模式
9、桥接模式
10、组合模式
11、享元模式
12、策略模式
13、模板模式
14、观察者模式
15、迭代器模式
16、责任链模式
17、命令模式
18、状态模式
19、备忘录模式
20、访问者模式
21、中介者模式
22、抽象工厂模式
23、解释器模式。