转载

Java相关

HashMap的实现原理

HashMap是一个散列桶（数组和链表组成）。插入一个键值对的步骤：

1）对key的hashCode做hash，再计算下标；

2）如果没碰撞直接放到桶中（碰撞的意思是计算得到的hash值相同，需要放到同一个bucket中）；

3）如果碰撞了，调用equals()比较key，相同则替换旧值，不同则以链表的方式链接到后面；

4）如果碰撞导致链表过长（大于等于TREEIFY_THRESHOLD = 8），就把链表转为红黑树.链表长度低于6（UNTREEIFY_THRESHOLD = 6），就把红黑树转为链表；

5）如果bucket满了（超过current capacity* LOAD_FACTOR），就要resize。

有什么方法可以减少碰撞？

扰动函数可以减少碰撞，如果两个不相等的对象返回不同的hashCode，碰撞的几率就会小。（扰动即hash方法内部的算法实现，目的是让不同对象返回不同的hashCode）

使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法，会减少碰撞的发生。例如String、Integer。

hash函数怎么实现的？(JDK1.8)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

index = (n - 1) & hash; // n为capacity
复制代码

hashCode的高16位不变，低16位和高16位做了一个异或。因为table长度为2的幂，计算下标时采用&而不是%。

HashMap什么情况下会出现死循环？

多线程环境下使用HashMap进行put操作会引起死循环。因为多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永不为null，就会产生死循环。

HashMap在JDK1.7和JDK1.8的实现上有啥区别？

JDK1.8之前的实现中用链表解决冲突，产生碰撞的情况下，get的时间复杂度O(1) + O(n)。JDK1.8利用红黑树替换链表，get的时间复杂度为O(1) + O(logn)。

线程安全的Map有哪些？

ConcurrentHashMap，Hashtable。

HashMap和Hashtable的区别

(1) HashMap允许null的key和value，而Hashtable不允许

(2) HashMap不是线程安全的，而Hashtable是线程安全的(方法是synchronized的)

(3) HashMap继承自AbstractMap，而Hashtable继承自Dictionary

(4) HashMap重新计算hash值，Hashtable直接使用对象的hashCode

(5) HashMap有containsKey和containsValue方法，Hashtable只有contains方法

(6) HashMap初始大小是16，且一定是2的指数。Hashtable初始大小是11，扩容方式是old*2+1。负载因子都是0.75f。

HashMap是不是有序的？有序的Map实现类有哪些？如何保证有序的？

HashMap不是有序的。

有序的Map有LinkedHashMap(插入顺序)，TreeMap(大小顺序)。

LinkedHashMap是通过插入排序（put的时候的顺序是什么，取出来的时候就是什么样子）和访问排序（改变排序把访问过的放到底部）让键值有序。

TreeMap是通过实现SortMap接口，能够把它保存的键值对根据key排序，基于红黑树，从而保证TreeMap中所有键值对处于有序状态。

为什么选择红黑树而不是用二叉查找树？为什么不一直使用红黑树？

二叉查找树在极端情况下会变成一条线性结构（跟使用链表结构一样了），遍历查找会很慢。红黑树在插入新数据时会左旋、右旋、变色来保持平衡，解决链表查询深度的问题，属于平衡二叉树。保持平衡需要付出代价，该代价损耗的资源比遍历线性链表要少，所以链表长度小于8时，引入红黑树反而会慢。

Hashtable效率低下的原因

Hashtable的方法是同步的，所有访问Hashtable的线程都必须竞争同一把锁。当一个线程访问Hashtable的同步方法，其他线程也访问Hashtable的同步方法时，会进入阻塞或轮询状态。

例如：
public synchronized V get(Object key) {...}
public synchronized V put(K key, V value) {...}
public synchronized int size() {...}
复制代码

ConcurrentHashMap实现原理

锁分段技术。首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据能被其他线程访问。

结构

