java问题笔记

朱雀 2022-10-23 12:55 208阅读 0赞

**目录**

0、时间复杂度大小关系？

1、自动装箱和拆箱怎么理解？

2、如何理解重写和重载？

3、equals与==的区别？

4、hashcode相等值也想等吗？

5、String、String StringBuﬀer 和 StringBuilder 的区别是什么？

6、ArrayList 和 linkedList 的区别？

7、HashMap 和 HashTable 的区别？

8、Collection 包结构，与 Collections 的区别

9、Java 的四种引用，强弱软虚

10、a=a+b 与 a+=b 有什么区别吗?

11、try catch ﬁnally，try 里有 return，ﬁnally 还执行么？

12、Java 线程实现/创建方式

13、线程池作用、原理？

14.Java 常用算法

15、Spring Beans

16、什么是Java虚拟机？

17、JDK和JRE的区别是什么？

18、"static"关键字是什么意思？Java中是否可以覆盖一个private或者是static的方法？

19、Java支持的基本数据类型有哪些？什么是自动拆装箱？

20、Java支持多继承么？如果不支持，如何实现?

21、什么是值传递和引用传递？java中是值传递还是引用传递，还是都有?

22、接口和抽象类的区别是什么?

23、构造器（constructor）是否可被重写（override）?

24、Math.round(11.5) 等于多少? Math.round(-11.5)等于多少?

25、HashMap的工作原理是什么?

26、HashMap与HashTable的区别是什么?

27、CorrentHashMap的工作原理?

28、HashSet和HashMap 区别？

29、Hash1.7是基于数组和链表实现的，为什么不用双链表？HashMap1.8中引入红黑树的原因是？为什么要用红黑树而不是平衡二叉树？

30、遍历一个List有哪些不同的方式？

31、fail-fast与fail-safe有什么区别？

32、Array和ArrayList有何区别？什么时候更适合用Array？

33、哪些集合类提供对元素的随机访问？

34、LinkedHashMap 的实现原理?

35、LinkedList和ArrayList的区别是什么?

36、什么是线程？进程和线程的关系是什么？

37、Thread 类中的start() 和 run() 方法有什么区别？

38、什么是线程安全?

39、Java中有哪几种锁?

40、ThreadLocal理解

41、为什么wait, notify 和 notifyAll这些方法不在thread类里面?

42、平衡二叉树数据结构

43、红黑树数据结构

--------------------

## 0、时间复杂度大小关系？ ##

o(1)<o(logn)<o(n)<o(blogn)<o(n2)

## 1、自动装箱和拆箱怎么理解？ ##

valueof  
将基础数据类型转换为包装类型：  
装箱：Integer.valueOf(j) Integer i= 10  
拆箱：Integer.intValue int j = i  
引申：  
问题一：  
Integer i1 = 100;  
Integer i2 = 100;  
Integer i3 = 200;  
Integer i4 = 200;  
i1 == i2 ---> true  
i3 == i4 ---> false  
原因：  
public static Integer valueOf(int i) \{  
if (i >= IntegerCache.low && i <= IntegerCache.high)  
return IntegerCache.cache\[i + (-IntegerCache.low)\];  
return new Integer(i);  
\}  
数值在\[-128,127\]之间，便返回指向IntegerCache.cache中已经存在的对象的引用；否则创建一个新的Integer对象。  
  
问题二：  
Double i1 = 100.0;  
Double i2 = 100.0;  
Double i3 = 200.0;  
Double i4 = 200.0;  
  
i1==i2 ---> false  
i3==i4 ---> false  
  
原因：  
public static Double valueOf(String s) throws NumberFormatException \{  
return new Double(parseDouble(s));  
\}  
每次都是一个新对象  
  
总结：Integer、Short、Byte、Character、Long这几个类的valueOf方法的实现是类似的。  
Double、Float的valueOf方法的实现是类似的。  
  
问题三：  
Boolean i1 = false;  
Boolean i2 = false;  
Boolean i3 = true;  
Boolean i4 = true;  
i1==i2 --- true  
i3==i4 --- true  
  
原因：  
public static Boolean valueOf(boolean b) \{  
return (b ? TRUE : FALSE);  
\}  
比较的是同一个静态成员  
  
问题四：  
谈谈  
Integer i = new Integer(xxx)  
和  
Integer i =xxx;  
这两种方式的区别  
  
答：  
Integer i = new Integer(xxx) 不会触发自动装箱流程  
Integer i =xxx; 会触发，一般情况下，这种效率和资源占用更优

问题五：  
Integer a = 1;  
Integer b = 2;  
Integer c = 3;  
Integer d = 3;  
Integer e = 321;  
Integer f = 321;  
Long g = 3L;  
Long h = 2L;  
  
