[关闭]
@w460461339 2020-06-04T09:50:26.000000Z 字数 22200 阅读 1029

面经不会的问题总结


求职面经


1、枚举可以继承抽象类吗?枚举可以实现接口吗?

a)枚举类在编译时期会继承Enum类,形成一个自己的类,因此它是无法实现继承类的,更不用说继承抽象类。并且值得注意的是,枚举类也是无法被其他类继承的,因为枚举类生成的对应类,被final修饰了。

b)接口是可以实现的。

2、volatile。

a) volatile可以说是一种弱同步方式,它能保证变量的修改是可见的,但也仅此而已。

b) 基本的实现原理是,对volatile变量的每次读都会从主内存中读取,每次写都会立即写入主内存。这里还需要牵扯到JVM的内存模型,大概就是分为主内存,和每个线程各自的缓存,每个线程执行的时候,把需要的变量读取到自己的缓存上,通过然后进行修改,执行完毕后,再把缓存上修改过的变量值写会主存上。

c) volatile只能够保证可见性,对于那种计算值依赖变量过去的值的情况,volatile是无法保证线程安全的。

d) 此处还需要提到一个叫做先行发生原则的东西,即如果线程A先对一个volatile变量进行写操作,然后线程B对volatile对象进行读操作,那么线程A之前所有对该变量的的操作,都对线程B可见。(这是volatile体现的,但差不多也是这个意思)

e) 另外,volatile变量的读写指令不能够被优化重排。

3、设计模式。双重检验锁,静态内部类

这里就简单提提两种,单例模式和工厂模式。
a)单例模式,即一个类只有一个实例。可以通过私有化构造方法,先自行创建对象(饿汉),或者等需要时在创建对象(饱汉)。注意,由于构造方法私有化,他们都是不可继承的。

单例模式如何实现线程安全:双重检验锁
双重检验锁模式(double checked locking pattern),是一种使用同步块加锁的方法。程序员称其为双重检查锁,因为会有两次检查 instance == null,一次是在同步块外,一次是在同步块内。为什么在同步块内还要再检验一次?因为可能会有多个线程一起进入同步块外的 if,如果在同步块内不进行二次检验的话就会生成多个实例了。

  1. public static Singleton getSingleton() {
  2. if (instance == null) { //Single Checked
  3. synchronized (Singleton.class) {
  4. if (instance == null) { //Double Checked
  5. instance = new Singleton();
  6. }
  7. }
  8. }
  9. return instance ;
  10. }

这段代码看起来很完美,很可惜,它是有问题。主要在于instance = new Singleton()这句,这并非是一个原子操作,事实上在 JVM 中这句话大概做了下面 3 件事情。

1、给 instance 分配内存
2、调用 Singleton 的构造函数来初始化成员变量
3、将instance对象指向分配的内存空间(执行完这步 instance 就为非 null 了)

但是在 JVM 的即时编译器中存在指令重排序的优化。也就是说上面的第二步和第三步的顺序是不能保证的,最终的执行顺序可能是 1-2-3 也可能是 1-3-2。

如果是后者,则在3执行完毕、2未执行之前,被线程二抢占了,这时 instance 已经是非 null 了(但却没有初始化),所以线程二会直接返回 instance,然后使用,然后顺理成章地报错。

关于为什么会报错:
image_1boikmvi377gf391cojupm1pjn1b.png-58kB

我们只需要将 instance 变量声明成 volatile 就可以了。

  1. public class Singleton {
  2. private volatile static Singleton instance; //声明成 volatile
  3. private Singleton (){}
  4. public static Singleton getSingleton() {
  5. if (instance == null) {
  6. synchronized (Singleton.class) {
  7. if (instance == null) {
  8. instance = new Singleton();
  9. }
  10. }
  11. }
  12. return instance;
  13. }
  14. }

有些人认为使用 volatile的原因是可见性,也就是可以保证线程在本地不会存有 instance 的副本,每次都是去主内存中读取。
但其实是不对的。使用volatile的主要原因是其另一个特性:禁止指令重排序优化。也就是说,在volatile变量的赋值操作后面会有一个内存屏障(生成的汇编代码上),读操作不会被重排序到内存屏障之前。

比如上面的例子,取操作必须在执行完 1-2-3 之后或者 1-3-2 之后,不存在执行到1-3然后取到值的情况。从「先行发生原则」的角度理解的话,就是对于一个volatile变量的写操作都先行发生于后面对这个变量的读操作(这里的“后面”是时间上的先后顺序)。

但是特别注意在 Java 5 以前的版本使用了 volatile 的双检锁还是有问题的。其原因是 Java 5 以前的 JMM (Java 内存模型)是存在缺陷的,即时将变量声明成 volatile 也不能完全避免重排序,主要是 volatile 变量前后的代码仍然存在重排序问题。这个 volatile 屏蔽重排序的问题在 Java 5 中才得以修复,所以在这之后才可以放心使用 volatile。

相信你不会喜欢这种复杂又隐含问题的方式,当然我们有更好的实现线程安全的单例模式的办法。

静态内部类 static nested class
我比较倾向于使用静态内部类的方法,这种方法也是《Effective Java》上所推荐的。

使用这个方法要指导为什么它是懒汉式的,(因为只有当它或者它的子类第一次被调用时,静态内部类的静态对象才会被创建,因此是懒汉式的。)

  1. public class Singleton {
  2. private static class SingletonHolder {
  3. private static final Singleton INSTANCE = new Singleton();
  4. }
  5. private Singleton (){}
  6. public static final Singleton getInstance() {
  7. return SingletonHolder.INSTANCE;
  8. }
  9. }

这种写法仍然使用JVM本身机制保证了线程安全问题;由于 SingletonHolder 是私有的,除了 getInstance() 之外没有办法访问它,因此它是懒汉式的;同时读取实例的时候不会进行同步,没有性能缺陷;也不依赖 JDK 版本。
b)工厂模式,有点类似于依赖注入的味道,目的是将复杂的实例化过程封装起来,使得调用者通过调用工厂类对应的方法就可以获取实例。

