Android第十七次面试总结（Java数据结构）-EW帮帮网

一、Java 集合体系核心架构与高频考点

1. 集合体系架构图

Java集合框架
├─ Collection（单列集合）
│  ├─ List（有序、可重复）
│  │  ├─ ArrayList（动态数组，随机访问快）
│  │  ├─ LinkedList（双向链表，插入删除快）
│  │  └─ Vector（线程安全，已过时）
│  ├─ Set（无序、唯一）
│  │  ├─ HashSet（哈希表，插入/查询O(1)）
│  │  ├─ TreeSet（红黑树，有序）
│  │  └─ LinkedHashSet（链表维护顺序）
│  └─ Queue（队列，FIFO）
│     ├─ LinkedList（双向链表实现队列）
│     └─ PriorityQueue（堆结构，优先级排序）
└─ Map（键值对）
   ├─ HashMap（哈希表，非线程安全）
   ├─ TreeMap（红黑树，键有序）
   ├─ LinkedHashMap（链表维护插入顺序）
   └─ Hashtable（线程安全，已过时）

二、List 体系高频面试题

数组（Array）是内存连续的定长结构，作为所有线性表的底层基础，它在创建时必须指定固定长度，数据在物理地址上紧密排列。这种连续布局带来极速的随机访问能力，按索引获取元素的时间复杂度恒定在 O(1)；但长度不可变成为致命短板：想添加元素必须创建新数组并复制旧数据，耗时达 O(n)。数组适合已知长度且频繁读写的场景，如三维动画中存储顶点坐标。

ArrayList 本质是动态数组，通过封装数组实现了自动扩容机制。初始化时分配较小容量（默认10），当插入元素超出容量时会创建1.5倍大的新数组（JDK 1.8+采用位运算扩容：newCapacity = oldCapacity + (oldCapacity >> 1)），然后迁移数据。这种结构保留数组的核心优势：支持快速随机访问（get(index)仍为O(1)）；但插入删除元素时，为保持连续性需移动后续所有元素，尾部操作耗时O(1)而中间操作可能到O(n)。最适合数据总量波动不大的读密集型场景，如Android的RecyclerView数据源。

LinkedList 采用双向链表实现，每个元素（Node）包含前驱/后继指针和数据本体，各节点物理地址随机分布。这种离散式存储导致随机访问性能低下：获取第n个元素需从头/尾遍历，时间复杂度O(n)。但修改结构异常高效：插入或删除节点只需修改相邻节点指针（O(1)），无需数据迁移。尤其擅长频繁在首尾增删的操作，如实现阻塞队列（BlockingQueue）或LRU缓存。代价是每个元素额外消耗24字节（12字节对象头+8字节前指针+8字节后指针），内存开销显著大于ArrayList。

核心差异体现在操作代价：ArrayList像自动扩容的书籍书架——取书快但插入新书需移动后部书籍；LinkedList像自行车链条——增删链节只需调整挂钩，但查找特定链节需从头数起；原始数组则是固定尺寸的保险箱：存取快但容量锁死。实际开发中，ArrayList凭综合能力成为90%场景首选，LinkedList专注高频修改的特定需求，数组则沉淀为系统级优化的基石（如Java HashMap的桶数组）。

场景应用和扩展：

1. ArrayList的绝对统治场景

在Android开发中，ArrayList是最高频使用的集合，80%的数据存储场景由其承担。RecyclerView的Adapter数据源、Activity/Fragment参数传递的putIntegerArrayList()、SharedPreferences返回的字符串集合都依赖ArrayList。其连续内存特性在虚拟机GC时具有天然优势——当列表元素为原始类型（如Int、Float）时，SparseArray可能替代HashMap但ArrayList仍是首选，因为序列化/反序列化时其连续内存布局传输效率远超其他结构。

2. LinkedList的特需领域

在需要高频头尾操作的特定组件中LinkedList闪耀价值：Messenger应用的聊天消息队列（尾部持续追加新消息，头部删除过期消息）、音乐播放列表的双向导航（prev()/next()操作消耗O(1)时间）、以及自定义ViewGroup的触摸事件分发链（通过链表快速插入高优先级事件处理器）。需警惕的是：实测在Android 10上遍历500元素的LinkedList耗时是ArrayList的18倍，故仅当增删频率超查询3倍时才考虑使用。

