38.美团二面(补充一面)

8种数据类型
int long short byte char float boolea double

Integer缓存数据的范围
-128~127

数据的隔离级别都有哪些 举一些例子
读已提交
事务A 50 未提交之前被事务B读取 读到了50 之后事务A提交的时候数据变成100 然后事务B再次读取 此时读到了100 就是说事务B读的时候 事务A已经进行了提交
读未提交
事务A 50 修改成100 但是此时还没有提交修改 此时事务如果发生回滚 事务B看到了事务B成了100 但是事务A此时已经回滚成了50
可重复读
对一个记录多次读取的结果都是相同的 对于一个数A读取的话 一直都是A
串行化
在并发的情况下 和串行化时的读取是一样的
4.事务的四大特性
原子性
事务是一个整体 是不能分开的 要么同时成功 要么同时失败
一致性
在系统的角度看 就是说事务发生前与发生后 事务保持一致
隔离性
事务之间的操作是分离的 不可见的 就是我给你转账之后 你才能得知
持久性
事务可以持久化到数据库中

内存溢出与内存泄露
内存泄露就是申请一块内存之后 无法释放掉这块内存空间 丢失了这段内存的引用
内存泄露就是 内存不够用了 申请的时候抛出了outofmemory

JVM分哪几块
堆 栈 方法区 本地方法栈 程序计数器
堆中存放着对象 堆和方法区一样是线程共享的区域
方法区中存放着程序运行的时候的各种信息 比如说类的常量 静态变量 编译后的数据等等
栈中存放着基本数据类型 以及对象的引用 局部变量表 操作数栈 方法出口等信息
程序计数器选取下一条需要执行的字节码的指令 每个线程都有自己独立的程序计数器 是线程私有的
本地方法栈 本地方法栈执行的是native方法服务 栈为java方法服务

wait和sleep的区别
sleep是thread类的静态方法,是线程用来控制自身流程的,线程会暂停执行一段时间,而把执行的机会让给其他的线程,等到计时的时间到了线程会自动苏醒
wait是object类的方法,用于线程之间的通信,这个方法会是当前拥有该对象锁的进程等待,
直到其他的线程调用object类的方法notify,或者notifyall方法才能醒来.
sleep不涉及线程之间的通信,因此调用sleep方法并不会释放掉锁,但是调用wait方法的时候,线程会释放掉它所占用的锁,从而使线程所在的对象中的气压的synchronized数据可以被其他线程使用.
wait必须放在同步方法,或者同步语句块中,sleep可以放在任意地方.
sleep必须捕获异常,wait不需要.
sleep不会释放锁标志,容易产生死锁的发生.

讲一讲hashmap
存储的时候hashmap允许空的键值存在,但是只能有一个key为null,hashtable不允许空的键值存在.
HashMap扩容时总是2的幂次方大小
当定义初始容量的时候,构造函数并不是将定义的数值叫做HashMap容量大小,而是将该数值当做参数调用方法tableSizeFor,然后将返回值作为初始容量大小
该方法会返回一个大于等于当前参数2的倍数 因此HashMap的table数组的容量大小总是2的倍数

hashMap使用的是懒加载,构造完hashmap对象,只要不进行put方法插入元素之前,hashmap并不会去初始化或者扩容table.

当数组长度为2的n次幂的时候,不同的key算得的index相同的几率较小,那么数组在数组上分布的就比较均匀,也就是说碰撞的几率比较小

(n-1)&hash n永远是2的次幂 通过二进制表示 永远都是尾端以连续的1的形式表示 (n-1)与hash做与运算 会保留hash中后x位的1 &比取模运算快 能保证索引值肯定在容量之中

底层使用的是数组和链表的实现,存取使用的是put以及get,长度增加到大概容量的0.75的时候,为了效率就要进行扩容,临界点就是table数组的长度*加载因子,扩容比较耗时,重新计算在数组中的位置并复制元素到新的区域,所以在能遇见大小的场合尽量初始化的时候就指定合适的长度.

put
在put的时候 插入第一个元素的时候 需要初始化数组的大小
key为null 将entry放在table[0]中
求key的hash值,找到对应的数组下标 遍历一下对应下标处的链表 看是否有重复的key已经存在 如果有 直接覆盖 使用put方法返回旧值
如果不存在重复的key 将此entry添加到链表中

get
根据key计算hash值 找到相应的数组下标 hash&(length-1)
遍历该数组位置的链表 直到找到==或equals的key

