[数据结构与算法]Java高频面试题笔记（更新...）

集合类

1.List，Set，Map三者的区别

List： 有序集合（有序指存入的顺序和取出的顺序相同，不是按照元素的某些特性排序），可存储重复元素，可存储多个null。
Set： 无序集合（元素存入和取出顺序不一定相同），不可存储重复元素，只能存储一个null。
Map： 使用键值对的方式对元素进行存储，key是无序的，且是唯一的。value值不唯一。不同的key值可以对应相同的value值。

2.常用集合框架底层数据结构

List：
ArrayList：数组
LinkedList：双线链表

Set：
HashSet：底层基于HashMap实现，HashSet存入读取元素的方式和HashMap中的Key是一致的。
TreeSet：红黑树

Map：
HashMap： JDK1.8之前HashMap由数组+链表组成的， JDK1.8之后有数组+链表/红黑树组成，当链表长度大于8时，链表转化为红黑树，当长度小于6时，从红黑树转化为链表。这样做的目的是能提高HashMap的性能，因为红黑树的查找元素的时间复杂度远小于链表。
HashTable：数组+链表
TreeMap：红黑树

3.哪些集合类是线程安全的

Vector：相当于有同步机制的ArrayList
Stack：栈
HashTable
enumeration：枚举

4.Java集合的快速失败机制 “fail-fast”和安全失败机制“fail-safe”是什么

快速失败：
Java的快速失败机制是Java集合框架中的一种错误检测机制，当多个线程同时对集合中的内容进行修改时可能就会抛出ConcurrentModificationException异常。其实不仅仅是在多线程状态下，在单线程中用增强for循环中一边遍历集合一边修改集合的元素也会抛出ConcurrentModificationException异常。看下面代码

public class Main{
    public static void main(String[] args) {
    List<integer> list = new ArrayList&lt;&gt;();
        for(Integer i : list){
            list.remove(i);  //运行时抛出ConcurrentModificationException异常
        }
    }
}

正确的做法是用迭代器的remove()方法，便可正常运行。

public class Main{
    public static void main(String[] args) {
    List<integer> list = new ArrayList&lt;&gt;();
    Iterator<integer> it = list.iterator();
        while(it.hasNext()){
            it.remove();
        }
    }
}

造成这种情况的原因是什么？可以发现两次调用的remove()方法不同，一个带参数据，一个不带参数，这个后面再说，经过查看ArrayList源码，找到了抛出异常的代码

final void checkForComodification() {
      if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
}

从上面代码中可以看到如果modCount和expectedModCount这两个变量不相等就会抛出ConcurrentModificationException异常。那这两个变量又是什么呢？继续看源码

protected transient int modCount = 0; //在AbstractList中定义的变量

从上面代码可以看到，modCount初始值为0，而expectedModCount初始值等于modCount。也就是说在遍历的时候直接调用集合的remove()方***导致modCount不等于expectedModCount进而抛出ConcurrentModificationException异常，而使用迭代器的remove()方法则不会出现这种问题。那么只能在看看remove()方法的源码找找原因了

public E remove(int index) {
    rangeCheck(index);
 
    modCount++;
    E oldValue = elementData(index);
 
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}

从上面代码中可以看到只有modCount++了，而expectedModCount没有操作，当每一次迭代时，迭代器会比较expectedModCount和modCount的值是否相等，所以在调用remove()方法后，modCount不等于expectedModCount了，这时就了报ConcurrentModificationException异常。但用迭代器中remove()的方法为什么不抛异常呢？原来迭代器调用的remove()方法和上面的remove()方法不是同一个！迭代器调用的remove()方法长这样：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
 
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;    //这行代码保证了expectedModCount和modCount是相等的
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

从上面代码可以看到expectedModCount = modCount，所以迭代器的remove()方法保证了expectedModCount和modCount是相等的，进而保证了在增强for循环中修改集合内容不会报ConcurrentModificationException异常。

