(1)java基础
一、JDK、JRE、JVM,以及三者的关系
1)JDK 指的是 java 开发工具包,它包括编译器、JAVA核心类库、JVM、开发辅助工具(jps、jinfo、jmap、jconsole、jvisualvm)
2)JRE 指的是 JAVA 程序运行环境,主要包括 JAVA 核心类库、JVM
3)JVM 是字节码执行引擎,java 程序运行在 java 虚拟机上,同时负责 java 程序的内存管理、垃圾回收
三者的关系:JDK 包含 JRE,JRE 包含 JVM
二、字符串
1.String 和 StringBuffer、StringBuilder 的区别是什么?
主要从两个方面来比较,一个是可变性,一个是线程安全性
1)String 是不可变字符串;StringBuffer、StringBuilder 是可变字符串,可以通过 append() 方法来改变
2)线程安全性:String 因为是对象不可变的,因此它是线程安全的,StringBuffer 的方法度加了 synchronized,它是线程安全的,而 StringBuilder 的方法没有加锁,因此它是线程不安全的
2.String 是不可变对象是指什么
1)一个 String 对象被创建之后,它的内容就不能被改变
2)如果尝试修改一个 String 对象的内容,实际上会创建一个新的 String 对象,举个例子
String str = "a"; String str = str + "b";
尝试把字符串 a 改成 ab,实际上是再创建一个 ab 对象,原来的 a 对象还驻留在内存中
3.String 为什么是不可变的
final 关键字修饰的数组保存字符串并不是 String 不可变的根本原因,因为这个数组保存的字符串是可变的
1)保存字符串的 char[] 数组被 final 修饰且为私有的,并且 String 类并没有提供修改这个字符串的方法
2)String 类被 final 修饰,因此其不能被继承,进而避免了子类破坏 String 的不可变性。如果 String 类没有被 final 修饰,那就可以通过继承 String 类,然后重写 String 的构造方法,从而导致 String 变成可变的。举个例子:
// 定义一个没有被 final 修饰的 String 类
public class String {
private final char[] name;
public String(char[] name) {
this.name = name;
}
@Override
public java.lang.String toString() {
return "A{" +
"name=" + Arrays.toString(name) +
'}';
}
}
public class StringSub extends String {
public StringSub(char[] name) {
super(new char[]{'g', 'h'});
}
}
public class Main {
public static void main(java.lang.String[] args) {
char[] c = {'d', 'e'};
String a = new StringSub(c);
System.out.println(a);
}
}
4.String 为什么要设计成不可变的
1)保证线程安全,因为 String 是一个比较特殊的对象,假如一个字符串在多个地方被使用,如果 String 是可变的,那么一个地方修改就会引起其它地方的同步改动,这样的话会给程序带来很严重的不可靠性
2)字符串常量池的需求,字符串常量池需要 String 不可变。当创建一个 String 对象时,若此字符串已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。如果字符串变量允许改变,会导致各种逻辑错误,如改变一个对象会影响到另一个独立对象
3)支撑哈希表(HashMap/HashSet)的正常工作:当 String 作为 HashMap 的 Key 时,若后续修改了 String 的字符序列,其 hashCode 会随之改变。此时,原 Key 所在的哈希桶位置与新 hashCode 对应的桶位置不一致,导致后续无法通过 Key 找到对应的 Value,哈希表彻底失效
4)保障 Java 核心 API 的安全性:文件路径(File file = new File(String path)):若 path 可变,创建 File 后若 path 被篡改,可能导致程序访问错误的文件(甚至敏感文件)
5.String 的不可变有什么缺点
1)每次对 String 对象的修改都会创建一个新的 String 对象,在频繁修改字符串的场景中,会比较消耗内存
2)如果字符串比较大,复制字符串的时候会比较耗性能
3)针对这些缺点,可以通过使用可变字符串来代替 String
- 字符串常量池
1)用于存储字符串字面量,位于堆内存中
2)字符串常量池是用于优化字符串存储和复用的关键机制,本质是一块专门存储字符串常量的内存区域(在 JDK 7 及之后位于堆内存中,此前在方法区)
3)为什么要设计字符串常量池
· 解决字符串的高频重复问题,字符串是程序中使用最频繁的数据类型之一,很多场景下会创建大量内容相同的字符串,因此字符串常量池可以减少对象的重复创建
· 节省内存
6.创建多少个对象的问题
1)先了解 String 创建对象的方式
· 字面量声明的方式:String str = "a";
· new 方式:String str = new String("a");
2)String str = "a";
如果字符串常量池有 a,则不会创建对象,把引用 str 指向字符串常量池中的a,否则创建一个对象放在常量池
3)String str = new String("a");
如果字符串常量池有 a,则在堆上创建一个,否则创建两个,在字符串常量池中创建一个,在堆上创建一个
4)String str = "a" + "b";
在编译期,会把 "a" + "b" 替换为 "ab",因此实际上就等价于 String str = "ab"。所以创建0个或者1个放在字符串常量池中
5)String str = "a"; String str = "a" + "b";
创建0个或者1个或者2个。如果字符串常量池已经存在a、ab,则创建0个;如果字符串常量池不存在a、ab,则创建2个;如果字符串常量池存在a不存在ab或者存在ab不存在a,则创建1个
6)String str = new String("a") + "b";
7)String str = "b" + new String("a");
题目 3.2:String s4 = s1 + s2;(s1, s2 为变量)创建了几个对象
答案:至少 1 个。
由于涉及变量,编译期无法优化,会在运行时使用 StringBuilder进行拼接。
过程如下:
创建一个 StringBuilder对象。
调用 append()方法拼接 s1和 s2。
调用 toString()方法,new一个 String对象(在堆中)。
因此,会创建 StringBuilder对象和最终的 String对象。如果 s1和 s2本身对应的常量池字符串不存在,还会创建它们。
终极题:new String("a") + new String("b")
题目:String s5 = new String("a") + new String("b");创建了多少对象?
答案:最多 6 个。我们来一步步数:
"a"字面量:常量池中创建 1 个 "a"对象。
new String("a"):堆中创建 1 个 新的 String 对象。
"b"字面量:常量池中创建 1 个 "b"对象。
new String("b"):堆中创建 1 个 新的 String 对象。
拼接过程:
创建一个 StringBuilder对象(第 5 个)。
toString()方法会 new String("ab")(第 6 个)。注意:"ab"这个字面量不会被放入字符串常量池!
- String str = new String("a") + "b";
执行过程:
new String("a"):
检查字符串常量池是否有 "a":
如果没有,在常量池创建 "a"(对象1)
在堆内存中创建一个新的 String对象(对象2)
拼接 "b":
检查字符串常量池是否有 "b":
如果没有,在常量池创建 "b"(对象3)
使用 StringBuilder进行拼接:
创建 StringBuilder对象(对象4)
调用 append()方法拼接 new String("a")和 "b"
调用 toString()方法,在堆中创建新的 String对象(对象5)
对象创建总结:
最多创建 5 个对象:
常量池中的 "a"(如果不存在)
堆中的 new String("a")
常量池中的 "b"(如果不存在)
StringBuilder对象
最终拼接结果的 String对象("ab",不会放入常量池)
StringBuilder的 toString()方法创建的字符串(如 "ab"或 "ba")不会自动放入字符串常量池。
三、重载和重写
1.重载
1)发生在同一个类中,方法名相同,参数列表不同。例如一个类中有两个方法的方法名一样,但是它们的参数列表一个是String str 一个是int i,则这两个方法就是重载方法
2)重载属于编译时的多态
2.重写
1)重写发生在父子类之间,指的是子类重新定义父类的方法,对父类方法实现逻辑进行重写。子类返回值的类型可以跟父类的不一样,但是类型的范围要比父类的小
2)重写属于运行时多态
四、接口和抽象类
1.接口和抽象类的区别是什么?
1)抽象类更多的是为了代码复用,接口则侧重于解耦
2)从类的继承层次上来看,抽象类是一种自下而上的设计思路,先有子类的代码重复,然后再抽象成上层的父类(也就是抽象类)。而接口正好相反,它是一种自上而下的设计思路。我们在编程的时候,一般都是先设计接口,再去考虑具体的实现
2.什么时候用接口?什么时候用抽象类?
1)如果是侧重于定义一种行为规范,那么就使用接口
2)如果是侧重于代码复用,那么就使用抽象类
五、Java 是值传递还是引用传递
1.属于值传递
2.代码分析
1)如果是基本类型,传递的就是具体的数值。a方法调用b方法时传递基本变量i,在b方法中把变量 i 的值改为另一个值,a方法中的变量i依然是原来的值
2)如果是引用类型,传递的就是引用所指向的对象,这个对象实际上也可以当做一个具体值来看到,因此也属于值传递。a方法调用b方法时传递引用类型变量 user,在b方法中把传过来的变量置空,a方法中的变量 user 依然指向原来的对象
public static void main(String[] args) {
// 传递基本类型时
int i = 1;
m(i);
System.out.println(i);
// 传递引用类型时User user = new User();user.setName("aaa");m2(user);System.out.println(user);
}public static void m(int i) {i = 2;
}public static void m2(User user) {user = null;
}
六、封装、继承、多态
-
封装
-
继承
1)可以继承私有成员吗
2)java 为什么不支持多继承 -
多态
1)多态的字面含义:多指的是多种,态指的是形态,结合起来就是多种形态。综合 oop 的语境,就是指对同一个方法的调用可以表现出多种形态/多种行为
2)多态的定义:同一个类型的引用指向不同的对象,然后该引用调用同一个方法表现出不同的行为
3)多态的实现方式,主要有以下两种
· 继承 + 方法重写:子类重写父类的方法,然后使用父类类型的引用来指向子类对象,在运行时根据实际对象类型调用对应的方法
· 接口实现:多个类实现同一个接口,每个类提供不同的实现方式,然后通过接口类型的引用来调用这些方法
4)常见误区:没有所谓的编译时多态和运行时多态的划分
七、java 中的异常体系
1.Error 和 Exception 的区别
2.RunTimeException 和非 RunTimeException 的区别
八、对象的序列化和反序列化
1.概念
1)java 自带的序列化和反序列化:把对象的属性转出二进制字节数组、把二进制字节数组转成对象
2)json 序列化:把对象属性转成 json 格式的字符串
2.如何实现对象的序列化和反序列化
1)Java 自带的序列化机制
2)fastjson
3)Gson 或 Jackson 库
4)Protobuf(gRPC 框架使用的序列化方式)
3.序列化的应用场景(什么时候会用到序列化)
1)返回给前端的数据
2)RPC
3)Redis 缓存
九、浅拷贝和深拷贝
1.概念
1)拷贝指的是拷贝对象的属性,把原对象的属性复制到新创建的对象中
2)二者的区别在于对引用类型的处理。对于引用类型成员变量,浅拷贝复制指向原对象的引用,深拷贝会创建新的对象去复制
2.实现方式
1)浅拷贝的实现方式
· 创建一个新对象,然后把原对象的属性设置进新对象中
· 实现 Cloneable 接口
2)深拷贝的实现方式
· 创建一个新对象,然后把原对象的属性设置进新对象中,如果碰到引用类型的成员变量,需要同时创建该引用类型的对象
· 实现 Cloneable 接口,如果原对象有引用类型的成员变量,该引用类型同样需要实现 Cloneable 接口
· java 本身的序列化和反序列化机制
· fastjson
· org.apache.commons.lang3.SerializationUtils 提供了 clone() 方法,可以深拷贝实现了 Serializable 接口的对象
· 使用 Gson 或 Jackson 库
· 使用 Stream API 和方法引用,对于集合,可以使用 Java 8 的 Stream API 和方法引用来实现深拷贝,例如使用 stream().map(YourClass::new).collect(Collectors.toList())
十、零碎问题
1.& 和 && 的区别
主要的区别是 && 具有短路作用,就是当遇到 false 的时候就直接判定不成立,不需要再进行后面的判断
2.== 和 equals 的区别
3.hashCode() 和 equals() 关系
4.为什么重写 equals() 时必须重写 hashCode()
1)这是因为这两个方法之间有一个重要的契约关系,相等的对象必须具有相同的哈希码,即如果两个对象通过 equals() 方法比较结果为 true,那么它们的 hashCode() 方法返回的值必须相同
2)在集合类 HashMap 以及 HashSet 中,当插入一个对象时,集合类会先计算其哈希码,然后根据哈希码将对象存储在特定的位置,当查找或删除一个对象时,集合类会先计算该对象的哈希码,找到对应的存储位置,然后再使用 equals() 方法进行精确匹配,因此如果只重写了 equals() 而不重写 hashCode() ,在查找数据的时候就无法通过 hashCode() 找到期望的数据
4.Integer 缓存池有了解过吗
1)Integer 缓存池属于自动装箱机制的一部分
1)对于-128到127的数值不是创建 Integer 对象,而是直接从缓存池中获取,这样做的目的是为了节约内存和减少垃圾回收
2)所以对于-128到127的 Integer 对象进行 == 比较的时候,比较的不是对象的内存地址,而是常量
5.BigDecimal 有了解过吗
6.一个线程两次调 start() 方法会出现什么情况
将会抛出 IllegalThreadStateException,因为只有 NEW 状态的线程才可以调用 start() 方法,而调用完 start() 方法之后线程状态不是 NEW 状态,所以会抛出 IllegalThreadStateException
7.什么是内部类,有什么作用
8.JDK8 有哪些新特性
9.用过哪些 JDK 提供的工具
10.java 中的队列有哪些,有什么区别
11.SPI 有了解过吗
12.JDK9 把 String 中 char 数组改成了 byte 数组,你知道为什么吗
13.如何用 java 代码列出一个目录下的所有文件
1)java7 之前,可以使用 java.io.File 类来遍历一个目录下的所有文件和子目录
2)java7 之后,可以使用 java.nio.file.Files 和 java.nio.file.Path 类来遍历目录
14.在 Java 中如何操作调用外部可执行程序或系统命令
一、ArrayList
1.数据结构
1)底层是数组结构,特点是查询比较快,增删比较慢
2)当对象初始创建的时候,如果没有指定容量,它的容量默认是0,当调用add方法添加元素的时候,容量会初始化成10,然后每次扩容之后的容量是之前的1.5倍
2.ArrayList 为什么是线程不安全的
add() 方法造成的,add() 方法主要做两个动作,一是扩容操作,二是为数组对应的索引赋值以及赋值完毕后把 size 加1,多个线程同时调用 add() 方法可能会出现以下两种情况
1)发生索引越界异常,假设线程A开始进行扩容操作时 size 的值为9,则无需扩容,此时线程A挂起,线程B进来,线程B进行扩容操作时 size 的值还是9,则无需扩容,线程B把元素添加到索引为9的位置,然后 size 加1变成10,线程A恢复,线程A往索引为10的位置添加元素,由于数组的容量为10,因为发生索引越界异常
2)数组中的元素被覆盖,线程A在给数组的索引赋值完成之后,还没有为 size 加1,线程挂起,此时线程B读取到的 size 的值与线程A是一样的,所以线程B也往线程A那个索引位置添加元素,然后就会把线程A添加的那个元素给覆盖了,最终就是线程A添加元素失败
3.解决ArrayList的线程安全问题
1)Collections.synchronizedList(new ArrayList<>())
2)java.util.concurrent.CopyOnWriteArrayList(适合读多写少的场景)
二、LinkedList
1)底层是一个双向链表结构(JDK1.6之前为双向循环链表),特点的话跟 ArrayList 相反,就是增删元素比较快,查询效率相对较低
2)LinkedList 是线程不安全的
三、HashSet
1)HashSet一个主要的特点是无序,另外一个是它不能存放重复的元素
2)HashSet如何检查重复,先调用 hashCode() 方法获取哈希值,如果集合中没有相同的哈希值,则直接添加,如果有相同的哈希值,则比较两个元素的equals() 方法,如果返回true,判定为重复元素则不添加,否则就添加元素
3)如果 HashSet 的泛型是自定义类型,则必须重写 hashCode() 和 equals() 方法
四、HashMap
1.数据结构
1)在1.7版本为数组加单链表
2)在1.8版本改成了数组 + 单链表 + 红黑树,当链表长度大于8并且哈希桶数量大于64时,会将单链表转成红黑树,当红黑树的节点数量小于等于6时,红黑树会重新再转成单链表
2.HashMap 几个重要的属性
哈希桶:transient Node<K,V>[] table;
桶的默认初始容量:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
哈希桶的阈值:int threshold;(threshold = 哈希桶的容量 * 扩容因子 = table.length * loadFactor)
扩容因子:final float loadFactor;(默认扩容因子0.75; static final float DEFAULT_LOAD_FACTOR = 0.75f;)
实际存在的键值对数量:transient int size;
3.根据 key 计算键值对在哈希桶中的位置
/**
- 1)调用 key 的 hashCode() 方法计算哈希值 = hashCode
- 2)将哈希值不带符号右移16位 = hashCode2
- 3)将哈希值与右移16位之后的哈希值做异或运算,int hash = hashCode ^ hashCode2
- 4)将哈希桶的数组长度减1之后与上一步的结果做与运算,int index = (数组的大小 - 1) & hash
*/
public static void main(String[] args) {
String str = "bbb";
int hashCode = str.hashCode(); // 97314
int hashCode2 = str.hashCode() >>> 16; // 0001 0111 1100 0010 0010 -> 0000 0000 0000 0000 0001
int hash = hashCode ^ hashCode2; // 0001 0111 1100 0010 0010 ^ 0000 0000 0000 0000 0001 = 0001 0111 1100 0010 0011
int i = (16 - 1) & hash; // 0000 0000 0000 0000 1111 & 0001 0111 1100 0010 0011 = 0000 0000 0000 0000 0001
System.out.println(i); // 3
}
4.put() 方法的执行过程
1)如果数组还没有创建,则先创建数组
2)根据 key 以及数组的长度确定键值对在哈希桶中的位置
3)如果该位置为空,则直接把键值对放在该位置
4)如果这个位置不为空,则判断这个位置的 key 与要 put 的 key 是否相同,如果相同,则把这个位置的 value 替换为要 put 的value;如果 key 不相同,则判断这个位置上的元素是不是红黑树类型,如果是红黑树类型,则挂到红黑树上,如果不是红黑树类型,则判断链表的长度大于等于8并且数组大小大于等于64,如果成立则先把链表转成红黑树,然后挂到红黑树上,否则挂到链表上
(无论是把放入数组、链表或还是红黑树,都会先判断 key 是否相同,如果相同则替换该位置上的 value)
5)最后 size++ 以及判断是否需要扩容
5.get() 方法的执行过程
1)根据 key 以及数组的长度计算出数组的下标
2)根据下标从数组中获取元素,如果该位置上的 key 与传进去的 key 相同,则直接返回该元素,如果不同,则获取下一个节点,判断该节点如果是红黑树,则从红黑树中获取元素,否则从链表中获取元素
6.resize() 方法的执行过程
7.将链表转成红黑树的方法 treeifyBin()
8.扩容机制
1)默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1
2)以2的n次幂扩容的原因是为了在取模和扩容时做优化
9.HashMap 线程不安全的原因
HashMap 线程不安全有三个场景
1)并发扩容时导致死循环
JDK 7 中 HashMap 采用「头插法」处理哈希冲突的链表,并发扩容时可能导致链表成环,引发死循环
原理:
· 当 HashMap 元素数量超过阈值(capacity * loadFactor)时,会触发扩容(resize()),新建更大的数组并将旧元素迁移到新数组
· 并发扩容时,多个线程同时迁移同一链表,由于「头插法」会改变链表顺序,可能导致两个节点互相引用,形成环形链表
· 后续查询该链表时,会陷入无限循环(next 指针永远无法指向 null),最终导致 CPU 使用率飙升
(大白话:两个线程在同时进行put操作时,由于元素数量超过阈值而同时进行扩容,多个线程迁移同一链表,头插法会导致形成环形链表,后续查询该链表时,会导致死循环)
2)并发执行 put() 操作时,可能导致后插入的元素覆盖先插入的元素,造成数据丢失
原理:
线程 A 计算出 key 的哈希索引后,判断该位置为空,准备插入新节点
线程 B 同时计算出相同的哈希索引,且也判断该位置为空,先于线程 A 插入新节点
线程 A 恢复运行后,仍认为该位置为空,直接插入新节点,覆盖线程 B 插入的数据
3)get() 可能返回 null
一个线程执行 put() 插入元素后,另一个线程执行 get() 可能无法获取到该元素,返回 null
原理:
HashMap 的 size、table 等字段未被 volatile 修饰,不保证多线程间的内存可见性
线程 A 插入元素后,其修改的 table 或 size 可能未及时刷新到主内存
线程 B 读取时仍使用本地缓存中的旧数据,导致无法感知线程 A 插入的新元素
10.初始容量为什么是16(为什么要以2的n次幂扩容)
· HashMap 在计算元素要存放在数组中的 index 时,使用位运算代替了取模运算,之所以可以做等价替换,前提是要求 HashMap 的容量一定要是2的次幂,那么既然是2^n,为什么一定要是16呢?为什么不能是4、8或者32呢?这应该是个经验值,需要在效率和内存使用上做一个权衡,这个值既不能太小,也不能太大,太小了就有可能频繁发生扩容,影响效率。太大了又浪费空间,不划算,所以,16就作为一个经验值被采用了
· 减少哈希冲突,如果不是2的n次幂,可能数组的一些位置永远都不会插入数据,浪费数组的空间,加大 hash 冲突
11.扩容因子为什么是0.75
· 在空间和时间之间取得一个平衡
· 减少哈希冲突
12.为什么要用位运算代替取模运算
因为位运算直接对内存数据进行操作,不需要转成十进制,所以位运算要比取模运算的效率更高
13.JDK1.7 多线程 put 操作导致死循环
14.是同一个 key 的判断标准
1)如果 key 的哈希值以及 equals() 方法为 true,则认为是同一个 key
2)两个不同的对象,有可能出现这两个对象的哈希值相同并且 equals() 也为 true 的情况,这两个对象被当做 key 使用时,则就认为是同一个 key
五、ConcurrentHashMap
1.数据结构
在1.7版底层是个分片数组,为了保证线程安全它有个分段锁即Segment锁,这个Segment继承于ReentranLock来保证它的线程安全的,它每次只给一段加速来保证它的并发度,另外在1.8的时候,它改成了与HashMap一样的数据结构,数组加单链表或者红黑树的数据结构,在1.8放弃了分段锁机制,而使用Synchronized和CAS来操作
2.ConcurrentHashMap 的 get() 方法需要加锁吗
3.为什么 ConcurrentHashMap 不支持 key 或者 value 为 null
六、其它常见问题
1.如何把线程不安全的集合类变成线程安全的
任何集合类都可以通过使用同步包装器变成线程安全的
List
Map<K , V> synchHashMap = Col1ections.synchronizedMap(new HashMap<K , V>0);
2.HashMap 和 HashTable 有什么区别
3.HashMap 和 HashSet 有什么区别
4.LinkedHashMap 有了解过吗
5.TreeMap 有了解过吗
6.IdentityHashMap 有了解过吗
7.WeakHashMap 有了解过吗
(2)
一、ArrayList
1.数据结构
1)底层是数组结构,特点是查询比较快,增删比较慢
2)当对象初始创建的时候,如果没有指定容量,它的容量默认是0,当调用add方法添加元素的时候,容量会初始化成10,然后每次扩容之后的容量是之前的1.5倍
2.ArrayList 为什么是线程不安全的
add() 方法造成的,add() 方法主要做两个动作,一是扩容操作,二是为数组对应的索引赋值以及赋值完毕后把 size 加1,多个线程同时调用 add() 方法可能会出现以下两种情况
1)发生索引越界异常,假设线程A开始进行扩容操作时 size 的值为9,则无需扩容,此时线程A挂起,线程B进来,线程B进行扩容操作时 size 的值还是9,则无需扩容,线程B把元素添加到索引为9的位置,然后 size 加1变成10,线程A恢复,线程A往索引为10的位置添加元素,由于数组的容量为10,因为发生索引越界异常
2)数组中的元素被覆盖,线程A在给数组的索引赋值完成之后,还没有为 size 加1,线程挂起,此时线程B读取到的 size 的值与线程A是一样的,所以线程B也往线程A那个索引位置添加元素,然后就会把线程A添加的那个元素给覆盖了,最终就是线程A添加元素失败
3.解决ArrayList的线程安全问题
1)Collections.synchronizedList(new ArrayList<>())
2)java.util.concurrent.CopyOnWriteArrayList(适合读多写少的场景)
二、LinkedList
1)底层是一个双向链表结构(JDK1.6之前为双向循环链表),特点的话跟 ArrayList 相反,就是增删元素比较快,查询效率相对较低
2)LinkedList 是线程不安全的
三、HashSet
1)HashSet一个主要的特点是无序,另外一个是它不能存放重复的元素
2)HashSet如何检查重复,先调用 hashCode() 方法获取哈希值,如果集合中没有相同的哈希值,则直接添加,如果有相同的哈希值,则比较两个元素的equals() 方法,如果返回true,判定为重复元素则不添加,否则就添加元素
3)如果 HashSet 的泛型是自定义类型,则必须重写 hashCode() 和 equals() 方法
四、HashMap
1.数据结构
1)在1.7版本为数组加单链表
2)在1.8版本改成了数组 + 单链表 + 红黑树,当链表长度大于8并且哈希桶数量大于64时,会将单链表转成红黑树,当红黑树的节点数量小于等于6时,红黑树会重新再转成单链表
2.HashMap 几个重要的属性
哈希桶:transient Node<K,V>[] table;
桶的默认初始容量:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
哈希桶的阈值:int threshold;(threshold = 哈希桶的容量 * 扩容因子 = table.length * loadFactor)
扩容因子:final float loadFactor;(默认扩容因子0.75; static final float DEFAULT_LOAD_FACTOR = 0.75f;)
实际存在的键值对数量:transient int size;
3.根据 key 计算键值对在哈希桶中的位置
/**
- 1)调用 key 的 hashCode() 方法计算哈希值 = hashCode
- 2)将哈希值不带符号右移16位 = hashCode2
- 3)将哈希值与右移16位之后的哈希值做异或运算,int hash = hashCode ^ hashCode2
- 4)将哈希桶的数组长度减1之后与上一步的结果做与运算,int index = (数组的大小 - 1) & hash
*/
public static void main(String[] args) {
String str = "bbb";
int hashCode = str.hashCode(); // 97314
int hashCode2 = str.hashCode() >>> 16; // 0001 0111 1100 0010 0010 -> 0000 0000 0000 0000 0001
int hash = hashCode ^ hashCode2; // 0001 0111 1100 0010 0010 ^ 0000 0000 0000 0000 0001 = 0001 0111 1100 0010 0011
int i = (16 - 1) & hash; // 0000 0000 0000 0000 1111 & 0001 0111 1100 0010 0011 = 0000 0000 0000 0000 0001
System.out.println(i); // 3
}
4.put() 方法的执行过程
1)如果数组还没有创建,则先创建数组
2)根据 key 以及数组的长度确定键值对在哈希桶中的位置
3)如果该位置为空,则直接把键值对放在该位置
4)如果这个位置不为空,则判断这个位置的 key 与要 put 的 key 是否相同,如果相同,则把这个位置的 value 替换为要 put 的value;如果 key 不相同,则判断这个位置上的元素是不是红黑树类型,如果是红黑树类型,则挂到红黑树上,如果不是红黑树类型,则判断链表的长度大于等于8并且数组大小大于等于64,如果成立则先把链表转成红黑树,然后挂到红黑树上,否则挂到链表上
(无论是把放入数组、链表或还是红黑树,都会先判断 key 是否相同,如果相同则替换该位置上的 value)
5)最后 size++ 以及判断是否需要扩容
5.get() 方法的执行过程
1)根据 key 以及数组的长度计算出数组的下标
2)根据下标从数组中获取元素,如果该位置上的 key 与传进去的 key 相同,则直接返回该元素,如果不同,则获取下一个节点,判断该节点如果是红黑树,则从红黑树中获取元素,否则从链表中获取元素
6.resize() 方法的执行过程
7.将链表转成红黑树的方法 treeifyBin()
8.扩容机制
1)默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1
2)以2的n次幂扩容的原因是为了在取模和扩容时做优化
9.HashMap 线程不安全的原因
HashMap 线程不安全有三个场景
1)并发扩容时导致死循环
JDK 7 中 HashMap 采用「头插法」处理哈希冲突的链表,并发扩容时可能导致链表成环,引发死循环
原理:
· 当 HashMap 元素数量超过阈值(capacity * loadFactor)时,会触发扩容(resize()),新建更大的数组并将旧元素迁移到新数组
· 并发扩容时,多个线程同时迁移同一链表,由于「头插法」会改变链表顺序,可能导致两个节点互相引用,形成环形链表
· 后续查询该链表时,会陷入无限循环(next 指针永远无法指向 null),最终导致 CPU 使用率飙升
(大白话:两个线程在同时进行put操作时,由于元素数量超过阈值而同时进行扩容,多个线程迁移同一链表,头插法会导致形成环形链表,后续查询该链表时,会导致死循环)
2)并发执行 put() 操作时,可能导致后插入的元素覆盖先插入的元素,造成数据丢失
原理:
线程 A 计算出 key 的哈希索引后,判断该位置为空,准备插入新节点
线程 B 同时计算出相同的哈希索引,且也判断该位置为空,先于线程 A 插入新节点
线程 A 恢复运行后,仍认为该位置为空,直接插入新节点,覆盖线程 B 插入的数据
3)get() 可能返回 null
一个线程执行 put() 插入元素后,另一个线程执行 get() 可能无法获取到该元素,返回 null
原理:
HashMap 的 size、table 等字段未被 volatile 修饰,不保证多线程间的内存可见性
线程 A 插入元素后,其修改的 table 或 size 可能未及时刷新到主内存
线程 B 读取时仍使用本地缓存中的旧数据,导致无法感知线程 A 插入的新元素
10.初始容量为什么是16(为什么要以2的n次幂扩容)
· HashMap 在计算元素要存放在数组中的 index 时,使用位运算代替了取模运算,之所以可以做等价替换,前提是要求 HashMap 的容量一定要是2的次幂,那么既然是2^n,为什么一定要是16呢?为什么不能是4、8或者32呢?这应该是个经验值,需要在效率和内存使用上做一个权衡,这个值既不能太小,也不能太大,太小了就有可能频繁发生扩容,影响效率。太大了又浪费空间,不划算,所以,16就作为一个经验值被采用了
· 减少哈希冲突,如果不是2的n次幂,可能数组的一些位置永远都不会插入数据,浪费数组的空间,加大 hash 冲突
11.扩容因子为什么是0.75
· 在空间和时间之间取得一个平衡
· 减少哈希冲突
12.为什么要用位运算代替取模运算
因为位运算直接对内存数据进行操作,不需要转成十进制,所以位运算要比取模运算的效率更高
13.JDK1.7 多线程 put 操作导致死循环
14.是同一个 key 的判断标准
1)如果 key 的哈希值以及 equals() 方法为 true,则认为是同一个 key
2)两个不同的对象,有可能出现这两个对象的哈希值相同并且 equals() 也为 true 的情况,这两个对象被当做 key 使用时,则就认为是同一个 key
五、ConcurrentHashMap
1.数据结构
在1.7版底层是个分片数组,为了保证线程安全它有个分段锁即Segment锁,这个Segment继承于ReentranLock来保证它的线程安全的,它每次只给一段加速来保证它的并发度,另外在1.8的时候,它改成了与HashMap一样的数据结构,数组加单链表或者红黑树的数据结构,在1.8放弃了分段锁机制,而使用Synchronized和CAS来操作
2.ConcurrentHashMap 的 get() 方法需要加锁吗
3.为什么 ConcurrentHashMap 不支持 key 或者 value 为 null
六、其它常见问题
1.如何把线程不安全的集合类变成线程安全的
任何集合类都可以通过使用同步包装器变成线程安全的
List
Map<K , V> synchHashMap = Col1ections.synchronizedMap(new HashMap<K , V>0);
2.HashMap 和 HashTable 有什么区别
3.HashMap 和 HashSet 有什么区别
4.LinkedHashMap 有了解过吗
5.TreeMap 有了解过吗
6.IdentityHashMap 有了解过吗
7.WeakHashMap 有了解过吗