一个ConcurrentHashMap包含一个Segment数组。Segment是一种可重入锁(ReentrantLock)。一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构的元素。每个Segment守护着一个HashEntry数组里的元素。当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁。

get()

get过程不加锁，除非读到的值是空会加锁重读。get()方法里将要使用的共享变量都定义成volatile。

LinkedHashMap

LinkedHashMap继承自HashMap，使用双向链表存储Map中Entry的顺序关系。一种是插入有序，一种是访问有序。由构造函数的accessOrder参数决定。不是线程安全类。

访问有序：调用get方法后会将访问的元素移至链表尾部。

面向对象的六大原则

一、优化代码第一步——单一职责原则

一个类中应该是一组相关性很高的函数、数据的封装，应该仅有一个引起它变化的原因。

二、让程序更稳定、更灵活——开闭原则

软件中的对象（类、模块、函数等）应该对于扩展是开放的，但是，对于修改是关闭的。

三、构建扩展性更好的系统——里式替换原则

所有引用基类的地方必须能透明地使用其子类的对象。只要父类能出现的地方子类就可以出现，而且替换为子类也不会产生任何错误或异常，使用者可能根本不需要知道是父类还是子类。

四、让项目拥有变化的能力——依赖倒置原则

1.高层模块不应该依赖低层模块，两者都应该依赖其抽象

2.抽象不应该依赖细节

3.细节应该依赖抽象

模块间的依赖通过抽象发生，实现类之间不发生直接的依赖关系，其依赖关系是通过接口或抽象类产生的。

五、系统有更高的灵活性——接口隔离原则

类间的依赖关系应该建立在最小的接口上。客户端不应该依赖它不需要的接口。

六、更好的可扩展性——迪米特原则

一个对象应该对其他对象有最少的了解。类与类之间的关系越密切，耦合度越大，当一个类发生改变时，对另一个类的影响也越大。

String

面试题：Java中的String有没有长度限制？

编译期：若是采用String s = ""的格式，最大长度为65534。在Java中，所有需要保存在常量池的数据，长度最大不超过2^16=65536，null值使用两个字节表示，因此字符串长度不超65536-2=65534。

运行期：长度不能超过Integer.MAX_VALUE。

Java并发编程基础

更多线程相关面试题

1. 面试题：进程和线程有什么区别？

进程是一个独立的运行环境，有自己的内存空间，可以被看做一个程序或者一个应用。进程间的切换开销大。

线程是进程中执行的一个任务，可以被称为轻量级进程，创建一个线程比创建一个进程需要更少的资源。线程可以共享进程中的资源（线程安全的问题），每个进程都至少有一个线程。线程切换开销小。

进程是资源分配的最小单位线程是CPU调度的最小单位

2. 如何创建一个线程？

方法1：实现Runnable接口

new Thread(new Runnable() {
    @Override
    public void run() {
        
    }
}).start();
复制代码

方法2：继承Thread

class MyThread extends Thread {
    @Override
    public void run() {
        super.run();
    }
}
new MyThread().start();
复制代码

3. 直接调用Thread的run()方法会怎样？

和普通方法一样，运行在当前线程中而不是新线程中。

4. 如何确保线程安全？

Synchronization(同步)是Java线程安全中最简单、用得最广的方法。
使用线程安全的集合类，如ConcurrentHashmap。
在变量前使用volatile关键字，每个线程取得的值都是内存中的，而不是线程缓存中的。
使用各种锁。
使用java.util.concurrent.atomic包中的Atomic Wrapper类。例如AtomicInteger。

5. 多线程编程的好处

在多线程程序中，多个线程并发执行可以提高程序的效率，CPU不会因为某个线程需要等待资源而进入空闲状态。多个线程共享堆内存，因此创建多个线程去执行一些任务会比创建多个进程更好。

6. 线程有哪些生命周期？