3、类的初始化创建顺序

成员变量,静态成员变量等等内类数据的创建顺序。

  1. // 注释表示执行顺序
  2. public class Person{
  3.   public static String name="张三"; //1
  4.   public static int age; //2
  5.   static{
  6. age=20; //2
  7.     System.out.println("初始化age"); //3
  8.   }
  9.   public static String address; //4
  10.   static{
  11.     address="北京市"; //4
  12.     age=34; //5
  13.   }
  14.   public static void main(String[] args) {
  15. System.out.println(name);
  16. System.out.println(age);
  17. System.out.println(address);
  18. }
  19. }
  1. public class Person{
  2.   {
  3.     name="李四"; //1
  4.     age=56; //2
  5.     System.out.println("初始化age"); //3
  6.     address="上海"; //4
  7.   }
  8.   public String name="张三"; //5
  9.   public int age=29; //6
  10.   public String address="北京市"; //7
  11.   public Person(){
  12.     name="赵六"; //8
  13.     age=23; //9
  14.     address="上海市"; // 10
  15.   }
  16. }
  1. public class Animal {
  2. public String name; //1
  3. public int age; //2
  4. public void eat(){
  5. System.out.println("动物可以吃东西");
  6. }
  7. public Animal(){
  8. System.out.println("Animal构造方法执行了"); //3
  9. }
  10. }
  11. public class Dog extends Animal {
  12. private int sex=0 //4
  13. public Dog(){
  14. System.out.println("Dog构造方法执行了"); //5
  15. }
  16. }

4、hashmap源码

a)HashMap的数据结构:底层是数组+单向链表实现的。数组中存储的是链表的头结点,hash值相同的keyvalue对会被放入同一个链表。

b)hashMap默认的初始容量是16,负载因子是0.75,那么当存储数据量超过16*0.75的时候,将会自动调用refresh方法,将数组的大小翻倍。扩容时会重新计算key的hash值,全部重新放置。

c)hashMap中实现key值唯一的方法。不是使用equals一一对比,而是先通过hashcode计算该keyvalue应该被存储到哪个链表上,然后在于该链表上的元素进行equals比对,如果存在相同则覆盖,并返回原值,不然就加在最后。

d)关于null的存储,在hashmap中,如果是null,那么hashcode返回0,不然调用对应的hashcode方法。因此是可以存储null为key的。

5、动态代理

参考:
https://www.jianshu.com/p/6f6bb2f0ece9
https://www.zhihu.com/question/20794107

JDK自带的动态代理是通过反射实现的!

a) 相比于静态代理,动态代理不需要手工编写代理类。静态代理的代理类在编译期就已经产生,而动态代理则是在运行期才得以确定。

b) 就只说说JDK自带的动态代理方式。JDK实现的动态代理的实现是这样的,首先需要实现调用处理器,得到一个处理器类,之后,将委托类的类加载器,委托类对应接口的Class对象以及处理器类一并传入Proxy类的newProxyInstance方法,得到一个代理对象。通过该对象就能够方便的代理委托类的各种方法。

c) 具体实现,Proxy根据传入的委托类和委托类接口的class对象,生成类一个该委托类的实例,该实例就是我们委托类的的代理对象。该对象中的成员方法和委托类对应的接口方法一一对应,并通过反射拿到对应的方法,通过调用处理器类中的invoke方法来完成对方法的调用。

d) 最大的问题就是JDK本身支持的动态代理,只能代理接口。因为在创建代理类时,这些代理类都有一个共同的父类,Proxy,因此只能够通过implements的方法去代理接口。

7、Spring原生注解

IoC用到的:
a)用于类标注的有:@Component,@Controller,@Service,@Repository,@Configuration
b)用于标注字段或者方法的:@Bean,@Autowired(byType),@Qualifier,@Resource(byName),@Value

AOP用到的:
a)用于标注类的:@aspect
b)用于标注pointcut的:@pointcut
c)定义切入点函数:@after,@before。。。

8、ConcurrentHashMap

1、HashTable效率低下原因:所有数据都是用同一把锁
2、锁分段技术,每段数据一把锁。具体是,存在一个以Segment为元素的数组,每个元素都是一把锁。
3、而每个segment都会对应一个HashEntry的数组,而一个HashEntry数组的每个元素就对应一个链表。(其实就相当于每个Seg锁了一个小的HashMap。)

CurrentHashMap

4、基础方法分为这么几种: 
    4.1 段内加锁的:put,putIfAbsent,remove,replace等 
    4.2 不加锁的:get(用了volatile),containsKey等 
    4.3 整个数据结构加锁的:size,containsValue等
5、put方法
    5.0 先加锁
    5.1 定位Segment时需要对key值进行两次Hash。
    5.2 不同于HashMap的先插入,后扩容;而CurrentHashMap先扩容,后插入。因为有可能出现扩容后,没有新元素继续插入的现象,使得本次扩容白费了。而CurrentHashMap的扩容方式则保证扩容是在必须时才扩容。
    5.3 扩容是针对一个Segment所锁定的HashEntry数组,即某个分段上。
    5.4 进入put后,是被分段锁给锁住的。
6、get方法。没有锁机制,只有volatile,直接读取就好。也是通过和put相同的定位手段获取。
7、remove。首先,HashEntry的next字段是final的,即不可改表。而table中存储的链表头的next是可以改变的。(这也是为什么put总是把元素插在表头。)因此,每次删除元素时,会将删除元素之前的元素重新存储一遍。就会有下面情况。3删除后,按照插入1,插入2的顺序重新插入,那么1就会指向4,2指向1,成为新的头结点。

remove