3.SparseArray 在 Android 中的核心应用

SparseArray 是专为 Android 设计的轻量化映射容器，旨在解决 HashMap<Integer, Object> 的内存浪费问题。其核心采用双数组结构：一个 int[] 存储键，一个 Object[] 存储值，通过二分查找在键数组中快速定位数据。这种设计避免了 Integer 对象的自动装箱开销，单元素存储可节省 30%-40% 内存。典型场景是视图 ID 与对象的映射：例如在 RecyclerView 适配器中，将 position 映射到数据项 (SparseArray<Data> itemCache)，或缓存通过 findViewById 获取的视图引用 (SparseArray<View> viewCache)。但需注意，其性能边界约在 5,000 个元素以内——此时二分查找耗时约 0.3ms，而超过万级数据时哈希表的 O(1) 时间复杂度将显现优势。

4.LruCache 的实现机制与应用场景

LruCache 本质是封装了 LinkedHashMap LRU 策略的内存控制器。其内部维护一个以访问顺序排序的链表（LinkedHashMap(0, 0.75f, true) 中 true 表示访问后节点移至尾部），链表头部保存最久未访问的数据。当插入新数据导致当前内存超过阈值（通过 maxSize 设定），自动从头部移除旧数据直至满足限制。开发者必须重写 sizeOf() 精确计算单对象内存占比——如图片缓存需返回 bitmap.getByteCount()/1024（单位为 KB），否则默认按条目数计算将导致缓存大小失控。该组件广泛应用于 Bitmap 资源管理（如 Glide 内存缓存）、网络响应缓存（配合 Retrofit 实现离线读取）、高频计算结果的复用场景。进阶用法可结合 DiskLruCache 构建二级缓存，并通过监控命中率 （hitCount/requestCount） 优化 maxSize 参数。

三、Map 体系高频面试题（核心中的核心）

HashMap 的扩容机制与结构设计

HashMap 的扩容触发基于负载因子（loadFactor）与数组容量的协同机制。当元素数量达到阈值（size > threshold，其中 threshold = capacity * loadFactor），系统自动执行2倍扩容（如16→32）。具体过程分为三步：创建新数组、遍历旧数组、节点重定位。重定位过程采用(n-1) & hash的优化算法替代取模（hash % n）——利用位运算加速索引计算，同时通过高低位拆分（JDK1.8+）解决哈希冲突：原链表节点根据 (e.hash & oldCap) == 0 的判定被精准分配到新数组的原下标或原下标+oldCap位置。这一优化避免JDK1.7头插法导致的死链风险，且保持链表顺序。

核心结构演变（JDK1.7 vs 1.8）

JDK1.7采用纯数组+链表结构，插入时采用头插法（新节点置链表头），扩容后链表顺序倒置。而JDK1.8引入临界值控制的三态结构：

桶节点数<8：保持单向链表
桶节点数≥8且数组长度≥64：转为红黑树（时间复杂度从O(n)降至O(log n)）
扩容或删除导致节点数<6：退化为链表
红黑树的阈值8依据泊松分布设定：当负载因子0.75时，单个桶节点数超过8的概率仅为千万分之一（1/10,000,000），有效平衡树化开销与查询性能。

ConcurrentHashMap 的并发安全结构

JDK1.7 分段锁架构

采用分段锁（Segment） 实现16路并发（默认）。每个Segment是继承ReentrantLock的独立HashMap，写操作仅需锁定当前段。但查询时需遍历所有Segment，内存浪费且并发度固定无法提升。

ConcurrentHashMap 采用 CAS + synchronized 的细粒度锁机制实现高并发安全。在 JDK1.8 中彻底重构：废弃分段锁，转而将锁粒度缩小到每个桶的首节点。读操作全程无锁（依赖 volatile 修饰的 Node 数组保证可见性）；写操作则分层处理——桶为空时用 CAS 无锁插入，桶非空时仅对链表头或树根节点加 synchronized 锁。其内部采用与 HashMap 相同的 数组 + 链表 + 红黑树结构，但通过 ForwardingNode 标记迁移状态实现并发扩容：当超过容量阈值（默认75%）时，多线程协同迁移数据（每个线程领取迁移区间），期间读写操作若访问未迁移桶可正常执行，访问迁移中桶则转发到新数组。