New（初始状态）：线程被构建，还没调用start()
Runnable（运行状态）：Java线程把就绪（Ready）和运行（Running）统称运行中
Blocked（阻塞状态）
Waiting（等待状态）：等待一些资源，一旦等待状态结束，状态变为Runnable
Terminated（终止状态）：线程已经执行完

详细 Java中的线程生命周期 - Java中的线程状态

7. 什么是死锁？手写一个死锁的代码。

死锁是指两个或两个以上的线程永远被阻塞的情况，这种情况的产生至少需要两个以上的线程和两个以上的资源。

private void deadLock() {
    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            synchronized (A) {
                try {
                    Thread.currentThread().sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (B) {
                    Log.i(TAG, "B");
                }
            }
        }
    });
    Thread t2 = new Thread(new Runnable() {
        @Override
        public void run() {
            synchronized (B) {
                try {
                    Thread.currentThread().sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (A) {
                    Log.i(TAG, "A");
                }
            }
        }
    });
    t1.start();
    t2.start();
}
复制代码

8. 如何避免死锁？

首先来看产生死锁的条件（缺一不可）

互斥条件：一段时间内某资源只能由一个线程占用。
请求和保持条件：线程已保持至少一个资源，但又提出新的资源需求，且该资源被其他线程占有。
不剥夺资源：线程已获得的资源在未使用完之前，不能被剥夺，只能在使用完由自己释放。
环路等待条件：发生死锁时必然存在一个 线程-资源 的循环链。

避免方法：

(1)避免一个线程同时获取多个锁；

(2)避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源；

(3)避免无限期等待，尝试使用定时锁。

9.synchronized和volatile的区别？

volatile：
- 是轻量级的synchronized，比synchronized的使用和执行成本低，因为不会引起上下文的切换和调度，不会阻塞线程
- 在多线程编程中保证了共享变量的 可见性 （可见性是指当一个线程修改一个共享变量时，另一个线程能读到这个修改的值）
- 只能修饰变量，Java线程内存模型确保所有线程看到的这个变量是一致的
- 修饰的变量不会被编译器优化（指令重排序）

tips(volatile实现原理)

1. 将当前处理器缓存行的数据写回到系统内存。

2. 一个处理器的缓存回写到内存会导致其他处理器的缓存无效。

synchronized
- Java中的每一个对象都可以作为锁
- 对于普通同步方法，锁是当前对象实例
- 对于静态同步方法，锁是当前类的class对象
- 对于同步代码块，锁是synchronized()括号里配置的对象
- 可能会造成线程阻塞
- 修饰方法或代码块
- 可以被编译器优化
- 保证共享变量的可见性和 原子性 （不可被中断的一个或一系列操作）

tips

方法同步和代码块同步实现细节不一样。代码块同步使用monitorenter和monitorexit指令实现

10. 你对线程优先级理解是什么？

线程分配到的时间片决定了线程使用CPU资源的多少，线程优先级决定线程需要多或者少分配一些CPU资源的属性。Java中通过整形成员变量priority(0~10)来控制优先级，默认优先级是5。优先级高的线程分配的时间片多于优先级低的线程。有些操作系统会忽略对优先级的设定。

11. 什么是ThreadLocal？

ThreadLocal是一个以ThraedLocal为键、任意对象为值得存储结构，是一个线程内部的数据存储类，通过它可以在指定线程中存储数据，也只有在指定线程中可以获取到存储的数据。通过set()设值，get()取值。

// 例如，在Android中，Looper类利用ThreadLocal特性，保证了每个线程只存在一个Looper对象
static final ThreadLocal<Looper> sThreadLocal = new ThreadLocal<Looper>();
private static void prepare(boolean quitAllowed) {
    if (sThreadLocal.get() != null) {
        throw new RuntimeException("Only one Looper may be created per thread");
    }
    sThreadLocal.set(new Looper(quitAllowed));
}
复制代码

12. synchronized修饰实例方法和修饰静态方法有什么不同？

