Java基础

Java8种基本数据类型

ArrayList和LinkedList的区别

• ArrayList 是用数组来实现的，LinkedList 是基于链表实现的。
• 数组和链表的最大区别就是数组是可以随机访问，而链表只能从头开始遍历。
• 改查 ArrayList 的效率高
• 增删在尾部时并且数据量大时 ArrayList 效率高，在其他地方LinkedList效率高。

数组因为在物理内存上的连续性，当要增删元素时，会导致后续元素都要移动一位,所以效率比较低，而链表则可以轻松的断开和下一个元素的连接，直接插入新元素或者移除旧元素效率较高,但增删在尾部的时候，不需要移动后续元素，所以 ArrayList 比较快。

单向链表和双向链表的区别

单向链表
组成：链接方向是单向的，链表的遍历要从头部开始顺序读取；结点构成，head指针指向第一个成为表头结点，终止于最后一个指向NULL的指针。
优点：单向链表增加删除节点简单，遍历时候不会死循环。
缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。

双向链表
组成：双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null。
优点：可进可退，能找到前驱和后继。
缺点：占用内存较大，需要多分配一个前驱指针，遍历复杂。

双向循环链表
组成：双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个循环，LinkedList就是双向循环列表组成的。
优点：从循环链表中的任何一个结点出发都能找到任何其他结点。

HashMap

底层实现

JDK 1.7
存储结构：数组+链表
插入方式：头插法
扩容方式：先扩容，再添加
扰动函数:要进行4次位运算 + 5次异或运算

JDK 1.8
存储结构：数组+链表+红黑树
插入方法：尾插法
扩容方式：先添加，再扩容
扰动函数：进行1次位运算 + 1次异或运算

引入红黑树原因

为了解决hash碰撞后，链表过长引起的查询效率问题。

红黑树转化条件

数组的长度大于64，链表长度大于8才会从链表转换为红黑树。

当数组长度小于64时，数组+链表比红黑树占用空间较小，而且红黑树自平衡比较耗时，hash碰撞严重时不如先扩容来解决冲突。

线程安全问题

• JDK1.7：因为采用头插法，所以当并发执行扩容操作时环形链表的情况。
• JDK1.8：采用尾插法解决了1.7的环形链表问题，但是当并发执行put操作时会发生数据丢失等情况。

负载因子

• 负载因子:0.75
• 扩容机制：0.75 * 16=12，当容量达到了12的时就会执行扩容操作。
• 原因：根据泊松分布，当负载因子为0.75时，空间利用率比较高，hash碰撞的频率较少，属于时间和空间平衡的最佳大小。

put操作顺序

1.先判断数组是否为空，为空则调用resize()进行扩容,直接插入到对应的数组中。
2.不为空则根据当前key来计算数据的索引值判断当前key是否存在，如果存在，则覆盖value值。
3.不存在则判断是否是红黑树，是红黑树结构则直接插入。
4.不是红黑树的话，遍历链表准备插入，若链表长度小于8且数组长度小于64时，直接插入链表，数组的长度大于64，链表长度大于8的时候，则将链表转为红黑树，转成功之后，再插入。
5.判断++size是否大于threshold,大于则进行一次resize();

ConcurrentHashMap

底层实现

1.7
存储结构： Segment数组 + HashEntry数组 + 链表

线程安全实现：Segment继承了ReentrantLock，用来做分段锁，理论上如果有 n 个 Segment，那么最多可以同时支持 n 个线程的并发访问，从而大大提高了并发访问的效率。

分段锁：ConcurrentHashMap由多个Segment组成(Segment下包含很多Node)，每个Segment都有一把锁来实现线程安全，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

1.8
存储结构： Node数组 + 链表/红黑树

线程安全实现：取消了分段锁的概念，采用synchronized关键字和CAS来保证其线程安全，CAS失败自旋保证成功，再失败就synchronized保证。
synchronized：只锁定当前链表或者红黑树的首节点。

CAS(compare and swap):CAS 操作包含三个操作数—内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么会自动将该位置值更新为新值。否则，不做任何操作。

并发多线程相关

synchronized关键字

作用

synchronized关键字用来来防止线程干扰和内存一致性错误，解决了多线程之间资源的一致性。

用法

• 修饰实例方法 锁是当前实例对象
• 修饰静态方法 锁是当前类的Class对象
• 修饰代码块 锁是synchonized括号里配置的对象

底层原理

对象中内置一个Monitor监视器
Monitor 可以理解为一个同步工具或一种同步机制，通常被描述为一个对象。每一个 Java 对象就有一把看不见的锁，称为内部锁或者 Monitor 锁。

对象在内存中由三个部分组成

分别为：对象头，实例数据和对其填充(非必须)构成。

Mark Word：存在于对象头中，存储对象的hashcode、锁信息、分代年龄和GC标志等信息,锁升级的过程就是基于修改Mark Word来实现的。

如何实现同步
同步方法:是隐式的，无须通过字节码指令来控制，通过ACC_SYNCHRONIZED访问标志判断一个方法是否声明为同步方法。
同步代码块:通过monitorenter和monitorexit两条指令来实现同步，关联到一个monitor对象，进入时设置Owner为当前线程，进入计数器+1、退出计数器-1。

锁升级过程

过程：无锁状态->偏向锁状态(1次CAS)->轻量级锁状(多次CAS)->重量级锁状态
锁升级的过程是不可逆的,锁升级是为了将众多细粒度锁转换为较少的粗粒度的锁的过程，以削减系统开销，降低锁带来的性能消耗。

