【牛客面经汇总】——阿里一面面经含答案

2024-03-12 11:42:20

Java 基础——容器

Java中的常见集合

  • List

    • ArrayList
    • LinkedList

  • Set

    • HashSet
    • TreeSet

  • Map

    • HashMap

    • TreeSet

（1）list、set、map的区别？

List (对付顺序的好帮手)： 存储的元素是有序的、可重复的。
Set (注重独一无二的性质): 存储的元素是无序的、不可重复的。
Map (用 Key 来搜索的专家): 使用键值对（kye-value）存储，类似于数学上的函数y=f(x)， “x”代表 key， "y"代表 value， Key 是无序的、不可重复的， value 是无序的、可重复的，每个键最多映射到一个值

（2）Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
  3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

HashMap的底层数据结构

JDK1.8 之前：

底层是数组+链表，即链表散列。HashMap通过key的hashCode经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

【牛客面经汇总】——阿里一面面经含答案

JDK1.8 之后：

当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

【牛客面经汇总】——阿里一面面经含答案

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

红黑树的具体原理

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

HashMap的线程不安全问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

主要是以下三个问题：

(一) 数据覆盖问题

执行 put 操作时，可能会导致出现数据覆盖的问题：

JDK1.7 版本下，插入某个节点采用的是头插法。设有线程A 和线程B同时进行 put 操作，A 和 B 的 key 同时都指向同一个数组下标 table[i]。A先获取table[i]的头节点，将自己插入的节点作为新头节点准备插入时，时间片使用完，轮到B 执行插入完成。这时候再轮到A插入，就会覆盖B插入的节点，从而导致数据覆盖。

（二）扩容导致死循环

源代码为：

void transfer(Entry[] newTable, boolean rehash) {

    int newCapacity = newTable.length;
    for (EntryK,V> e : table) {
        while(null != e) {
            EntryK,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
       }
    }
}

解释：

  • 扩容之前，线程B在遍历 table 时获取到一个节点 e（e = a），并且获取到下一个节点 next（next=b）。B的时间片使用完毕

  • 这时A获取到时间片，完成扩容。这时他的节点链表变为 c->b->a->null

  • B获得时间片，进行扩容。这时 B 的 e 引用依旧是 a ，同理 next 引用的是 b。这时我们执行 newTable[i] = e;这一句，则会直接指向a节点，而且b节点就是下一个 e 节点。

  • 循环到下一个节点，e引用的为 b 节点，b节点的下一个节点还是a节点，newTable[i]= e将头节点设置为 b 节点。

  • 又循环到 a 节点，这时将 a 节点作为头节点再次插入，a.next = b 。形成环形链表。

循环链表问题在 JDK1.8 得到解决，将头插法改进为尾插法，从而保证了安全性。

（三）数据丢失

一些博客里会说 JDK1.8 中多线程HashMap有数据丢失，我的理解其实就是多线程下对链表的插入操作，多个线程同时获取到尾节点 tail，某个线程插入后没来得及将插入节点A改为尾节点，就被另一个线程获取到时间片。将节点B插入到尾节点tail，这时就出现了一个孤立的节点A。

HashMap rehash 过程是什么样的？各个变量（capacity、size、threshold、loadFactor）意义，他们和扩容的关系？

HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。一般都是2的幂次方

capacity：容量一般为2的幂，举例假设为1024；

size：每个节点上存放的KV个数之和为size，0号桶存放了4个KV，2号桶存放了2个KV，1006号桶存放了50个KV，1008号桶存放了3个KV，则size为4+2+50+3=59

threshold：capacity * loadFactor(0.75) = 768，表示当size（KV的总量）超过768时会扩容

loadFactor：装载因子的阈值为0.75，装载因子用来衡量HashMap满的程度。现在的装载因子为size(59) / loadFactor(0.75) = 0.05

【牛客面经汇总】——阿里一面面经含答案

插曲——redis比较

redis的hash怎么实现以及 rehash过程是怎样的？和JavaHashMap的rehash有什么区别，与ConcurrentHashMap扩容的策略比较？

问： HashMap与redis中的Hash比较：

从数据结构的角度来看，redis的dict和java的HashMap很像，区别在于rehash：HashMap在resize时是一次性拷贝的，然后使用新的数组，而dict维持了2个dictht，平常使用ht[0]，一旦开始rehash则使用ht[0]和ht[1]，rehash被分摊到每次的dictAdd和dictFind等操作中。

当hash内部的元素比较拥挤时(hash碰撞比较频繁)，就需要进行扩容。扩容需要申请新的两倍大小的数组，然后将所有的键值对重新分配到新的数组下标对应的链表中(rehash)。redis中，如果hash结构很大，比如有上百万个键值对，那么一次完整rehash的过程就会耗时很长。这对于单线程的Redis里来说有点压力山大。所以Redis采用了渐进式rehash的方案。它会同时保留两个新旧hash结构，在后续的定时任务以及hash结构的读写指令中将旧结构的元素逐渐迁移到新的结构中。这样就可以避免因扩容导致的线程卡顿现象。

ht是一个数组，有且只有俩元素ht[0]和ht[1];其中，ht[0]存放的是redis中使用的哈希表，而ht[1]和rehashidx和哈希表的 rehash有关。ht[0]，是存放数据的table，作为非扩容时容器。ht[1]，只有正在进行扩容时才会使用，它也是存放数据的table，长度为ht[0]的两倍。
扩容时，单线程A负责把数据从ht[0] copy到ht[1] 中。如果这时有其他线程
进行读操作：会先去ht[0]中找，找不到再去ht[1]中找。
进行写操作：直接写在ht[1]中。