上面介绍的只是单线程的情况，用迭代器调用remove()方法即可正常运行，但如果是多线程会怎么样呢？

答案是在多线程的情况下即使用了迭代器调用remove()方法，还是会报ConcurrentModificationException异常。这又是为什么呢？还是要从expectedModCount和modCount这两个变量入手分析，刚刚说了modCount在AbstractList类中定义，而expectedModCount在ArrayList内部类中定义，所以modCount是个共享变量而expectedModCount是属于线程各自的。简单说，线程1更新了modCount和属于自己的expectedModCount，而在线程2看来只有modCount更新了，expectedModCount并未更新，所以会抛出ConcurrentModificationException异常。

安全失败:
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会抛出ConcurrentModificationException异常。缺点是迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生了修改，迭代器是无法访问到修改后的内容。java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用。

5.Array 和 ArrayList 有何区别

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
Array大小是固定的，ArrayList的大小是动态变化的。(ArrayList的扩容是个常见面试题)
相比于Array，ArrayList有着更多的内置方法，如addAll()，removeAll()。
对于基本类型数据，ArrayList 使用自动装箱来减少编码工作量；而当处理固定大小的基本数据类型的时候，这种方式相对比较慢，这时候应该使用Array。

6.comparable 和 comparator的区别

comparable接口出自java.lang包，可以理解为一个内比较器，因为实现了Comparable接口的类可以和自己比较，要和其他实现了Comparable接口类比较，可以使用compareTo(Object obj)方法。compareTo方法的返回值是int，有三种情况：
返回正整数（比较者大于被比较者）
返回0（比较者等于被比较者）
返回负整数（比较者小于被比较者）

comparator接口出自java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序，返回值同样是int，有三种情况，和compareTo类似。

它们之间的区别：
很多包装类都实现了comparable接口，像Integer、String等，所以直接调用Collections.sort()直接可以使用。如果对类里面自带的自然排序不满意，而又不能修改其源代码的情况下，使用Comparator就比较合适。此外使用Comparator可以避免添加额外的代码与我们的目标类耦合，同时可以定义多种排序规则，这一点是Comparable接口没法做到的，从灵活性和扩展性讲Comparator更优，故在面对自定义排序的需求时，可以优先考虑使用Comparator接口。

7.遍历一个 List 有哪些不同的方式

先说一下常见的元素在内存中的存储方式，主要有两种：

顺序存储（Random Access）：相邻的数据元素在内存中的位置也是相邻的，可以根据元素的位置（如ArrayList中的下表）读取元素。
链式存储（Sequential Access）：每个数据元素包含它下一个元素的内存地址，在内存中不要求相邻。例如LinkedList。

主要的遍历方式主要有三种：

for循环遍历：遍历者自己在集合外部维护一个计数器，依次读取每一个位置的元素。
Iterator遍历：基于顺序存储集合的Iterator可以直接按位置访问数据。基于链式存储集合的Iterator，需要保存当前遍历的位置，然后根据当前位置来向前或者向后移动指针。
foreach遍历：foreach 内部也是采用了Iterator的方式实现，但使用时不需要显示地声明Iterator。

那么对于以上三种遍历方式应该如何选取呢？

在Java集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常用来标记List的实现是否支持RandomAccess。所以在遍历时，可以先判断是否支持RandomAccess（list instanceof RandomAccess），如果支持可用 for循环遍历，否则建议用Iterator或 foreach遍历。

8.ArrayList的扩容机制

ArrayList的初始容量为10，扩容时对是旧的容量值加上旧的容量数值进行右移一位（位运算，相当于除以2，位运算的效率更高），所以每次扩容都是旧的容量的1.5倍。

9.ArrayList 和 LinkedList 的区别是什么

