Android面试题：App性能优化之Java和Kotlin常见的数据结构优化

Java常见数据结构特点

ArrayList

• ArrayList底层是基于数组实现
• add、删除元素需要进行元素位移耗性能，但查找和修改块
• 适合不需要频繁添加删除的

链表

• LinkedList 是双链表插入和删除节点快，查找和修改耗时

HashMap

• 1.7之前是数组+链表；1.8之后是数组+链表+红黑树
• 计算key的位置时用的位运算：h & (length-1)，位运算更快
• HashMap对应的key、value是一一对应的唯一的

扩容

• 默认HashMap大小是16，必须是2的倍数
• 加载因子：默认是0.75
• 阈值：0.75 * 16 = 12的时候扩容
• 扩容是为了避免冲突，提升性能，扩容的时候会重新计算哈希，比较耗性能
• 要尽量避免扩容，初始化的时候要设置HashMap的大小，会自动计算到最接近的2的次幂
• HashMap真正初始化的时候是在put的时候，节约内存
• 为什么是2的次幂，是为了计算index：h & (length-1)，后面是1111，计算index更不容易碰撞
• HashMap是用空间换时间

HashMap的一个经典的优化就是初始化时，尽可能的设置要初始化的容量，尽量避免扩容的发生

SparseArray

• 原理是2个数组，key一个数组，value一个数组，key和value一一对应
• key是int，value是object
• key数组是按照大小顺序排，查找的时候是2分查找，提升性能
• remove的时候，不会真的移除，而是会做个标记，这样不用arraycopy，下次再put就是一个赋值操作，提升性能
• 会越用越快，缺点是key只能是int

ArrayMap

• 原理是HashMap+SparseArray，也是2个数组，key数组和value数组，不过key不限于int
• key的计算和HashMap一样，不过有哈希冲突时，没有用链表而是追加到后面

Kotlin中的优化

Kotlin提供了一些优化和特性来简化和高效地操作常见的数据结构，如 List 和 Map。以下是一些针对这些数据结构的优化和特性示例：

List

1. Immutable Lists: 使用 listOf() 创建不可变列表。
2. Mutable Lists: 使用 mutableListOf() 创建可变列表。
3. 操作符重载: 你可以使用标准库中的高阶函数、扩展函数和操作符重载来高效地操作列表。

// 创建不可变列表
val numbers: List<Int> = listOf(1, 2, 3, 4, 5)

// 创建可变列表
val mutableNumbers: MutableList<Int> = mutableListOf(1, 2, 3)
mutableNumbers.add(4)

// 使用扩展函数
val doubled = numbers.map { it * 2 }  // [2, 4, 6, 8, 10]
val filtered = numbers.filter { it > 2 }  // [3, 4, 5]

Map

1. Immutable Maps: 使用 mapOf() 创建不可变映射。
2. Mutable Maps: 使用 mutableMapOf() 创建可变映射。
3. Destructuring: 优化遍历和解构键值对。

// 创建不可变映射
val map: Map<String, Int> = mapOf("a" to 1, "b" to 2, "c" to 3)

// 创建可变映射
val mutableMap: MutableMap<String, Int> = mutableMapOf("x" to 10, "y" to 20)
mutableMap["z"] = 30

// 使用扩展函数
val keys = map.keys  // 获取所有的键
val values = map.values  // 获取所有的值

// Destructuring
for ((key, value) in map) {
    println("Key: $key, Value: $value")
}

特定优化和高级功能

1、Kotlin的序列提供了懒加载特性，有助于处理大量数据。 2、在扩展函数中使用默认参数提高代码可读性和灵活性。

// Lazy Sequence
val lazyList = listOf(1, 2, 3, 4, 5).asSequence()
    .filter { it % 2 == 0 }
    .map { it * 2 }
    .toList()

// 使用默认参数的扩展函数
fun List<Int>.sum(defaultValue: Int = 0): Int {
    return this.fold(defaultValue) { acc, i -> acc + i }
}

val sum = listOf(1, 2, 3).sum()  // 默认参数，结果是6
val sumWithInitial = listOf(1, 2, 3).sum(10)  // 初始值为10，结果是16

通过这些优化和特性，Kotlin使得操作常见数据结构变得更加简洁和高效。同时，通过深入使用Kotlin标准库中的扩展函数和特性，我们也可以大大简化代码并提高其可读性和可维护性。

作者介绍

中年程序猿，十年移动端开发老司机，分享一线开发经验和知识，正在探索通过副业渡过中年危机

越努力越幸运，加油💪，一起遇见更好的自己