修饰实例方法：对调用该方法的对象加锁，俗称“对象锁”。同一个对象在两个线程中访问两个同步方法会产生互斥。不同对象在两个线程中访问同一个同步方法不会产生互斥。
修饰静态方法：对该类对象加锁，俗称“类锁”。调用同步方法时都会产生互斥。

13. 线程池的作用

降低资源消耗：重复利用已创建的线程降低线程创建和销毁造成的消耗
提高响应速度：当任务到达时，任务可以不需要等到线程创建就能立即执行
提高线程的可管理性：使用线程池可以进行统一分配、调优和监控

14. 线程之间的通信机制有几种？

1.共享内存（volatile、synchronized）

线程之间共享程序的公共状态，通过读写内存中的公共状态进行隐式通信。

同步是显示进行的，程序员必须指定某个方法或某段代码需要在线程之间互斥进行。

2.消息传递（notify、notifyAll、wait）

线程之间没有公共状态，线程之间必须通过发送消息进行显示通信。

消息的发送必须在消息的接收之前，同步是隐式进行的。

Java并发采用的是共享内存模型。在Java中，所有实例域、静态域和数组元素都存储在堆内存中，堆内存在线程之间共享。局部变量、方法定义参数和异常处理参数不会在线程之间共享。

15. 简述happens-before规则

如果一个操作happens-before另一个操作，那么第一个操作的执行结果将对第二个操作可见，而且第一个操作的执行顺序排在第二个操作之前。
两个操作之间存在happens-before关系，并不意味着Java平台的具体实现必须按照happens-before关系的指定顺序来执行。如果重排序之后的执行结果，与按happens-before关系来执行的结果一致，那么这种重排序并不非法。

happens-before具体规则

程序顺序规则：一个线程中的每个操作，happens-before于该线程中的任意后续操作
监视器锁规则：对一个锁的解锁，happens-before于随后对这个锁的加锁
volatile变量规则：对一个volatile域的写，happens-before于任意后续对这个volatile域的读
传递性：如果A happens-before B， B happens-before C，那么A happens-before C
start()规则：如果线程A执行操作ThreadB.start()（启动线程B），那么A线程的ThreadB.start()操作happens-before于线程B中的任意操作
join()规则：如果线程A执行操作ThreadB.join()并成功返回，那么线程B中的任意操作happens-before于线程A从ThreadB.join()操作成功返回

16. 简述DCL失效原因，解决办法

DCL（双重检查锁定）是常见的延迟初始化技术，延迟初始化用来降低初始化类和创建对象的开销。

1 public static Singleton getInstance() {
2    if (instance == null) {                   // 第一次检查
3        synchronized (Singleton.class) {      // 加锁
4            if (instance == null) {           // 第二次检查
5                instance = new Singleton();
6           }
7        }
8    }
9    return instance;
10 }
复制代码

在第5行如果发生重排序（1.线程A分配了对象的内存空间，2.并将instance指向内存空间，3.然后再初始化对象），另一个并发线程B可能在第2行判断instance不为null，线程B接下来将访问instance所引用的对象，但此时这个对象有可能还没被A线程初始化。

解决办法1：volatile（禁止指令重排序）

当声明对象的引用为volatile后，指令重排序在多线程环境中将被禁止。（1. 线程A分配对象的内存空间，2.初始化对象，3.设置instance指向刚分配的内存地址）

解决办法2：基于类初始化的解决方案（静态内部类单例模式）

在执行类的初始化期间，JVM会去获取一个锁，这个锁可以同步多个线程对同一个类的初始化。

比较两种方法的差别：

方法1：除了可以对静态字段实现延迟初始化外，还可以对实例字段实现延迟初始化。

方法2：实现代码简洁。

如果需要对实例字段使用线程安全的延迟初始化，使用volatile。如果需要对静态字段使用线程安全的延迟初始化，使用方法2。