8、size方法。基本原理是这样。每个segment都有一个volatile变量count(统计该hashentry中的元素数目),该变量在每个segment对应的haspMap元素增减时都会有相应的修改。因此最基本的想法是累加这个count就可以了。但是在获得最新count数据的时候,可能该segment又改变了。那么,我们个每个segment在添加一个变量,成为modcount,用于统计segment内变化操作的次数。然后两次累加所有的count值和modcount值,如果前后的modcount值一样,那么表明此时的count就是所有的元素数量,可以用。不然就要重来。重来的次数一般为2次。之后再不行,用加锁的方式来进行统计。

9、需要注意的是,由于modcount不是volatile的,且modcount对象的自增操作先于count的更新操作,需要先在size中读取count,让modecount的最新值刷到主存中,才能够读取到最新的modcount值。(先行发生)

9、MySQL索引

因为提到了红黑树和AVL树,说一下两者的区别。

1、红黑树,有红链接和黑链接一说,而平衡是指该节点左右两子树的最深叶子节点到根节点的黑链接数量差1.
2、AVL树,就是最完美的平衡二叉树。

下面这篇文章对各种树有了很好的介绍:
http://blog.csdn.net/chlele0105/article/details/8473846

两个原则(后面也会提到):

1、局部性原则:这页数据被用到了,相邻的数据也会被用到。
2、预读:通常不止读一页,会把这一页附近的都读入。

对应的两种加快索引的方式:

1、让索引数据尽可能放在一起。(为什么不用红黑树/AVL树)
2、每一页中尽可能的放更多的数据。(为什么不用B-树)

关于索引:

1、有多种形式的索引,比如普通索引,组合索引,主键索引/外键索引等等。
2、索引的目的是为了加速查询。
3、首先理解索引怎么加速查询。数据库的数据是存储在硬盘上,那么存硬盘上读取数据需要IO,而IO是非常非常耗费时间的。如果一一对比的话,时间超多。而索引提供给我们一种方法,使得我们可以通过少量的IO操作就可以读取到想要的存储在硬盘上的数据。
4、B+树和B-树最大的区别:B+树将数据节点放在叶子节点上,而B-树则是在非叶子节点上也会有数据节点。通常而言,一个节点的大小就是磁盘上一页的大小为4k或者8k,那么存储的数据越大,一页所能够存储的数据量越少,会造成树越高,而树的高度直接一项查询的效率。因此相同页容量和相同数据的情况下,B-树通常会高于B+树,使得查询变慢。
5、另外,复合索引中,索引是最左匹配。

关于建立索引的原则:

1、最左匹配,遇到范围查询停止。
2、选择区分度高的字段作为索引,主键字段作为索引区分度为1,太低。
3、注意,索引的列不能参与运算。

MySQL innoDB引擎下索引的构成:

1、B+树,叶节点保存数据完整记录

为什么不用红黑树:

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

局部性原理和磁盘预读:

由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取,而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理:

    当一个数据被用到时,其附近的数据也通常会马上被使用
    程序运行期间所需要的数据通常比较集中

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

10、Cookie和Session

Cookie:

1、服务器和客户端通过在请求头和响应头中添加SetCookies和Cookie字段来进行Cookie信息的交互。
2、Cookie存储在客户端。

Session:

1、每个会话生成一个唯一的sessionID。
2、服务器仅将session发送给客户端。
3、session所包含的信息,如登陆信息等,存储在服务器端,且有过期时间。
4、客户端通过将session-id包含在请求内,发送给服务器,服务器才可以找到对应的session,从而正确的响应session。
5、另外,客户端会保存session-id,这个保存的容器就是cookie。//当然,当cookie被禁止了后,可以使用url重写的方式来搞定。

11、Http长连接和短连接

长短连接定义:

1、Http是应用层协议,它的运输层是通过TCP来实现进程间通信的。
2、而长短连接其实是对于TCP而言的。
3、我们知道,TCP是面向连接的,即在开始传输数据前,需要事先建立连接。
4、而一个网页上有很多数据,比如JS,CSS,图片等。
5、对于HTTP/1.0而言,是采用每个数据使用一个TCP连接,这样导致获得一个完整的网页需要建立很多连接,很浪费资源。每次资源请求都新建一个连接,这是短连接。
6、因此,在HTTP/1.1之后,会维护一个长连接,通过这一个连接,来传输上述的资源。当然,这个链接不是一直都存在,而是会在一定时间后过期。
7、设置连接为长连接,则是通过在HTTP的响应头中,加入Connection:Keep-alive通知的。

什么时候用长/短连接:

1、长连接用于操作频繁,点对点,且连接数不能太多的通讯。比如数据库连接。
2、而普通的web站点,由于访问量大,如果维护较多长连接,会很容易造成资源耗尽,因此使用短连接会更加节约性能,提高并发性。

12、HashMap+IP转域名

HashMap底层:

数组加单链表。初始容量16,阀值0.75,平均查找复杂度o(1+a),a为链表平均长度。数组上限是65535.,IP4的情况下,最多有255*255*255*255=2^32-1.

IP转域名,由于IP是有一定规律的,因此可以考虑用类似于B+树的方式来进行存储查找。

13、线程实现的四种方式:

http://www.cnblogs.com/felixzh/p/6036074.html

线程主要有四种实现方式:

1、继承Thread类,重写run方法。
2、实现Runnable接口,重写run方法。
3、实现Callable接口,用FutureTask重写run方法。
4、利用线程池来执行。

最主要的区别是这样:

1、首先,如果选择继承Thread类,意味着无法继续继承其他类的。而实现接口,则类的继承和接口的实现都不受影响。
2、Callable和Runnable的最大区别是,Callable可以通过和FutureTask一起使用,实现有返回值的线程。
3、Callable要和FutureTask搭配使用,通过FutureTask的get方法来获取返回值。get方法是阻塞执行的,即挂起当前线程,等待刚被我们执行的线程返回一个值,然后在继续执行。

