时间戳

首页 > 技术文章 > 面试题的一些补充

面试题的一些补充

feng-zhi 2021-06-25 21:35 原文

1. ArrayList和LinkedList的区别

  1. 首先底层数据结构不同,ArrayList底层是基于数组实现的,LinkedList是基于链表实现的

  2. 由于底层结构不同,适应的场景也不同,ArrayList适合随机查询,LinkedList适合添加和删除,删除.添加.查询的时间复杂度不同

  3. 两者都实现了list接口,但是LinkedList额外实现了Deque(双端队列)接口,因此LinkedList可作为队列来使用

ArrayList的复杂度？

如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1)

在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。

总结：

ArrayList 是线性表（数组）
get() 直接读取第几个下标，复杂度 O(1)
add(E) 添加元素，直接在后面添加，复杂度O（1）
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）
remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）

LinkedList的复杂度？

get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n) （这个比较容易想错）
remove（）删除元素，直接指针指向操作，复杂度O(1)

2.说一下Hashmap的Put方法

1.根据key通过哈希算法与与操作运算得到数组下标

2.如果数组下标位置为空,则将key和value封装成Node对象(JDK 1.7是Entry对象;JDK 1.8是Node对象)并放入该位置

3.如果数组下标位置元素不为空,则分情况讨论

a.如果是JDK 1.7,先判断是否需要扩容,如果需要就进行扩容,如果不用扩容就生成Entry对象,并使用**头插法**添加到当前位置的链表中
b.如果是JDK 1.8,则会先判断当前位置的Node类型,看是红黑树Node还是链表Node
  i.如果是红黑树Node,则将key和value封装成红黑树节点并添加到红黑树中去,在这个过程中会判断红黑树是否存在当前key,如果存在则更新value
  ii.如果此位置Node对象是链表节点,则将key和value封装成链表Node并通过**尾插法**插入到链表的最后位置去,因为是尾插法,所以需要遍历整个链表,在遍历链表的过程中会判断是否存在当前key,如果存在则更新value,当遍历完链表后,将新链表Node插入到链表中,插入到链表后,会看到当前链表的节点个数,如果超过了8,则会将链表转化为红黑树
  iii.将key和value封装成Node插入到链表或者红黑树中后,才回去判断是否需要扩容,需要就扩容,不需要就结束Put方法

3.说一下ThreadLocal

1.是Java中所提供的的线程本地存储机制,可以利用该机制将数据缓存在某个线程内部,该线程可以在任意时刻,任意方法中获取缓存的数据
2.ThreadLocal底层是通过ThreadLocalMap来实现的,每个Thread对象(注意:不是ThreadLocal对象)中都存在一个ThreadLocalMap,Map的key为ThreadLocal对象,Map的value为需要缓存的值
3.如果在线程池中使用ThreadLocal会造成内存泄露,因为当ThreadLocal对象使用完之后,应该要把设置的key,value,也就是Entry对象进行回收,但线程池的线程不会回收,而线程对象是通过强引用指向ThreadLocalMap,ThreadLocalMap也是强引用指向Entry对象,线程不被回收,Entry也就不会被回收,从而出现内存泄漏,解决方法是:在使用了ThreadLocal对象之后,手动调用ThreadLocal的remove方法,手动清除Entry对象
4.ThreadLocal经典的应用场景就是连接管理(一个线程持有一个连接,连接对象可以在不同的方法之间进行传递 ,线程之间不共享同一个连接)

4.说一下JVM中,哪些是共享区,哪些可以作为GC ROOT?

1.方法区和堆都是所有线程共享的,虚拟机栈,本地方法栈,程序计数器都是每个线程独有的
2.什么是GC ROOT,jvm在进行垃圾回收时,需要找到"垃圾"对象,也就是没有引用的对象,但是直接找"垃圾"对象是比较耗时的,所以反过来,先找"非垃圾"对象,也就是正常对象 ,那么就需要从某些"根"的引用路径查找到正常对象,而这些"根"有个特征,就是它会引用其他对象,而不会被其他对象引用.
例如:栈中的本地变量,方法区的静态变量,本地方法栈的变量,正在运行的线程等都可以作为GC ROOT

5.如果查看线程死锁?

1.可以通过jstack命令来查看,jstack命令中会显示发生了死锁的线程
2.或者两个线程去操作数据库时,数据库发生了死锁,这时可以查询数据库的死锁情况

6.线程之间如何进行通讯的?

1.线程之间基于共享内存或者基于网络来进行通信
2.如果是共享内存来进行通信 ,则需要考虑并发问题,什么时候阻塞,什么时候唤醒
3.java中wait()是阻塞,notify()是唤醒
4.通过网络就比较简单了,通过网络连接将通信数据发送给对方,当然也要考虑到并发的问题,处理方式就是加锁等方式