c==(a+b) --- true --- 算数运算触发自动拆箱，比较的是数值  
c.equals(a+b) --- true --- 先拆箱后装箱，再比较  
g==(a+b) --- true --- 先拆箱后装箱，再比较  
g.equals(a+b) --- false --- 先拆箱后装箱，但装箱是调用的Integer.valueOf  
g.equals(a+h)) --- true --- 先拆箱后装箱，但装箱是调用的Long.valueOf

## 2、如何理解重写和重载？ ##

重写：子类复写父类方法 方法名，参数列表，返回类都一致，访问修饰权限不能少于父类  
重写方法一定不能抛出新的检查异常或者比被重写方法申明更加宽泛的检查型异常  
重载：同一个类中，同名的方法，参数列表不同

## 3、equals与==的区别？ ##

== 比较的是变量(栈)内存中存放的对象的(堆)内存地址，即是否是指相同一个对象  
equals 用来比较的是两个对象的内容是否相等

## 4、hashcode相等值也想等吗？ ##

hashCode：它返回的就是根据对象的内存地址换算出的一个值。  
因此hashcode相等，hash值不一定相等，但 值相等，hashcode一定相等  
可以参考 hashmap的 数据结构 对照了解下

## 5、String、String StringBuﬀer 和 StringBuilder 的区别是什么？ ##