13.1 线程的五种状态

image_1c5uv3f9rolu1260190ndvf13un9.png-126.1kB

13.2 线程阻塞状态详解

14、ArrayList与LinkedList

ArrayList:

1、数组实现的list。
2、支持高效的随机访问,但插入和删除需要移动之后所有的数据。
3、当数组的实际存储量超过一定容量后,需要对数据进行扩容操作。延长为原来的1.5倍

LinkedList:

1、双向链表实现的list,每个元素都有指向前和后的指针。
2、不支持高效的随机存储。
3、插入,删除等操作效率较高。
4、可以模拟栈,队列等数据结构。

Array'List实现LinkedList:

1、新建一个类,类中保存有存储的数据和下一个节点的下标。
2、从0开始,长度不够进行扩充。一个一个往后填充。
3、包括中间添加,修改也是。

15、String,StringBuffer和StringBuilder

String字符串类

StringBuffer:线程安全的字符串类

StringBuilder:线程不安全,相对高效的字符串类。

1、String是不可变对象,每次对String类型的实例修改时,都是产生了一个新的String实例。因此,如果频繁变动内容的字符串用String的话,会产生大量无用对象。
2、StringBuffer则不是,每次都是对同一个对象中的值进行修改,不会创建新的对象。

StringBuffer则是线程安全的StringBuilder。

String不可变性的缘由:

1、String类型最终的存储是通过一个char数组来实现的。
2、而那些返回值为String的方法,是通过该char数组,再新建一个一个String实现的,因此当然每次String都会返回一个新的对象。

StringBuilder为什么不会生成新的对象:

1、StringBuilder虽然内部也是通过char数组来实现对字符串的存储,但每次有修改时,它是通过修改字符串数组来实现的修改,StringBuilder本身不变。

说一说为什么这么设计String:

1、很多时候,不同的String实例表达都是同一个字符串。如果为每个实例都创在一个对应的char数组来存储,那样会很浪费资源。比如一篇文章,有500个‘and’,如果为每个and都创在一个char数组来存储,会很浪费资源。
2、那么,一种称为字符串池的技术出现了,它让and只保留一份,所有需要表示为and的String类型都指向他。
3、那么,为了保证and不会因为一个指向他的实例修改而改变,就需要让String类是不可变的,每次修改都意味着创建一个新的值。
4、因此就有了这样的设计。

16、抽象类和接口

抽象类其实和父类类似,只是:

1、被abstract修饰,不能实例化
2、可以有构造方法, 也可以提供方法的默认实现。
3、是is-a的关系。

接口:

1、like-a的关系

17、MySQL的隔离级别

首先明白三种读数据时会遇到的情况:

1、脏读
简单而言,脏读是指读到了一个还未提交的数据。比如B正在修改数据1,从100修改到1000,但未提交。此时A来读,读取了1000。后来B发现有问题,1000不对,就回滚了,那么A读到的数据就是脏的,即为脏读。

2、不可重复读。
A在执行事务1,先读了数据1,得到1000,此时事务1还没结束;而B又进来,修改了数据1,为2000,并提交了;A在事务1中继续读,会发现数据1变成了2000.即同一个事务中,两次读取相同数据,值不同。

3、幻读。
幻读和不可重复读最大的差别就在于,不可重复读是针对某一个特定数据,而幻读是针对某一个操作。比如统计符合要求的项数。A开启事务1,统计工资高于100的人,为10人;此时B又加了一个工资高于100的人进来;A在事物1中再次读,会发现人变成11了。

那么四种隔离级别也是根据上面三种情况而言的:

1、未提交读:即允许脏读,不可重复读和幻读。没有任何保障措施。
2、提交读:不允许脏读,允许不可重复读和幻读。
3、可重复读:不允许脏读,不可重复读,但允许幻读。
4、可串行化:都不允许。

那么是如何实现:

1、首先,数据库有两种锁,一种是共享锁,一种是排他锁。共享锁可以理解为读锁,允许其他事务继续添加共享锁(但不能是排他锁),一般是在读取的时候用到。排它锁可以认为是写锁,不允许其他的事务添加任何锁。
2、提交读采用的策略是:修改时添加排它锁,并在事务提交后才释放;而读取时添加共享锁,读取完就释放。这样可以保证不会读取到未提交的修改数据,但是不能避免不可重复读问题。因为共享锁不是在事务结束,而是在读结束后就释放,其他事务可以在本地事务读后修改内容。
3、可重复读:针对上面的问题,让共享锁在事物完成后再释放,就不会有不可重复读问题了。但这些锁因为是针对某一条数据的,对新数据的插入没有效用,因此会有幻读问题。
4、可串行化:不允许并发,只能够通过串行执行。

18、MySQL多表查询

分类:

内连接:只返回满足条件的数据。(inner join=join)
外连接:除了返回满足条件的数据外,还返回左(右)表中不满足条件的数据。(left/right join)
笛卡尔积:表a有5项内容,表b有6项内容,则返回30项结果。
全连接:虽然mysql不支持,但是可以通过union+左右连接实现。全连接可以理解为两个集合的并集,注意与笛卡尔积的区别。表a有5项内容,表b有6项内容,其中有2项相同,则最终结果有5+6-2=9项。

条件:

可以用where来操作
但是还是偏向喜欢table1 join table2 on table1.colums1=table2.colums2

19、SpringMVC工作流程和原理

image_1bofd802t1pn89d8ndnm7u1inb9.png-48.1kB

常见的处理器适配器:适配器嘛,让自己写的handler决定需要重写那些方法,不用一次性把结果所有的方法都实现了。

SimpleControllerHandlerAdapter
HttpRequestHandlerAdapter

基本步骤:

1、配置dispatchServlet,来指定要接受的request。
2、根据接收到的request,以及处理器映射器,来找到相应的处理器和方法。
3、处理器根据配置的处理器适配器来实现。
4、处理器调用service等方法,处理完数据后,根据适配器的要求,将数据封装进modelandView中,并根据要求,返回视图。(不同的处理器适配器会要求有不同的view的返回)(以及可以有xml配置开发和注解开发)
5、根据配置的视图解析器解析视图,并将元素进行渲染填充,然后返回给客户端。

20、Spring IOC

目的:

1、解耦,使得各个模块能够更加着重于本身的业务逻辑。
2、IOC让初始化本类所需要的对象从外界传入。而不是自己new。
3、而让这些对象传入,需要大量的new,IOC可以帮助我们new这些对象。
4、另外,IOC可以让类的创建细节被隐藏。不需要关心太多。

控制反转精髓:

1、没有IoC时,对象A如果依赖对象B,那么在A需要对象B时,需要自己手动去创建或者寻找一个对象B。
2、有了IoC,那么就不需要自己手动寻找,IoC会把你所依赖的对象创建好直接给你。

依赖注入是实现控制反转的一种方法(还有一种是依赖查找):

1、依赖注入就是将实例变量传入到一个对象中去。即原本类A需要自己内部通过new的方式初始化对象a,但现在该对象通过构造方法传递进来,不用自己new啦。

21、Spring AOP

面向切面变成
优秀参考:
http://blog.csdn.net/javazejian/article/details/56267036

21、Bitmap排序和布隆过滤器

什么是Bitmap排序:

1、(2,4,1,12,9,7,6)如何对它排序
2、因为最大是12,所以用2个byte,一共16位来表示。
3、第0位表示1,第1位表示2.
4、如果该位下标对应的数存在,那么该位置1

此处输入图片的描述
之后按照位,把这个结果输出一遍就好。

优点:

1、效率高,不允许进行比较和移位
2、占用内存少,比如32个整数,使用bit存储需要4byte,使用int数组需要32*4byte

缺点:

1、无法对重复数据进行排序和查找
2、数据量很小,但范围很大时就有问题= - 

应用场景:

1、对10亿个不重复的整数进行排序。
2、找出10亿个数字中重复的数字。

布隆过滤器

1、比如10亿个电话号码的黑名单过滤(黑名单数量超多)。
2、选择K个hash算法,每个算法会把一个电话好嘛映射到k个不同的值上,这些值的范围在12亿到0之间。
3、将黑名单上的号码映射到byte数组上,对应位置1.
4、如果有一个电话,它经过K个hash算法计算后,其每一位对应都是1,那它就是黑名单一员。
5、会出现误判,这是由于hash碰撞。但概率很小,可以接受,可以使用白名单解决。

22、Java常见锁

此处输入图片的描述
此处输入图片的描述
Java加锁的机制有两种,一种是synchronized修饰符,一种是Lock接口。synchronized提供原生层面的锁(指令码),lock是API层面的锁,但提供更为丰富的锁特性。

什么是CAS:

1、compareAndSwitch
2、“我认为位置 V 应该包含值 A;如果包含该值,则将 B 放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。“
3、CAS即将比较和改变着两步变成了一个原子性的操作。
4、但会有ABA问题,即在比较和改变之间将原值从A改到B,又改到A,这样是无法检测的。

如何用CAS实现自旋锁(乐观锁):

这种模式下,已经没有所谓的锁概念了,每条线程都直接先去执行操作,计算完成后检测是否与其他线程存在共享数据竞争,如果没有则让此操作成功,如果存在共享数据竞争则可能不断地重新执行操作和检测,直到成功为止,可叫CAS自旋。

23、怎么解决多用户并发操作数据库

这个感觉就是几个隔离级别,以及MySQL如何实现的。(共享锁和排它锁。)

24、垃圾回收之CMS

CMS 全称为 Concurrent Mark Sweep。它是现在非常主流的一款老年代的垃圾回收器,因为它能够实现和用户线程并行进行,而不需要像其他的垃圾收集器一样(如 Serial Old,Parallel Old) "stop the world"。

工作步骤:

1、初始标记
2、并发标记
3、重新标记
4、并发清除

其中,初始标记和重新标记都要stop the world的。

初始标记标记一下GC ROOTS对象(这个是有一张表记录的,空间换时间)。

并发标记,和用户线程并发执行,这里标记的是还存活的对象。会有浮动垃圾问题,即标记过的对象用户线程又说不要了。

重新标记,标记那些并发过程中新生成的对象。

并发清除。标记清楚算法,会有空间碎片。

25、Java内存泄漏

什么是Java下的内存泄漏:

指不再会被使用的对象的内存不能够被回收,就是内存泄漏。

内存泄露:指程序中动态分配内存给一些临时对象,但是对象不会被GC所回收,它始终占用内存。即 被分配的对象可达但已无用

发生情况:

1、长生命周期的对象持有短生命周期对象的引用
    这是内存泄露最常见的场景,也是代码设计中经常出现的问题。
    例如:在全局静态map中缓存局部变量,且没有清空操作,随着时间的推移,这个map会越来越大,造成内存泄露。

2、修改hashset中对象的参数值,且参数是计算哈希值的字段
    当一个对象被存储进HashSet集合中以后,就不能修改这个对象中的那些 参与计算哈希值的字段,否则对象修改后的哈希值与最初存储进HashSet集合中时的哈希值就不同了,在这种情况下,即使在contains方法使用该对象的当前引用作为参数去HashSet集合中检索对象,也将返回找不到对象的结果,这也会导致无法从HashSet集合中删除当前对象,造成内存泄露。

3、机器的连接数和关闭时间设置
    长时间开启非常耗费资源的连接,也会造成内存泄露。

解决办法:

1、尽早释放无用对象的引用
2、使用字符串处理,避免使用String,应大量使用StringBuffer
3、尽量少用静态变量,因为静态变量存放在永久代(方法区),永久代基本不参与垃圾回收
4、避免在循环中创建对象