1.是否线程安全：ArrayList和LinkedList都是不保证线程安全的
2.底层实现：ArrayList的底层实现是数组，LinkedList的底层是双向链表。
3.内存占用：ArrayList会存在一定的空间浪费，因为每次扩容都是之前的1.5倍，而LinkedList中的每个元素要存放直接后继和直接前驱以及数据，所以对于每个元素的存储都要比ArrayList花费更多的空间。
4.应用场景：ArrayList的底层数据结构是数组，所以在插入和删除元素时的时间复杂度都会收到位置的影响，平均时间复杂度为o(n)，在读取元素的时候可以根据下标直接查找到元素，不受位置的影响，平均时间复杂度为o(1)，所以ArrayList更加适用于多读，少增删的场景。LinkedList的底层数据结构是双向链表，所以插入和删除元素不受位置的影响，平均时间复杂度为o(1)，如果是在指定位置插入则是o(n)，因为在插入之前需要先找到该位置，读取元素的平均时间复杂度为o(n)。所以LinkedList更加适用于多增删，少读写的场景。

10.ArrayList 和 Vector 的区别是什么

相同点：
都实现了List接口
底层数据结构都是数组

不同点：
线程安全：Vector使用了Synchronized来实现线程同步，所以是线程安全的，而ArrayList是线程不安全的。
性能：由于Vector使用了Synchronized进行加锁，所以性能不如ArrayList。
扩容：ArrayList和Vector都会根据需要动态的调整容量，但是ArrayList每次扩容为旧容量的1.5倍，而Vector每次扩容为旧容量的2倍。

11.简述 ArrayList、Vector、LinkedList 的存储性能和特性

ArrayList底层数据结构为数组，对元素的读取速度快，而增删数据慢，线程不安全。
LinkedList底层为双向链表，对元素的增删数据快，读取慢，线程不安全。
Vector的底层数据结构为数组，用Synchronized来保证线程安全，性能较差，但线程安全。

12.HashSet 的实现原理

HashSet的底层是HashMap，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。HashSet的值存放于HashMap的key上，HashMap的value统一为PRESENT。

13.HashSet如何检查重复

这里面涉及到了HasCode()和equals()两个方法。
String类中重写的equals方法。

String类中重写的equals方法。

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

从源码中可以看到：
equals方法首先比较的是内存地址，如果内存地址相同，直接返回true；如果内存地址不同，再比较对象的类型，类型不同直接返回false；类型相同，再比较值是否相同；值相同返回true，值不同返回false。
总结一下，equals会比较内存地址、对象类型、以及值，内存地址相同，equals一定返回true；对象类型和值相同，equals方法一定返回true。
如果没有重写equals方法，那么equals和==的作用相同，比较的是对象的地址值。

hashCode：

hashCode方法返回对象的散列码，返回值是int类型的散列码。散列码的作用是确定该对象在哈希表中的索引位置。

关于hashCode有一些约定：
1.两个对象相等，则hashCode一定相同。
2.两个对象有相同的hashCode值，它们不一定相等。
3.hashCode()方法默认是对堆上的对象产生独特值，如果没有重写hashCode()方法，则该类的两个对象的hashCode值肯定不同

介绍完equals()方法和hashCode()方法，继续说下HashSet是如何检查重复的。

HashSet的特点是存储元素时无序且唯一，在向HashSet中添加对象时，首先会计算对象的HashCode值来确定对象的存储位置，如果该位置没有其他对象，直接将该对象添加到该位置；如果该存储位置有存储其他对象（新添加的对象和该存储位置的对象的HashCode值相同），调用equals方法判断两个对象是否相同，如果相同，则添加对象失败，如果不相同，则会将该对象重新散列到其他位置。

14.HashMap 的长度为什么是2的幂次方

因为HashMap是通过key的hash值来确定存储的位置，但Hash值的范围是-2147483648到2147483647，不可能建立一个这么大的数组来覆盖所有hash值。所以在计算完hash值后会对数组的长度进行取余操作，如果数组的长度是2的幂次方，(length - 1)&hash等同于hash%length，可以用(length - 1)&hash这种位运算来代替%取余的操作进而提高性能。