hashtable是线程安全的,hashmap线程不安全的,性能上hashmap可能要好于hashtable
hashmap存在fail-fast机制,并发访问的时候可能会导致失败,hashtable线程安全不存在此机制
java8中对其做出了一些修改,最大的不同就是利用了红黑树,所以其由数组,链表,红黑树组成.
java7中通过hash值定位数组的具体的下标,但是之后需要顺着链表一个个比较下去才能找到需要的,时间复杂度为链表的长度为O(n) 为了降低这部分的开销在java8中 当链表中的元素超过8个 会将链表转换成红黑树 降低查找的时间复杂度为logN

Object有哪些方法?
clone getClass toString finalize equals hashCode wait notify notifyAll

计算机网络有哪七层 TCP UDP HTTP在哪几层
物理层 数据链路层 网络层 传输层 会话层 表示层 应用层
TCP UDP在传输层
HTTP在应用层

ArrayList与LinkedList的区别
ArrayList是实现了动态数组的数据结构 LinkedList是基于链表的数据结构
ArraiList因为是直接依靠数组指针作为索引所以查找非常快,但是在插入和删除的时候,必须要移动整个数组的数据,所以数组查找快,删除以及查找比较慢.
LinkedList是基于链表的数据结构,查找的时候从第一个数字往后查找,增加删除的时候,只需要移动前一个元素的指针以及插入节点的指针即可,所以链表查找慢,但是增加和删除很快.

介绍下ConCurrenthashMap
支持并发操作 它由一个个段组成 就是分段锁
ConcurrentHashMap就是一个segment数组,segment通过集成ReetrantLock来进行加锁.每次加锁的操作锁住的是一个segment,这样只要保证每个segment是线程安全的,就保证全局安全
concurrenthashmap有16个segment,所以默认理论情况下,最大支持16个线程并发写.
初始容量,指的是整个ConcurrentHashMap的初始容量,实际操作的时候平均分给每个Segment
segment数组不能扩容,负载因子是segment内部使用
Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容

put
根据hash值很快就能找到相应的segment,之后就是segment内部的put操作了
往segment中写入之前 需要获取该segment的独占锁 再利用hash值 求出放置的数组的下标
node为null 则初始化设置为链表 不为null将其直接设置为表头

如果超过了该segment的阈值 segment需要扩容

手写单例模式
public class SingletonDemo{
private volatile static SingletonDemo instance;
private SingletonDemo(){
system.out.println("Singleton has loaded");
}
public static SingletonDemo getInstance(){
if(instance==null){
sychronized(SingletonDemo.class){
if(instance==null){
instance = new SingletonDemo();
}
}
}
return instance;
}
}
双重锁模式
1.线程A访问getInstance方法,单例没有实例化,所以进入了锁定块
2.线程b访问getInstance方法,因为单例还没有实例化,所以访问下面的代码块,而代码块已经被线程A锁定
3.线程A此时进入下一个判断,因为单例还没有进行实例化, 进入代码块实例化,成功实例化后返回实例,退出代码块,解除锁定.
4.线程B进入代码块,锁定线程,进入判断,因为已经实例化,退出代码块,解除锁定.
5.线程A实例化对象返回,线程B返回线程A创建的实例,实现单例模式

package pandy.test;

public class SingletonDemo {
private volatile static SingletonDemo instance;
private SingletonDemo() {
System.out.println("SingletonDemo has loaded");
}
public static SingletonDemo getInstance() {
if(instance==null) {
synchronized(SingletonDemo.class) {
if(instance==null) {
instance = new SingletonDemo();
}
}
}
return instance;
}
}

垃圾回收算法
引用计数算法
给每个对象设置一个计数器 当有地方引用这个对象的时候 计数器的值+1当引用失效的时候 计数器-1 当计数器为0 对象不再被使用
引用计数器实现简单 效率高 但是不能解决循环引用问题 同时计数器的运算也是一笔开销 在jdk1.1 之后该算法不再使用

根搜索方法
通过一些GCRoots对象作为起点,从这些节点开始往下搜索,搜索通过的路径称为引用链,当一个对象没有被GC的引用链连接的时候,说明这个对象是不可用的.
GCRoot对象包括:
1.虚拟机栈中引用的对象
2.方法区域中类静态属性引用的对象
3.方法区域中常量引用的对象
4.本地方法栈中JNI的引用对象