26、不同集合类的使用场景

HashMap什么时候用:

1、现在想来,hashmap特点是:
    1.1 线程不安全
    1.2 数组+单链表,无序
2、那么,hashmap在对线程安全没有要求,且对存储数据顺序没有要求的情况下可以使用。
3、一个例子:
    3.1 处理request时,一般每个request用一个线程处理
    3.2 每个request中都包含有一个些数据
    3.3 这些数据在处理时即可使用hashmap来进行存储。因为这些数据仅在这个线程又请求的需求。(猜测Tomcat里面也这样用的!)
    3.4 ThreadLocal里面有用到!

ConcurrentHashMap什么时候用:

1、CurrentHashMap:
    1.1 线程安全
    1.2 相比于HashTable,大量数据的存储和读取效率要高。
    1.3 创建Segment锁数组需要空间。
2、那么,CurrentHashMap在有大量数据需要存储,且对并发性要求较高,并且内存空间较为宽裕的情况下可以使用。

27、队列

java中具有Queue功能的类主要有如下几个:

1、AbstractQueue,LinkedList,PriorityQueue和Arraydeque
2、ArrayBlockingQueue,LinkedBlockingQueue,PriorityBlockingQueue,DelayQueue。
3、ConcurrentLinkedQueue
27.1 简单队列

首先说说ArrayDeque

1、数组实现的队列,基本实现是维护两个index,一个指向头元素head,一个指向尾元素的下一位,tail。
2、不仅提供往队尾插入的方法,也提供往对头插入的方法。
3、不仅提供移除对头的方法,也提供移除队尾的方法。
4、用循环数组实现,因此需要考虑两个指针旨在头尾时的越界问题。
5、当tail与head重合时,说明没有空间了,此时需要扩容。
6、复制时,先复制head右边,在复制head左边。
7、用它来模拟栈的话,用addlast来加入,用removelast来取出即可。

此处输入图片的描述

优先队列PriorityQueue:

1、二叉堆实现,即一个完全二叉树,树的每个节点的值,都小于它子节点的值。
2、remove实现,每次这个二叉堆堆顶元素都是最小的,当要把这个元素取出时,具直接拿走吧,然后把最后一个元素交换到这个空出来的位置。之后在进行下沉操作,就可以得到新的最小值。
3、add实现,每次在堆尾进行数据插入,然后进行上浮操作。
4、比较是通过compareTo实现的,因此不允许null。
5、由于是二叉堆,简单的实现可以通过数组完成。
6、线程不安全。
27.2 阻塞队列

10、 生产者消费者模型和阻塞队列

    10.1 一个线程生产数据,一个线程消费数据。
    10.2 两者的速度不一样;生产过快,导致数据最终放不下;消费过快,导致可能拿到null。
    10.3 阻塞队列可以解决这个问题。
    10.4 阻塞队列存放生产者生产的数据,如果队列满了,生产者再进行put操作时,会触发生产者所在线程的挂起操作;如果队列空了,消费者进行get操作时,会触发消费者所在线程的挂起操作。

可以看到,在队列操作(添加/获取)当前不可用时,BlockingQueue 的方法有四种处理方式:

抛出异常 
    对应的是 add(), remove(), element()
返回某个值(null 或者 false) 
    offer(), poll(), peek()
阻塞当前线程,直到操作可以进行 
    put(), take()
阻塞一段时间,超时后退出 
    offer(), poll()

ArrayBlockingQueue:

1、基于数组实现的队列,且数组长度不可变。

2、有一个可重入锁对象lock,通过它获取两个condition对象,noEmpty和noFull。

3、当进行put操作时,如果数组满了,那么noFull就调用await,使得当前线程挂起;当进行take操作时,如果数组为空,那么就用noEmpty的wati,挂起当前线程;

4、当put操作结束,调用noEmpty的signal方法,通知所用因为noEmpty挂起的线程;当take操作结束,调用noFull的signal方法,通知所有因为noFull挂起的线程。

5、这里用可重入锁是为了实现公平锁。当然,默认是不开启公平锁的。

6、另外,arrayblockingarray是基于环形数组的实现。

7、由于take和put操作用的是同一个lock对象,因此put和take操作是不可以并发进行的,这一点会影响效率。

LinkedBlockingQueue:

1、链表实现队列。

2、对于写入和取出两个操作,分别用了两个锁(都是可重入锁)。takelock和用它获得的notempty;putlock和用它获得的notfull

3、这样操作可以让put和take并发执行。

4、计数器使用AtomicInteger来保证对该对象操作的原子性。

LinkedBlockingQueue和ArrayBlockingQueue的区别:

1、ArrayBlockingQueue大小固定;LinkedBlockingQueue大小可变。
2、ArrayBlockingQueue所需内存一开始就分配好,LinkedBlockQueue所需内存动态变化。
3、ArrayBlockingQueue出队和入队采用同一个锁;LinkedBlockingQueue采用两个锁,吞吐更加高效。
4、JDK的线程池采用LinkedBlockingQueue,就是因为它的长度可以动态增加,不会出现队列满而造成的异常。

28、线程池

这里简单说一下线程池具体是怎么用的。

1、设置核心线程数量。
2、设置最大线程数量。
3、设置队列容量。
4、当一个新的任务进来了:
    4.1 运行的线程数是否大于核心线程数:
        4.1.1 不大于,创建一个新线程,并运行任务。
    4.2 大于,那么任务队列是否满了。
        4.2.1 队列没满,加入任务加入队列;
    4.3 队列满了,那么运行线程数是否大于最大线程数
        4.3.1 不大于,那么开启一个新线程执行任务
        4.3.2 大于,那么执行饱和策略。