7.介绍一下Spring,通过源码介绍下大致流程?

1.Spring是一个快速开发框架,Spring帮助程序员来管理对象
2.Spring的源码实现是非常优秀的,包括并发安全的实现,面向接口的设计,设计模式的应用等
3.在创建Spring容器,也就是启动Spring时:
a.首先会进行扫描,扫描得到所有的BeanDefinition对象并存在一个Map中
b.然后筛选出非懒加载的单例BeanDefinition进行创建Bean,对于多例Bean则不需要在启动的过程中去创建,对于多例 Bean会在每次获取Bean时利用BeanDefinition去创建
c.利用BeanDefinition创建Bean就是Bean的创建生命周期,这期间包括了合并BeanDefinition,推断构造方法,实例化,属性填充,初始化前,初始化,初始化后等步骤,其中AOP就是发生在初始化后这一步骤的
4.单例Bean创建完之后,Spring会发布一个容器启动事件
5.Spring启动结束
6.在源码中会更加复杂,比如源码中提供一些模板方法,让子类来实现,比如BenaFactoryPostProcessor和BeanPostProcessor的注册,Spring的扫描就是通过BenaFactoryPostProcessor来实现的,依赖注入就是通过BeanPostProcessor
7.在Spring启动过程中还会去处理@import注解

8.说一下Spring的事务机制

1.Spring事务底层是基于数据库事务和AOP机制的
2.首先对于使用了@Transactional注解的Bean,Spring会创建一个代理对象作为Bean
3.当调用代理对象的方法时,会判断该方法是否加了Transactional注解
4.如果加了,则会利用事务管理器创建一个数据库连接
5.并且修改数据库连接的autocommit属性会为false,禁止此连接的自动提交,这是实现Spring的事务非常重要的一步
6.然后执行当前方法,方法中会执行sql
7.执行完当前方法后,如果没有出现异常就直接提交事务
8.如果出现了异常,并且这个异常是需要回滚的就会回滚事务,否则仍然提交事务
9.Spring的事务的隔离级别对应的就是数据库的隔离级别
10.Spring事务的传播机制是Spring事务自己实现的,也是Spring事务中最复杂的
11.Spring事务的传播机制是基于数据库连接来做的,一个数据库连接一个事务,如果传播机制配置为需要新开一个事务,那么实际上就是先建立一个数据库连接,在此新数据库连接后在执行sql

9.什么时候@Transactional失效?

1.Spring事务是基于代理来实现的,所以某个加了@Transactional的方法只有是被代理对象调用时,这个注解才会生效;如果不是被代理对象调用这个方法时,那么@Transactional注解是不会生效的
2.同时如果某个方法是private的 ,那么@Transactional也会失效,因为底层cglib是基于父子类来实现的,子类是不能重载父类的private方法的,所以无法很好的利用代理,也会导致@Transactional失效
3.方法抛出的异常并不属于rollbackFor所指定的异常或者子类的异常的话,@Transactional也会失效

10.Dubbo是如何做系统交互的?

1.Dubbo底层是通过RPC来完成服务和服务之间的调用的,Dubbo支持很多协议,比如默认的dubbo协议,比如http协议,比如rest等都是支持的,它们的底层所使用的技术是不太一样的,比如dubbo协议底层使用的是netty,也可以使用mina,http协议底层使用的是tomcat或者jetty.
(RPC, Remote Procedure Call 即远程过程调用。见名知意：从远程主机调用一个过程/函数。
RPC 的目标是：使得本程序调用其它远程主机上的函数，好像调用本程序内的函数一样简单，并且屏蔽编程语言的差异性。
要实现上述目标首先需要设计一种通信协议，这被称为：RPC协议(RPC Protocol)
2.服务消费者在调用某个服务时,会将当前所调用的服务接口信息,当前方法信息 ,执行方法所传入的入参信息等组装成一个Invocation对象,然后不同的协议通过不同的数据组织方式和传输方式将这个对象传送给服务提供者,提供者接收到这个对象后,找到对应的服务实现,利用反射执行相应的方法 ,得到方法结果在通过网络响应给服务消费者
3.当然,Dubbo在这个调用工程中还做很多其他的设计,比如服务容错,负载均衡,Filter机制,动态路由机制等,让Dubbo能处理更多企业中的需求.

11.Dubbo的负载均衡策略

Dubbo目前支持:

1.平衡加权轮询算法
2.加权随机算法
3.一致性哈希算法
4.最小活跃数算法

推荐阅读