[数据结构与算法]滴滴面试题-1

concurrenthashmap的size函数是不是线程安全的？

我们都知道Hash表的结构是数组加链表，有时候我们甚至可以把每个元素称为“桶”。在插入元素的时候，首先通过对传入的键进行hash处理。 hashMap并不是线程安全的，因为扩容容易导致数据丢失。

聊聊HashMap

hashMap是由 数组+链表组成的数据结构，1.8 数组加链表+红黑树，数组的每个地方都存了key-value这样的对象，1.7是hashEntry 在1.8中叫做node。 当链表长度大于8的时候为了提高查询效率会转换成红黑树（链表定位数据的时间复杂度是O(N) 红黑树是O(logN)）。
HashMap的扩容机制，hashMap()的扩容机制。
则容量变为原来的2倍，阈值也变为原来的2倍

聊一聊HashMap的get和Put

put的底层实现原理：

1. 判断当前桶是否为空，空的就需要初始化（resize中会判断是否进行初始化）
2. 根据当前key的hashcode定位到具体的桶中并判断是否为空，为空表明没有Hash冲突就直接在当前位置创建一个新桶即可。
3. 如果当前桶有值（Hash冲突），那么就要比较当前桶中的key、key的hashcode与写入的key是否相等，相等就赋值给e，在第8步的时候统一进行进行赋值返回。
4. 如果当前为红黑树，就按照红黑树的方式写入数据。
5. 如果是个链表，就需要将当前的key、value封装成一个新节点写入到当前桶后面（形成链表）
6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换成红黑树。
7. 如果在遍历过程中找到key相同直接退出遍历。
8. 如果e ！= null就说明存在相同的key，将值覆盖。
9. 判断是否需要扩容
   Get 方法的底层实现原理：

• 首先将key hash之后取得所定位的桶。
• 如果桶为空则直接返回null。
• 否则判断桶的第一个位置（有可能是链表，红黑树）的key是否为查询的key，是就直接返回value。
• 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
• 红黑树就按照树遍历，不然就按照链表的方式匹配返回值。

再转回concurrenthashmap

线程安全的hashmap ： hashtable 和 concurrentHashMap
Hashtable 把所有地方都加了锁 synchronized 就会导致效率非常低
JDK1.8 中 放弃了分段锁，使用CAS 和 Synchronized的方式来保证并发操作的。采用了hashmap一样的结构，直接数组加链表。
当链表长度大于8的时候为了提高查询效率会转换成红黑树（链表定位数据的时间复杂度是O(N) 红黑树是O(logN)）。

代码上也和jdk1.8很像，也是将原来的HashEntry改为Node类，但是还是使用了volatile修饰了当前值和next的值。从而保证了在获取数据的时候高效。
JDK1.8中的concurrentHashMap在执行put方法的时候还是有些复杂的，主要是为了保证线程安全才做了一系列的措施。

1. 第一步通过key进行hash。
2. 第二步判断是否需要初始化数据结构。
3. 第三步根据key定位到当前node，如果当前位置为空，则可以写入数据，利用CAS机制尝试写入数据，如果写入失败，说明存在竞争，将会通过自旋来保证成功。
4. 第四步如果当前的hashcode值等于MOVED则需要进行扩容（扩容的时候也用CAS来保证了线程安全）
5. 第五步如果上面四步都不满足，那么则采用synchronized阻塞锁将数据写入
6. 第六步如果数据量大于TreeIfY_THRESHOLD需要转换成红黑树

JDK1.8的concurrentHashMap的get方法就比较简单了
1. 根据hashcode找到具体的桶上
2. 如果是红黑树则按照红黑树的方式查找数据
3. 如果是链表就按照遍历链表的方式去查找数据

concurrentHashMap的size方法
JDK1.7 中的concurrenthashMap的size方法，计算size的时候会先不加锁的获取一次数据长度，然后再获取一次，比较前后的值，如果相同的话说明不存在竞争的编辑操作，就直接把值返回就可以了。
JDK1.8 中

/**
 * {@inheritDoc}
 */
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

sumCount 中的basecount是private transient volatile long baseCount
首先对baseCount做CAS自增操作
如果并发导致了baseCount的CAS失败了，则使用counterCells进行CAS
如果counterCells进行CAS也失败了，那么则进入FullAddCount()方法, fullAddCount()方法进入死循环，直到成功为止。

总结

无论是JDK1.7 还是JDK1.8 ConcurrentHashMap的size()方法都是线程安全的，都是准确的计算出实际数量，但是这个数据在并发场景下是随时都在变的。

