Không ai tuyển bạn chỉ vì bạn nhớ Big-O của Quick Sort. Nhưng danh sách 20.000 item cuộn giật, ô search khựng lại sau mỗi ký tự, app bị kill vì ăn RAM — nguyên nhân thường là một quyết định cấu trúc dữ liệu sai đưa ra từ lâu. Trên Android, cấu trúc dữ liệu và giải thuật quyết định hiệu năng ứng dụng Android có sống được trong ngân sách RAM, CPU và pin của điện thoại hay không.
Mục lục
Cập nhật 2026
- Kotlin 2.4.21 ổn định (10/2026), K2 compiler mặc định từ 2.0. API
List,Set,Map,Sequencecủa stdlib không đổi. - Compose BOM 2026.09.00 (runtime/UI 1.12.1, Material 3 1.4.0).
LazyColumnvớikeylà chuẩn; DiffUtil vẫn cần cho RecyclerView. - Macrobenchmark và Perfetto là cách đo chuẩn. Đừng kết luận từ debug build hay cảm giác cuộn tay.
- DSA nền tảng không đổi; chỉ công cụ đo và API UI thay đổi.
Vì sao cấu trúc dữ liệu và giải thuật quyết định hiệu năng ứng dụng Android
Hệ thống cấp heap cho từng process; vượt ngưỡng là OutOfMemoryError, xuống nền thì bị trim hoặc kill. Mọi thứ chạm giao diện phải chạy trên main thread: lọc 50.000 item có thể lâu hơn một frame, và frame đó bị bỏ; lặp lại đủ nhiều thành jank. Pin là ràng buộc thứ ba — vòng lặp lồng nhau đọc dữ liệu và cấp phát object nhiều hơn, CPU và GC làm việc nhiều hơn.
| Ràng buộc | Điều bạn thấy | Việc cần làm |
|---|---|---|
| Heap có giới hạn | OOM, app bị kill khi ở nền | Giữ ít object, cache có ngưỡng |
| Main thread | Jank khi cuộn, ANR khi search | Đẩy việc nặng sang Dispatchers.Default |
| CPU và pin | Máy nóng, pin tụt nhanh | Giảm số vòng lặp và cấp phát |
Big-O: đọc đúng, đừng học thuộc
Big-O đo cách số phép tính tăng khi n tăng, không đo thời gian thực. Bạn bỏ hằng số và số hạng nhỏ, giữ số hạng lớn nhất: với n = 10.000, O(n) là 10.000 phép, O(n log n) khoảng 130.000, còn O(n^2) là 100 triệu. Quan trọng hơn con số là vị trí vòng lặp — O(n) chạy trong onDraw tệ hơn O(n log n) chạy một lần lúc tải dữ liệu, vì cái sau không nằm trên đường tới frame.
Collection trên Android: chọn theo thao tác, không theo thói quen
ArrayList và LinkedList
ArrayList giữ một mảng liên tục: truy cập index O(1), thêm cuối trung bình O(1), chèn/xóa giữa O(n) vì phải dời phần sau. Với dữ liệu UI — adapter, item, kết quả search — đây gần như luôn là lựa chọn đúng.
LinkedList là chuỗi node, mỗi phần tử một object riêng chứa giá trị và hai tham chiếu. Thêm/xóa hai đầu O(1), nhưng truy cập index là O(n): list[5000] phải đi qua 5.000 node, và đặt phép đó trong vòng lặp là tự tạo O(n^2). Node nằm rải rác trong heap nên duyệt tuần tự cũng chậm. Kotlin có ArrayDeque cho stack và queue; LinkedList hiếm khi là lựa chọn đúng trong app Android.
HashMap, SparseArray, ArrayMap
HashMap tra cứu trung bình O(1), xấu nhất O(n) khi hash va chạm nhiều. Với khóa Int, mỗi khóa bị box thành Integer và mỗi entry là một object — rất tốn bộ nhớ khi số phần tử lớn.
SparseArray trong android.util ánh xạ int sang object bằng hai mảng song song đã sắp xếp: khóa không bị box, không có entry object. Tra cứu là binary search O(log n), thêm/xóa O(n) vì phải dời mảng. Nó thắng HashMap về bộ nhớ khi khóa là int và số phần tử vừa phải — đúng kiểu id tài nguyên, id view. Cùng họ có LongSparseArray, SparseBooleanArray, SparseIntArray.
ArrayMap (androidx.collection) là bản Map tổng quát theo cùng ý tưởng hai mảng: nhẹ hơn HashMap với map nhỏ, nhưng chậm hơn khi map lớn hoặc chèn/xóa liên tục.
| Cấu trúc | Mạnh ở | Tránh khi |
|---|---|---|
ArrayList |
Index O(1), duyệt tuần tự nhanh | Chèn/xóa giữa liên tục |
LinkedList |
Thêm/xóa hai đầu | Truy cập index, duyệt dữ liệu lớn |
HashMap |
Tra cứu O(1), khóa bất kỳ | Khóa int số lượng vừa, cần tiết kiệm RAM |
SparseArray |
Khóa int, ít object | Map lớn, chèn/xóa nhiều |
ArrayMap |
Map nhỏ, nhẹ | Map hàng nghìn entry |
List, Set hay Map: chọn interface trước
Chọn theo câu hỏi cần trả lời: List khi thứ tự và index có nghĩa, Set khi cần kiểm tra thành viên, Map khi tra theo khóa. List.contains là O(n), gọi n lần thành O(n^2); HashSet.contains trung bình O(1).
// Sai: O(n * m) - quét toàn bộ selected cho từng order
val visible = orders.filter { order ->
selected.any { it.id == order.id }
}
// Đúng: O(n + m) - index một lần rồi kiểm tra membership
val selectedIds = selected.mapTo(HashSet()) { it.id }
val visible = orders.filter { it.id in selectedIds }
LinkedHashSet giữ thứ tự chèn khi cần cả hai. groupBy và associateBy biến list thành map một lần rồi dùng lại nhiều lần, rẻ hơn firstOrNull trong vòng lặp.
Immutable collection và lazy sequence
listOf() là read-only interface, không phải bất biến — một cast unchecked sang MutableList vẫn compile. Cần chia sẻ dữ liệu thì dùng toList() hoặc buildList, buildMap, buildSet.
kotlinx.collections.immutable cung cấp persistentListOf, persistentMapOf. Cấu trúc persistent chia sẻ phần lớn bộ nhớ giữa hai phiên bản; thêm/xóa trả về instance mới với chi phí gần logarit thay vì copy toàn bộ. Đổi lại, index chậm hơn ArrayList một chút và thêm một dependency. Lợi ích thật: Compose ổn định hơn và StateFlow emit đúng theo equals.
Sequence chạy lười, không tạo list trung gian, và dừng sớm với first, find, take.
val firstMatch = orders.asSequence()
.filter { it.total > 0 }
.map { it.customerName }
.firstOrNull { it.startsWith("Nguyễn") }
// Dừng ngay khi gặp phần tử đầu tiên, không duyệt phần còn lại
Đừng dùng Sequence cho vài chục phần tử: overhead iterator và lambda trên từng phần tử thường làm nó chậm hơn vòng lặp thường. Nó hợp lý khi có từ ba phép biến đổi trở lên hoặc cần short-circuit trên dữ liệu lớn.
DiffUtil và key của LazyColumn
RecyclerView dùng DiffUtil: areItemsTheSame theo id ổn định, areContentsTheSame theo giá trị. Sai equals thì diff coi mọi item đều đổi và rebind toàn bộ. ListAdapter và AsyncListDiffer chạy diff ngoài main thread; gọi calculateDiff trong onBindViewHolder là chặn frame. Chi phí diff phụ thuộc số item và edit distance, nên đừng diff mỗi frame.
Compose không cần DiffUtil: items(orders, key = { it.id }). Key ổn định giữ state, di chuyển thay vì tạo lại, tránh recompose thừa. Key phải duy nhất — trùng key làm Compose ném lỗi. Không truyền key thì index là key, và chèn item ở đầu làm mọi item sau bị coi là mới. contentType giúp tái sử dụng đúng nhóm item.
Cache, phân trang và giữ bộ nhớ có giới hạn
LruCache giữ object có ngưỡng và đẩy ra phần ít dùng gần nhất khi vượt maxSize. Nó không thread-safe: dùng một thread hoặc bọc synchronized. sizeOf tính theo KB; maxSize lấy một phần nhỏ của Runtime.maxMemory (1/8 là điểm khởi đầu).
val bitmapCache = object : LruCache<String, Bitmap>(maxSizeKb) {
override fun sizeOf(key: String, value: Bitmap): Int = value.byteCount / 1024
}
// Đọc/ghi từ một thread, hoặc bọc synchronized(bitmapCache)
Chỉ cache thứ đắt: bitmap decode, JSON parse, query nặng. Cache mọi thứ là đường nhanh nhất tới OOM. Không đặt Activity hay Context vào LruCache — đó là leak. Với ảnh, dùng cache của Coil thay vì tự viết.
Phân trang: đừng giữ toàn bộ dataset trong một List. Paging 3 tải theo trang, giữ cửa sổ item quanh vị trí người dùng, cachedIn(viewModelScope); trong Compose dùng collectAsLazyPagingItems. Merge trang bằng HashSet id, không bằng List.contains — mỗi lần là O(n), tổng thành O(n^2).
Đừng tạo O(n^2) trong UI
Các dạng hay gặp: lọc từng item bằng một phép quét toàn list, indexOf trong vòng lặp, lồng LazyColumn trong LazyColumn, tính section mỗi lần recompose, sort lại mỗi frame. Quy tắc: một phép O(n) chỉ nên chạy khi dữ liệu đổi, không phải khi UI vẽ.
// Sai: sort và group lại mỗi lần recompose
val sections = orders.sortedBy { it.createdAt }.groupBy { it.status }
// Đúng: chỉ tính lại khi chính danh sách thay đổi
val sections = remember(orders) {
orders.sortedBy { it.createdAt }.groupBy { it.status }
}
Ví dụ: search danh sách lớn với debounce và Flow
Bạn có vài chục nghìn item đã tải sẵn và một ô search. Cách naive là lọc toàn bộ list trong onQueryChange, trên main thread, mỗi ký tự một lần:
// Naive: mỗi ký tự lọc lại toàn bộ, lại còn trên main thread
fun onQueryChange(text: String) {
val result = allOrders.filter { it.customerName.contains(text, ignoreCase = true) }
_state.value = result
}
Hai vấn đề: mỗi ký tự tạo list mới và so khớp chuỗi cho từng item, tất cả trên main. Cách đúng là debounce, chạy nền, hủy phép lọc cũ khi có query mới, và precompute khóa search lúc map dữ liệu:
// File: domain/Order.kt
data class Order(val id: Long, val customerName: String, val searchKey: String)
sealed interface SearchUiState {
data object Idle : SearchUiState
data class Results(val orders: List<Order>) : SearchUiState
}
// File: ui/search/OrderSearchViewModel.kt
@OptIn(ExperimentalCoroutinesApi::class)
class OrderSearchViewModel(
private val repository: OrderRepository
) : ViewModel() {
private val query = MutableStateFlow("")
private val allOrders: List<Order> = repository.all() // tải một lần
val results: StateFlow<SearchUiState> = query
.debounce(300) // gõ xong mới lọc
.distinctUntilChanged() // query không đổi thì bỏ qua
.mapLatest { text -> // query mới hủy phép lọc cũ
val key = text.trim().lowercase()
if (key.isEmpty()) {
SearchUiState.Idle
} else {
val matches = withContext(Dispatchers.Default) {
allOrders.filter { key in it.searchKey }
}
SearchUiState.Results(matches)
}
}
.stateIn(
scope = viewModelScope,
started = SharingStarted.WhileSubscribed(5_000),
initialValue = SearchUiState.Idle
)
fun onQueryChange(text: String) {
query.value = text
}
}
searchKey được tính một lần lúc map từ network hoặc database: lowercase, bỏ dấu, nối các trường cần tìm, nên mỗi lần lọc chỉ còn so khớp chuỗi mà không cấp phát. debounce(300) cắt số lần lọc xuống một lần sau khi người dùng ngừng gõ; mapLatest hủy phép lọc đang chạy khi có query mới; WhileSubscribed dừng pipeline khi UI không còn quan sát. Compose thu kết quả bằng collectAsStateWithLifecycle(). Nếu StateFlow còn lạ, xem lại bài Coroutines, Threads và RxJava.
Đo trước khi sửa: Macrobenchmark và Perfetto
Đo trên release build, máy thật tầm trung, không phải emulator debug. Macrobenchmark chạy qua Gradle Managed Devices, dùng StartupTimingMetric và FrameTimingMetric trong measureRepeated để có số liệu lặp lại được trên CI. Perfetto cho trace toàn hệ thống: thêm slice bằng androidx.tracing.trace("filter-orders") quanh đoạn lọc để thấy nó chiếm bao nhiêu trong frame. Debug build khác release rất nhiều, đừng dùng nó để kết luận.
Pitfall thường gặp
- Tối ưu sớm. Danh sách 200 item không cần index, cache hay
Sequence. Tối ưu khi có phép đo hoặc khi biết dữ liệu sẽ tăng. LinkedListđể truy cập index. Mỗi lần truy cập O(n); trong vòng lặp thành O(n^2) cộng hàng nghìn object node. DùngArrayList, cần hai đầu thì dùngArrayDeque.- Cấp phát trong vòng vẽ. Tạo
Paint,Rect, chuỗi format hay list mới trongonDrawhoặc trong composition sinh rác mỗi frame và kéo theo GC. Khởi tạo ngoài vòng vẽ, dùngremembercho object dùng lại. - Sort trên main thread.
sortedBytrên vài chục nghìn item với so sánh chuỗi đủ để bỏ frame. Sort một lần khi dữ liệu đổi, trênDispatchers.Default, rồi giữ kết quả. - Object graph quá lớn. Giữ nguyên response network, model lồng nhiều tầng, hay
Bitmaptrong từng item làm heap phình và GC chạy nhiều. Chỉ giữ trường bạn hiển thị; ảnh để thư viện ảnh quản lý.
Chọn gì cho tình huống nào
| Tình huống | Chọn | Vì sao |
|---|---|---|
| Dữ liệu UI theo thứ tự, cần index | ArrayList |
Truy cập O(1), ít object |
Khóa là int, số lượng vừa |
SparseArray |
Không box khóa, không entry object |
| Tra cứu theo id nhiều lần | Map từ associateBy |
O(1) thay vì O(n) mỗi lần |
| Kiểm tra thành viên, loại trùng | HashSet |
contains trung bình O(1) |
| Chuỗi biến đổi dài, dữ liệu lớn | Sequence |
Không list trung gian, dừng sớm |
Hướng 2027
Kotlin 2.5.0 dự kiến ra mắt 12/2026, hiện chưa phát hành, nên đừng viết code dựa trên nó. Compose vẫn là UI mặc định cho app mới. DSA không đổi, chỉ công cụ đo tốt hơn — nên lý do tối ưu mò ngày càng yếu.
Checklist trước khi commit
- Mọi collection có khóa tra cứu đều được index một lần bằng
associateByhoặcgroupBy, khôngfirstOrNulltrong vòng lặp. - Lọc, sort, parse không chạy trên main thread và không chạy lại mỗi frame.
- Item trong
LazyColumncókeyổn định, duy nhất; RecyclerView cóDiffUtilvớiareItemsTheSametheo id. - Cache có ngưỡng, có khóa rẻ, và không giữ
Context. - Danh sách dài dùng phân trang, cửa sổ item có giới hạn, merge trang bằng
HashSetid. - Đã đo bằng Macrobenchmark hoặc Perfetto trên release build trước và sau khi sửa.
Đọc tiếp
Nếu cú pháp Kotlin còn chưa chắc, đọc Học Kotlin cho Android: Cú pháp và Khái niệm Cốt lõi. Cách DiffUtil và RecyclerView ghép thành danh sách động nằm ở Xây dựng Danh sách Động với RecyclerView. Toàn bộ thứ tự học nằm trong Android Developer Roadmap – Lộ trình học Lập trình viên Android.