标记清除算法
标记-清除 将回收分为两个阶段 标记阶段和清除阶段 在标记阶段 首先通过根节点,标记所有从根节点开始的可达对象 未被标记的对象就是未被引用的垃圾对象 然后在清理阶段 清除所有未被标记的对象
效率问题:标记和清除两个过程的效率都不高
空间问题:标记清除之后会产生大量不连续的内存碎片 空间碎片太多可能会导致以后在程序的运行过程中需要分配较大的对象时 无法找到足够的内存 而不得不触发下一次垃圾收集

标记整理算法
它和标记清除算法类似,但是标记完对象后,不是直接对可回收对象进行清理,而是让所有存活的对象向一端移动,然后直接清理掉边界以外的内存.
缺点:
效率问题:标记整理两个过程的效率都不高
优点:
相对于标记清除算法,解决了内存碎片问题
没有内存碎片之后 对象创建内存分配更快了

复制算法
将内存划分为两块 每次只使用其中一块,一块用完,就将还存活的对象复制到另一块上,然后把已经使用过的内存空间一次清理掉,这样每次都是对整个半区进行回收,内存分配的时候也就不用考虑内存碎片等复杂情况.
优点
效率高,没有内存碎片
缺点
浪费一般的内存空间
复制算法在对象存活率较高时就进行较多的复制操作 效率低

分代收集算法
当前商业虚拟机都是使用分代收集算法,根据对象的存活周期的不同将内存划分为几块,一般是把java堆分为新生代和老年代,根据各个年代的特点采用最适合的算法,在新生代,每次收集都发现有大量对象死去,只有少量存活,就选用复制算法,老年代对象的存活率高,没有额外对象进行分配担保,采用标记清理,或者标记整理算法.

二叉树的深度遍历
package pandy.test.tree;
/*

• 二叉树的节点
  */
  public class Node {
  //数据项
  public long data;
  //数据项
  public String sData;
  //左子节点
  public Node leftChild;
  //右子节点
  public Node rightChild;

  /*

  • 构造方法
    */
    public Node(long data,String sData) {
    this.data=data;
    this.sData=sData;
    }
    }

public void frontOrder(Node localNode) {
    if(localNode!=null) {
        //访问根节点
        System.out.println(localNode.data + "," +localNode.sData);
        //前序遍历左子树
        frontOrder(localNode.leftChild);
        //前序遍历右子树
        frontOrder(localNode.rightChild);
    }
}

介绍一些虚拟机的内存模型
程序计数器
当前线程执行的字节码的行号指示器,执行命令的指令指针
字节码解释器工作时,通过改变此计数器的值来选取下一条需要执行的字节码指令,分支,循环,跳转,异常处理.
线程恢复等基础功能也是依赖这个计数器来完成的.java虚拟机是通过多线程轮流分配处理器的执行时间,一个时刻,一个处理器,只会执行一条线程中的指令,因此线程切换后能恢复到正确的执行位置,每个线程都有一个独立的程序计数器,各个线程之间的计数器互不影响,独立存储,这类内存区域为线程私有的内存.
如果当前执行的是java方法,计数器记录着虚拟机字节码指令的地址,如果执行的是native方法,计数器则为空.
此内存是唯一一个在java虚拟机中没有规定任何outofmemoryError情况的区域.

虚拟机栈
每个方法执行的时候都会创建一个栈桢,用于存储局部变量表,操作栈,动态链接,方法出口等信息,每一个方法调用知道执行完成的过程,就对应着一个栈桢在虚拟机栈中从入栈到出栈的过程.

本地方法栈
虚拟机栈为虚拟机指定java方法,而本地方法栈为虚拟机使用到的native方法服务.

java堆
虚拟机所管理的内存中最大的一块,一块线程共享的内存区域.虚拟机启动的时候创建,此区域存在的唯一的目的就是存放对象实例,几乎所有的对象实例都在此处分配内存.
java堆中还可以细分为:新生代,老年代,再细致一点的有Eden空间,From Survivor空间,ToSurvivor空间等.
java堆可以在物理上不连续 只要在逻辑上连续即可

方法区
线程共享的内存区域,用于存储已被虚拟机加载的类信息,常量,静态变量,即时编译器编译后的代码等数据.

动态规划手写
排序算法手写实现 选择 冒泡 希尔 快速 堆 二分 回溯
手撕二叉树 二叉树的遍历 增加 查找 删除(100行代码)
具体场景 代码解
算法各种解