**不同的是，**Redis的字典只能是字符串，另外他们rehash的方式不一样，因为Java的HashMap的字典很大时，rehash是个耗时的操作，需要一次全部rehash。Redis为了追求高性能，不能堵塞服务，所以采用了渐进式rehash策略。

渐进式rehash会在rehash的同时**，保留新旧两个hash结构，**查询时会同时查询两个hash结构，然后在后续的定时任务以及hash操作指令中，**循环渐进地将旧hash的内容一点点地迁到新的hash结构中。当搬迁完成了，就会使用新的hash结构取而代之。**当hash移除最后一个元素后，该数据结构自动删除，内存被回收。

hash结构也可以用来存储用户信息，与字符串需要一次性全部序列化整个对象不同，hash可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时，可以进行部分获取。而以整个字符串的形式去保存用户信息的话，就只能一次性全部读取，这样就会浪费网络流量。但是hash结构的存储消耗要高于单个字符串。

问：与ConcurrentHashMap扩容的策略比较？

ConcurrentHashMap采用的扩容策略为： “多线程协同式rehash“。

这里的多线程指的是，有多个线程并发的把数据从旧的容器搬运到新的容器中。扩容时大致过程如下：
线程A在扩容把数据从oldTable搬到到newTable，这时其他线程
进行get操作：这个线程知道数据存放在oldTable或是newTable中，直接取即可。
进行写操作：如果要写的桶位，已经被线程A搬运到了newTable。
那么这个线程知道正在扩容，它也一起帮着扩容，扩容完成后才进行put操作。
进行删除操作：与写一致。

两者对比：

  1. 扩容所花费的时间对比： 一个单线程渐进扩容，一个多线程协同扩容。在平均的情况下，是ConcurrentHashMap 快。这也意味着，扩容时所需要 花费的空间能够更快的进行释放。
  2. 读操作，两者性能相差不多。
  3. 写操作，Redis的字典返回更快些，因为它不像ConcurrentHashMap那样去帮着扩容(当要写的桶位已经搬到了newTable时)，等扩容完才能进行操作。
  4. 删除操作，与写一样。

多线程问题

创建线程的几种方式

（1）继承Thread类创建线程类，重写 run 方法

（2）通过 Runnable 接口创建线程类，重写 run 方法

（3）通过 Callable 和 FutureTask 创建线程

  1. 创建 Callable 接口实现类，重写 call 方法
  2. 创建 Callable 类的实例，使用 FutureTask 类对象包装该实例，FutueTask 对象封装了 Callable 对象 call 方法的返回值
  3. 将 FutureTask 作为 Thread 对象的 target 属性传入，并启动线程。
  4. 调用 FutureTask 对象的 get 方法，获取返回值。

线程池

线程池的优点

采用线程池的方案，将线程重复利用，从而保证系统的效率，避免过多资源浪费在创建销毁线程上。

提高相应速度，请求或者任务到达可以直接相应处理

将任务提交和执行分离，降低耦合

提高线程的可管理性。使用线程池统一分配，调优，监控。

设计一个线程池的思路：

《Java并发编程的艺术》
https://cloud.tencent.com/developer/article/1673042
https://dunwu.github.io/javacore/concurrent/Java%E7%BA%BF%E7%A8%8B%E6%B1%A0.html
https://mp.weixin.qq.com/s/q0Qt-ha9ps12c15KMW7NfA
https://www.jianshu.com/p/94852bd1a283

  1. 启动线程池时，我们需要预先创建并启动若干个线程以用来接收传入的任务。

  2. 创建的线程名称，优先级等待属性需要统一设置，我们可以通过一个特定或默认的工厂进行批量生产

  3. 启动线程后，我们还要对线程进行重复利用，那么需要容器来存取线程。

  4. 启动的线程数必须要有限制，不然无尽的线程数会使cpu频繁切换上下文，从而使cpu资源严重浪费，同时大量的线程也会占用大量的内存空间，导致 OOM

  5. 如果传入新任务，但所有线程都在执行任务中，无暇顾及传入的任务。需要将其缓存下来，等待任务完毕的某个线程接收该任务继续工作

  6. 继续传入新任务，导致超出缓存大小，或者缓存过大占用大量内存空间进而 OOM。那么可以增加若干个线程，加快处理任务的进度

  7. 如果还是不停的有任务加入，但是依照现在的资源状况，既不允许将任务缓存，也不能允许增加线程进行处理。就只好寻找一个策略来处理这些的任务。

  8. 任务逐渐处理完毕，不需要新创建的线程就能够应对了，可以将这些线程销毁来降低资源的消耗。不过考虑到万一销毁后马上又有大批新任务处理不过来，于是设置一个空闲等待的销毁时间，这段时间里这些线程还是空闲，则销毁，反之则继续运行。（这里我搞不清到什么时候就判定新创建线程是空闲线程）

  9. 如果运行过程中，需要将线程池停下来，要么所有线程马上停止，要么正在运行的线程运行完毕后停止

  10. 所有任务全部都处理完毕了，所有线程都处于空闲状态了，需要将所有线程封存起来，以尽力降低空闲线程的消耗。

插曲：cookie和session的区别

(1)、cookie数据存放在客户的浏览器上，session数据放在服务器上 ；

(2)、cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗,如果主要考虑到安全应当使用session ；

(3)、session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能，如果主要考虑到减轻服务器性能方面，应当使用COOKIE ；

(4)、单个cookie在客户端的限制是3K，就是说一个站点在客户端存放的COOKIE不能3K；

(5)、所以将登陆信息等重要信息存放为SESSION;其他信息如果需要保留，可以放在COOKIE中。

上一篇：redis之hash解析


下一篇：单线程照样飞起 | redis字典快速映射+hash釜底抽薪+渐进式rehash