中望软件java后端一面面试回顾

自己整理下，也帮助下别人给个参考。

算法与数据结构：

1、了解快排吗，说一下快排的原理，快排最差的时间复杂度是多少？有稳定nlogn的算法吗

每次找的pivot将数组分成两部分，其中有一部分是空，这样递归树就变成了一棵倾斜的树。树的深度为n-1,这样时间复杂度就变成了O(N^2).
一般当数据有序或者局部有序的时候会出现这种坏的情况，比如数组正序或者逆序，（数字完全相同的时候也是有序的特殊情况）。归并排序。

2、讲一下堆排序的原理。

堆的初始化，时间复杂度为O(n)。在堆排序中一次进行堆的初始化操作，其时间复杂度为O(n)，n-1次进行堆的调整，每次调整的时间复杂度为O(logn)，所以，堆排序的时间复杂度为O(nlogn)。

因为堆的每次插入、删除元素均需要重新调整堆，所以插入语删除元素的时间复杂度为O(logn).

3、讲一下hashmap，为什么是哈希值对数组大小减一进行相&而不是取余，计算机是怎么实现取余的，

计算机中直接求余效率不如位移运算，HashMap对取模做了优化。源码中做了优化: hash&(length-1)，hash%length == hash&(length-1)的前提是length是2的n次方，所以容量为2的n次方就是为了取模速度；取余是通过电路进行二进制除法来实现的，

计算机网络：

4、交换机和路由器在网络中哪个位置

最初的的交换机是工作在OSI／RM开放体系结构的数据链路层，也就是第二层，而路由器一开始就设计工作在OSI模型的网络层。由于交换机工作在OSI的第二层（数据链路层），所以它的工作原理比较简单，而路由器工作在OSI的第三层（网络层），可以得到更多的协议信息，路由器可以做出更加智能的转发决策。

5、路由器的作用，网关，网关的作用

网关是设备与路由器之间的桥梁，正确的网关配置才能保证用户可以正常上网。网关（gateway）能在不同协议间移动数据，而路由器（router）是在不同网络间移动数据，相当于传统所说的IP网关（IP gateway）。路由有IP地址，分内外网，也就是LAN和WAN口，四个LAN口一个IP，一个WAN口一个IP，如果你的路由支持vlan且能设置vlan IP的话，那就有更多的IP了。网桥在数据链路层上实现局域网互连;

6、tcp和udp的区别，tcp保证可靠性的核心。

重传机制。

mysql：

7、索引的数据结构，什么情况下会索引时效。

对于多列索引，需要使用第一个索引才会命中索引，还有其他不走索引的方式。

操作系统

8、逻辑地址和物理地址的区别。怎么实现一一对应。

物理地址就是唯一的，按照物理硬件定义的地址，逻辑地址就是人为规定的，方便通讯的而定义的地址。如果启用了分页机制，那么线性地址会使用页目录和页表中的项变换成物理地址。如果没有启用分页机制，那么线性地址就直接成为物理地址了。

Spring

9、 spring的A op是怎么实现的。

现在我们就以代理模式为基础先实现我们自己的AOP框架，再来研究Spring的AOP的实现原理。先以静态代理实现，静态代理关键是在代理对象和目标对象实现共同的接口，并且代理对象持有目标对象的引用。

aop可以发现通过动态代理和发射技术，基本实现了AOP的功能，实现InvocationHandler接口，通过反射建立要代理的对象。