项目里使用了缓存，能说一下

关于redis的应用场景

1. 计数器相关应用场景：，高并发的秒杀活动、分布式序列号生成、限制手机短信发送数量、工单号递增计数场景，可以使用redis的incrby命令实现原子性的递增
2. 限时业务应用场景： 限时的优惠活动信息、手机验证码 redis 可以 使用expire命令设置一个键的生存时间，到时间之后redis会删除它
3. 热点数据缓存应用场景： 缓存热点数据，启用allkeys-Iru淘汰策略 — 系统功能如下： 可以发布文章；可以对文章进行点赞；在首页可以按文章的发布时间或者文章的点赞数进行排序显示；文章信息用hash来存储 文章包括标题、作者、赞数等信息，在Redis中使用HASH来存储每种信息以及对应的值得映射
4. 排行榜相关的问题应用场景： 排行榜方面查询速度普遍在关系型数据库中偏慢，可以借助redis的SortedSet进行热点数据的排序。在活动中，我们需要展示各个部门的点赞排行榜，所以我针对每个部门做了一个SortedSet，然后以用户的openid作为上面的Username以用户的点赞数作为上面的得分，然后针对每一个用户做一个hash，通过zrangebyscore就可以按照点赞数获取排行榜，然后根据username获取用户的hash信息、
5. 分布式锁应用场景： 使用redis的setnx命令进行，如果不存在则成功设置缓存返回1，否则返回0。在定时任务中，给这个lock加一个过期时间，比如说30分钟执行一次定时任务。
6. 分页模糊搜索： redis的set集合中提供了一个zrangebylex， 通过zrangebylex zset - + LIMT 0 10 可以进行分页数据查询，其中-+表示获取全部数据
7. 队列应用场景： redis 有list push 和 list pop

java中常用的数据结构?

MyISAM和InnoDB的区别

1. InnoDB支持事务，MyISAM不支持
2. InnoDB支持外键，MyISAM不支持，带有外键的InnoDB表转MyISAM会失败
3. InnoDB是聚集索引，使用B+Tree作为索引结构，必须要有主键。MyISAM是非聚集索引，使用B+Tree作为主键
4. InnoDB支持行级锁和表级锁，MyISAM只支持表级锁。
5. InnoDB必须要有主键。InnoDB存储的时候索引和文件存在一个文件里，MyISAM是分开的

java锁的使用场景以及原理

java锁
乐观锁悲观锁

synchronized关键字

1.互斥性：确保线程互斥的访问同步代码
2.可见性：保证共享变量的修改能够及时可见
3.有序性：有效解决重新排序问题
用法也有三个
1.修饰实例方法，锁对象
2.修饰静态方法 锁类对象
3.修饰实例方法的代码块 锁实例对象

Lock接口

• lock的存储结构：一个int类型的状态值（用于锁状态的变更），一个双向链表（用于存储等待中的线程）
• lock获取锁的过程：本质上是通过CAS获取状态值修改，如果当场没有获取到，会将该线程放在线程等待链表中
• lock释放锁的过程：修改状态值，调整等待链表
  一般使用ReentrantLock类作为锁，多个线程中必须要使用一个ReentrantLock类作为对象才能保证锁生效。而且在加锁和解锁的地方需要lock（）和unlock（）显示指出。一般会在finally里面写unlock防止死锁。

AQS（AbstractQueuedSynchronizer）

java中的大部分同步类（Lock、Semaphore、ReentrantLock）都是基于AQS实现的。AQS是一种提供了原子式管理同步状态、阻塞和唤醒线程功能以及队列模型的简单框架。
AQS的核心思想：如果被请求的共享资源空闲，那么就将当前请求资源的线程设置为有效工作线程，将共享资源设置为锁定状态；如果共享资源被占用，就需要一定的阻塞等待唤醒机制来保证锁分配。

ReentrantLock

ReentrantLock 实现了Lock接口，是Lock 的实现类。 通过内部抽象类 Sync 实现了公平锁和非公平锁。Sync继承 AbstractQueuedSynchronizer 实现了锁的可重入，并且是独享锁模式。ReentrantLock意思为可重入锁，指的是一个线程能够对一个临界资源重复加锁

ReenTrantLock的实现是一种自旋锁，通过循环调用CAS操作来实现加锁。它的性能比较好也是因为避免了使线程进入内核态的阻塞状态。

锁类型：ReentrantLock可以指定构造函数的boolean类型来创建公平锁和非公平锁（默认）

