1. Interview-Java

作者: allen锅 | 来源:发表于2020-07-16 11:47 被阅读0次

HashMap

参考：https://www.jianshu.com/p/8324a34577a0

1 HashMap原理

1.1 HashMap JDK1.7实现

1.1.1 HashMap基础数据结构

HashMap特点

HashMap特点

HashMap特点2

HashMap是存储key-value键值对的集合，每一个键值对也叫作Entry，这些Entry分散在数组当中，HashMap的主干就是数组。
HashMap是按照数组元素下表检索数据，每个元素的初始值都是null；
HashMap的key唯一，value可重复；允许null键null值，元素无序；
HashMap最常用的两个方法是put和get；
HashMap初始容量是16，扩容方式是2N；HashTable初始容量是11，扩容方式是2N+1

HashMap初始长度为什么是16？长度为什么是2的次幂？

HashMap的默认初始长度是16(为了得到尽量均匀分布的无偏hash函数)，每次自动扩展或手动初始化，长度必须是2的次幂。
- 怎么得到无偏hash函数？利用key的hashcode值来做某种运算。
- HashMap的hash函数为什么不根据length取模？取模简单但是效率低，HashMap采用的hash算法是位运算的方式：index=hashcode(key) & (length-1)。
  - 反观长度16或者其他2的幂，length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
  - hashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)。
容量n为2的次幂，n-1的二进制全为1，位运算可以充分散列，避免不必要的哈希冲突。

HashMap时间复杂度分析

数组查找时间复杂度分析：
- 不考虑哈希冲突情况下，哈希表的时间复杂度为O(1)
- 指定下标的查找，O(1)
- 给定value值查找，需要遍历数组对比，O(n)
- 二分查找、插值查找，O(logn)

HashMap解决哈希冲突的方法？

HashMap如何解决哈希冲突

HashMap解决哈希冲突的方法是链地址法(数组+链表) / 拉链法(开放散列)。
开放定址法(封闭散列)：发生冲突继续寻找下一个未被占用的下标，Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
- 线性探测再散列：di=1,2,3，…，m-1；
- 二次探测再散列：di=1^2,-12,2^2,-22，⑶^{2，…，±（k)}2,(k<=m/2）；
- 伪随机探测再散列：di=伪随机数序列。
再散列函数法：再通过其他哈希函数进行再散列直到没有冲突为止
建立一个公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

1.1.2 HashMap Put方法

得到数组下标，index=hash(key)，将这个key插入到数组index下标处。
当Entry很多时候可能会发生hash冲突，HashMap解决hash冲突用的是链地址法，用链表来实现。当发生hash冲突时候，新来的Entry插入链表会采用“头插法”。(HashMap的发明者认为，后插入的Entry被查找的可能性更大)

1.1.3 HashMap Get方法

得到数组下标，index=hash(key)，由于index可能有多个元素，定位到下标后还要顺着链表头节点一个个往下查找到key对应的value。
如果hashcode相同，HashMap会遍历整个链表，通过key的equals方法判断是否为同一key，如果key相同，则新的value会覆盖旧的value；如果不是同一key，则插入链表头。

1.1.4 HashMap扩容机制

HashMap为什么需要扩容？

数组容量固定有限，元素越来越多后，哈希冲突加剧，提高查询效率。

HashMap什么时候扩容？

HashMap.Size >= threshold = Capacity * LoadFactor

HashMap怎么扩容？

HashMap扩容方式是2N，HashTable扩容方式是2N+1

HashMap的负载因子loadFactor为什么是0.75？

loadFactor过大，发生扩容几率变少，提高了空间利用率，但是哈希冲突加剧，底层红黑树变得复杂，查询效率变低。
loadFactor过小，更容易触发扩容，填充元素少了，哈希冲突也少了，查询效率增加了，但是空间利用率降低了。
loadFactor设置为0.75，是时间和空间的权衡。遵循泊松分布，loadFactor设置为0.75，链表超过8个节点概率千万分之六，哈希冲突概率最低。

HashMap负载因子

1.1.5 HashMap线程安全问题

HashMap为什么不是线程安全的？

在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
put时候导致多线程数据不一致
- 线程A插入数据获得到index，准备插入链表头时候时间片用完了，此时线程B插入数据成功插入；
- 线程A再次获得资源持有过期的链表头信息，A插入记录覆盖了B插入的记录，造成了数据不一致的问题。
resize引起链表死循环
- 两个线程同时检测到需要扩容，同时修改了链表结构形成了循环链表；
- 通过get方法获取元素时候就会出现死循环。
fast-fail策略
- 使用迭代器过程中HashMap被修改，抛出ConcurrentModificationException

HashMap线程非安全会有什么问题？

数据一致性
死循环
错误的结果
无法预料的结果

HashMap线程安全的实现方式？

HashTable：本质是synchronized加锁、阻塞同步、效率低
Map m = Collections.synchronizedMap(new HashMap)：本质是synchronized加锁、阻塞同步、效率低
ConcurrentHashMap：锁分段技术，锁粒度小，效率高

1.2 HashMap JDK1.8实现

1.2.1 HashMap JDK1.8实现

数据结构
源码
- put和get
- resize

HashMap 1.8-数据结构与主要参数

HashMap 1.8-put和get

HashMap 1.8-resize

1.2.2 HashMap JDK1.8与1.7区别

HashMap 1.8改进-数据结构

HashMap 1.8改进-添加元素

HashMap 1.8改进-hashcode计算

HashMap 1.8改进-扩容

引入了红黑树

Java8采用了数组+链表+红黑树，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以由原来JDK1.7的O(n)，降为时间复杂度为 O(logn)。
若链表中元素小于等于6时，红黑树还原成链表形式。

红黑树特点

HashMap 1.8引入红黑树

HashMap添加数据

扩容后数据存储位置的计算方式

在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）
JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。
在计算hash值的时候，JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或。

HashMap 1.8改进-扩容

1.8数组存储位置计算

1.8数组位置转化示意图

链表插入由头插法改为尾插法

JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法就是能够提高插入的效率，但是也会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

1.2.3 HashMap 1.8常见问题梳理

HashMap链表长度超过8为什么要转化为红黑树？

随机hashcode算法节点分布遵循泊松分布，当链表元素为8时，哈希冲突概率为千万分之六，几乎是不可能事件。
- 容器中节点分布在hash桶中的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。

0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

为什么不直接用hashcode()得到的哈希码作为数组下标？

哈希码为什么不直接做下标

为什么采用哈希码与运算计算数组下标？

为什么采用哈希码与运算计算下标

为什么在计算下标前需要对哈希码进行扰动处理？

为什么要对哈希码进行扰动处理

HashMap 1.8 resize(扩容)怎么形成环形链表死循环的？

HashMap 1.8扩容导致环形链表死循环

1.3 泊松分布与指数分布

泊松分布：单位时间内独立事件发生次数的概率分布

泊松分布公式

泊松分布规律

指数分布：独立事件的时间间隔的概率分布

指数分布公式

指数分布规律

1.4 HashMap为什么String、Integer适合做key？

HashMap为什么String、Integer适合做key？

1.5 HashMap中用Object做key，需要实现hashcode和equals

HashMap中用Object做key，需要实现hashcode和equals

1.4 HashMap与HashTable区别？

null值： HashMap允许null键和null值，HashTable的键值都不允许为null
线程安全性：HashMap是线程非安全的，HashTable是线程安全的
效率：在单线程环境下，HashMap效率比HashTable高，因为HashTable由synchronized实现的阻塞同步，效率低，要做一些额外的线程安全方面的控制。
扩容：HashMap初始容量是16，扩容方式为2N；HashTable初始容量为11，扩容方式为2N+1
迭代器：HashMap的迭代器是Iterator，它是fail-fast迭代器，HashTable的迭代器是enumerator，不是fail-fast迭代器。
- 当有其他线程修改了HashMap的结构(增加或删除元素)，将会抛出ConcurrentModificationException
- 迭代器本身的remove()移除元素不会抛出ConcurrentModificationException
- 这也不是一定会发生的，取决于JVM
- 其他线程可以通过set()方法更改集合对象，因为没有从结构上更改集合；如果已经从结构上更改，再调用set()方法，将会抛出IllegalArgumentException

2 ConcurrentHashMap原理

2.1 Java7 ConcurrentHashMap

ConcurrentHashMap是线程安全的，多线程环境建议用ConcurrentHashMap替代HashMap
整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁，减少锁的粒度，提高并发性能。
ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

2.2 Java8 ConcurrentHashMap

Java8改进

数据结构
- 摒弃了分段锁，链表元素超过8个转化为红黑树，时间复杂度从O(n)降为O(logn)
- 从Java7的Segment+ReentrantLock+HashEntry到Java8的synchronized+CAS+HashEntry+红黑树
- Java7默认16个Segments，最多支持16个线程并发写，这个值在初始化时候可以改，但是一旦初始化后就不可扩容。
并发控制方式：
- put操作，如果key为null，通过CAS设置当前值；如果key不为null，用synchronized加锁
- get操作，Node的key值和hash值都有final修饰，数组和Node都有volatile修饰，不用担心可见性问题。
锁粒度
- Java7锁的是Segment，包含多个HashEntry
- Java8锁的是每个数组元素即Node
ConcurrentHashMap的存储结构基本单元是Node，继承自HashMap中的Entry。

     <strong>class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    //... 省略部分代码
} </strong>