String 是只读字符串，它并不是基本数据类型，而是一个对象。  
从底层源码来看是一个ﬁnal 类型的字符数组，所引用的字符串不能被改变，一经定义，无法再增删改。每次对 String 的操作都会生成新的 String 对象。  
源码：  
public final class String  
implements java.io.Serializable, Comparable<String>, CharSequence \{  
/\*\* The value is used for character storage. \*/  
private final char value\[\];  
...

StringBuﬀer 和 StringBuilder 他们两都继承了 AbstractStringBuilder 抽象类，他们的底层都是可变的字符数组，所以在进行频繁的字符串操作时，建议使用 StringBuﬀer 和 StringBuilder 来进行操作。  
StringBuﬀer 对方法加了同步锁或者对调用的方法加了同步锁，所以是线程安全的。  
StringBuilder 并没有对方法进行加同步锁，所以是非线程安全的。

## 6、ArrayList 和 linkedList 的区别？ ##

Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。  
ArrayList: 可以看作是能够自动增长容量的数组  
ArrayList 的 toArray 方法返回一个数组  
ArrayList 的 asList 方法返回一个列表  
ArrayList 底层的实现是 Array, 数组扩容实现  
\--- 顺序存储  
LinkList 是一个双链表,在添加和删除元素时具有比 ArrayList 更好的性能.但在 get 与 set 方面弱于ArrayList  
\--- 链式存储

## 7、HashMap 和 HashTable 的区别？ ##

（1）两者父类不同  
HashMap 是继承自 AbstractMap 类，而 Hashtable 是继承自 Dictionary 类。不过它们都实现了同时实现了 map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

（2）对外提供的接口不同  
Hashtable 比 HashMap 多提供了 elments() 和 contains() 两个方法。  
elments() 方法继承自 Hashtable 的父类 Dictionnary。elements() 方法用于返回此 Hashtable 中的 value 的枚举。  
contains()方法判断该 Hashtable 是否包含传入的 value。它的作用与 containsValue()一致。事实上，contansValue() 就只是调用了一下 contains() 方法。

（3）对 null 的支持不同  
Hashtable：key 和 value 都不能为 null。  
HashMap：key 可以为 null，但是这样的 key 只能有一个，因为必须保证 key 的唯一性；可以有多个 key 值对应的 value 为 null。

（4）安全性不同  
HashMap 是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自己处理多线程的安全问题。  
Hashtable 是线程安全的，它的每个方法上都有 synchronized 关键字，因此可直接用于多线程中。虽然 HashMap 是线程不安全的，但是它的效率远远高于 Hashtable，这样设计是合理的，因为大部分的使用场景都是单线程。当需要多线程操作的时候可以使用线程安全的 ConcurrentHashMap。  
ConcurrentHashMap 虽然也是线程安全的，但是它的效率比 Hashtable 要高好多倍。因为  
ConcurrentHashMap 使用了分段锁，并不对整个数据进行锁定。

（5）计算 hash 值的方法不同

## 8、Collection 包结构，与 Collections 的区别 ##

Collection 是集合类的上级接口，子接口有 Set、List、LinkedList、ArrayList、Vector、Stack、Set  
Collections 是集合类的一个帮助类， 它包含有各种有关集合操作的静态多态方法，用于实现对各种集合的搜索、排序、线程安全化等操作。

## 9、Java 的四种引用，强弱软虚 ##

强引用：是平常中使用最多的引用，强引用在程序内存不足（OOM）的时候也不会被回收  
String str = new String("str");  
软引用：软引用在程序内存不足时，会被回收  
SoftReference<String> wrf = new SoftReference<String>(new String("str"));  
可用场景：创建缓存对象  
弱引用：弱引用就是只要 JVM 垃圾回收器发现了它，就会将之回收  
WeakReference<String> wrf = new WeakReference<String>(str);  
java 源码中的 java.util.WeakHashMap 中的 key 就是使用弱引用  
虚引用：虚引用的回收机制跟弱引用差不多，但是它被回收之前，会被放入 ReferenceQueue 中。  
注意哦，其它引用是被 JVM 回收后才被传入 ReferenceQueue 中的。  
使用场景：由于这个机制，所以虚引用大多被用于引用销毁前的处理工作。还有就是，虚引用创建的时候，必须带有 ReferenceQueue  
PhantomReference<String> prf = new PhantomReference<String>(new String("str"), new ReferenceQueue<>());

## 10、a=a+b 与 a+=b 有什么区别吗? ##

隐式自动类型转换  
short s1= 1;  
s1 = s1 + 1; --- 会编译报错，short 类型在进行运算时会自动提升为 int 类型  
  
short s1= 1;  
s1 += 1; --- 不会报错，+=操作符会对右边的表达式结果强转匹配左边的数据类型

## 11、try catch ﬁnally，try 里有 return，ﬁnally 还执行么？ ##

执行  
ﬁnally 是在 return 后面的表达式运算后执行的  
此时并没有返回运算后的值，而是先把要返回的值保存起来，管ﬁnally 中的代码怎么样，返回的值都不会改变，任然是之前保存的值，  
所以函数返回值是在ﬁnally 执行前确定的；  
注意：ﬁnally 中最好不要包含 return，否则程序会提前退出，返回值不是 try 或 catch 中保存的返回值

## 12、Java 线程实现/创建方式 ##

（1）继承 Thread 类  
Thread 类本质上是实现了 Runnable 接口的一个实例，代表一个线程的实例。  
启动线程的唯一方法就是通过 Thread 类的 start()实例方法。start()方法是一个 native 方法，  
它将启动一个新线程，并执行 run()方法。  
public class MyThread extends Thread \{  
public void run() \{  
System.out.println("MyThread.run()");  
\}  
\}  
MyThread myThread1 = new MyThread();  
myThread1.start();

（2）实现 Runnable 接口  
public class MyThread extends OtherClass implements Runnable \{  
public void run() \{  
System.out.println("MyThread.run()");  
\}  
\}  
//启动 MyThread  
MyThread myThread = new MyThread();  
Thread thread = new Thread(myThread);  
thread.start();   
target.run()  
public void run() \{  
if (target != null) \{  
target.run();  
\}  
\}

## 13、线程池作用、原理？ ##

线程池做的工作主要是控制运行的线程的数量。  
降低资源消耗 减少线程创建、销毁 消耗  
提高响应速度 任务不需要等待线程创建  
提高线程可管理性 防止线程过多，消耗内存  
  
线程池 线程数量 如何定？ --- 和cpu，io相关  
cpu密集型应用：线程池数量：N+1  
IO密集型应用，线程池数量：2N+1  
最佳线程数目 = （（线程等待时间+线程CPU时间）/线程CPU时间 ）\* CPU数目  
线程池的5种运行态  
RUNNING ： 该状态的线程池既能接受新提交的任务，又能处理阻塞队列中任务。  
\---- 能接收任务，能处理任务  
SHUTDOWN：该状态的线程池\*\*不能接收新提交的任务\*\*，\*\*但是能处理阻塞队列中的任务\*\*。  
处于 RUNNING 状态时，调用 shutdown()方法会使线程池进入到该状态。  
\---- 不能接收任务，但能处理任务  
STOP： 该状态的线程池不接受新提交的任务，也不处理在阻塞队列中的任务，还会中断正在执行的任务。  
在线程池处于 RUNNING 或 SHUTDOWN 状态时，调用 shutdownNow() 方法会使线程池进入到该状态；  
\---- 不能接收任务，不能处理任务，还会中断任务  
TIDYING： 如果所有的任务都已终止，workerCount (有效线程数)=0 。  
线程池进入该状态后会调用 terminated() 钩子方法进入TERMINATED 状态。  
TERMINATED： 在terminated()钩子方法执行完后进入该状态，默认terminated()钩子方法中什么也没有做。  
线程池如何关闭：  
shutdown 只会中断空闲线程，进入SHUTDOWN  
shutdownNow 中断所有线程，进入STOP  
核心线程池：  
ThreadPoolExecutor  
public ThreadPoolExecutor(int corePoolSize,  
int maximumPoolSize,  
long keepAliveTime,  
TimeUnit unit,  
BlockingQueue<Runnable> workQueue,  
ThreadFactory threadFactory,  
RejectedExecutionHandler handler) \{  
参数：  
corePoolSize 线程池基本大小 个人认为：也可以理解为最小线程数  
一个空的线程池，只要有任务进来就会创建线程，直到线程数达到corePoolSize，不会管有没有空闲线程  
maximumPoolSize 线程池最大线程数  
keepAliveTime 当线程数量超过 corePoolSize 时，多余的空闲线程的存活时间，即多次时间内会被销毁。  
unit：keepAliveTime 的单位，可选单位有DAYS、HOURS、MINUTES、毫秒、微秒、纳秒。  
workQueue 用于保存等待执行任务的阻塞队列  
ArrayBlockingQueue 基于数组的有界阻塞队列，最大线程数为maximumPoolSize  
LinkedBlockingQueue 基于链表的无界阻塞队列  
PriorityBlokingQueue 支持优先级的无界阻塞队列，最大线程数只能达到corePoolSize  
threadFactory 线程工厂，用于创建线程，一般用默认的即可  
handler：拒绝策略，当任务太多来不及处理，如何拒绝任务。  
AbortPolicy 默认策略，不能处理直接抛出异常  
CallerRunsPolicy 用调用者线程执行任务  
DiscardOldestPolicy 丢弃阻塞队列中最靠前的一个任务，并执行当前任务  
DiscardPolicy 直接丢弃任务  
线程池（ThreadPoolExecutor）工作流程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p3ZW50YW8wMQ_size_16_color_FFFFFF_t_70][]

## 14.Java 常用算法 ##

快速排序：选择一个关键值作为基准值。比基准值小的都在左边序列，比基准值大的都在右边。一般选择序列的第一个元素。挖坑填数  
冒泡排序：两两交换  
直接插入排序：类似扑克牌摸牌，将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表。  
归并排序：含有 n 个元素的数列，可以将其分解成 n 个子序列，每个子序列含有一个元素，因此每一个子序列皆为有序数列，两两合并，可以合并成 n/2 个有序数列，依次类推，最终合并成一个完整的有序数列。

## 15、Spring Beans ##

Spring beans 是那些形成Spring应用的主干的java对象。它们被Spring IOC容器初始化，装配，和管理。  
这些beans通过容器中配置的元数据创建。

## 16、什么是Java虚拟机？ ##

Java 虚拟机是一个可以执行 Java 字节码的虚拟机进程。Java 源文件被编译成能被 Java 虚拟机执行的字节码文件。

## 17、JDK和JRE的区别是什么？ ##

JDK: java开发工具包,包含了JRE、编译器和其它工具  
JRE: java运行环境,包含java虚拟机和java程序所需的核心类库。

## 18、"static"关键字是什么意思？Java中是否可以覆盖一个private或者是static的方法？ ##

static方法时编译时静态绑定的，属于类，而覆盖是运行时动态绑定的(动态绑定的多态)，因此不能覆盖.

## 19、Java支持的基本数据类型有哪些？什么是自动拆装箱？ ##

java支持的基本数据类型有:byte,shot,int,long,float,double,char,boolean.  
自动拆装箱是java从jdk1.5引用，目的是将原始类型自动的装换为相对应的对象，也可以逆向进行，即拆箱。这也体现java中一切皆对象的宗旨。  
所谓自动装箱就是将原始类型自动的转换为对应的对象，而拆箱就是将对象类型转换为基本类型。

## 20、Java支持多继承么？如果不支持，如何实现? ##

不支持，一个类只能继承一个父类  
两种方式可以实现多继承效果：接口和内部类

## 21、什么是值传递和引用传递？java中是值传递还是引用传递，还是都有? ##

值传递 就是在方法调用的时候，实参是将自己的一份拷贝赋给形参，在方法内，对该参数值的修改不影响原来实参  
引用传递 是在方法调用的时候，实参将自己的地址传递给形参，此时方法内对该参数值的改变，就是对该实参的实际操作。  
\---> 不要以为java是引用传递  
  
实际是 值传递，原因如下：  
在Java中对象作为参数传递时，是把对象在内存中的地址拷贝了一份传给了参数

## 22、接口和抽象类的区别是什么? ##

接口中所有的方法隐含的都是抽象的。而抽象类则可以同时包含抽象和非抽象的方法。  
类可以实现很多个接口，但是只能继承一个抽象类  
类如果要实现一个接口，它必须要实现接口声明的所有方法。但是，类可以不实现抽象类声明的所有方法，当然，在这种情况下，类也必须得声明成是抽象的。  
抽象类可以在不提供接口方法实现的情况下实现接口。  
Java 接口中声明的变量默认都是 final 的。抽象类可以包含非 final 的变量。  
Java 接口中的成员函数默认是 public 的。抽象类的成员函数可以是 private，protected 或者是 public 。  
接口是绝对抽象的，不可以被实例化(java 8已支持在接口中实现默认的方法)。抽象类也不可以被实例化，但是，如果它包含 main 方法的话是可以被调用的。

## 23、构造器（constructor）是否可被重写（override）? ##

构造方法是不能被子类重写的，但是构造方法可以重载，也就是说一个类可以有多个构造方法。

## 24、Math.round(11.5) 等于多少? Math.round(-11.5)等于多少? ##

Math.round(11.5)= =12 Math.round(-11.5)==-11 round 方法返回与参数 最接近的长整数，参数加 1/2 后求其 floor

## 25、HashMap的工作原理是什么? ##

hashmap数据结构：  
hashmap是一个键值对key-value的组合，每一个键值对也叫 entry  
这些 entry 分散在一个数组中，相当于主干  
数组每个元素 均为 null  
put方法原理：  
put方法 含义 就是将 一个key-value组合(entry) 放入 hashmap中  
那么该放到数组的哪个节点呢？  
需要计算hash值：index = Hash（key），如果计算出index=2，就放到数组中索引为2的位置处，如果此处还没放元素，那正好占这个坑  
如果这个位置已经有元素了，怎么办呢？  
利用链表来解决：数组中放置的每一个entry对象，它同时也是一个链表的头结点  
因此，如果index=2出已经有entry对象了，那将它的next指针，指向自己，也就是插入这个链表中  
（jdk1.7头插法，jdk1.8尾插法）。  
\---> 这里要注意下，并发情况下，插入同一个链表，容易将next指向自己，产生死循环问题  
get方法原理：  
如何拿到这个entry对象呢？  
首先：计算hash值：index = Hash（key），根据hash值找到对应数组索引位置，由于链表的存在，就需要顺着头结点，向下寻找key相等的entry  
hashmap默认长度：16，自动扩展或初始化时，长度必须是2的幂  
为什么是这样：  
为了让entry在数组上均匀分布  
实际hash函数运算方法：index = HashCode（Key） & （Length - 1） 比如长度为16，其实就是和 1111(16-1) 做 & 运算  
如果长度不是2的幂，那么会导致某些index出现的几率变大，不符合均匀分布原则  
hashmap扩容  
条件：HashMap.Size（存在的元素个数） >= Capacity（当前长度） \* LoadFactor（负载因子，默认值为0.75f）  
扩容步骤：  
创建一个新的entry空数组，长度是原来2倍  
遍历原数组，将所有encry重新hash到新数组中，原因是 长度变化，会影响hash值  
以上jdk1.7：是entry数组+链表的实现形式  
  
 jdk1.8：  
将 entry数组 改为 node数组，以前一个entry元素是链表，现在一个node对应一个entry，其结构是链表或者红黑树  
当链表长度超过8，结构就转换为红黑树  
一般插入链表后，再判断长度是否达到8，是否需要转换为红黑树

## 26、HashMap与HashTable的区别是什么? ##

HashTable 其实就是 hashmap + synchronized，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低

## 27、CorrentHashMap的工作原理? ##

jdk1.7：  
segment数组+链表+分段锁，分段锁含义是 将 entry数组分成多段，每一段称之为segment，分别加锁，避免hashtable整表上锁问题  
由于segment的存在，查询和插入，需要两次hash，第一次到segment，第二次到entry  
 jdk1.8：  
node数组+链表/红黑树+Synchronized/CAS，锁针对 node链表的头结点

1）HashMap和ConcurrentHashMap区别  
了解两者的数据结构，这个区别一目了然，简述下：  
ConcurrentHashMap 线程安全

2）ConcurrentHashMap的数据结构  
见上

3）高并发HashMap的环是如何产生的  
见上

4）HashMap1.7与HashMap1.8的区别，从数据结构上、Hash值的计算上、链表数据的插入方法、内部Entry类的实现上分析？  
见上  
  
HashMap如果我想要让自己的Object作为K应该怎么办？  
首先要理解这个问题含义： key-value中的 key如果是含有多种属性的object，应该怎么办？  
我们都知道 key 涉及到 hash值的计算：index = HashCode（Key） & （Length - 1），因此将object作为key，  
需要重写 hashcode方法，还有 equals方法

HashMap相关put操作，get操作等流程？（下图作为参考）  
见上

## 28、HashSet和HashMap 区别？ ##

hashset实现的是set接口，集合内不能包含重复元素  
基于hashmap，当hash值一致的时候，会调用equals判断元素是否相等，不相等才插入

## 29、Hash1.7是基于数组和链表实现的，为什么不用双链表？HashMap1.8中引入红黑树的原因是？为什么要用红黑树而不是平衡二叉树？ ##

单链表就够用了，双链表复杂度上升，还需要更大的存储空间  
红黑树引入，是为了解决链表过长，导致索引效率慢的问题，提高增删改查速度  
红黑树平衡度较低，但插入和删除后，重构树的开销要低，性能相对折中，更合适

## 30、遍历一个List有哪些不同的方式？ ##

List<String> strList = new ArrayList<>();  
//for-each  
for(String str:strList) \{  
System.out.print(str);  
\}

//use iterator 尽量使用这种 更安全(fail-fast)  
Iterator<String> it = strList.iterator();  
while(it.hasNext) \{  
System.out.printf(it.next());  
\}

## 31、fail-fast与fail-safe有什么区别？ ##

Iterator的安全失败fail-safe是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。  
java.util包下面的所有的集合类都是快速失败fail-fast的，而java.util.concurrent包下面的所有的类都是安全失败fail-safe的。  
快速失败fail-fast的迭代器会抛出ConcurrentModificationException异常，而安全失败fail-safe的迭代器永远不会抛出这样的异常。

## 32、Array和ArrayList有何区别？什么时候更适合用Array？ ##

Array可以容纳基本类型和对象，而ArrayList只能容纳对象。  
Array是指定大小的，而ArrayList大小是固定的

## 33、哪些集合类提供对元素的随机访问？ ##

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

## 34、LinkedHashMap 的实现原理? ##

LinkedHashMap 基于 hashmap，但又进行了改造：  
将 hashmap 中的 entry 新增了 两个属性 before 和 after，这两个属性和next相似，也是指向entry，  
不过是按插入顺序指向的。  
另外还有一个独立于 hashmap之外 entry header头结点，包含 before 和 after属性，其和其他entry节点链接在一起，  
组成了一个双向列表。  
通过hashmap和双向链表的结合，实现了插入顺序和访问顺序排序。默认为插入顺序  
参考链接：https://blog.csdn.net/u012860938/article/details/95613684

## 35、LinkedList和ArrayList的区别是什么? ##

ArrayList是基于数组实现，LinkedList是基于链表实现  
ArrayList在查找时速度快，LinkedList在插入与删除时更具优势

## 36、什么是线程？进程和线程的关系是什么？ ##

线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度实体。  
在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。  
一个进程可以有多个线程，而且至少有一个可执行线程。  
打个比喻:进程好比工厂(计算机)里的车间，一个工厂里有多个车间(进程)在运转,  
每个车间里有多个工人（线程）在协同工作，这些工人就可以理解为线程。

线程和进程的关系:  
线程是进程的一个组成部分.  
进程的多个线程都在进程地址空间活动.  
系统资源是分配给进程的，线程需要资源时，系统从进程的资源里分配给线程.  
处理机调度的基本单位是线程.

## 37、Thread 类中的start() 和 run() 方法有什么区别？ ##

start()方法被用来启动新创建的线程，而且start()内部调用了run()方法，  
这和直接调用run()方法的效果不一样。当你调用run()方法的时候，只会是在原来的线程中调用，  
没有新的线程启动，start()方法才会启动新线程。

## 38、什么是线程安全? ##

当多个线程访问某个类时，不管运行时环境采用何种调度方式或者线程将如何交替执行，  
并且在主调代码中不需要任何额外的同步或协同，这个类都能表现出正确的行为。  
线程安全的核心是“正确性”，也就是说当多个线程访问某个类时，能够得到预期的结果，那么就是线程安全的。

## 39、Java中有哪几种锁? ##

自旋锁: 自旋锁在JDK1.6之后就默认开启了。基于之前的观察，共享数据的锁定状态只会持续很短的时间，  
为了这一小段时间而去挂起和恢复线程有点浪费，所以这里就做了一个处理，让后面请求锁的那个线程在稍等一会，  
但是不放弃处理器的执行时间，看看持有锁的线程能否快速释放。为了让线程等待，  
所以需要让线程执行一个忙循环也就是自旋操作。  
在jdk6之后，引入了自适应的自旋锁，也就是等待的时间不再固定了，  
而是由上一次在同一个锁上的自旋时间及锁的拥有者状态来决定

偏向锁: 在JDK1.之后引入的一项锁优化，目的是消除数据在无竞争情况下的同步原语。  
进一步提升程序的运行性能。 偏向锁就是偏心的偏，意思是这个锁会偏向第一个获得他的线程，  
如果接下来的执行过程中，改锁没有被其他线程获取，则持有偏向锁的线程将永远不需要再进行同步。  
偏向锁可以提高带有同步但无竞争的程序性能，也就是说他并不一定总是对程序运行有利，  
如果程序中大多数的锁都是被多个不同的线程访问，那偏向模式就是多余的，  
在具体问题具体分析的前提下，可以考虑是否使用偏向锁。

轻量级锁: 为了减少获得锁和释放锁所带来的性能消耗，引入了“偏向锁”和“轻量级锁”，  
所以在Java SE1.6里锁一共有四种状态，无锁状态，偏向锁状态，轻量级锁状态和重量级锁状态，  
它会随着竞争情况逐渐升级。锁可以升级但不能降级，意味着偏向锁升级成轻量级锁后不能降级成偏向锁。  
这种锁升级却不能降级的策略，目的是为了提高获得锁和释放锁的效率，下文会详细分析  
  
以上3中锁，其实说的都是锁的一种状态：  
了解锁升级过程（无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁），就明白上述三种锁是啥含义：  
JDK 1.6 为了减少获得锁和释放锁所带来的性能消耗，在JDK 1.6里引入了4种锁的状态：无锁、偏向锁、轻量级锁和重量级锁，  
它会随着多线程的竞争情况逐渐升级，但不能降级。  
  
研究发现，大多数情况下，锁都不存在多线程竞争，一般由同一个锁获得，为了不让这个线程每次获取锁都要做  
CAS操作，消耗性能，就引入了偏向锁。当一个线程访问对象并获取锁时，会在对象头里存储偏向这个线程的ID，  
以后该线程再访问这个对象时，只需要判断对象头的Mark Word里是否有这个线程的ID，如果有就不需要进行CAS  
操作，这就是偏向锁。  
当线程竞争更激烈时，偏向锁会升级为轻量级锁状态，这种锁认为竞争是存在的，但理想情况下，  
竞争程度很低，锁的锁定时间也很短，因此让线程等待一段时间（也就是自旋），等上一个线程释放锁；  
但当自旋超过一定次数，存在第三个线程来竞争时，轻量级锁会升级为重量级锁，也就是Synchronized，  
重量级锁会使除拥有锁的线程以外的其他线程都阻塞。  
\--- 什么是无锁，即不锁住资源，多个线程只能有一个能修改资源成功，其他会重试 ，比如CAS

锁的讲解参考链接：  
https://tech.meituan.com/2018/11/15/java-lock.html  
https://zhuanlan.zhihu.com/p/112649693

## 40、ThreadLocal理解 ##

ThreadLocal是一个创建线程局部变量的类。通常情况下我们创建的变量,可以被多个线程访问并修改,通过ThreadLocal创建的变量只能被当前线程访问。  
ThreadLocal的值是放入了当前线程的一个ThreadLocalMap实例中，所以只能在本线程中访问，其他线程无法访问。  
ThreadLocal并不会导致内存泄露,因为ThreadLocalMap中的key存储的是ThreadLocal实例的弱引用,因此如果应用使用了线程池,即便之前的线程实例处理完之后出于复用的目的依然存活,也不会产生内存泄露。

## 41、为什么wait, notify 和 notifyAll这些方法不在thread类里面? ##

## 42、平衡二叉树数据结构 ##

首先要明白什么是平衡二叉树？需要满足三个条件：  
1、每个节点最多只有两个子节点，也就是 要是一颗 二叉树  
2、每个节点的值 比 它左子树 所有节点的值 都大；比 它右子树 所有节点的值 都小  
3、每个节点，其左子树和右子树的高度差 绝对值 不超过 1  
如何旋转：  
找到最小不平衡子树，距离插入节点最近的，且平衡因子BF的绝对值大于1的节点为根的 子树，称之为 最小不平衡子树。  
\[什么是平衡因子：二叉树节点的 左子树深度 减去 右子树深度 的值 称为 平衡因子BF\]  
\--- 旋转最小不平衡子树  
一般情况下，旋转符合如下条件，旋转一次即可：  
当平衡因子 BF > 1，说明左子树更深，需要右旋  
BF < -1，说明右子树更深，需要左旋  
但实际存在 旋转一次 无法达到 平衡状态的情况，  
进行分析可知，这种情况发生时，存在如下现象：  
最小不平衡子树中：  
（1）根节点 平衡因子BF为 正数，距离根节点最近的子树节点 平衡因子BF为 负数  
如何处理：  
先 因 距离根节点最近的子树节点 BF 为负，以 该子树节点 为轴，进行 左旋  
后 因 根节点 BF为 正数，以 根 为轴，进行右旋  
  
（2）根节点 平衡因子BF为 负数，距离根节点最近的子树节点 平衡因子BF为 正数  
如何处理：  
先 因 距离根节点最近的子树节点 BF 为正，以 该子树节点 为轴，进行 右旋  
后 因 根节点 BF为 负数，以 根 为轴，进行左旋  
举例：  
以 50 为 根的 左子树 为最小不平衡子树  
根节点 50 BF=2， 距离根节点最近的子树节点40 为-1  
因此  
先 因 距离根节点最近的子树节点 BF 为负，以 40 为轴，进行 左旋  
后 因 根节点 BF为 正数，以 50 为轴，进行右旋  
(2)  
50  
/ \\  
(-1) (0)  
40 60  
/ \\  
(0) (1)  
30 45  
/  
(0)  
42  
  
先左旋如下，旋转时，因为出现两个左节点40和42，会把42断开，挂到40的右节点上：  
(2)  
50  
/ \\  
(2) (0)  
45 60  
/  
(0)  
40  
/ \\  
(0) (0)  
30 42  
  
后右旋如下：  
(0)  
45  
/ \\  
(0) (-1)  
40 50  
/ \\ \\  
(0) (0) (0)  
30 42 60

以上理解参考：《大话数据结构》  
https://www.pianshen.com/article/9609779212/

## 43、红黑树数据结构 ##

红黑树是一棵 二叉搜索树：  
左子树节点值 < 根节点值 < 右子树节点值  
红黑树具备如下种性质：  
1、每个节点只有两种颜色，红色或者黑色  
2、根节点是黑色的  
3、每个叶节点(NIL)是黑色的 --- 这里的几点指 为 空的 叶子节点  
4、如果一个节点是红色的，则它的两个子节点都是黑色的（红色不连续）  
5、对每个节点，从该节点 到 其所有 后代叶节点 的简单路径上，均包含 相同数目的 黑色节点  
  
一个节点有 5 中属性：颜色color、指向左子节点的指针、指向右子节点的指针、指向父节点的指针、节点值  
相比普通二叉树节点，就多了个 颜色color  
  
插入操作：  
默认插入的节点颜色都是红色，因为插入黑色节点会破坏根路径上的黑色节点总数  
如果出现连续红色怎么办？  
旋转 + 变色  
分析插入情况可知：  
（1）被插入的节点是根节点  
处理方法：直接把此节点涂为黑色。  
（2）被插入的节点的父节点是黑色  
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。  
（3）被插入的节点的父节点是红色。  
处理方法：那么，该情况与红黑树的“特性(4)”相冲突。  
这种情况下，被插入节点是一定存在非空祖父节点的；  
进一步的讲，被插入节点也一定存在叔叔节点  
(即使叔叔节点为空，我们也视之为存在，空节点NIL本身就是黑色节点)。  
具体可分如下三种情况：  
case1 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。  
(01) 将“父节点”设为黑色。  
(02) 将“叔叔节点”设为黑色。  
(03) 将“祖父节点”设为“红色”。  
(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。  
case2 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子  
(01) 将“父节点”作为“新的当前节点”。  
(02) 以“新的当前节点”为支点进行左旋。  
case3 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子  
(01) 将“父节点”设为“黑色”。  
(02) 将“祖父节点”设为“红色”。  
(03) 以“祖父节点”为支点进行右旋。  
上面三种情况(Case)处理问题的核心思路都是：  
将红色的节点移到根节点；然后，将根节点设为黑色。  
上述说明，参考：https://www.cnblogs.com/luanxm/p/10809478.html，这篇博客关于插入的说明讲解的很好，但举得例子是有问题的。  
关于红黑树的一个形象的动画网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html，可以实际演练  
参考：https://www.cnblogs.com/gcheeze/p/11176882.html 这篇博客最后的实例是完整正确的，可以参考  
删除操作：  
\--- 暂时不太懂  
第一步：先将红黑树当作一棵二叉搜索树，将节点删除  
（1）被删除的节点没有儿子，即为叶节点 --- 直接删除即可  
（2）被删除的节点只有一个儿子，那么直接删除该节点，并用这个子节点顶替  
（3）被删除的节点有两个儿子？？？  
第二步：通过“旋转和变色”修正为红黑树

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p3ZW50YW8wMQ_size_16_color_FFFFFF_t_70]: /images/20221023/3b98180c6b894cb49e9fe8f0cea33d83.png