集合<一>(早)
-
Java中有哪些容器(集合类)? 集合中的容器主要分为两种,分别为Map和Collection,Collection下有List/Set/Queue这些子接口, 其中,List接口的主要实现类有ArrayList,LinkedList,Vector;Set接口的主要实现类有HashSet,TreeSet,LinkedHashSet;Queue接口主要是BlockingQueue子接口,BlockingQueue接口的主要实现类有BlockingQueueArrayList等
-
Java中的容器,线程安全和线程不安全的分别有哪些? 主要讲一下那些是线程安全的,主要有Vector,CopyOnWriteArrayList,Collections.SynchronizedXXX,HashTable,Properties,ConcurrentHashMap等。
-
Map接口有哪些实现类? Map接口的实现类有HashMap,TreeMap,HashTable,Properties,ConrurrentHashMap等
-
如何得到一个线程安全的Map? 使用HashTable或者ConcurrentHashMap或者使用Collections.synchronizedMap方法
-
HashMap有什么特点? 线程不安全,允许key和value为null,效率较高
-
JDK7和JDK8中的HashMap有什么区别?
-
数据结构不一样:jdk7的HashMap使用的是数组加链表的形式,而jdk8的HashMap采用的是数组加链表加红黑树的形式。
-
存储方式不一样:jdk7存储时,如果hash冲突,则放到链表的的最后,最终可能链表很长,导致查询速度变慢,速度是O(N)。jdk8加入红黑树存储后,查询速度为O(logn),提高了查询速度。
-
扩容机制不一样:jdk7扩容时会为每个元素重新计算hash和索引值,这个过程比较消耗性能。jdk8只需要在某个位上进行简单的判断,如果为0,则放在原来的位置,若为1,则位置变为原来位置+容量,每个元素只是进行简单判断,而不需要每次重新进行hash值和索引的计算。
-
介绍一下HashMap底层的实现原理(主讲jdk8) 它是基于hash算法,通过put和get方法进行存储和获取键值对。
put方法时,它会传入key计算元素的hash值和索引值, 然后进一步存储(问put的过程再细讲), 如果元素的个数达到了loadFactor, 则自动扩容(问扩容机制再细讲)。
get方法时,它会传入key计算元素的hash值和索引值, 再通过equeals方法获取元素。
-
描述一下Map put的过程(主讲jdk8)
1.若数组为空,则进行首次扩容,初始化容量16。 2.先对key进行一个hash运算得到在hash表的下标。然后会去判断该位置是否含有元素,如果没有则直接放入,如果有的话,则判断keys中是否存在(因为如果有相同的key也只会出现在该下标链表位置),如果存在则直接覆盖,如果不存在,就继续判断是否是红黑树,如果不是红黑树则放到链表最后(并且发现,如果放入后链表的个数达到了8个而且hash表数量超过64,则还会自动转为红黑树以便提高查询速率),如果是红黑树,则放到红黑树中。 3.若元素个数超过了threhold,则再次扩容。
-
介绍一下HashMap的扩容机制(主讲jdk8) HashMap默认初始化容量是16,负载因子是0.75,当元素的个数达到阈值时,会自动扩容,每次扩容两倍。 扩容时,会对元素二进制的hash值中新增的bit位进行判断,如果是0,则元素的位置不变,如果是1,则是原来的位置+容量大小。 可以画出给面试官:
n-1表示的是容量,hash1表示的是元素1的hash值,hash2表示的是元素2的hash值,他们扩容前都是同一hash表位置(可能链表位置不同而已),扩容后,hash2的新增bit位是1,而hash1的新增bit位是0,因此,hash1的元素索引位置不变,而hash2的元素索引位置变为原来的位置+容量大小。因此他们可以有效避免hash冲突,将冲突的元素分散到不同的bucket。
-
HashMap中的循环链表是如何产生的? 简单来说,就扩容而言,当多线程同时进行扩容时,会导致一个线程的指针由于第二个线程完成扩容完成后,发生了指针指向顺序出错,结合扩容采用的是头插法,这种情况下,就会导致循环链表的产生。 11.HashMap为什么用红黑树而不用B树? 简单来说, 红黑树是平衡二叉树,节点高度比较低,在内存中的查询效率较高,因为它在内存中减少了到某节点需要比较的次数; B树是多路搜索树,节点大小比较大,在外存中的查询效率较高,因为它减少了磁盘IO的操作次数
-
HashMap为什么线程不安全? 在并发执行put操作或者扩容时,可能会产生循环链表。 13.HashMap如何实现线程安全? 使用Collections.SynchronizedMap方法,或者使用HashTable或者ConcurrentHashMap
-
HashMap是如何决哈希冲突的?(首先要明白什么是hash冲突?简单来说就是两个元素竞争同一个hash表位置) 通过链式寻址法和红黑树解决
扩展:hash冲突解决办法
线性探测法
链式寻址法
再hash法
建立公共移除区
-
说一说HashMap和HashTable的区别 hashmap性能较高,线程不安全, hashTable性能较低,但线程安全, hashmap的key-value均可为null hashTable的key-value不能为null
-
HashMap与ConcurrentHashMap有什么区别? hashmap性能较高,线程不安全。 ConcurrentHashMap性能较低,但线程安全。 hashmap的key-value均可为null。 ConcurrentHashMap的key-value不能为null。
-
介绍一下ConcurrentHashMap是怎么实现的? jdk1.7版本中,ConcurrentHashMap采用的是Segment 数组和 HashEntry 数组+链表构成,其中使用Segment是分段式可重入锁实现并发安全,锁住的是一个Segment对象。
扩展:可重入锁ReentrantLock,允许一个线程多次使用同一把锁。
jkd1.8版本中,ConcurrentHashMap采用的是数组+链表+红黑树的数据结构,采用CAS操作和 synchronized 关键字实现并发安全,锁住的是每个数组的头节点,锁的粒度更小,而且检索操作不加锁,性能也更高。
-
linkedHashMap的底层原理 主要是继承了HashMap,维护了一个双向链表,每个节点都有一个前驱引用和后驱引用。
集合<二>(早)
-
请介绍TreeMap的底层原理 treemap的底层结构是红黑树,treemap的成员变量是size,comparator,root,其中root节点是红黑树的根节点,它的数据类型是Entry,Entry包括了key,value,parent,left,right,color。treemap的Entry可以根据key进行排序,而key比较大小时是根据比较器进行判断的。
扩展:
treemap的构造器
默认的无参构造器
有参构造器,传入一个comparator比较器
有参构造器,传入一个map值
有参构造器,传入一个sortmap值
红黑树数据结构时间复杂度 查询时间复杂度是以2为底的O(logn)。
-
Map和Set有什么区别? Set是单列集合,Map是双列集合, Set的元素是无序不可重复的,LinkedHashSet的key本质是无序的,底层只是使用了一个双向链表实现有序,Map的key也是无序不可重复的。
-
List和Set有什么区别? List是有序可重复的,Set是无序不可重复的。
-
ArrayList和LinkedList有什么区别? 实现方式: ArrayList是以数组实现的,LinkedList是以链表实现的。 应用场景: ArrayList适合随机访问,因为它可以通过数组下标直接访问,但也不是说插入一定会慢,如果插入到最后,而且没有超出容量限制,时间复杂度是O(1)。LinkedList适合插入操作,因为它不需要扩容以及移动元素,但也不是说访问速度一定慢,如果访问头元素,时间复杂度是O(1)。 内存大小: LinkedList比ArrayList更占内存,因为LinkedList除了存储数据,还存储了前一个元素和后一个元素。
-
有哪些线程安全的List? Vector,Collections.SynchronizedList,CopyOnWriteArrayList
扩展:Vector:每次只允许一个线程操作, 性能最低。 Collections.SynchronizedList:SynchronizedList是Collections的一个内部类,同时Collections提供了一个方法,可以将一个List转成SynchronizedList,也可以使用SynchronizedList的构造器。SynchronizedList比Vector有更好的扩展和兼容以及性能。扩展就是在SynchronizedList构造器中还可以指定锁对象,兼容就是在SynchronizedList构造器中指定LinkedList和ArrayList,性能快是因为它锁的粒度比较小,锁住的是代码块,而Vector锁住的方法,一般来说锁粒度的大小和性能成反比。但也不是性能最优的。 CopyOnWriteArrayList:底层采用的是复制数组实现写操作。但多个线程对它进行读操作的时候,读取的都是集合本体,而多个线程对它写操作的时候,它会复制数组到副本,然后对副本加锁进行写操作,操作完成后指向原集合,从而实现了线程安全,它是目前所有线程安全的List中,性能最高的。
-
介绍一下ArrayList的数据结构? ArrayList底层数据结构是动态数组,默认初始化大小是10,每次扩容增加50%,扩容的原理是,创建新数组,将旧数组复制到新数组,将新元素放到新数组中,然后指向原数组变量。
扩展: 常见的构造器: 1.默认构造器,初始化容量是10 2.指定容量
-
谈谈CopyOnWriteArrayList的原理 CopyOnWriteArrayList就是一个线程安全的ArrayList, 读操作的时候,读取的是本身集合, 写操作的时候,会在写操作的方法中会复制一个新的数组,完成写操作后再指向原引用。整个写操作过程是上锁的,其他线程此时不允许写操作,所以实现了线程安全。
扩展 优点:读的效率很高,适合读多写少的并发场景。 缺点: 1.数据不可以实时更新,因为使用的是读写分离的方式,读写操作并不是同步的。而Vector的数据是可以实时更新的,因为读写操作均用Synchronized上锁,可以保证读写操作是同步的。 2.占用内存,数据量大时,每次写操作都复制整个数组,对内存压力比较大,而且还会进行频繁的GC回收。
-
说一说TreeSet和HashSet的区别 1.TreeSet底层是用红黑树实现的,HashSet底层是用hash表实现的 2.TreeSet支持自然排序和定制排序两种排序方式 3.TreeSet的元素不允许为null,HashSet的元素允许为null
-
说一说HashSet的底层结构 HashSet底层结构实际上是HashMap的结构, 需要存储的值实际上是存储在hashMap中的key中的,value值则使用了一个静态的默认值PRESENT,是一个Object对象。 它的默认构造器的初始化容量是16,负载因子是0.75。
扩展: HashSet的构造器: 常见的又: 1.默认构造器 2.指定容量 3.指定容量和负载因子
-
BlockingQueue中有哪些方法,为什么这样设计? 第一组(抛异常组):add(e),remove(),element() 第二组(特定值组):Offer(e),poll(),peek() 第三组(阻塞组):put(e),take() 第四组(超时组):offer(e,time,unit),poll(time,unit) 这样设计的原因是:如果希望增加,删除,检查操作不能立即执行时,可以做出相应的表现,满足不同的业务场景。
扩展: 抛异常:不能立即执行时,会抛出异常。 特定值:不能立即执行时,典型的返回true或者false。 阻塞:不能立即执行时,会一直等待,直到能执行为止。 超时,不能立即执行时,会一直等待,直到超过某个时间,如果不能执行,典型的则返回一个false。
-
BlockingQueue是怎么实现的?
BlockingQueue了解的并不是很多,这里主要简单讲一下,BlockingQueue是一个接口,它的实现类有很多,这里拿ArrayBlockingQueue类讲一下,ArrayBlockingQueue类的构造器初始化了两个成员变量,一个是ReentrantLock和Condition,其中ReentrantLock是AQS的一个子类,Condition是AQS的一个内部类,ReentrantLock提供了一个方法生成Condition,而Condition则可以调用AQS的方法。他们共同保证,在操作不能立即进行时,put和take方法是阻塞的。
异常
-
如何处理异常?
异常通常有两种,一种是编译异常,一种是运行异常。
编译异常,通常在编译前处理,编译异常通常是提示或者警告作用,需要进行显示处理,通常使用throws关键字声明式抛出或者try-catch-finally处理,否则无法通过编译
运行异常,可以使用try-catch-finally,try代码块尝试捕捉throw抛出的异常,并交给catch处理,catch拿到异常对象后,选择相应的异常处理方法进行处理,finally通常用于释放资源,比如线程、网络、IO、数据库连接等,无论是否产生异常,均会执行,如果抛出异常后没有相应的try-catch-finally处理,则会使用throws自动抛出。
-
异常机制?
异常抛出后,会抛出给调用调用者,一层一层往上传递,直到能处理它的地方,如果一直找不到异常处理的方法,就会抛给JVM处理,如何JVM机都无法处理,则会停止程序。
-
异常接口
Throwable是顶级父类,有两个直接子类,Error和Exception
Error是错误,一般是虚拟机出现的错误,如系统崩溃,内存溢出等问题,会导致程序直接终止。
Exception是异常,包括编译异常和运行时异常。
-
在finally中使用return会发生什么?
通常不要在finally中使用return和throw等关键字,因为在try和catch代码块中执行return时,不会立即执行,而会先去寻找有没有finally代码块,如果有就先执行finally中的代码,执行完再返回,但是如果在finally中使用return或者throw,则不会返回try或者catch中执行return了。
其它
-
static和finally的区别
static用于修饰外部类的成员,即静态成员变量,静态成员方法,静态代码块,静态内部类,不能修饰外部类。
静态成员变量:类加载时会存放在方法区,可以通过类名访问。
静态成员方法:可以通过类名访问。
静态代码块:类加载时会执行一次。
静态内部类:可以被继承也可以被实例化。
static有一个重要的原则:静态成员不能访问实例成员,因为很多时候类成员加载了,实例成员还没有被加载,就会出现大量错误。
finally 可以修饰类,变量,方法。
类:表示不可继承。
变量:表示不可修改。
方法:表示不能被重写。
finally修饰的变量,如果是类变量,可以在声明时赋值,静态初始化代码块中赋值;如果是实例变量,可以在声明时赋值,普通初始化代码块中赋值,构造器中赋值;如果是局部变量,可以在声明时赋值,或者后续代码中赋值。
*多线程(晚)
-
创建线程的方式(我可以理解成创建线程执行类的方式,他们称之为线程,我只是为了区分)
有三种,一种是继承Thread类,一种是实现Runnable接口(run方法无返回值),一种是实现Callable接口(call方法有返回值)。
推荐使用Runable接口或者Callable接口创建多线程(多线程一定要理解好,new 多个Thread线程来执行同一个线程执行对象才是多线程),Runable接口和Callable接口创建线程类似,一个有返回值,一个没有放回值,因为这种方式都能够使多个相同线程执行对象线程共享同一份资源,同时也单继承带来的问题。使用Thread类适合创建单线程,比较简单。
-
run方法和start方法的区别
run方法是线程执行体,是该线程执行对象需要完成的任务,如果只是单纯调用run方法,只是简单的方法调用,只有调用start才会启动线程,表示为可运行状态,而何时运行线程还要看JVM的运行时机。
-
线程的生命周期
有六个。
新建状态:new一个线程执行对象后。
可执行状态:调用start方法后。
等待状态:没有具体的等待时间,比如调用本线程的wait()方法(会释放锁),子线程的join()方法。
超时等待状态:有具体的的等待时间,比如调用本线程的wait(time)方法,子线程的join(time)方法,本线程Thread.sheep(time)休眠方法(不会释放锁)。
阻塞状态:兄弟线程持有锁,本线程由于暂时无法持有锁进入阻塞状态,等待兄弟线程锁的释放。
结束状态。
当线程数小于处理器个数时,这些线程是并行执行的,一个处理器只处理一个线程。
当线程数大于处理器的个数,这些线程则是并发执行的,一个处理器使用时间片轮转处理不同的线;也可能是并发并行执行。
等待状态的线程和阻塞状态的线程没有太大的区别,等待状态是通过wait方法让正在运行的线程主动释放锁,需要再通过唤醒重新进入就绪状态去获得锁让cpu执行,而阻塞状态是线程运行前,由于没有获得相应锁,即兄弟线程正在持有锁,本线程就会进入阻塞状态,同理,需要再通过唤醒重新进入就绪状态去获得锁让cpu执行。
-
线程同步的方式
-
同步方法,同步真个方法,性能极低。
-
同步代码块,同步部分代码,性能较高。
-
ReentrantLock类,和syschronized关键字一样,默认都是可重入、互斥、非公平锁,区别在于ReentrantLock类有一个可以设置为公平锁的构造器,但不推荐使用,比较影响性能。
-
Volatile关键字,修饰域变量,告诉虚拟机该域可能会被其它线程修改,所以每次使用会重新计算,而不是使用寄存器中的值,保证了线程之间的可见性和禁止指令重排。
-
原子变量
-
-
线程间的通讯方式(线程安全的,才能相互通讯)。
-
如果是Syschronized实现线程安全的,需要使用到syschronized使用的锁对象的wait方法、notify方法、notifyAll方法。
锁对象有两个队列,一个是阻塞队列,一个是就绪队列,wait方法将当前执行的线程暂停放进阻塞队列,notify方法或者notifyAll方法将在阻塞队列的线程唤醒放到就绪队列去抢占锁让CPU执行,这些方法都在syschronized代码块中被调用。
-
如果是使用ReentrantLock类实现线程安全的,需要使用到condition对象的await方法、signal方法、signalAll方法,实现线程间通信原理与1类似,同时这些方法在lock.lock和lock.unlock之间被调用。用来替代传统使用wait、notify、notifyAll方法实现线程间通讯,这种方法更加高效安全。
-
采用BlockingQueue。BlockingQueue是Queue的子接口,但并不作为容器使用,而是作为线程通讯的工具。
BlockingQueue队列的一个重要特征:当一个线程向该队列放入元素,但是该队列满时,该线程就进入阻塞队列,当一个线程从该线程取出一个元素,但是该线程是空时,该线程也会进入阻塞队列。BlockingQueue就是生产者消费者模型的解决方案。
-
-
线程池的核心参数和作用
主要有6个。
corePoolSize(核心工作线程数):即主要的工作线程,当前的线程数小于corePoolSize时,即使有空闲线程,仍然会新建新的线程执行任务。
maximumPooSize(最大线程数):当前的队列满,线程数小于maximumPooSize时,会创建新的线程执行任务。
keepAliveTime(空余线程存活时间):当前的线程数大于核心线程数,空闲线程空闲时间大于keepAliveTime时,会自动销毁线程,直到线程数小于核心线程数。
workQueue(阻塞队列):即用于保存等待执行任务的队列。
threadFactory(线程工程):即用于创建线程的工厂,统一使用new Thread()的方式创建线程,使用pool-m-thread-n的命名规范,m表示池编号,n表示线程编号。
handler(拒绝策略):当队列满,线程池满,再加入的线程会执行次策略。