为什么Java8的ConcurrentHashMap用synchronized替代ReentrantLock？

锁的粒度变小了，synchronized的性能并不比ReentrantLock差
JDK1.6后synchronized做了很多无锁优化，无锁、偏向锁、轻量级锁、重量级锁等

3 Java集合类关系图

java集合类

Java集合框架

1. java集合类概述

集合类存放于java.util包中。
集合类存放的都是对象的引用，而非对象本身，出于表达上的便利，我们称集合中的对象就是指集合中对象的引用（reference)。
集合类型主要有3种：set(集）、list(列表）和map(映射)。
集合接口分为：Collection和Map，list、set、queue实现了Collection接口

2. Collections

它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。Collections工具类包含如下几类方法：

排序操作
- void sort(List list),按自然排序的升序排序
- void sort(List list, Comparator c);定制排序，由Comparator控制排序逻辑
- void shuffle(List list),随机排序
- void swap(List list, int i , int j),交换两个索引位置的元素
- void reverse(List list)：反转
- void rotate(List list, int distance),旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面。
查找替换操作
- int binarySearch(List list, Object key), 对List进行二分查找，返回索引，注意List必须是有序的
- int max(Collection coll),根据元素的自然顺序，返回最大的元素。类比int min(Collection coll)
- int max(Collection coll, Comparator c)，根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
  *void fill(List list, Object obj),用元素obj填充list中所有元素
- int frequency(Collection c, Object o)，统计元素出现次数
- int indexOfSubList(List list, List target), 统计targe在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).
- boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素。

3. Arrays

Arrays位于java.util包下，主要包含了操纵数组的各种方法。

Arrays.asList(T... data)

将数组转换为集合，接收一个可变参

Integer[] data = {1, 2, 3};
List<Integer> list = Arrays.asList(data);
System.out.println(list.size());// 3
list.forEach(System.out::println); // 1 2 3

如果将基本数据类型的数组作为入参，该方法会把整个数组当作返回的List中的第一个元素

int[] data2 = {1, 2, 3};
List<int[]> list2 = Arrays.asList(data2);
System.out.println(list2.size()); // 1
System.out.println(Arrays.toString(list2.get(0))); // [1, 2, 3]

Arrays.fill()

Arrays.fill(Object[] array, Object obj)：用指定元素填充整个数组（会替换掉数组中原来的元素）

Integer[] data = {1, 2, 3, 4};
Arrays.fill(data, 9);
System.out.println(Arrays.toString(data)); // [9, 9, 9, 9]

Arrays.fill(Object[] array, int fromIndex, int toIndex, Object obj)：用指定元素填充数组，从起始位置到结束位置，取头不取尾（会替换掉数组中原来的元素）

Integer[] data = {1, 2, 3, 4};
Arrays.fill(data, 0, 2, 9);
System.out.println(Arrays.toString(data)); // [9, 9, 3, 4]

Arrays.sort()

Arrays.sort(Object[] array)：对数组元素进行排序（串行排序）

String[] data = {"1", "4", "3", "2"};
System.out.println(Arrays.toString(data)); // [1, 4, 3, 2]
Arrays.sort(data);
System.out.println(Arrays.toString(data)); // [1, 2, 3, 4]

Arrays.sort(T[] array, Comparator<? super T> comparator)：使用自定义比较器，对数组元素进行排序（串行排序）

String[] data = {"1", "4", "3", "2"};
System.out.println(Arrays.toString(data)); // [1, 4, 3, 2]
// 实现降序排序，返回-1放左边，1放右边，0保持不变
Arrays.sort(data, (str1, str2) -> {
    if (str1.compareTo(str2) > 0) {
        return -1;
    } else {
        return 1;
    }
});
System.out.println(Arrays.toString(data)); // [4, 3, 2, 1]

Arrays.sort(Object[] array, int fromIndex, int toIndex)：对数组元素的指定范围进行排序（串行排序）

String[] data = {"1", "4", "3", "2"};
System.out.println(Arrays.toString(data)); // [1, 4, 3, 2]
// 对下标[0, 3)的元素进行排序，即对1，4，3进行排序，2保持不变
Arrays.sort(data, 0, 3);
System.out.println(Arrays.toString(data)); // [1, 3, 4, 2]

Arrays.sort(T[] array, int fromIndex, int toIndex, Comparator<? super T> c)：使用自定义比较器，对数组元素的指定范围进行排序（串行排序）

String[] data = {"1", "4", "3", "2"};
System.out.println(Arrays.toString(data)); // [1, 4, 3, 2]
// 对下标[0, 3)的元素进行降序排序，即对1，4，3进行降序排序，2保持不变
Arrays.sort(data, 0, 3, (str1, str2) -> {
    if (str1.compareTo(str2) > 0) {
        return -1;
    } else {
        return 1;
    }
});
System.out.println(Arrays.toString(data)); // [4, 3, 1, 2]

Arrays.parallelSort()

Arrays.parallelSort(T[] array)：对数组元素进行排序（并行排序），当数据规模较大时，会有更好的性能

String[] data = {"1", "4", "3", "2"};
Arrays.parallelSort(data);
System.out.println(Arrays.toString(data)); // [1, 2, 3, 4]

其余重载方法与 sort() 相同

Arrays.binarySearch()

在调用该方法之前，必须先调用sort()方法进行排序，如果数组没有排序，
那么结果是不确定的，此外如果数组中包含多个指定元素，则无法保证将找到哪个元素

Arrays.copyOf()
Arrays.copyOfRange(T[] original, int from, int to)
Arrays.equals(Object[] array1, Object[] array2)
Arrays.deepEquals(Object[] array1, Object[] array2)
Arrays.hashCode(Object[] array)
Arrays.deepHashCode(Object[] array)
Arrays.toString(Object[] array)
Arrays.deepToString(Object[] array)
Arrays.setAll(T[] array, IntFunction
Arrays.parallelSetAll(T[] array, IntFunction
Arrays.spliterator(T[] array)
Arrays.stream(T[] array)

返回数组的流Stream，然后我们就可以使用Stream相关的许多方法了

Integer[] data = {1, 2, 3, 4};
List<Integer> list = Arrays.stream(data).collect(toList());
System.out.println(list); // [1, 2, 3, 4]

4. Collection

它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
以下接口实现了Collection接口：
- List：可以存放重复的内容
- Set：不能存放重复的内容，所以重复内容靠hashCode()和equals()两个方法区分
- Queue：队列接口
Collection提供了很多通用方法：
- boolean add(Object o)：添加对象到集合
- boolean addAll(Collection c)：将集合c中的所有元素添加到该集合
- boolean remove(Object o)：删除集中中指定的对象
- void removeAll(Collection c)：从集合中删除集合c中也有的元素
- void retainAll(Collection c)：从集合中删除集合c中不包含的元素
- void clear()：删除集合中所有元素
- boolean contains(Object o)：查找集合中是否有指定对象
- boolean containsAll(Collection c)：查找集合中是否含有集合c中的元素
- int size()：返回集合中元素的个数
- boolean isEmpty()：判断集合是否为空
- Iterator iterator()：返回一个迭代器

5. Iterator

Iterator源码

public interface Iterator {
    boolean hasNext();  //检查容器中是否还有下个元素
    Object next();  //获得容器中的下一个元素
    void remove();  //删除迭代器刚越过的元素
}

6. Queue

特殊的list，队列是一种数据结构，FIFO，先进先出。

ConcurrentLinkedQueue

4 Map有哪些实现方式，常用的有哪些？

Map集合框架

map的主要特点是键值对的形式，一一对应，且一个key只对应1个value。其常用的map实现类主要有HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap、weakHashMap等等。

HashMap

key唯一，value可重复
最多只允许一条记录的key为null，允许多条记录的value为null
线程不安全，如果要使HashMap线程安全，可用两种方式：
- Collections.synchronizedMap()
- ConcurrentHashMap
- HashTable
Java7的实现是数组 + 链表
- capacity：当前数组容量，始终保持2的n次方，可以扩容，扩容后为当前容量的2倍，初始容量是16
- loadFactor：负载因子，默认为0.75
- threshold：扩容的阈值，等于capacity*loadFactor
Java8的实现是数组 + 链表 + 红黑树
- 查找的时候当哈希值相同，我们需要遍历链表才能找到元素，时间开销取决于链表的长度，时间复杂度为O(n)；
- Java8中当链表元素超过8个会将链表转化为红黑树，时间复杂度为O(logN)

HashTable

遗留类，继承自Dictionary类，线程安全的，并发性不如ConcurrentHashMap，不建议使用，线程安全的场合用ConcurrentHashMap替代，线程非安全的场合用HashMap替代。
null值： HashMap允许null键和null值，HashTable的键值都不允许为null
线程安全性：HashMap是线程非安全的，HashTable是线程安全的
效率：在单线程环境下，HashMap效率比HashTable高，因为HashTable由synchronized实现的阻塞同步，效率低，要做一些额外的线程安全方面的控制。
扩容：HashMap初始容量是16，扩容方式为2N；HashTable初始容量为11，扩容方式为2N+1
迭代器：HashMap的迭代器是Iterator，它是fail-fast迭代器，HashTable的迭代器是enumerator，不是fail-fast迭代器。
- 当有其他线程修改了HashMap的结构(增加或删除元素)，将会抛出ConcurrentModificationException
- 迭代器本身的remove()移除元素不会抛出ConcurrentModificationException
- 这也不是一定会发生的，取决于JVM
- 其他线程可以通过set()方法更改集合对象，因为没有从结构上更改集合；如果已经从结构上更改，再调用set()方法，将会抛出IllegalArgumentException

ConcurrentHashMap

Java7的实现
- ConcurrentHashMap是线程安全的，多线程环境建议用ConcurrentHashMap替代HashMap
- 整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁，减少锁的粒度，提高并发性能。
- ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。
- Java7默认16个Segments，最多支持16个线程并发写，这个值在初始化时候可以改，但是一旦初始化后就不可扩容
Java8改进
- 数据结构
  - 摒弃了分段锁，链表元素超过8个转化为红黑树，时间复杂度从O(n)降为O(logn)
  - 从Java7的Segment+ReentrantLock+HashEntry到Java8的synchronized+CAS+HashEntry+红黑树
- 并发控制方式：
  - put操作，如果key为null，通过CAS设置当前值；如果key不为null，用synchronized加锁
  - get操作，Node的key值和hash值都有final修饰，数组和Node都有volatile修饰，不用担心可见性问题。
- 锁粒度
  - Java7锁的是Segment，包含多个HashEntry
  - Java8锁的是每个数组元素即Node
- ConcurrentHashMap的存储结构基本单元是Node，继承自HashMap中的Entry。

TreeMap

TreeMap底层数据结构是红黑树
TreeMap实现SortedMap接口，默认按照key的升序排序，也可以指定排序的比较器。当用Iterator遍历时，得到的顺序是排过序的。
使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则在运行时会跑出java.lang.ClassCastException异常。

LinkedHashMap

HashMap的子类，保存了记录的插入顺序，当用Iterator遍历时，得到的顺序是排过序的。
线程非安全：LinkedHashMap相对于HashMap，增加了双链表的结果（即节点中增加了前后指针），其他处理逻辑与HashMap一致，同样也没有锁保护，多线程使用存在风险。
LinkedHashMap保证了可以数据按照访问顺序或插入顺序来操作。如android中LruCache就是运用了这个的LRU（近期最少使用算法），固定大小的LinkedHashMap，当超过阈值的时候就进行LRU进行删除，以达到缓存的策略。DiskLruCache也是跟Lrucache类同，只不过是LruCache内存存储的缓存策略，而DiskLruCache是在磁盘或外部存储上的存储缓存策略。

5 List有哪些实现？

List集合框架

ArrayList数组

有序可重复，底层是数组，随机查找和遍历快，插入删除慢
线程不安全
容量不够，默认扩容当前容量1.5倍+1

Vector

有序可重复，底层是数组，随机查找和遍历快，插入删除慢
线程安全效率低，支持线程同步，某一时刻只有一个线程能够写Vector，避免多线程同时写的不一致性，但是花费代价很高，访问比ArrayList慢
容量不够，默认扩容一倍

LinkedList

有序可重复，底层是双向循环链表，随机查找和遍历速度慢，插入删除快
线程不安全
提供了List中没有的方法操作表头和表尾元素，可以当做堆栈、队列使用。

6 Set有哪些实现？

Set集合框架

HashSet

无序不可重复，底层用hash表实现，存取速度快，内部是HashMap
hash表存放的是哈希值，元素的哈希值是通过元素的hashcode来获取的，HashSet先通过hashcode比较哈希值，若相同继续比较equals()，哈希值相同equals不同的元素顺延存放，即放在一个哈希桶中。
HashSet初始容量是16，扩容方式为2n

LinkedHashSet

HashSet + LinkedHashMap，采用hash表存储，并用双向链表记录插入顺序
内部是LinkedHashMap

TreeSet

无序不可重复，底层用二叉树实现，排序存储，内部是TreeMap的SortedSet
Integer和String可以进行默认的TreeSet排序，自定义类必须实现Comparable接口并且重写compareTo()才能使用TreeSet排序。

7 HashMap & HashSet

接口不一样：HashMap实现自Map接口，HashSet实现自Set接口；
存储结构不一样：HashMap存储的是键值对，HashSet存储的是集合对象；
添加方法名不一样：HashMap用put()添加元素，HashSet用add()添加元素；
hashcode计算方式不一样：HashMap使用key来计算hashcode，HashSet使用成员对象来计算hashcode，hashcode相同情况使用equals()判断对象的相等性；
速度不一样：HashMap速度较快，因为使用唯一的key获取对象；HashSet较HashMap慢。

8 TreeMap & TreeSet

TreeMap和TreeSet相同点

TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的。
TreeMap和TreeSet都是线程非安全的，不过可以使用方法Collections.synchroinzedMap()来实现同步
运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logn)，而HashMap/HashSet则为O(1)。

TreeMap和TreeSet不同点

最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口
TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）
TreeSet中不能有重复对象，而TreeMap中可以存在
TreeSet实现了对TreeMap的封装，底层是通过TreeMap来实现的，绝大部分方法都是直接调用TreeMap方法实现的；TreeMap的底层采用红黑树的实现，完成数据有序的插入和排序。
TreeSet适用于实现key值去重外加对key值进行排序场景；TreeMap适用于有序的map场景。

红黑树的特点(https://blog.csdn.net/chenssy/article/details/26668941)

性质 1：每个节点要么是红色，要么是黑色。
性质 2：根节点永远是黑色的。
性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

9 LinkedList & ArrayList & Vector

9.1 ArrayList和LinkedList

ArrayList和LinkedList相同点

ArrayList和LinkedList都是线程非安全的

ArrayList和LinkedList异同点

数据结构：
- ArrayList底层基于数组实现；
- LinkedList底层基于双向链表来实现的，
线程安全性：
- Vector是线程安全的，ArrayList和LinkedList是线程非安全的。
效率
- 当对数据的主要操作是索引或只在集合的末端增加、删除元素时，使用ArrayList或Vector效率比较高；
- 当对数据的操作主要为指定位置或删除操作时，使用LikedList效率比较高；
LinkedList的CRUD的处理逻辑(都涉及到根据index去找到Node的操作)
- LinkedList 是双向列表。根据index处于前半段还是后半段进行折半查找，来判断已头结点还是尾结点为起来来遍历，来获得当前index所代表的值，提高查询效率。
- 链表批量增加，是靠for循环遍历要添加的数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的。增加一定会修改modCount。
- 删也一定会修改modCount。按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node。
- 改也是先根据index找到Node，然后替换值。改不修改modCount。
- 查本身就是根据index找到Node。

9.2 ArrayList和Vector

ArrayList和Vector相同点

ArrayList、Vector和LinkedList类均在java.util包下
ArrayList和Vector底层都是基于数组实现的，因为数据存储是连续的，所以它们支持用下标来访问元素，索引数据的速度比较快。

ArrayList和Vector异同点

扩容机制：
- ArrayList初始容量是10，默认扩充为原来的1.5n+1；
- Vector初始容量是10，默认扩充为原来的2n
线程安全性：
- ArrayList是线程非安全的，Collections.synchronizedList()方法可以把list变为线程安全的集合，但是意义不大，因为可以使用Vector；
- Vector是线程安全的，synchronized实现的。
效率
- 由于Vector提供了线程安全的机制，其性能上也要稍逊于ArrayList。
Vector可以设置增长因子，而ArrayList不可以。

10 CopyOnWriteArrayList & CopyOnWriteArraySet

CopyOnWrite并发容器使用场景

CopyOnWrite是写时复制，延时懒惰策略。其适用于读多写少的并发场景。
- 比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索。

CopyOnWrite并发容器缺陷

内存占用问题。
因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。
数据一致性问题。
CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

解决CopyOnWrite内存占用问题

可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如，如果元素全是10进制的数字，可以考虑把它压缩成36进制或64进制。
不使用CopyOnWrite容器，而使用其他的并发容器，如ConcurrentHashMap。

CopyOnWriteArrayList

CopyOnWriteArrayList是基于"写时复制"策略的线程安全的数组实现的，特点是写加锁读不加锁。
- 就是复制一个数组，对复制后产生的新数组进行操作，而旧的数组不会有影响，所以旧的数组可以依旧就行读取(可以看出来，读的时候如果有新的数据正在写是无法实时的读取到的，有延时，得等新数据写完以后，然后才可以读到新的数据)。
CopyOnWriteArrayList的add()需要加锁
- 如果多个线程同时去写，多线程写的时候会Copy出N个副本出来，那么可能内存花销很大，所以用一个锁ReetrantLock锁住，一次只能一个线程去添加，这个线程是可重入的。

CopyOnWriteArraySet

CopyOnWriteArraySet是基于CopyOnWriteArrayList实现的，只有add的方法稍微有些不同，因为CopyOnWriteArraySet是Set也就是不能有重复的元素，故在CopyOnWriteArraySet中用了addIfAbsent（e）这样的方法。

11 List与Set、Map区别及适用场景

List,Set都是继承自Collection接口，Map则不是
- List特点：元素有放入顺序，元素可重复；
- Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）
- Map适合储存键值对的数据
Set和List对比：
- Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
- List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
线程安全集合类与非线程安全集合类
- LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
- HashMap是非线程安全的，HashTable是线程安全的;

12 预计用HashMap存10000数据，构造时候传入10000会触发扩容吗？传入1000呢？

HashMap扩容条件

HashMap存储的数据量达到threshold时，就会触发扩容。

HashMap的threshold计算逻辑

HashMap的threshold不止直接使用外部传入的initialCapacity，而是经过了this.threshold=tableSizeFor(initialCapacity)处理后再复制给threshold。
tableSizeFor()方法通过逐步位运算，让返回值保持在2^n。

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap传入10000和1000会触发扩容吗？

HashMap传入10000，经过tableSizeFor()处理后变成2^14=16384，在不扩容情况下可存储的数据容量是16384*0.75=12288，所以存入10000条数据不会触发扩容。
HashMap传入1000，调整后的值是1024，threshold其实是1024*0.75=768，所以存入1000条数据会触发扩容。

HashMap的初始容量initialCapacity怎么设置？

通常在初始化 HashMap 时，初始容量都是根据业务来的，而不会是一个固定值，为此我们需要有一个特殊处理的方式，就是将预期的初始容量，再除以 HashMap 的装载因子，默认时就是除以 0.75。

例如想要用 HashMap 存放 1k 条数据，应该设置 1000 / 0.75，实际传递进去的值是 1333，然后会被 tableSizeFor() 方法调整到 2048，足够存储数据而不会触发扩容。
当想用 HashMap 存放 1w 条数据时，依然设置 10000 / 0.75，实际传递进去的值是 13333，会被调整到 16384，够存储数据而不会触发扩容。

13 hash表的原理？

13.1 hash定义

哈希表又叫散列表或者Hash table，它通过把关键码值key通过一个函数f(key)映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数/哈希函数，存放记录的数组叫做哈希表/散列表/hashtable。
任意key经过哈希函数映射到数组中的任何一个地址的概率相等，这样的散列函数为均匀散列函数。
存在k1不等于k2，使得f(key1)=f(key2)，就叫哈希冲突。哈希冲突理论上不可能完全消除，但是应该尽量避免。

13.2 为什么理想情况下hash表的时间复杂度是O(1)？

hash表物理存储是个数组，极端情况下，如果所有key都发生了哈希冲突，则数组退化成链表，时间复杂度为O(n)。
如果不考虑哈希冲突，key可以通过哈希函数快速定位到数组下标找到记录value，时间复杂度为O(1)。

13.3 hash函数&hashcode

hash函数(哈希)，也叫散列/杂凑函数，将任意长度的输入转换为固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，散列值的空间通常小于输入空间，不同的输入可能得到相同的输出。
hash函数的基础是hash算法，hash算法也可以认为是一种思想，没有固定的公式，只要符合散列思想的算法都可以成为hash算法，hash算法很难找到逆向规律，可以提高空间利用率，提高数据查询效率，常用于数字签名。
hashcode，哈希码，Java的Object.hashCode()记录在Markword中，Hotspot虚拟机由xor-shift算法(异或和移位)实现，用于哈希表的查找

13.4 构造hash函数的方法

直接定址法
- H(key) = a·key + b，其中a和b为常数，这种线性散列函数也叫做自身函数
- 此法仅适合于：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。
- 实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。
数字分析法
- 因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 此法适于：能预先估计出全体关键字的每一位上各种数字出现的频度。
平方取中法
- 因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。
- 此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。
折叠法
- 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。
- 这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。
- 数位叠加可以有移位叠加和间界叠加两种方法：
  - 移位叠加是将分割后的每一部分的最低位对齐，然后相加；
  - 间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
随机数法
- 设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数
- 此法适于：对长度不等的关键字构造哈希函数。
除留余数法
- 取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数(n为存在的数据元素个数)，若p选的不好，容易产生同义词。
基数转换法
- 将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
- 为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。
随机乘数法
- 亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积fk的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n(fk%1)」其中“fk%1”表示fk 的小数部分，即fk%1=fk-「fk」
- 此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比较理想。
字符串数值哈希法
- 把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内。
旋转法
- 旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。
减去法
- 减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

13.5 解决hash冲突的方法

开放定址法(封闭散列)
- Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
  - 线性探测再散列：di=1,2,3，…，m-1；
  - 二次探测再散列：di=1^2,-12,2^2,-22，⑶^{2，…，±（k)}2,(k<=m/2）；
  - 伪随机探测再散列：di=伪随机数序列。
- 优点：
  - 记录更容易进行序列化（serialize）操作
  - 如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的
- 缺点：
  - 存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷；
  - 使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低；
  - 由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费；
  - 删除记录时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。
再散列法
- Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
链地址法/拉链法(开放散列)
- 链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
- 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
- 优点：
  - 对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销)；
  - 由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了；
  - 删除记录时，比较方便，直接通过指针操作即可。
- 缺点：
  - 存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销；
  - 如果所有的 key-value 对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数（perfect hash function），此时封闭散列的性能将远高于开放散列；
  - 由于使用指针，记录不容易进行序列化（serialize）操作。
建立一个公共溢出区
- 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

13.6 hash表的查找性能

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

散列函数是否均匀；
处理冲突的方法；
散列表的装填因子。
- 散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
- α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

13.7 著名的hash算法

MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

MD4(RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。

MD5(RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

SHA-1 及其他

SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。

13.8 hash算法在信息安全方面的应用

文件校验
- 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。
- MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。
数字签名
- Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
鉴权协议
- 如下的鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

14 Java序列化与反序列化

14.1 序列化定义

序列化
简单说就是为了保存在内存中的各种对象的状态在字节数组中，并且可以把保存的对象状态再读出来。虽然你可以用你自己的各种各样的方法来保存Object States，但是Java给你提供一种应该比你自己好的保存对象状态的机制,那就是序列化。序列化指的是把堆内存中的 Java 对象数据，通过某种方式把对象存储到磁盘文件中或者传递给其他网络节点（在网络上传输）。这个过程称为序列化。通俗来说就是将数据结构或对象转换成二进制串的过程。
反序列化
把磁盘文件中的对象数据或者把网络节点上的对象数据，恢复成Java对象模型的过程。也就是将在序列化过程中所生成的二进制串转换成数据结构或者对象的过程。

14.2 序列化的两个作用

对象存储：保存/持久化对象及其状态到内存或者磁盘
对象网络传输

14.3 Java实现序列化

需要序列化的对象的类必须实现Serializable接口，这是一个标记接口，没有任何属性和方法
java底层通过 " Java对象 instanceof Serializable ” 判断当前对象是否是Serializable实例，如果是，才允许进行序列化操作。
java中使用对象流完成序列化和反序列化
- 序列化：ObjectOutputStream的writeObject()
- 反序列化：ObjectInputStream的readObject()

14.4 序列化的特例

序列化ID要一致
序列化并不保存静态变量，序列化保存的是对象的状态，静态变量属于类的状态，因此序列化并不保存静态变量。
要想父类序列化，父类也要实现serializable接口

14.5 Transient关键字

transient修饰的变量，不会被序列化到文件中；
反序列化后transient变量的值被设为初始值，int类型是0，对象型的是null。

14.6 序列化版本问题

在完成序列化操作后，由于项目的升级或修改，可能我们会对序列化对象进行修改，比如增加某个字段，那么我们在进行反序列化就会报错。解决办法就是在 JavaBean 对象中增加一个 serialVersionUID 字段，用来固定这个版本，无论我们怎么修改，版本都是一致的，就能进行反序列化。

14.7 Externalizable和Serializable的区别

java序列化除了实现Serializable接口外，也可以实现Externalizable接口，Externalizable是继承自Serializable的
实现Externalizable接口的类必须提供一个public的无参构造器
Externalizable接口提供了两个抽象方法：writeExternal()、readExternal()。当使用Externalizable接口进行序列化和反序列化操作时，开发人员必须重写writeExternal()和readExternal()，否则对象的状态并不会被持久化。

15 JDK的SPI & Dubbo的SPI

SPI定义
SPI的全名为Service Provider Interface。JDK的SPI实现了为接口自动寻找实现类的功能。
SPI的使用方式
当服务提供者提供一个接口的多个实现的时候，一般会在META-INF/services/ 下面建立一个与接口全路径同名的文件，在文件里配置接口具体的实现类。当外部调用模块的时候的时候就能实例化对应的实现类。
JDK和Dubbo实现SPI的异同
- JDK的SPI用ServiceLoader实现，Dubbo的SPI用ExtensionLoader实现
- JDK的SPI会在一次实例化所有实现，可能会比较耗时，而且有些可能用不到的实现类也会实例化，浪费资源而且没有选择；Dubbo的SPI是延迟加载的。
- dubbo的spi文件定义在META-INF/dubbo/internal/路径下面和jdk的spi类似。但是dubbo的spi文件里面格式和jdkSPI有点不一样，是key-value形式，格式是扩展名=全路径的类名。
- dubbo的spi增加了对扩展点IOC和AOP的支持，一个扩展点可以直接setter注入其他扩展点。这是jdk spi不支持的。

16 抽象类和接口有什么好处？有什么区别？

语法层面上的区别：
- 抽象类可以提供成员方法的实现细节，而接口中只能存在public abstract方法；
- 抽象类中的成员变量可以是各种类型的，而接口中的成员变量只能是public static final类型的；
- 接口中不能含有静态代码块以及静态方法，而抽象类可以有静态代码块和静态方法；
- 一个类只能继承一个抽象类，而一个类却可以实现多个接口。
设计层面上的区别：
- 抽象类是对一种事物的抽象，即对类抽象，而接口是对行为的抽象。抽象类是对整个类整体进行抽象，包括属性、行为，但是接口却是对类局部（行为）进行抽象。继承是一个"是不是"的关系，而接口实现则是"有没有"的关系。如果一个类继承了某个抽象类，则子类必定是抽象类的种类，而接口实现则是有没有、具备不具备的关系，比如鸟是否能飞（或者是否具备飞行这个特点），能飞行则可以实现这个接口，不能飞行就不实现这个接口。
- 设计层面不同，抽象类作为很多子类的父类，它是一种模板式设计。而接口是一种行为规范，它是一种辐射式设计。什么是模板式设计？最简单例子，大家都用过ppt里面的模板，如果用模板A设计了pptB和pptC，pptB和pptC公共的部分就是模板A了，如果它们的公共部分需要改动，则只需要改动模板A就可以了，不需要重新对pptB和pptC进行改动。而辐射式设计，比如某个电梯都装了某种报警器，一旦要更新报警器，就必须全部更新。也就是说对于抽象类，如果需要添加新的方法，可以直接在抽象类中添加具体的实现，子类可以不进行变更；而对于接口则不行，如果接口进行了变更，则所有实现这个接口的类都必须进行相应的改动。

17 final关键字的作用？

用来修饰一个引用
- 如果引用为基本数据类型，则该引用为常量，该值无法修改；
- 如果引用为引用数据类型，比如对象、数组，则该对象、数组本身可以修改，但指向该对象或数组的地址的引用不能修改。
- 如果引用时类的成员变量，则必须当场赋值，否则编译会报错。
用来修饰一个方法
- 当使用final修饰方法时，这个方法将成为最终方法，无法被子类重写。但是，该方法仍然可以被继承。
用来修饰类
- 当用final修改类时，该类成为最终类，无法被继承。

18 lambda表达式

使用lambda表达式实现Runnable接口：

Java 8之前：

new Thread(new Runnable() {

    @Override

    public void run() {

        System.out.println("Before Java8, too much code for too little to do");

    }

}).start();

Java 8方式：

new Thread( () -> System.out.println("In Java8, Lambda expression rocks !!") ).start();

19 jdk8新特性

Lambda表达式
函数式接口
方法引用和构造器调用
Stream API
接口中的默认方法和静态方法
新时间日期API

20 Comparator & Comparable

Comparable

Comparable java.lang 内比较器
传入一个对象，与自身进行比较，返回差值正整数 0 负整数。
实现接口：public interface Comparable<T>
接口定义的方法：public int compareTo(T o);

private static  class Student implements Comparable{
    int id;
 
    private Student(int id){
        this.id = id;
    }
 
    @Override
    public int compareTo(Object o) {
        return this.id - ((Student)o).id;
    }
}
public void studentCompareTo(){
    Student s1 = new Student(10);
    Student s2 = new Student(20);
 
    int b = s1.compareTo(s2);
    System.out.println(String.valueOf(b));
}

Comparator

Comparator java.util 外比较器
传入两个对象，进行比较
实现接口：public interface Comparator<T>
接口定义的方法 int compare(T o1, T o2);

Comparator & Comparable区别

个性化比较：如果实现类没有实现Comparable接口，又想对两个类进行比较（或者实现类实现了Comparable接口，但是对compareTo方法内的比较算法不满意），那么可以实现Comparator接口，自定义一个比较器，写比较算法。
解耦：实现Comparable接口的方式比实现Comparator接口的耦合性要强一些，如果要修改比较算法，要修改Comparable接口的实现类，而实现Comparator的类是在外部进行比较的，不需要对实现类有任何修改。从这个角度说，其实有些不太好，尤其在我们将实现类的.class文件打成一个.jar文件提供给开发者使用的时候。

21 Iterator & Iterable

Iterator&Iterable

iterator()是Iterable接口中的一个方法，方法的返回值是Iterator。Iterator中的方法：
- hasNext();
- next();
- remove();
在jdk 1.5以后，引入了Iterable，使用foreach语句（增强型for循环）必须使用Iterable类。
Java设计者让Collection继承于Iterable而不是Iterator接口。
- 首先要明确的是，Iterable的子类Collection，Collection的子类List，Set等，这些是数据结构或者说放数据的地方。
- Iterator是定义了迭代逻辑的对象，让迭代逻辑和数据结构分离开来，这样的好处是可以在一种数据结构上实现多种迭代逻辑。
更重要的一点是：每一次调用Iterable的Iterator()方法，都会返回一个从头开始的Iterator对象，各个Iterator对象之间不会相互干扰，这样保证了可以同时对一个数据结构进行多个遍历。这是因为每个循环都是用了独立的迭代器Iterator对象。

22 String&StringBuffer&StringBuilder

String字符串常量，不可变的对象；StringBuffer和StringBuilder字符串变量，可改变的对象
执行速度：StringBuilder>StringBuffer>String
StringBuilder线程非安全，StringBuffer线程安全，方法前都加了synchronized
操作少量字符串用String，单线程操作字符串缓冲区大量数据用StringBuilder，多线程操作字符串缓冲区大量数据用SringBuffer

23 Java异常体系

23.1 异常分类

Java异常体系

Throwable
- Error
- Exception
  - RuntimeException：JVM运行时异常，程序员需要处理的地方
  - CheckedException：外部错误，发生在编译阶段，Java编译器强制程序去try catch异常。一般都是如下几个方面：
    - 试图在文件尾部读取数据
    - 试图打开一个错误格式的URL
    - 试图根据给定的字符串查找class对象，而这个字符串表示的类不存在

23.2 异常处理方式

异常抛出
- throws
  - 用在函数上，后面跟异常类，多个异常类用逗号分隔
  - 声明异常，异常可能出现也可能不出现
  - 消极方式处理异常，异常并没有真实处理
- throw
  - 用在函数内部，后面跟异常对象
  - throw代表一定出现了异常，执行到throw语句功能就结束了，跳转到调用者，并将具体问题对象抛给调用者，throw后面的语句都不会被执行
  - 消极方式处理异常，真正处理异常由函数的上层调用处理
异常处理
- try ... catch ... finally

23.3 统一异常处理

{
"code": -1,
"msg": "some error message here",
"data": null
}
{
"code": 0
"msg": "success",
"data": {
            "id": 20,
            "cupSize": "B",
            "age": 25
           }
}

24 Java反射机制

Java反射

24.1 反射应用场景

动态获取信息、动态调用对象方法的功能叫做反射
Person p = new Student()

编译时类型，Person
运行时类型，Student

24.2 Java反射API

Class：反射的核心类，可以获取类的属性、方法等信息
Field：类的属性
Method：类的方法
Constructor：类的构造方法

24.3 反射使用步骤

获取类的Class对象，常用三种方法：
- getClass()
- 类.class
- Class.forName(类的全路径)，最常用、最安全、性能最好
调用Class类中的方法，用反射API操作

24.4 创建对象的两种方法

Class对象的newInstance()
先得到Class对象，再得到Constructor对象，调用Constructor对象的newInstance()

25 注解Annotation

Java Annotation

26 Java内部类

静态内部类：定义在类内部的静态类
成员内部类：定义在类内部的非静态类
局部内部类：定义在方法中的类
匿名内部类：直接用new来生成一个对象的引用

27 Java泛型

Java泛型都是在编译器层次实现的，在生成的Java字节码中是不包含泛型中的类型信息的。

28 Java复制

直接赋值：复制引用
浅拷贝：复制引用但不复制引用对象
深拷贝：复制引用及引用对象

29 hashcode & equals

29.1 hashCode()如何计算出来的？

Object 的 hashcode 方法是本地方法，也就是用 c 或 c++ 实现的，该方法直接返回对象的内存地址。
如果没有重写hashCode()，则任何对象的hashCode()值都不相等；Object类原生的hashcode()比较的是地址值。

29.2 hashCode()方法为什么要选择31作为生成hashcode的乘数？

更少的乘积结果冲突
- 31是一个不大不小的质数，如果你使用的是一个如2的较小质数，那么得出的乘积会在一个很小的范围，很容易造成哈希值的冲突。而如果选择一个100以上的质数，得出的哈希值会超出int的最大范围，这两种都不合适。而如果对超过 50,000 个英文单词（由两个不同版本的 Unix 字典合并而成）进行 hash code 运算，并使用常数 31, 33, 37, 39 和 41 作为乘子，每个常数算出的哈希值冲突数都小于7个（国外大神做的测试），那么这几个数就被作为生成hashCode值得备选乘数了。
31可以被JVM优化(位运算)
- 左移 << : 左边的最高位丢弃，右边补全0（把 << 左边的数据*2的移动次幂）。
- 右移 >> : 把>>左边的数据/2的移动次幂。
- 无符号右移 >>> : 无论最高位是0还是1，左边补齐0。
- 31 * i = (i << 5) - i（左边 312=62,右边 22^5-2=62） - 两边相等，JVM就可以高效的进行计算

29.3 为什么重写equals还要重写hashcode？

如果没有重写hashCode()，则任何对象的hashCode()值都不相等。
HashMap中的比较key是这样的，先求出key的hashcode(),，比较其值是否相等，若相等再比较equals()，若相等则认为他们是相等的。若equals()不相等则认为他们不相等。
如果只重写equals没有重写hashCode()，就会导致相同的key值也被hashcode认为是不同的key值（因为没有重写hashCode()，则任何对象的hashCode()值都不相等），就会在hashmap中存储相同的key值（map中key值不能相同），这就不符合条件了。

29.4 equals和hashcode的关系

equal()相等的两个对象他们的hashCode()肯定相等，也就是用equal()对比是绝对可靠的。
hashCode()相等的两个对象他们的equal()不一定相等，也就是hashCode()不是绝对可靠的

30 设计一个分布式环境下全局唯一的发号器

UUID
数据库自增ID+步长
数据库sequence表+乐观锁
Redis的incr和incrby
Twitter的snowflake算法

30.1 UUID

优点：

简单，代码方便。
生成ID性能非常好，基本不会有性能问题。 \3. 全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更
等情况下，可以从容应对。

缺点：

没有排序，无法保证趋势递增。
UUID往往是使用字符串存储，查询的效率比较低。
存储空间比较大，如果是海量数据库，就需要考虑存储量的问题。
传输数据量大
不可读。

30.2 数据库自增ID+步长

优点：

简单，代码方便，性能可以接受。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

不同数据库语法和实现不同，数据库迁移的时候或多数据库版本支持的时候需要处理。
在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。
在性能达不到要求的情况下，比较难于扩展。
如果遇见多个系统需要合并或者涉及到数据迁移会相当痛苦。
分表分库的时候会有麻烦。

优化方案：
针对主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，可以是Master的个
数。比如：Master1 生成的是 1，4，7，10，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。这样就可以
有效生成集群中的唯一ID，也可以大大降低ID生成数据库操作的负载。

30.3 数据库sequence表+乐观锁

sequence表

select id from sequence where name=B
//获得id=100,更新sequence表
update sequence set id=id+1 where name=B and id=100

优点：

操作简单，使用乐观锁可以提高性能
生成的id有序递增，连续
可适用于分布式环境，可以进行分库分表

缺点

需要单独设置一张表，浪费存储空间
数据库更新比较频繁，写压力太大

改进方案
可以将每次获取一个主键，改为每次获取500个或者更多，然后缓存再当前机器中，用完这500个后，再去请求数据库，做更新操作，可以减少数据库的读写压力，但是会造成主键的不连续。

30.4 Redis的incr和incrby

优点：

不依赖于数据库，灵活方便，且性能优于数据库。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
需要编码和配置的工作量比较大。

30.5 Twitter的snowflake算法

snowflake

优点：

不依赖于数据库，灵活方便，且性能优于数据库，理论上单机最多可生成1000*2^12=400万个ID。
ID按照时间在单机上是递增的。

缺点：
在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全局递增的情况，时钟回拨问题。

31 权限系统怎么做？RBAC了解吗？

Apache shiro
Spring security