1. Interview-Java

2020-07-16  本文已影响0人  allen锅
HashMap

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

1 HashMap原理

1.1 HashMap JDK1.7实现

1.1.1 HashMap基础数据结构

HashMap特点

HashMap特点 HashMap特点2

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

HashMap时间复杂度分析

HashMap解决哈希冲突的方法？

HashMap如何解决哈希冲突

1.1.2 HashMap Put方法

1.1.3 HashMap Get方法

1.1.4 HashMap扩容机制

HashMap为什么需要扩容？

HashMap什么时候扩容？

HashMap怎么扩容？

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

HashMap负载因子

1.1.5 HashMap线程安全问题

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

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

HashMap线程安全的实现方式？

1.2 HashMap JDK1.8实现

1.2.1 HashMap JDK1.8实现

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改进-扩容

引入了红黑树

红黑树特点 HashMap 1.8引入红黑树 HashMap添加数据

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

HashMap 1.8改进-扩容 1.8数组存储位置计算 1.8数组位置转化示意图

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

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

1.2.3 HashMap 1.8常见问题梳理

HashMap链表长度超过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区别？

2 ConcurrentHashMap原理

2.1 Java7 ConcurrentHashMap

2.2 Java8 ConcurrentHashMap

Java8改进

     <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？

3 Java集合类关系图

java集合类 Java集合框架

1. java集合类概述

2. Collections

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

3. Arrays

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

  1. 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

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]
  1. Arrays.fill()
Integer[] data = {1, 2, 3, 4};
Arrays.fill(data, 9);
System.out.println(Arrays.toString(data)); // [9, 9, 9, 9]

Integer[] data = {1, 2, 3, 4};
Arrays.fill(data, 0, 2, 9);
System.out.println(Arrays.toString(data)); // [9, 9, 3, 4]
  1. Arrays.sort()
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]

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]

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]

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]
  1. Arrays.parallelSort()
String[] data = {"1", "4", "3", "2"};
Arrays.parallelSort(data);
System.out.println(Arrays.toString(data)); // [1, 2, 3, 4]
  1. Arrays.binarySearch()

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

  1. Arrays.copyOf()

  2. Arrays.copyOfRange(T[] original, int from, int to)

  3. Arrays.equals(Object[] array1, Object[] array2)

  4. Arrays.deepEquals(Object[] array1, Object[] array2)

  5. Arrays.hashCode(Object[] array)

  6. Arrays.deepHashCode(Object[] array)

  7. Arrays.toString(Object[] array)

  8. Arrays.deepToString(Object[] array)

  9. Arrays.setAll(T[] array, IntFunction

  10. Arrays.parallelSetAll(T[] array, IntFunction

  11. Arrays.spliterator(T[] array)

  12. Arrays.stream(T[] array)

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

4. Collection

5. Iterator

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

6. Queue

ConcurrentLinkedQueue

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

Map集合框架

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

HashMap

HashTable

ConcurrentHashMap

TreeMap

LinkedHashMap

5 List有哪些实现？

List集合框架

ArrayList数组

Vector

LinkedList

6 Set有哪些实现？

Set集合框架

HashSet

LinkedHashSet

TreeSet

7 HashMap & HashSet

8 TreeMap & TreeSet

TreeMap和TreeSet相同点

TreeMap和TreeSet不同点

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

9 LinkedList & ArrayList & Vector

9.1 ArrayList和LinkedList

ArrayList和LinkedList相同点

ArrayList和LinkedList异同点

9.2 ArrayList和Vector

ArrayList和Vector相同点

ArrayList和Vector异同点

10 CopyOnWriteArrayList & CopyOnWriteArraySet

CopyOnWrite并发容器使用场景

CopyOnWrite并发容器缺陷

解决CopyOnWrite内存占用问题

CopyOnWriteArrayList

CopyOnWriteArraySet

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

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

HashMap扩容条件

HashMap的threshold计算逻辑

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的初始容量initialCapacity怎么设置？

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

13 hash表的原理？

13.1 hash定义

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

13.3 hash函数&hashcode

13.4 构造hash函数的方法

13.5 解决hash冲突的方法

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来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

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

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

14 Java序列化与反序列化

14.1 序列化定义

14.2 序列化的两个作用

14.3 Java实现序列化

14.4 序列化的特例

14.5 Transient关键字

14.6 序列化版本问题

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

14.7 Externalizable和Serializable的区别

15 JDK的SPI & Dubbo的SPI

  1. SPI定义
    SPI的全名为Service Provider Interface。JDK的SPI实现了为接口自动寻找实现类的功能。

  2. SPI的使用方式
    当服务提供者提供一个接口的多个实现的时候，一般会在META-INF/services/ 下面建立一个与接口全路径同名的文件，在文件里配置接口具体的实现类。当外部调用模块的时候的时候就能实例化对应的实现类。

  3. 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 抽象类和接口有什么好处？有什么区别？

17 final关键字的作用？

18 lambda表达式

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

new Thread(new Runnable() {

    @Override

    public void run() {

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

    }

}).start();

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

19 jdk8新特性

20 Comparator & Comparable

Comparable

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 & Comparable区别

21 Iterator & Iterable

Iterator&Iterable

22 String&StringBuffer&StringBuilder

23 Java异常体系

23.1 异常分类

Java异常体系

23.2 异常处理方式

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()

24.2 Java反射API

24.3 反射使用步骤

24.4 创建对象的两种方法

25 注解Annotation

Java Annotation

26 Java内部类

27 Java泛型

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

28 Java复制

29 hashcode & equals

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

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

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

29.4 equals和hashcode的关系

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

30.1 UUID

优点：

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

缺点：

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

30.2 数据库自增ID+步长

优点：

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

缺点：

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

优化方案：
针对主库单点，如果有多个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

优点：

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

缺点

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

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

30.4 Redis的incr和incrby

优点：

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

缺点：

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

30.5 Twitter的snowflake算法

snowflake

优点：

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

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

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

32

上一篇下一篇

猜你喜欢

热点阅读