Java常见面试题2
1.Java集合
面向对象语言对事物的体现都是以对象的形式，所以为了方便对多个对象的操作，就对对象进行存储，集合是存储对象最常用的一种方式。
数组虽然可以存储对象，但长度是固定的；集合长度的可变的，数组可以存储基本数据类型，集合只能存储对象。
集合的特点：
集合只能用于存储对象
集合长度是可变的
集合可以存储不同类型的对象
上述类图中，实线边框的是实现类，比如ArrayList，LinkedList，HashMap等，折线边框的是抽象类，比如AbstractCollection，AbstractList，AbstractMap等，而点线边框的是接口，比如Collection，Iterator，List等。
Java的集合主要有两个接口派生而出：Collection和Map
Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口和实现类。
Collection接口
Collection接口是List接口和Set接口的父接口。Collection接口中定义了对集合进行增、删、改、查的方法，List接口和Set接口继承了这些方法。
| 返回值 | 方法 | 说明 |
|---|---|---|
| boolean | add(E e) | 向集合末尾添加一个元素 |
| boolean | addAll(Collection<? extends E> c) | 将集合c中所有元素都添加到当前对象中 |
| boolean | remove(Object o) | 删除集合中的指定的元素 |
| boolean | removeAll(Collection<?> c) | 删除当前集合中所有等于由集合c指定的元素。 |
| void | clear() | 清空集合中的所有元素 |
| boolean | contains(Object o) | 如果集合中包含指定元素o，返回true，否则返回false |
| boolean | containsAll(Collection<?> c) | 如果当前集合中包含指定集合c，返回true，否则返回false |
| boolean | retainAll(Collection<?> c) | 仅保留该指定集合中存在的所有元素。其余删除 |
| int | size() | 返回该集合中元素的个数 |
| boolean | isEmpty() | 集合为空返回true，否则返回false |
| Object[] | toAraay() | 将当前集合转换为Object数组 |
| Iterator |
iterator | 迭代器，集合专用的遍历方式 |
List接口及其实现类
List是有序可重复的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素。实现List接口的常用类有LinkedList，ArrayList，Vector。
| ArrayList | LinkedList | Vector | |
|---|---|---|---|
| 底层数据结构 | 数组 | 双向链表 | 数组 |
| 是否线程安全 | 非线程安全 | 非线程安全 | 线程安全 |
| 是否同步 | 非同步 | 非同步 | 同步 |
| 优缺点 | 检索效率高；增删效率低 | 检索效率低，增删效率高 | 保证了线程安全，但是效率低 |
List特有的方法：
| 返回值 | 方法 | 说明 |
|---|---|---|
| void | add(int index，0bject obj) | 在指定位置添加元素 |
| 0bject | remove(int index) | 根据指定索引删除元素，并把删除的元素返回 |
| 0bject | set(int index，0bject obj) | 把指定索引位置的元素修改为指定的值，返回修改前的值 |
| int | indexOf(0bject o) | 返回指定元素在集合中第一次出现的索引 |
| Object | get(int index) | 获取指定位置的元素 |
| ListIterator | listIterator() | 列表迭代器 |
| List | subList(int fromIndex，int toIndex) | 截取集合 |
ArrayList类
底层是Object数组，所以ArrayList集合查询效率高，增删效率低。
为什么数组检索效率高，增删效率低？
检索效率高是因为
- 第一：Java的数组中存储的每个元素类型一致，也就是说每个元素占用的空间大小相同；
- 第二：Java的数组中存储的每个元素的内存地址是连续状态的；
- 第三：首元素的内存地址作为整个数组对象的内存地址，可见我们是知道首元素内存地址的；
- 第四：数组中的元素是有下标的，有下标就可以计算出被查找的元素和首元素的偏移量。
增删效率低是因为往数组里某个下标位置增加元素需要把这个下标往后的元素后移一位，删除也同理。
ArrayList自动扩容机制：初始容量为10，扩容后为原容量的1.5倍。
ArrayList构造方法：
| 构造方法 | 说明 |
|---|---|
| ArrayList() | 构造一个初始容量为 10 的空列表 |
| ArrayList(Collection<? extends E> c) | 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。 |
| ArrayList(int initialCapacity) | 构造一个具有指定初始容量的空列表。 |
LinkedList类
底层采用双向链表结构，优势在于高效地插入和删除其中的元素，但随机访问元素的速度较慢，特性与ArrayList刚好相反。如果程序需要反复对集合做插入和删除操作，应选择LinkedList类。
LinkedList类有两个构造方法：
| 构造方法 | 说明 |
|---|---|
| LinkedList() | 构造一个空列表。 |
| LinkedList(Collection<? extends E> c) | 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。 |
LinkedList类还实现了Deque和Queue接口，实现了这两个接口中的指定的方法，用于处理首部和尾部的元素。可以利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。 它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等。
| 返回值 | 方法 | 说明 |
|---|---|---|
| public void | addFirst(E e) / addLast(E e） | 将指定元素e插/添加到当前列表的开头/结尾 |
| public boolean | offerFirst(E e) / offerLast(E e) | 将指定元素e插/添加到当前列表的开头/结尾。成功返回true，否则返回false |
| public E | removeFirst() / removeLast() | 获取并移除当前列表的第一个元素/最后一个元素。如果当前列表为空，则抛NoSuchElementExceotion异常 |
| public E | pollFirst() / pollLast() | 获取并移除当前列表的第一个元素/最后一个元素。如果列表为空，则返回null |
| public E | getFirst() / getLast() | 获取当前列表的第一个元素/最后一个元素。如果当前列表为空，则抛NoSuchElementExceotion异常 |
| public E | peekFirst()/peekLast() | 获取并移除当前列表的第一个元素/最后一个元素。如果列表为空，则返回null |
Vector类
底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素，不建议使用。
Set接口及其实现类
无序集合，不允许存放重复的元素；允许使用null元素。对 add()、equals() 和 hashCode() 方法进行更为严格的限制。 （ HashSet和TreeSet集合底层都是Map，HashSet底层是HashMap，TreeSet底层是TreeMap ）
HashSet类
HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。
具体实现唯一性的比较过程：
存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值，然后跟已经存储的元素的hashCode值比较，如果hashCode不相等，则所存储的两个对象一定不相等，此时存储当前的新的hashCode值处的元素对象；如果hashCode相等，存储元素的对象还是不一定相等，此时会调用equals()方法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比较的内容不相等，那么就是不同的对象，就该存储了，此时就要采用哈希的解决地址冲突算法，在当前hashCode值处类似一个新的链表， 在同一个hashCode值的后面存储存储不同的对象，这样就保证了元素的唯一性。
TreeSet类
集合底层是TreeMap，TreeMap底层是二叉树结构。与HashSet类不同，TreeSet类不是散列的，而是有序的。
元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法。
Iterator接口（迭代器）
Iterator接口是对Collection进行迭代的迭代器。利用这个接口，可以对Collection中的元素进行访问，实现对集合元素的遍历。
| 返回值 | 方法 | 说明 |
|---|---|---|
| boolean | hasNext() | 如果仍有元素可以迭代，则返回 true |
| E | Next() | 返回迭代的下一个元素 |
| void | remove() | 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（只有在调用Next()方法后才可以使用） |
迭代器一开始指向第一个对象，使用Next()后指向下一个对象。在迭代集合元素过程中，如果使用了出remove()方法之外的方式改变了集合结构，迭代器必须重新获取。且remove()只有在调用Next()方法后才可以使用，每次执行Next()之后最多调用一次。
public static void main(String[] args) {
// 创建ArrayList实例
ArrayList<Integer> list = new ArrayList<>();
// 给list添加元素
for (int i=1; i<9; i++) {
list.add(i);
}
// 返回Iterator迭代器
Iterator<Integer> it = list.iterator();
//迭代器遍历集合
while (it.hasNext()) { // 判断是否有元素
int x = it.next(); // 获取元素
System.out.println(x);
if (x == 5) // 元素为5时移除元素
it.remove();
}
// 转换为对象数组
Object[] a = list.toArray();
System.out.printf("删除之后的内容是： ");
for (int i=0; i<a.length; i++) {
System.out.printf("%s\t",a[i]);
}
}
结果：
1
2
3
4
5
6
7
8
删除之后的内容是： 1 2 3 4 6 7 8 Map接口
- Map集合和Collection集合没有继承关系
- Map集合以Key和Value的键值对方式存储元素
- Key和Value都是存储java对象的内存地址，key起到主导地位，value是key附属品
- 无序不可重复
遍历Map集合的四种方法：
public static void main(String[] args) {
Map<String, String> map= new HashMap<>();
map.put("关羽", "云长");
map.put("张飞", "益德");
map.put("赵云", "子龙");
map.put("马超", "孟起");
map.put("黄忠", "汉升");
//第一种遍历map的方法，通过加强for循环map.keySet()，然后通过键key获取到value值
for(String s:map.keySet()){
System.out.println("key : "+s+" value : "+map.get(s));
}
System.out.println("====================================");
//第二种只遍历键或者值，通过加强for循环
for(String s1:map.keySet()){//遍历map的键
System.out.println("键key ："+s1);
}
for(String s2:map.values()){//遍历map的值
System.out.println("值value ："+s2);
}
System.out.println("====================================");
//第三种方式Map.Entry<String, String>的加强for循环遍历输出键key和值value
Set<Map.Entry<String,String>> set = map.entrySet();
for(Map.Entry<String, String> entry : set){
System.out.println("键 key ："+entry.getKey()+" 值value ："+entry.getValue());
}
System.out.println("====================================");
//第四种Iterator遍历获取，然后获取到Map.Entry<String, String>，再得到getKey()和getValue()
Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<String, String> entry=it.next();
System.out.println("键key ："+entry.getKey()+" value ："+entry.getValue());
}
System.out.println("====================================");
}
HashMap类
HashMap集合底层是哈希表/散列表的数据结构。
哈希表是一个数组与单向链表的结合体。 所以哈希表在查询和增删数据方面效率都很高。
HashMap底层实际上是一个一维数组，数组里面存的是一个Node（HashMap.Node节点，这个节点里面存储了哈希值，键值对，下一个节点的内存地址）。哈希值是key的hashCode()方法的结果，hash值再通过哈希函数，可以转换为数组的下标。
map.put(k,v)实现原理：
①先将键值对k，v封装到Node对象中；
②底层会调用k的hashCode()方法得出hash值；
③通过哈希函数，将hash值转换为数组的下标。
④进行比较：下标位置如果没有任何元素，就把Node添加到这个位置上；如果下标位置上有链表，此时会拿着k和链表上的每一个节点的k用equals()方法进行比较（因为Map是不可重复的），如果没有重复的新节点就会加到链表末尾，否则则会覆盖有相同k值的节点。
map.get(k)实现原理：
①调用k的hashCode()方法得出hash值；
②进行比较：下标位置如果没有任何元素，返回null，如果下标位置上有链表，此时会拿着k和链表上的每一个节点的k用equals()方法进行比较，如果结果都是false，则返回null；如果有一个节点用了equals方法后结果为true，则返回这个节点的value值。
问：为什么哈希表随机增删、查询效率都高？
答：增删是在链表上完成的，查询也不需要都扫描，只需要部分扫描。
这里重点来了，上述调用了的hashCode()和equals()方法，都需要重写！
equals()重写原因：equals默认比较的是两个对象的内存地址，但我们需要比较的是k中的内容。
hashCode()重写原因：请看此处，为什么重写equals()就一定要重写hashCode()方法？****
结论：放在HashMap()集合key部分的元素，，以及放在HashSet集合中的元素，需要同时重写hashCode和equals方法。
TreeMap类
TreeMap类是Map接口的具体实现，底层是二叉树数据结构，**支持元素的有序存储**，可以按照元素的大小顺序自动排序。TreeMap类中所有元素都必须实现Comparable接口，与TreeSet类相似（TreeSet类底层是TreeMap,放在TreeSet集合中的元素，等同于放在TreeMap集合中的key部分）。
TreeMap类自动排序测试：
public static void main(String[] args) {
TreeSet<String> ts = new TreeSet<>();
ts.add("ss");
ts.add("abf");
ts.add("g");
ts.add("f");
ts.add("abcd");
ts.add("abc");
Iterator<String> it = ts.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
结果：
abc
abcd
abf
f
h
ss 对于自定义的类型，TreeMap是无法自动排序的。需要指定自定义对象之间的比较规则。如果没有指定（谁大谁小没有说明），TreeMap类不知如何给元素排序，就会报错（此处涉及二叉树的排序，可以通过这篇文章了解一下），比如以下这段代码：
public class TreeSetTest02 {
public static void main(String[] args) {
Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
TreeSet<Student> students = new TreeSet<>();
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
结果会报错：
java.lang.ClassCastException: class test.Student cannot be cast to class java.lang.Comparable
这时我们就需要对自定义类型实现Comparable接口，并重写compareTo()方法，需要在这个方法中编写比较的逻辑（比较规则）。
compareTo方法返回的是int值：
返回0表示相同，value会覆盖；
返回>0，会在右子树上找；
返回<0，会在左子树上找。
比较规则是自己设定的，首先比较年龄的大小，如果年龄一样，则比较字符串的大小。
public class TreeSetTest02 {
public static void main(String[] args) {
Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
TreeSet<Student> students = new TreeSet<>();
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
class Student implements Comparable<Student>{
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
// compareTO方法返回的是int值；
// 比较规则是自己设定的，首先比较年龄的大小，如果年龄一样，则比较字符串的大小；
public int compareTo(Student o) {
if (this.age != o.age)
return this.age - o.age;
else //年龄一样
return this.name.compareTo(o.name); // 此处调用的不是这个类中的compareTo方法，而是调用了字符串的compareTo方法
}
}
结果：
Student{name='Ana', age=18}
Student{name='Lip', age=18}
Student{name='Stark', age=21}
Student{name='Bob', age=25}TreeSet集合中元素可排序的第二种方式：使用比较器方式。 单独写一个比较器，这个比较器实现java.util.Comparator接口。并在创建TreeSet集合时，传入这个比较器。
public class TreeSetTest02 {
public static void main(String[] args) {
Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
//创建TreeSet集合时，需要传入这个比较器
TreeSet<Student> students = new TreeSet<>(new StudentComparator());
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
class Student {
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
//单独写一个比较器
//比较器实现java.util.Comparator接口
class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
if (o1.age != o2.age)
return o1.age - o2.age;
else
return o1.name.compareTo(o2.name);
}
}
当然也可以使用匿名内部类的方式。
public class TreeSetTest02 {
public static void main(String[] args) {
Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
//创建TreeSet集合时，需要传入比较器（使用匿名内部类）
TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if (o1.age != o2.age)
return o1.age - o2.age;
else
return o1.name.compareTo(o2.name);
}
});
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
class Student {
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
结论： 放到TreeSet或者TreeMap集合key部分的元素要想做到排序，包括两种方式:
- 第一种:放在集合中的元素实现java. lang. Comparable接口。（比较规则固定的时候使用这种）
- 第二种:在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象。（比较规则经常变化的时候使用这种）
Comparable 和 Comparator 有哪些区别？
答：Comparable 和 Comparator 的主要区别如下：
- Comparable 位于 java.lang 包下，而 Comparator 位于 java.util 包下；
- Comparable 在排序类的内部实现，而 Comparator 在排序类的外部实现；
- Comparable 需要重写 CompareTo() 方法，而 Comparator 需要重写 Compare() 方法；
- Comparator 在类的外部实现，更加灵活和方便。
- Post link: http://sovzn.github.io/2021/03/31/Java-interview-2/
- Copyright Notice: All articles in this blog are licensed under unless otherwise stated.
若没有本文 Issue，您可以使用 Comment 模版新建。
GitHub Issues