(length - 1)&hash解释：使用01111111…与hashcode取交，提高性能。

15.HashMap的扩容操作是怎么实现的

初始值为16，负载因子为0.75，阈值为负载因子*容量

resize()方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize()方法进行扩容。

每次扩容，容量都是之前的两倍

扩容时有个判断e.hash & oldCap是否为零，也就是相当于hash值对数组长度的取余操作，若等于0，则位置不变，若等于1，位置变为原位置加旧容量。

16.HashMap默认加载因子为什么选择0.75

这个主要是考虑空间利用率和查询成本的一个折中。如果加载因子过高，空间利用率提高，但是会使得哈希冲突的概率增加；如果加载因子过低，会频繁扩容，哈希冲突概率降低，但是会使得空间利用率变低。具体为什么是0.75，不是0.74或0.76，这是一个基于数学分析（泊松分布）和行业规定一起得到的一个结论。

17.为什么要将链表中转红黑树的阈值设为8？为什么不一开始直接使用红黑树

因为红黑树的节点所占的空间是普通链表节点的两倍，但查找的时间复杂度低，所以只有当节点特别多时，红黑树的优点才能体现出来。至于为什么是8，是通过数据分析统计出来的一个结果，链表长度到达8的概率是很低的，综合链表和红黑树的性能优缺点考虑将大于8的链表转化为红黑树。
链表转化为红黑树除了链表长度大于8，还要HashMap中的数组长度大于64。也就是如果HashMap长度小于64，链表长度大于8是不会转化为红黑树的，而是直接扩容。

18.HashMap是怎么解决哈希冲突的

哈希冲突：hashMap在存储元素时会先计算key的hash值来确定存储位置，因为key的hash值计算最后有个对数组长度取余的操作，所以即使不同的key也可能计算出相同的hash值，这样就引起了hash冲突。hashMap的底层结构中的链表/红黑树就是用来解决这个问题的。

HashMap中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景）

拉链法：
HasMap中的数据结构为数组+链表/红黑树，当不同的key计算出的hash值相同时，就用链表的形式将Node结点（冲突的key及key对应的value）挂在数组后面。

hash函数：
key的hash值经过两次扰动，key的hashCode值与key的hashCode值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样），这样做可以让hashCode取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。
原因：由于和（length-1）与运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。

红黑树：
在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。

19.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标

hashCode()处理后的哈希值范围太大，不可能在内存建立这么大的数组。

20.能否使用任何类作为 Map 的 key

需要重写equals()方法
而且重写了 equals()方法，也应该重写hashCode()方法。
最好定义key类是不可变的，这样key对应的hashCode()值可以被缓存起来，性能更好，这也是为什么String特别适合作为HashMap的key。

21.为什么HashMap中String、Integer这样的包装类适合作为Key

这些包装类都是final修饰，是不可变性的， 保证了key的不可更改性，不会出现放入和获取时哈希值不同的情况。
它们内部已经重写过hashcode(),equal()等方法。

22.如果使用Object作为HashMap的Key，应该怎么办呢

重写hashCode()方法，因为需要计算hash值确定存储位置
重写equals()方法，因为需要保证key的唯一性。

23.HashMap 多线程导致死循环问题

由于JDK1.7的hashMap遇到hash冲突采用的是头插法，在多线程情况下会存在死循环问题，但JDK1.8已经改成了尾插法，不存在这个问题了。但需要注意的是JDK1.8中的HashMap仍然是不安全的，在多线程情况下使用仍然会出现线程安全问题。

24.HashTable的底层实现

HashTable的底层数据结构是数组+链表，链表主要是为了解决哈希冲突，并且整个数组都是synchronized修饰的，所以HashTable是线程安全的，但锁的粒度太大，锁的竞争非常激烈，效率很低。

…待更新