2025.7.10 北京快手 数开面经

1、HashMap的底层数据结构是什么？

在JDK1.8中，由数组+链表+红黑树组成，当链表过长的时候，会严重影响HashMap的性能，红黑树搜索的时间复杂度是O(logn)，链表是O(n)；

引入红黑树以后，链表和红黑树在达到一定条件下会进行转化（当链表超过8且数据总量超过64才会转成红黑树；将链表转换成红黑树前会判断，如果数组的长度小于64，那么会选择先进行数据扩容，而不是转成红黑树以减少搜索时间）

7、Spark动态分区合并小文件的底层实现？

https://blog.csdn.net/syhiiu/article/details/140277490

1）底层原理概述

Spark动态分区合并是Spark SQL中自适应查询执行（Adaptive Query Execution，简称AQE）特性的一个重要组成部分，底层原理主要涉及到分区数据的优化处理和任务调度

在spark中，分区是组织数据的基本单位，分区数决定了并行计算的并发度，动态分区合并主要作用于shuffle阶段，针对shuffle后产生的小分区进行优化，通常是数据分布不均衡或者分区策略不当，shuffle后可能会产生大量的小分区，增加任务调度的开销，降低了作业的性能；

动态分区的底层原理是通过分许shuffle后的数据分布，将多个小分区合并成较大的分区，以减少任务数量，提高并行度，从而优化作业性能

2）动态分区合并实现方式

补充：spark动态分区合并的优点

1）通过合并小分区，减少任务数量，降低任务调度的开销

2）提高并行度，使得资源得到有效的利用，加快作业的执行速度

3）在大规模数据量时候，能显著减少IO操作次数，提高数据处理的效率

补充：spark动态分区合并的缺点

1）增加内存压力，在合并分区过程中，需要暂时将多个小分区的数据存储在内存中，会增加内存的使用量，如果内存资源不足，可能会导致数据溢写到磁盘上，从而影响性能

2）依赖AQE，动态分区合并时AQE的一个特性，如果配置不当，动态分区合并将无法正常工作