volatile关键字

特性

volatile是Java提供的轻量级的同步机制

• 保证可见性(JMM模型和MESI协议)
• 不保证原子性
• 禁止指令重排(基于内存屏障实现)

MESI协议

一种缓存一致性协议，主要来解决多核CPU访问内存比较慢和缓存不一致等问题。

JMM内存模型

1.所有的变量都存储在主内存中，每个线程都有一个私有的工作内存来存储共享变量的副本，并且每个线程只能访问自己的工作内存，无法访问其他线程的工作内存，也不能直接读写主内存中的变量。
2.不同线程之间无法直接访问对方工作内存中的变量，线程间变量值传递均需要在主内存来完成。

多线程并发编程中三个特性

• 可见性
  是指当多个线程访问同一个共享变量时，一个线程修改了这个变量的值，其他线程能够立即看到修改后的值。
• 原子性
  原子性指的一个操作或一组操作要么全部执行，要么全部不执行。
• 有序性
  有序性是指程序执行的顺序按照代码的先后顺序执行。

总线风暴

由于volatile基于MESI缓存一致性协议需要不断的从主内存嗅探和CAS不断循环无效交互导致总线带宽达到峰值。

AtomicInteger

基于volatile + CAS + Native 来实现的线程安全的int包装类

Lock

介绍

Lock锁也叫做同步锁，实现类为ReentrantLock。

Lock和synchronized的区别

• synchronized是关键字，作用于JVM层面的，Lock是API层面的锁。

• synchronized不需要手动释放锁，在线程结束或者异常时会自动释放锁。ReentrantLock必须手动去释放锁，遇到异常，释放不正确会导致死锁，一般在finally{}中释放。

• synchronized为非公平锁，ReentrantLock可以通过参数来设置是否为公平锁，是否公平取决于线程是否按照先后顺序获取锁。

• synchronized不可中断，ReentrantLock可以中断。

• ReentrantLock提供的Condition（条件）可以指定唤醒哪些线程，而synchronized只能随机唤醒一个或者全部唤醒。

• ReentrantLock比synchronized更灵活。

ThreadLocal

介绍

ThreadLocal类存储每个线程的私有数据，即线程的局部变量副本,每个线程维护自己的一份数据，从而达到线程隔离的效果。

内存泄露问题

ThreadLocalMap的生命周期与 Thread 一致，同时ThreadLocalMap 中的 Entry的 key 对 ThreadLocal 是弱引用，但是Entry中的value是被Entry强引用的，如果不手动的清除掉 ThreadLocalMap中Entry对象，在垃圾回收时，key会被回收掉，但是value会被回收，这样不管是否使用弱引用都有内存泄露的可能。所以一般在使用完后需要手动调用remove()方法清除掉。

应用场景

• 全局存储用户信息,方便获取。
• 代替参数的显示传递。
• 解决线程安全问题，达到线程隔离的效果。

线程

创建线程有哪几种方式

• 继承Thread类。
• 实现Runnable接口。
• 使用Callable和Future创建。
• 创建ThreadPool，从线程池中获取。

线程有哪几种状态

• New(新建)，新创建的线程进过初始化，进入Runnable(就绪)状态；
• Runnable(就绪)，等待线程调度，调度后进入Running(运行)状态；
• Running(运行)，线程正常运行，期间可能会因为某些情况进入Blocked(堵塞)
  状态(同步锁；调用了sleep()和join()方法进入Sleeping状态；执行wait()
  方法进入Waiting状态，等待其他线程notify通知唤醒)；
• Blocked(堵塞)，线程暂停运行，解除堵塞后进入Runnable(就绪)状态
  重新等待调度；
• Dead(死亡)：线程完成了它的任务正常结束或因异常导致终止；

线程池

线程池的优点

• 降低资源消耗。
• 提高响应速度。
• 提高线程的可管理性。
• 避免大量的线程间因互相抢占系统资源导致的阻塞现象。

线程池的核心参数

• corePoolSize 核心线程数
• maximumPoolSize 线程池最大线程数
• keepAliveTime 空闲线程存活时间
• unit 空闲线程存活时间单位
• workQueue 工作队列
• threadFactory 线程工厂
• handler 拒绝策略
  • AbortPolicy:丢弃任务并抛出RejectedExecutionException异常（默认）
  • DiscardPolicy:丢弃任务，但是不抛出异常。
  • DiscardOldestPolicy:丢弃队列最前面的任务，然后重新提交被拒绝的任务。
  • CallerRunsPolicy:由调用线程处理该任务。

创建线程池有哪几种方式

Executors

• newCachedThreadPool：创建一个可缓存线程池。
• newFixedThreadPool ： 创建一个定长线程池。
• newScheduledThreadPool ：创建一个定长线程池，支持定时及周期性任务执行。
• newSingleThreadExecutor ：创建一个单线程的线程池。
• newWorkStealingPool：创建了一个新的具有抢占式操作的线程池,每个线程都有一个任务队列存放任务。

ThreadPoolExecutor

• 根据核心参数定制你需要的线程池

如何设置核心线程数

• CPU密集型：核心线程数 = CPU核数 + 1
• IO密集型：核心线程数 = CPU核数 * 2
  具体可以参考：Java线程池实现原理及其在美团业务中的实践

JVM、Spring、Mysql、Redis等相关面试题持续更新中。