性能层面，它凭借 读无锁化、写锁单桶化 的设计，在32线程并发下读性能超 Hashtable 15倍，写性能超18倍。但严格来说仍非完全无锁，极端场景下（如所有写操作集中于同一桶）会退化为同步阻塞。为此它引入 树化降级机制：当红黑树节点少于6个自动退化为链表，减少锁竞争开销。相较于 JDK1.7 的16段固定并发度，1.8的动态锁粒度可随数据分布自适应伸缩，更契合现代多核处理器架构。

四、Set 体系高频面试题

1. HashSet 如何保证元素唯一？

源码解析：

// HashSet的add方法（底层是HashMap）
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null; // 利用HashMap的键唯一特性
}

面试回答：

HashSet 底层基于 HashMap 实现，元素作为键存储，值统一为PRESENT。添加元素时，通过以下步骤保证唯一：

计算元素的哈希值（hashCode()），确定存储桶；

若桶内无元素或元素相等（equals()），则不添加；

若桶内是链表 / 红黑树，遍历比较equals()，存在则忽略。

2. TreeSet 排序原理

回答：

TreeSet 基于 TreeMap 实现，元素作为键存储，利用红黑树的有序性。排序方式有两种：

自然排序：元素实现Comparable接口，重写compareTo()；

定制排序：创建 TreeSet 时传入Comparator，重写compare()。
插入时通过红黑树的旋转保持平衡，时间复杂度 O (log n)。

五、Queue 与特殊集合高频题

1. PriorityQueue 如何实现优先级排序？

源码解析：

// 小根堆实现，父节点≤子节点
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1; // 计算父节点索引
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0) break; // 父节点更小，停止上浮
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

回答：

PriorityQueue 基于堆（默认小根堆），元素通过自然顺序或Comparator排序。插入时上浮调整堆结构，删除堆顶元素后下沉调整，时间复杂度均为 O (log n)。应用场景：任务调度（如线程池中的任务队列）、Top-N 问题（取最大 / 最小元素）。

2. 集合中的 fail-fast 机制

回答：

概念：当集合结构被修改时（如增删），迭代器检测到modCount变化，抛出ConcurrentModificationException。

支持集合：ArrayList、HashMap、HashSet 等非线程安全集合；

原理：迭代器维护expectedModCount，每次操作检查是否与集合的modCount一致；

应用：快速发现并发修改错误，避免脏读，但无法保证绝对线程安全（适合单线程迭代场景）。

六、MVC和kotlin中的可变类型

1. MVC vs MVVM 在 Android 中的实践

对比表格（结合面试高频点）：

对比项	MVC	MVVM
耦合度	Activity 兼具 View 和 Controller，代码臃肿	View 与 ViewModel 解耦，Activity 仅作 View
数据绑定	手动更新 UI（findViewById+setXXX）	自动数据绑定（DataBinding/LiveData）
线程安全	需手动处理子线程更新 UI	ViewModel 通过 LiveData 自动切主线程
测试难度	难（依赖 UI 组件）	易（ViewModel 可独立测试）
典型问题	Activity 泄漏、回调地狱	无（ViewModel 生命周期感知）

实战回答：

在 Android 中，MVVM 通过 ViewModel 和 LiveData 实现：

ViewModel 负责业务逻辑和数据（不持有 Activity 引用）；

LiveData 感知生命周期，数据变化自动更新 UI（通过 Observer）；

DataBinding 减少 findViewById 和手动设置数据，降低耦合。
优势：解决 MVC 中 Activity 臃肿问题，提升可测试性，避免内存泄漏（ViewModel 随 Activity 销毁而销毁）。

2.可变类型的原理

只读接口 (kotlin.collections.List.kt)

public interface List<out E> : Collection<E> {
    // 只有查询方法，没有修改方法
    override val size: Int
    override fun isEmpty(): Boolean
    operator fun get(index: Int): E // 读取索引处元素
    fun indexOf(element: @UnsafeVariance E): Int
    fun lastIndexOf(element: @UnsafeVariance E): Int
    fun listIterator(): ListIterator<E>
    fun listIterator(index: Int): ListIterator<E>
    fun subList(fromIndex: Int, toIndex: Int): List<E>
    // ... 其他只读方法 ...
}