可重复：每次加锁都是对state加1，可重入则是对state叠加，每次unlock都会对state减1，当减到0时表示线程释放锁。

Synchronized为什么还需要Lock呢？

因为synchronized太严格了，除非代码块异常或者结束，否则不释放锁影响了效率。
一般情况区别不大，但是如果遇到了公平锁，分开处理wait和notify的时候需要用Lock，尽量用Synchronized

New 一个对象的时候会发生什么？

操作符new 在执行的时候会做四件事：

1. 在内存中创建一个新的空对象
2. 让this指向这个对象
3. 执行构造函数里代码，给这个新的对象添加属性和方法
4. 返回这个新对象

JAVA的内存回收算法

判断对象状态

JAVA的垃圾回收是指回收内存中已经“死亡”的对象的内存空间

1.1 引用计数法

引用计数法是一种比较简单直接的算法，即在虚拟机中保存每个对象的被引用次数，例如对象 A 被对象 B 引用，则对象 A 的引用次数加一；当对象 B 释放对对象 A 的引用时，对象 A 的引用次数减一。当某个对象的引用次数为 0 时表示该对象已经死亡，会在下一次垃圾回收时被系统回收。

缺点： 无法解决循环引用的问题，例如对象 A 引用了对象 B，而对象 B 中又引用了对象 A，此时对象 A 和对象 B 之间就形成了循环引用，两者的引用次数一直不为 0，也就一直无法被回收。

1.2 可达性算法

可达性算法又叫根搜索算法，该算法由每一个根节点触发，根据对象之间的引用关系遍历所有与根节点关联的对象节点，在遍历完成后那些没有被遍历到的对象即为死亡的对象，会在下一次垃圾回收时被系统回收。
可达性算法有四种对象可以作为根节点：

• 虚拟机栈（栈帧中的本地变量表）中引用的对象
• 方法区类静态属性引用的对象
• 方法区中常量引用的对象
• 本地栈中JNI引用的对象

垃圾回收算法

上面介绍了如何判断内存中对象状态，接下来介绍虚拟机在垃圾回收时是如何回收这些死亡的对象的。
垃圾回收主要有三种算法：标记-清除算法，标记-复制算法和标记-整理算法。

2.1 标记-清除算法

标记-清除算法即每次垃圾回收时直接从内存空间中回收那些已经死亡的对象，使用此算法进行垃圾回收会在内存中留下一段段不连续的大小不一致的内存空间，当需要创建新对象时，就从这些零碎的内存空间中寻找一片足够大的内存空间用于存放该对象。
缺点：会留下许多零碎的、难以管理的内存空间，造成内存浪费。

2.2 复制算法

复制算法将内存空间一分为二，每次只使用其中的一半内存，在这一半内存满了的时候就将这块内存中存活的对象复制到另一半的内存中，然后释放这一半的内存空间。

缺点：会浪费一半的内存空间。有可能遇到一半内存满了，并且这一半内存中的所有对象都是存活着的情况。

注：由于大部分对象的存活时间很短，因此大部分虚拟机按照 8:1:1 的比例将内存空间划分为 Eden 和两个 Survivor 空间，每次使用Eden和一块Survivor空间，垃圾回收时将存活的对象一次性复制到另一块Survivor空间上。

2.3标记-整理算法

标记-清除算法即在垃圾回收时从内存空间中回收那些已经死亡的对象，然后将剩下的存活的对象整理到一起，留下一片连续的内存空间。即在标记-清除的基础上加上整理的步骤。

缺点：整理阶段，由于移动了可用对象，需要去更新引用。

2.4 分代收集算法

现代虚拟机中一般会对内存区域进行划分：新生代，老年代。然后根据各个年代的特点选择合适的收集算法：对于新生代，每次垃圾回收都会有大量的对象死去，因此可以选用复制算法，只需要付出少量存活对象的复制成本就可以完成垃圾回收；在老年代中，对象的存活率比较高，所以一般使用“标记-清除”算法或者“标记-整理”算法进行回收。

• 大部分情况下，对象会在新生代的Eden区域分配内存
• 大对象（需要大量连续内存空间的java对象）会直接进入老年代
• 新生代中对象每次经历一次GC，年龄就加1，达到一定年龄之后就会移入老年代中，阈值是15岁
• 动态对象年龄判断：当survivor空间中相同年龄的所有对象大小综合超过survivor空间的一半时，Survivor空间中所有年龄大于等于该年龄的对象可以直接进入老年代，不需要等待年龄到达阈值。
• 空间分配担保机制：在分代收集算法中，老年代为新生代起担保作用，新生代内存满了会触发一次GC,在GC期间发现survivor空间不足以存放存活对象，那么这些存活对象会通过担保机制进入老年代