使用的时候,线程池不是返回一个线程对象给你用,而是把要做的任务传进去,让他帮你执行。
image_1c5v3a1tc1lhl1bro1dnbkdd1nom16.png-109.4kB

线程池的任务队列最好用LinkedBlockingQueue来实现,以免出现Exception

29、创建线程和开启线程

我们设目前正在执行的线程是A,希望再开启线程B,C,D.

1、在A中通过new Thread的方式,创建三个线程对象。此时这三个线程对象的内存是分配在堆中,其引用是存放在A线程对应的栈中。
2、当着三个线程一一启动后,每个线程都会有一个栈。每个线程中所需要的对象都会统一在堆中分配,其引用存放在各自线程对应的栈中。
3、因此,如果疯狂的新建线程而不启动的话,发生的肯定是堆内存溢出;如果每个线程中的存活对象数目很多,那么启动很多线程,会导致堆溢出;如果线程中对应的对象不多,且都很小,那么疯狂的启动线程会导致用于栈的内存溢出。

30、ThreadLocal

1、每个Thread对象都维护有一个ThreadLocalMap类型的map对象,用来存储本thread所需要存储的threadlocal数据。
2、而每个Thread下的ThreadLocalMap又会维护该thread所需要的所有threadlocal数据。
3、简单来来说,比如有三个线程A,B,C,他们都需要有三种类型的ThreadLocal变量String,Integer和Boolean,分别存储(a,1,true),(b,2,false),(c,3,true)。那么,每个线程,A,B,C,内部会有一个ThreadLocalMap的map对象,来保存不同threadlocal对象和对应的数据。

image_1bp3tj6pjjl97me19h8nd818ijg.png-28.3kB

上面那张图可以看得比较清楚整个存储过程,那么,当我想要获取thread2存储在ThreadLocal< Integer >张的内容时,可以这么做:

1、选择tl2,调用get方法。
2、如果此时是thread2正在执行,那么获得图中第二个map。
3、将tl2的this作为key传入,获得数据2.

当然,还有一种实现,就是不是为每个thraed建一个map,而是为每种存储类型建一个map,并将thread作为key值。这样就和网上这个例子类似了。
http://blog.csdn.net/cselmu9/article/details/9128397

下面展示的是一个实际的例子,即利用threadlocal存储数据库连接变量。从而避免因为synchronized造成的阻塞。
http://blog.csdn.net/shmilychan/article/details/69193624

Synchronized比较:

1、算是以空间换时间。
2、但不适合类似于累加那样的最终结果依赖其他线程的共享变量。

31、不同数据类型存储的大小

数据类型 byte short char int long float double boolean
所需字节数 1 2 2 4 8 4 8 1

这里说一下Unicode编码,它是将所有的字符转成一个对应的数字。

对于UTF-8而言,对0-127号的字符采用1个字节来保存,以上的采用2个字节来保存。因此最多存储范围0-65535。

而UTF-16,则是用2个字节保存所有内容。

而对于Java而言,其内部是普遍采用UTF-16的编码方式来进行存储的,即,一定是两个字节一个字符,因此char是2个字节保存。(称为内码)

而String.getBytes则是将字符串转换为系统默认的编码方式,或者自己制定的方式,一般我们采用utf-8,且转换的是0~127号的字符,因此采用1个字节保存。
参考:

https://www.zhihu.com/question/27562173
https://www.zhihu.com/question/22881537

32、字符流,字节流,缓冲字符/节流,

此处输入图片的描述
上图是字节流的一些实现类,但大多都离不开将一个对象/数组转化成字节/字节数组的形式进行存储。
而这样的存储方式有几点问题:

1、阻塞式读取,读取到指定的字节长度或者-1才停下来。
2、不支持缓存,是通过循环调用read方式来实现读取。

这里说一下BufferedInputStream是如何提高读取速度的问题:

1、一般的InputStream是通过循环调用一个本地方法read来逐个字节读取文件的。
2、而BufferedInputStream,是每次读取8192个字节的数据。
3、那么,对于个32000字节的文件,一般的InputStream需要调用32000次本地方,即经过32000次磁盘IO才能读取到完整的数据;而BufferedInputStream则只需要4次磁盘IO,就可以读取完整个数据。

33、创建一个HashMap时的内存分配

首先,HASHMAP的底层是数组+单链表的形式实现,并且还是用了泛型的。

而泛型在java里面其实是会擦出的,而链表的话,在运行时动态分配。= -

所以,其实是这样,在分配空间时,所用用到泛型的变量,其类型都转为object了,

int KeyHash
Object next
Object key
Object value

因此其所需要的堆空间也就可以确定了。(起码我是这么认为的)。

另外要说一点,虽然会有泛型擦出,但是编译器仍然会帮我们进行泛型检查= -

34、判断链表是否有环

大概就是让两个指针,一个指向表头slow,一个指向表格下一个fast。slow每次走一格,fast每次走两格。如果fast某一时刻等于null,说明没有环;如果fast某一时刻等于slow,说明有环。

  1. listnode_ptr fast=head->next;
  2. listnode_ptr slow=head;
  3. while(fast)
  4. {
  5. if(fast==slow)
  6. {
  7. printf("环!\n");
  8. return 0;
  9. }
  10. else
  11. {
  12. fast=fast->next;
  13. if(!fast)
  14. {
  15. printf("无环!\n");
  16. return 0;
  17. }
  18. else
  19. {
  20. fast=fast->next;
  21. slow=slow->next;
  22. }
  23. }
  24. }
  25. printf("无环!\n");
  26. return 0;

35、银行家算法

银行家算法是针对死锁这一个问题提出的:

1、对某一时刻,有k个线程在请求资源。
2、CPU遍历这些线程,查看哪些线程请求的资源可以被CPU目前空闲的资源加上之前执行线程将释放的资源满足。如果可以,那么就选择它作为下一个被执行的线程。
3、以此类推,形成一个线程的执行队列,是为银行家算法。