关键点： List<E> 接口只定义了获取数据的方法 (get, indexOf, iterator 等)，没有任何能修改集合内容的方法 (add, remove, set)。

可变接口 (kotlin.collections.MutableList.kt)

public interface MutableList<E> : List<E>, MutableCollection<E> {
    // 继承自List的方法：只读能力
    // 新增的修改方法：
    override fun add(element: E): Boolean
    override fun remove(element: E): Boolean
    fun add(index: Int, element: E)
    fun removeAt(index: Int): E
    operator fun set(index: Int, element: E): E // 写入索引处元素
    // ... 其他可变方法 ...
}

关键点：

MutableList<E> 继承自 List<E>，因此它拥有 List 的所有只读方法。
新增了专门用于修改集合内容的方法 (add, remove, set 等)。
这个接口是 List 接口的子类型（因为 out E 协变）。

具体实现（ArrayList 为例）
Kotlin 的标准集合类（如 ArrayList）同时实现了只读和可变接口：

public actual class ArrayList<E> : MutableList<E>, RandomAccess, 
    AbstractMutableList<E> {
    
    // 必须实现所有MutableList定义的方法（包括继承自List的只读方法和自身的可变方法）
    override fun get(index: Int): E = ... // 来自 List
    override fun set(index: Int, element: E): E = ... // 来自 MutableList
    override fun add(element: E): Boolean = ... // 来自 MutableList
    // ... 其他方法实现 ...
}

实战使用LiveData

在 Kotlin 的 Jetpack 组件中，LiveData 的可变性设计完美体现了 Kotlin 的类型安全哲学。LiveData 通过分层接口设计分离读写权限：LiveData<T> 是只读接口，仅暴露 observe() 等订阅方法；而 MutableLiveData<T> 作为可变子接口额外提供 setValue() 和 postValue() 等修改方法。这种接口分离机制在 ViewModel 中形成经典应用范式——开发者通常在 ViewModel 内部声明私有可变的 MutableLiveData 实例，通过类型转换对外暴露只读的 LiveData 引用。这种设计在编译期就强制实现读写隔离：当 UI 层通过 viewModel.data 获取到 LiveData 类型时，编译器会直接阻断任何修改数据的企图，杜绝了意外修改数据源的风险。

这种可变性控制在架构层面形成安全的数据流：ViewModel 作为唯一拥有 MutableLiveData 引用的数据源，在保障线程安全的前提下更新数据（主线程调用 setValue()，子线程使用 postValue()），更新后的数据会通过生命周期感知机制自动推送给已注册的 UI 观察者。而 UI 组件持有的只读 LiveData 实例仅具备订阅能力，无法反向修改数据，从根源上避免了数据流逆向混乱。这样的设计既遵守了单向数据流原则，又通过 Kotlin 的编译期检查机制使数据安全成为显式约束，开发者无需额外关注防篡改逻辑即可构建出健壮的响应式系统。

```kotlin
class MyViewModel : ViewModel() {
    //  私有可变源数据（仅内部可修改）
    private val _counter = MutableLiveData(0)
    
    // 对外暴露只读LiveData（外部只能观察）
    val counter: LiveData<Int> get() = _counter
    
    //  安全的修改入口
    fun increment() {
        // 原子操作更新数据（内部拥有修改权限）
        _counter.value = (_counter.value ?: 0) + 1
    }
}

class MainActivity : AppCompatActivity() {
    private val viewModel by viewModels<MyViewModel>()
    
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)
        
        //获取只读的LiveData观察者（无修改权限）
        viewModel.counter.observe(this) { value ->
            findViewById<TextView>(R.id.counterText).text = "Count: $value"
        }
        
        // 编译器会阻止任何修改尝试（直接报错）
        // viewModel.counter.value = 100  // ❌ 编译错误：value在LiveData中不可访问
        
        //  唯一合法的修改途径：调用ViewModel封装方法
        findViewById<Button>(R.id.button).setOnClickListener {
            viewModel.increment()  // 🚀 通过安全通道更新数据
        }
    }
}

/*  核心原理总结（基于LiveData源码）：
 * 
 * 1. 接口分离设计：
 *    - LiveData<T> { fun observe(...) }          // 只读观测接口
 *    - MutableLiveData<T> : LiveData<T> {        // 继承并扩展
 *        fun setValue(value: T)                  // 新增写方法
 *        fun postValue(value: T)
 *      }
 *    
 * 2. 类型安全限制：
 *    - 当声明为LiveData时 → 只能访问observe()方法
 *    - 声明为MutableLiveData → 额外获得setValue/postValue
 *    
 * 3. 单行道数据流：
 *    UI事件 → ViewModel.increment() → _counter.setValue() 
 *    → LiveData.observe()回调 → UI更新
 *    
 * 4. 线程安全封装：
 *    - setValue()强制主线程执行（检测线程抛异常）
 *    - postValue()自动切换主线程（后台线程安全更新）
 */
``` 