GC和FullGC

GC一般是新生代，FullGC发生在老年代，一般FULLGC伴随一次GC但是不绝对。

线程池的面试题

什么是线程池？线程池的好处？

所谓的线程池，通俗来讲，就是一个管理线程的池子。他可以容纳多个线程，其中的线程可以反复利用，省去了频繁创建线程对象的操作。
好处：

1. 降低了资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗
2. 提高了相应速度，任务可以不需要等到线程创建就能立即执行。
3. 提高了线程的可管理性。线程是稀缺资源，如果无限制的创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配，调优和监控

Integer之间的== 以及如何放到常量池子

Integer常量池大小为-128到127默认，如果是常量池子就==成功，否则就new。如果直接new 127以内的数，也是放到堆里面的。所以Integer = 127 和 new 也是不一样的

Java BIO NIO AIO 三者的区别 （JAVA网络编程的三个模型）

阻塞：进行读写操作时，没有东西可读可写时，程序就进入等待的状态，直到可读或可写为止。（简单的理解就是一根筋，必须要等这件事做完才去做其他的事情，否则一直处于等待的状态。）
非阻塞：进行读写操作时，没有东西可读可写时，Java调用会马上返回 ，程序不会等待。（你先排上号，先去干其他的事情，当叫到你的时候，你再去干这个事情）。
同步：当触发IO操作的时候，java自己处理IO的读写操作。（自己亲自出马去干的一些事情）
异步：Java将IO读写委托给OS处理，需要将数据缓冲区地址和大小传给OS，OS需要支持异步IO操作API 。（指示别人帮自己做一些事情，你可以先干些别的，做完了并通知自己一声）

BIO：同步并阻塞，服务实现模式为一个连接对应一个线程，即客户端发送一个连接，服务端需要有一个线程来处理。如果连接多了，线程数量不够，就只能等待，即会发生阻塞。
NIO：同步非阻塞，服务实现模式是一个线程可以处理多个连接，即客户端发送的连接都会注册到多路复用器上，然后进行轮训连接，有I/O请求处理
AIO：异步非阻塞，引入了异步通道，采用的是Proactor模式，特点是：有效的请求才启动线程，现有操作系统完成在通知服务端。

应用场景

BIO：适用于连接数目比较小且固定的架构，对服务器要求比较高，并发局限在应用中
NIO：适用于连接数目多且连接比较短的架构，如：聊天服务器，弹幕系统等，编程比较复杂
AIO：适用于连接数目多且连接长的架构，如相册服务器

单例模式

单例模式

懒汉式：只有在getInstance的时候发现为null才创建，否则不创建。线程不安全，如果想安全需要加synchronized关键字

饿汉式：在一开始就创建引用，不需要加锁，执行效率比较高

如果涉及到反序列化问题，可以考虑定义成枚举类型。
java 规范字规定，每个枚举类型及其定义的枚举变量在JVM中都是唯一的，因此在枚举类型的序列化和反序列化上，Java做了特殊规定。在序列化的时候java仅仅是将枚举对象的name属性输出到结果中，反序列化的时候则是通过java.lang.Enum的valueO方法来根据名字查找枚举对象。
也就是说，序列化的时候只将DATASOURCE这个名称输出，反序列化的时候再通过这个名称，查找对应的枚举类型，因此反序列化的实例也会和之前序列化的对象实例相同。

前后端如何交互

get post 之类的方法，传输一个json格式的字符串，然后最后给前端返回相应数据return值即可

项目中哪些地方会用到设计模式？

单例模式：数据库连接池。多线程中的线程池。
网站中的访问计数器，一般也是用单例模式实现
享元模式：由于做的是一个外卖的网站，发布一个外卖口味的问题之后，可以对其进行评论和转发。但实际在数据库中存储的该问题只有一个，有点类似于享元模式的思想。

应用：在一个系统中，如果有多个相同的对象，那么只共享一份就ok了。不必每个都去实例化一个对象，可以节省大量的内存空间。

在Java中，String类型的使用了享元模式，String对象是final类型的，对象一旦创建就不可以被改变。在Java中字符串常量都是存在常量池中的，Java会确保一个字符串常量在常量池中只有一个拷贝

transactional注解

增加菜品的时候需要增加口味信息，修改菜品的时候也需要修改口味信息，所以说必须要是事务级别的，否则就会出错。