最主要的问题就是:

1、额外维护安全队列,有花销。
2、执行过程中,需要事先确定哪些线程要被执行,不能临时加入。

36、TCP三次握手/四次分手

三次握手:

1、客户端发送报文,请求建立连接。
2、服务器接受报文,分配连接资源,返回确认信息。
3、客户端接收到确认信息,分配客户端连接资源,并返回确认信息。

四次挥手:

1、以客户端发起的请求结束为例子。
2、客户端发送信息,告诉服务器端,说我要关闭链接了。
3、服务器端收到信息,并返回ack。
4、然而服务器端还有一部分内容没有发完,客户端在收到ack后进入wait阶段。
5、服务器端发完数据后,发送fin给给客户端,
6、客户端收到后,返回ack给服务器,并等待一段时间,接受一些重传数据。

为什么握手三次挥手却四次:

1、握手时,客户端发送SYN给服务器后,服务器回复了两条信息,一个是SYN,表示我也准备好链接,一个是ACK,表示你的信息我收到。
2、因此客户端在收到服务器响应后,只需要将自己的ACK返回,表示自己也做好准备,就可以开始传递了。

3、而断开时,客户端发送fin给服务器,服务器只是说好的,我知道了。并返回ack。
4、等服务器处理完后,它另外通知客户端,说我要关了,此时客户端告诉服务器,说好的,我也知道了。
5、因此一共四次。

37、生产者消费者模式

这其中最重要的就是阻塞队列,java提供的阻塞队列有array的,linkedlist的等等。一般使用LinkedBlockQueue

一个实际的例子:

1、微信朋友圈。
2、最新的内容不会实时的显示,需要手动刷新才会。
3、刷新这个过程相当于消费者,而朋友圈的朋友写内容,是生产者。

还有一个类似的,就是公平模式下的线程池实现。

38、常见算法的时间复杂度

此处输入图片的描述
http://www.cnblogs.com/nannanITeye/archive/2013/04/11/3013737.html
冒泡排序:

1、将大的元素往后面调整
  1. int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
  2. int temp=0;
  3. for(int i=0;i<a.length-1;i++){
  4. for(int j=0;j<a.length-1-i;j++){
  5. if(a[j]>a[j+1]){
  6. temp=a[j];
  7. a[j]=a[j+1];
  8. a[j+1]=temp;
  9. }
  10. }
  11. }

选择排序:

选择后面最小的,放在第n个位置上。
  1. public void selectSort(int[] a){
  2. for(int i=0;i<a.length;i++){
  3. int small=a[i];
  4. int index=i;
  5. for(int j=i;j<a.length;j++){
  6. if(a[j]<small){
  7. small=a[j];
  8. index=j;
  9. }
  10. }
  11. int temp=a[i];
  12. a[i]=small;
  13. a[j]=temp;
  14. }
  15. }

插入排序:

将未排序元素插入到已排好的部分中。
  1. public void insertSort(int[] a){
  2. for(int i=1;i<a.length;i++){
  3. for(int j=i;j>=0;j--){
  4. if(a[j]<a[j-1]){
  5. int temp=a[j-1];
  6. a[j-1]=a[j];
  7. a[j]=temp;
  8. }
  9. }
  10. }
  11. }

快速排序:

对每个元素a,令该元素的坐标都小于它,右边都大于它。先排序后递归。
  1. Collections.sort(List);

归并排序

目标是将两个有序的数组进行排序,先递归后排序。
。。。。。

39、栈元素倒序

思想:把栈的逆序分为两步,第一步,将最上面的数出栈保存,然后将下面的栈逆序(这里用到递归);第二步,将原先最上面的数插到最底层(我用一个函数实现)。

  1. class ReverseStack {
  2. public:
  3.      vector<int> reverseStackRecursively(vector<int> stack, int top) {
  4.         if(top==1)//只有一个数的时候直接返回
  5.             return stack;
  6.         int temp;
  7.         temp=stack.back();
  8.         stack.pop_back();//最上面的数出栈
  9.         stack=reverseStackRecursively(stack,top-1);//递归调用
  10.         stack=insertToBottom(stack,temp);  //用一个函数实现将一个数插入到最底层
  11.         return stack;
  12.     }
  13.     vector<int> insertToBottom(vector<int> stack,int num)//将一个数插入到栈的最底层的函数
  14.     {
  15.         if(stack.size()==0)//栈空
  16.          {
  17.             stack.push_back(num);
  18.             return stack;
  19.         }
  20.         int top=stack.back();
  21.         stack.pop_back();//将最上面的数出栈保存
  22.         stack=insertToBottom(stack,num);//把数插入到最底层
  23.         stack.push_back(top);//再把原先的最上面的数入栈
  24. return stack;
  25.         
  26.     }
  27. };

40、放硬币问题

两人轮流往一个圆形桌面上放同样大小的硬币,每次一枚,但不允许任何两枚硬币有重叠部分,规定谁放下最后一枚,并使对方没有再放的位置,就算是获胜.假如两人都是内行,试问是先放者胜,还是后放者胜?

先放的自然是先手了,在桌子正中间放一枚;而后无论对手怎么放,自己都在刚放硬币的中心对称处放.由于对称的唯一性,只要有新放的硬币,必然在其旋转对称的地方可以找到放的空位.

41、MySQL常用引擎对比

首先说说Innodb吧

1、支持事务,支持XA(分布式事务中用到的接口规范),保存点(savepoint)
2、Innodb能保证事务安全,提供事务崩溃以及回滚处理。
3、Innodb提供行级别的锁。
4、读取表的行数时,是一行行数过去。

MyISAM:

1、不支持事务
2、读取的效率高
3、读取行数的时候不用遍历。

参考:
https://my.oschina.net/junn/blog/183341
http://blog.csdn.net/xifeijian/article/details/20316775

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注