> **工作流程可视化：**
> 
> ```
> [UI按钮点击] ──→ [ViewModel.increment()] 
>                     │
>                     ↓
>        [_counter.setValue()] → (数据变更)
>                     │
>                     ↓
> [counter.observe()回调] ──→ [更新TextView]
> ```
> 
> **编译期保护机制：**
> 当尝试在Activity中直接访问`counter.value`赋值时，Kotlin编译器会检查到：
> ```kotlin
> // 错误调用示例：
> viewModel.counter.value = 10  
> // 编译器报错：Val cannot be reassigned
> // 原因：LiveData接口未暴露public setter
> ```
> 
>  设计本质：通过**接口的编译期能力限制**+**ViewModel的封装**，构建出单向可预测的数据流体系。

七、集合选择指南

场景	推荐集合类	原因
频繁随机访问	ArrayList	数组索引访问 O (1)
频繁插入删除（首尾）	LinkedList	头尾操作 O (1)
唯一无序集合	HashSet	哈希表实现，插入 / 查询 O (1)
唯一有序集合	TreeSet/LinkedHashSet	红黑树 / 链表维护顺序
键值对无序存储	HashMap	性能最优（非线程安全）
键值对有序存储	TreeMap/LinkedHashMap	红黑树 / 链表维护键顺序
高并发场景	ConcurrentHashMap	CAS+Synchronized，锁粒度小
先进先出队列	LinkedList/ArrayDeque	双向链表支持高效头尾操作
优先级队列	PriorityQueue	堆结构实现优先级排序

Android第十七次面试总结（Java数据结构）

一、Java 集合体系核心架构与高频考点

1. 集合体系架构图

二、List 体系高频面试题

场景应用和扩展：

1. ArrayList的绝对统治场景

2. LinkedList的特需领域

3.SparseArray 在 Android 中的核心应用

4.LruCache 的实现机制与应用场景

三、Map 体系高频面试题（核心中的核心）

HashMap 的扩容机制与结构设计

核心结构演变（JDK1.7 vs 1.8）

ConcurrentHashMap 的并发安全结构

JDK1.7 分段锁架构

四、Set 体系高频面试题

1. HashSet 如何保证元素唯一？

2. TreeSet 排序原理

五、Queue 与特殊集合高频题

1. PriorityQueue 如何实现优先级排序？

源码解析：

2. 集合中的 fail-fast 机制

六、MVC和kotlin中的可变类型

1. MVC vs MVVM 在 Android 中的实践

2.可变类型的原理

七、集合选择指南

网站公告

今日签到

热门文章

最新发布

Android第十七次面试总结（Java数据结构）

一、Java 集合体系核心架构与高频考点

1. 集合体系架构图

二、List 体系高频面试题

场景应用和扩展：

1. ​ArrayList的绝对统治场景​

2. ​LinkedList的特需领域​

3.SparseArray 在 Android 中的核心应用

4.LruCache 的实现机制与应用场景

三、Map 体系高频面试题（核心中的核心）

HashMap 的扩容机制与结构设计

核心结构演变（JDK1.7 vs 1.8）

ConcurrentHashMap 的并发安全结构

JDK1.7 分段锁架构

四、Set 体系高频面试题

1. HashSet 如何保证元素唯一？

2. TreeSet 排序原理

五、Queue 与特殊集合高频题

1. PriorityQueue 如何实现优先级排序？

源码解析：

2. 集合中的 fail-fast 机制

六、MVC和kotlin中的可变类型

1. MVC vs MVVM 在 Android 中的实践

2.可变类型的原理

七、集合选择指南

网站公告

今日签到

热门文章

最新发布

1. ArrayList的绝对统治场景

2. LinkedList的特需领域