1. 为什么Android开发者绕不开数据结构这道坎刚入行那会儿我总觉得数据结构是面试造火箭、工作拧螺丝的东西。直到有一次做一个列表页数据量刚过两千条滑动就开始明显掉帧排查了半天才发现是每次onBindViewHolder里都在做线性查找。把ArrayList换成HashMap之后帧率直接从四十多拉回六十。那一刻我才真正意识到数据结构不是背给面试官听的它是实实在在影响你App流畅度的东西。Android开发说到底就是在跟数据打交道。从网络请求回来的JSON到本地数据库查出来的Cursor再到UI层要渲染的List中间每一个环节都涉及数据的组织、查找、插入和删除。你选择用什么容器装这些数据直接决定了代码的运行效率、内存占用甚至决定了你的App在低端机上能不能跑得动。这篇文章我打算把Android开发中最常打交道的几种数据结构掰开揉碎讲一遍。不是教科书那种从红黑树旋转讲起的路子而是从实际开发场景出发说清楚每种结构在什么情况下该用、为什么该用、用了之后性能差多少。适合已经会写Android代码但想搞清楚底层原理的朋友也适合准备面试想系统梳理一遍的同学。核心关键词就一个Android基础中的数据结构但我会把它落到真实的业务场景里去。2. 数组与ArrayList最熟悉却也最容易用错的一对2.1 数组在Android里的真实定位数组是最基础的数据结构连续内存、随机访问、长度固定。在Android里数组最典型的应用场景其实是那些长度确定的场景比如自定义View里存放路径点坐标、颜色值数组、矩阵变换的float数组。Matrix类的底层就是9个float组成的数组Canvas.drawBitmap传的矩阵参数也是数组。数组最大的优势是内存连续CPU缓存命中率高。你在做图像处理、音视频解码这类对性能敏感的操作时数组几乎是唯一选择。但它的短板也很明显长度一旦确定就不能改。你声明了int[] arr new int[10]想塞第11个元素就只能重新创建一个更大的数组然后拷贝过去。这里有个很多人忽略的细节数组的length是属性不是方法而ArrayList的size()是方法。面试里经常有人在这上面栽跟头写代码时arr.length()编译都过不了。2.2 ArrayList的扩容机制与性能陷阱ArrayList本质上就是对数组的封装它帮你处理了扩容的问题。默认构造函数创建的是一个空数组当你第一次add元素时才会分配容量默认是10。之后每次容量不够时扩容为原来的1.5倍。这个1.5倍是怎么来的源码里是newCapacity oldCapacity (oldCapacity 1)右移一位相当于除以2所以是1.5倍。为什么是1.5而不是2这是一个空间和时间的折中。扩太大浪费内存扩太小频繁拷贝。1.5倍在大多数场景下是个比较均衡的选择。但这里有个坑如果你事先知道要存多少数据一定要用new ArrayList(expectedSize)指定初始容量。我见过一个项目里有人往ArrayList里塞一万条数据从默认的10开始扩容中间经历了十几次数组拷贝每次拷贝都是O(n)的操作。如果一开始就指定容量这些拷贝全部省掉。// 不推荐默认容量10扩容十几次 ListData list new ArrayList(); for (int i 0; i 10000; i) { list.add(data[i]); } // 推荐一次性分配足够容量 ListData list new ArrayList(10000); for (int i 0; i 10000; i) { list.add(data[i]); }另一个容易踩的坑是在循环里做删除操作。你写for (int i 0; i list.size(); i) { list.remove(i); }结果会发现隔一个删一个。原因是remove之后后面的元素会前移索引i对应的元素已经变了。正确做法是用Iterator或者倒序遍历。2.3 什么时候该放弃ArrayListArrayList的查找是O(1)按索引但按值查找是O(n)插入和删除中间元素也是O(n)。如果你的场景是频繁在头部插入数据比如聊天记录倒序加载那ArrayList就不合适了。每次在索引0插入都要把后面所有元素后移一位。我做过一个消息列表一开始用ArrayList每次收到新消息就list.add(0, msg)消息多了之后明显卡顿。后来换成LinkedList插入变成O(1)问题就解决了。但LinkedList也不是银弹它的随机访问是O(n)如果你既要频繁插入又要频繁按索引读取那可能需要考虑其他方案。3. LinkedList与队列插入删除频繁时的正确选择3.1 LinkedList的双向链表本质LinkedList底层是双向链表每个节点除了存数据还存了前后两个指针。这意味着它的内存开销比ArrayList大因为每个元素都要额外存两个引用。但在插入和删除操作上它只需要改变指针指向不需要移动元素。在Android开发中LinkedList的典型应用场景是实现栈和队列。LinkedList同时实现了Deque接口所以它既可以当栈用push/pop也可以当队列用offer/poll。比如你要做一个撤销重做功能用LinkedList当栈就很合适。// 用LinkedList实现简单的撤销栈 LinkedListAction undoStack new LinkedList(); // 执行操作时入栈 undoStack.push(action); // 撤销时出栈 if (!undoStack.isEmpty()) { Action lastAction undoStack.pop(); lastAction.undo(); }3.2 ArrayDeque为什么比LinkedList更适合做队列虽然LinkedList可以做队列但如果你只是需要队列功能ArrayDeque通常是更好的选择。ArrayDeque底层是循环数组没有LinkedList每个节点的额外对象开销内存更紧凑缓存友好度也更高。我实测过一个场景十万次入队出队操作ArrayDeque比LinkedList快了将近一倍。原因就在于LinkedList每次操作都要创建或销毁Node对象GC压力大。而ArrayDeque只是在数组上移动头尾指针。所以选择策略很清晰如果你需要频繁在中间插入删除用LinkedList如果只是两端操作队列或栈优先ArrayDeque。LinkedList在Android里还有一个隐性成本就是每个Node对象都会增加内存占用在内存紧张的设备上可能触发更频繁的GC。3.3 阻塞队列在Android中的特殊价值Android里有个特殊的场景是生产者消费者模式比如一个线程下载图片另一个线程负责解码显示。这种场景下BlockingQueue就派上用场了。它的put和take方法在队列满或空时会自动阻塞省去了手动写wait/notify的麻烦。LinkedBlockingQueue和ArrayBlockingQueue是最常用的两个实现。前者基于链表容量可选不指定就是Integer.MAX_VALUE后者基于数组必须指定容量。在Android的线程池实现里ThreadPoolExecutor的workQueue参数就是一个BlockingQueue。注意在Android主线程上绝对不要调用BlockingQueue的take方法它会阻塞主线程导致ANR。这类操作必须放在子线程。4. HashMap与HashSet键值对存储的性能密码4.1 HashMap的哈希碰撞与扩容HashMap是Android开发中使用频率最高的数据结构之一没有之一。从缓存图片到存储用户配置到处都有它的身影。它的核心思想是通过哈希函数把key映射到数组的某个位置从而实现O(1)的平均查找时间。但哈希碰撞是不可避免的。两个不同的key可能算出相同的哈希值这就是碰撞。JDK1.8之前HashMap用链表解决碰撞碰撞多了查找就退化成O(n)。JDK1.8之后引入了红黑树当链表长度超过8且数组长度大于等于64时链表会转为红黑树查找复杂度降到O(log n)。Android的HashMap实现和JDK略有不同但核心思想一致。这里要提醒的是作为key的对象必须正确重写hashCode()和equals()方法。我见过有人用自定义对象当key只重写了equals没重写hashCode结果两个相等的对象算出了不同的哈希值存进去就找不回来了。// 正确的key对象写法 public class UserKey { private String userId; private int type; Override public int hashCode() { return Objects.hash(userId, type); } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; UserKey userKey (UserKey) o; return type userKey.type Objects.equals(userId, userKey.userId); } }4.2 初始容量与负载因子怎么定HashMap默认初始容量是16负载因子是0.75。意思是当元素数量超过容量乘以0.75时就会扩容每次扩容为原来的两倍。扩容时需要重新计算所有元素的哈希位置这是一个O(n)的操作。如果你要存1000个元素默认容量16的话会经历多次扩容。正确的做法是预估元素数量除以0.75再加1然后向上取到2的幂次。1000除以0.75约等于1334向上取2的幂次就是2048。所以new HashMap(2048)比默认构造少扩容好几次。// 预估存1000个元素 int expectedSize 1000; int initialCapacity (int) (expectedSize / 0.75f) 1; // 2048是大于1334的最小2的幂次 MapString, Data map new HashMap(2048);负载因子0.75是时间和空间的折中。调高会减少内存但增加碰撞概率调低则相反。大多数场景下不需要改这个值除非你有特殊的性能要求。4.3 SparseArrayAndroid特有的优化容器Android提供了一个专门优化过的容器叫SparseArray它用int作为key避免了Integer的自动装箱。在Android这种内存敏感的环境里自动装箱产生的临时对象会加重GC负担。SparseArray内部用两个数组一个存keyint[]一个存valueObject[]。查找时用二分查找复杂度是O(log n)。虽然比HashMap的O(1)慢但在元素数量不多几百个以内时省去装箱带来的收益更大。类似的还有SparseIntArray、SparseBooleanArray、LongSparseArray等。在Android开发中如果你的key是int或long优先考虑这些容器。我做过一个对比测试存500个int到String的映射SparseArray比HashMap节省了大约30%的内存插入速度也更快。容器key类型查找复杂度内存开销适用场景HashMap任意对象O(1)平均较高装箱Node通用场景SparseArrayintO(log n)低key为int数量1000LongSparseArraylongO(log n)低key为longArrayMap任意对象O(log n)较低数量少频繁遍历ArrayMap是另一个值得关注的容器它比HashMap更省内存适合元素数量少且需要频繁遍历的场景。但它的插入和删除是O(n)因为要移动数组。所以选择哪个容器关键看你的操作模式。5. 树结构在Android中的落地场景5.1 二叉树与递归遍历的实际应用树结构在Android里最典型的应用是View的层级结构。每个ViewGroup包含若干子View子View又可以是ViewGroup天然就是一棵多叉树。当你调用requestLayout时系统会从根View开始递归遍历整棵树测量、布局、绘制。理解树的遍历对自定义View非常重要。比如你要写一个遍历所有子View的方法递归是最自然的实现// 递归遍历View树 private void traverseViewTree(View view) { if (view instanceof ViewGroup) { ViewGroup group (ViewGroup) view; for (int i 0; i group.getChildCount(); i) { View child group.getChildAt(i); // 处理child traverseViewTree(child); } } }但递归有个问题层级太深会栈溢出。Android的View层级官方建议不超过10层除了性能考虑也是为了避免递归深度过大。如果确实需要处理很深的树可以改用迭代加栈的方式。5.2 红黑树与TreeMap的有序特性TreeMap底层是红黑树它保证了key的有序性。在Android里TreeMap的典型应用是需要按key排序的场景比如按时间戳排序的事件队列、按优先级排序的任务列表。红黑树是一种自平衡二叉查找树它通过颜色标记和旋转操作保证树的高度始终在O(log n)级别。这意味着插入、删除、查找都是稳定的O(log n)不会像普通二叉查找树那样在极端情况下退化成链表。// 用TreeMap按时间戳排序存储事件 TreeMapLong, Event eventMap new TreeMap(); // 插入时自动按key排序 eventMap.put(System.currentTimeMillis(), event); // 获取最早的事件 Map.EntryLong, Event earliest eventMap.firstEntry(); // 获取某个时间点之后的所有事件 SortedMapLong, Event laterEvents eventMap.tailMap(timestamp);TreeMap的key必须实现Comparable接口或者在构造时传入Comparator。如果key是自定义对象又没有实现Comparable运行时会抛ClassCastException。5.3 堆与优先队列从图片加载说起堆是一种特殊的完全二叉树分为大顶堆和小顶堆。大顶堆的父节点大于等于子节点小顶堆反之。堆最典型的应用是优先队列PriorityQueue就是基于堆实现的。在Android里优先队列的一个典型场景是图片加载框架的任务调度。比如Glide内部就用优先队列来管理加载任务优先级高的任务先执行。你可以给每个请求设置优先级框架会根据优先级决定先加载哪张图。// 按优先级排序的任务队列 PriorityQueueLoadTask taskQueue new PriorityQueue( (t1, t2) - t2.priority - t1.priority // 优先级高的排前面 ); taskQueue.offer(new LoadTask(url1, Priority.HIGH)); taskQueue.offer(new LoadTask(url2, Priority.LOW)); // 总是取出优先级最高的任务 LoadTask next taskQueue.poll();堆的插入和删除都是O(log n)取最值是O(1)。如果你需要频繁获取最大或最小元素同时又要不断插入新元素优先队列是最合适的选择。6. 数据结构选型中的几个实战判断6.1 从数据量级判断该用什么容器数据量是选型的第一判断依据。我一般按这个标准来分10个以内随便用什么性能差异可以忽略优先考虑代码可读性10到1000考虑内存开销int key用SparseArray对象key用ArrayMap1000以上考虑时间复杂度查找多用HashMap插入删除多用LinkedList10000以上必须仔细评估考虑初始容量、负载因子、是否需要并发容器这个分界不是绝对的但能帮你快速缩小选择范围。比如你要存一个配置项列表可能就十几条那用ArrayList遍历查找完全没问题没必要上HashMap。6.2 并发场景下的容器选择Android开发中子线程和主线程同时访问一个集合是常见场景。如果多个线程同时修改ArrayList会抛ConcurrentModificationException甚至可能导致数据错乱。ConcurrentHashMap是并发场景下的首选。它用分段锁JDK1.7或CASsynchronizedJDK1.8来保证线程安全性能比Collections.synchronizedMap好很多。CopyOnWriteArrayList适合读多写少的场景每次写操作都会复制整个数组写性能差但读性能极好。// 读多写少的场景 CopyOnWriteArrayListListener listeners new CopyOnWriteArrayList(); // 多线程频繁读写的场景 ConcurrentHashMapString, Cache cacheMap new ConcurrentHashMap();注意即使在主线程单线程操作集合如果这个集合会被传到子线程遍历也要考虑并发问题。我踩过一次坑主线程在遍历一个List的同时子线程在往里面add结果偶发崩溃排查了很久才定位到。6.3 内存与性能的权衡取舍数据结构选型本质上是在内存和性能之间做权衡。HashMap快但费内存SparseArray省内存但慢一点。没有绝对的最优解只有最适合当前场景的选择。我的经验是先保证功能正确再考虑性能优化。不要一上来就过度设计用最复杂的结构去解决一个简单问题。等真正遇到性能瓶颈了再用Profiler工具定位针对性地替换数据结构。大多数情况下代码可读性比微小的性能差异更重要。但有几个场景是必须提前考虑的列表页的数据容器、图片缓存、频繁调用的查找逻辑。这些地方的数据结构选型会直接影响用户体验值得在编码前就想清楚。7. 我踩过的那些数据结构相关的坑7.1 在遍历中修改集合的经典错误这个坑我踩过不止一次。写代码时顺手在for-each循环里remove元素运行时报ConcurrentModificationException。原因是for-each底层用的是Iterator而ArrayList的Iterator是fail-fast的检测到集合被修改就抛异常。正确的做法有三种用Iterator的remove方法、用倒序for循环、或者用removeIf方法。我一般推荐removeIf代码最简洁// 错误写法 for (Data data : list) { if (data.isExpired()) { list.remove(data); // 抛异常 } } // 正确写法一Iterator IteratorData it list.iterator(); while (it.hasNext()) { if (it.next().isExpired()) { it.remove(); } } // 正确写法二removeIf list.removeIf(Data::isExpired);7.2 自定义对象作为key的陷阱前面提过hashCode和equals要一起重写这里再强调一个细节如果对象是可变的用它当key会很危险。你存进去之后修改了对象的某个字段哈希值变了再想get就找不到了。我见过一个项目里用Entity对象当HashMap的key后来Entity的某个字段被更新了导致缓存全部失效。正确的做法是用不可变对象当key比如String、Integer或者用对象的唯一ID。7.3 自动装箱带来的性能损耗Android对自动装箱特别敏感因为每次装箱都会创建新对象加重GC负担。HashMapInteger, String在存取时都会自动装箱拆箱而SparseArrayString直接用int省去了这个过程。在循环里做大量装箱操作时这个差异会被放大。我做过一个测试一百万次存取操作SparseArray比HashMap快了大约40%。所以在Android里能用基本类型就用基本类型能用SparseArray就别用HashMap。7.4 初始容量设置不当导致的性能问题前面讲了ArrayList和HashMap的扩容机制这里补充一个实际案例。有个朋友做的一个页面每次打开都要加载几千条数据到ArrayList里页面打开速度很慢。我看了代码发现他用的是默认构造函数扩容了十几次。改成指定初始容量后加载时间从800毫秒降到了500毫秒。这个优化成本极低只需要在创建容器时多写一个参数但收益很明显。养成预估数据量的习惯能避免很多不必要的性能损耗。8. 从源码角度看几个关键实现细节8.1 ArrayList的grow方法到底做了什么ArrayList的扩容逻辑在grow方法里。核心代码是计算新容量然后调用Arrays.copyOf创建新数组并拷贝元素。Arrays.copyOf底层用的是System.arraycopy这是一个native方法比手动for循环拷贝快得多。// ArrayList.grow的简化逻辑 private Object[] grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } return elementData Arrays.copyOf(elementData, newCapacity); }注意这里有个边界处理如果1.5倍还不够就直接用需要的最小容量。这种情况出现在一次性add大量元素时比如addAll一个很大的集合。8.2 HashMap的putVal流程拆解HashMap的put操作看起来简单内部逻辑其实挺复杂。简化后的流程是计算key的哈希值定位到数组下标如果该位置为空就直接放如果不为空就遍历链表或红黑树找到相同的key就覆盖找不到就追加。// HashMap.putVal的简化逻辑 final V putVal(int hash, K key, V value) { NodeK,V[] tab; NodeK,V p; int n, i; if ((tab table) null || (n tab.length) 0) n (tab resize()).length; if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { // 遍历链表或红黑树找到则覆盖找不到则追加 // 链表长度超过8且数组长度64时转红黑树 } if (size threshold) resize(); // 扩容 return null; }这里有个细节(n - 1) hash等价于hash % n但位运算比取模快得多。这就是为什么HashMap的容量必须是2的幂次只有2的幂次减1的二进制才是全1位运算才能正确映射。8.3 SparseArray的二分查找实现SparseArray的查找用的是二分查找因为它的key数组是有序的。每次put新key时会先二分查找确定插入位置然后移动数组插入。这也是为什么SparseArray的插入是O(n)因为要移动元素。// SparseArray的二分查找 private static int binarySearch(int[] array, int size, int value) { int lo 0; int hi size - 1; while (lo hi) { final int mid (lo hi) 1; final int midVal array[mid]; if (midVal value) { lo mid 1; } else if (midVal value) { hi mid - 1; } else { return mid; } } return ~lo; // 没找到时返回插入点的反码 }返回~lo这个技巧很巧妙既表示了没找到又告诉了调用者应该插入到哪个位置。这种设计在源码里很常见值得学习。9. 面试中高频出现的数据结构问题9.1 ArrayList和LinkedList的区别怎么答这个问题几乎每场面试都会问。标准答案是从底层结构、时间复杂度、内存占用三个维度对比。但如果你想答得出彩可以补充实际开发中的选择经验。我的答法是ArrayList基于数组随机访问O(1)中间插入删除O(n)内存连续缓存友好LinkedList基于双向链表随机访问O(n)插入删除O(1)但每个节点有额外指针开销。实际开发中大多数场景用ArrayList就够了因为随机访问比插入删除更常见。只有在频繁在头部插入的场景比如消息列表才会考虑LinkedList。而且如果只是两端操作ArrayDeque比LinkedList更合适。9.2 HashMap的线程安全问题HashMap不是线程安全的多线程同时put可能导致数据丢失甚至死循环JDK1.7的扩容问题。JDK1.8修复了死循环问题但数据丢失仍然存在。解决方案有三个用Collections.synchronizedMap包装、用ConcurrentHashMap、或者自己加锁。推荐用ConcurrentHashMap它的分段锁或CAS机制性能更好。但要注意ConcurrentHashMap的size()方法返回的是近似值不是精确值。9.3 如何用两个栈实现一个队列这是道经典算法题。思路是用一个栈负责入队另一个栈负责出队。入队时直接压入stack1出队时如果stack2为空就把stack1的所有元素依次弹出压入stack2然后从stack2弹出。这样出队的顺序就反过来了实现了先进先出。class QueueWithTwoStacksT { private StackT stack1 new Stack(); // 入队 private StackT stack2 new Stack(); // 出队 public void enqueue(T item) { stack1.push(item); } public T dequeue() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.isEmpty() ? null : stack2.pop(); } }这道题考察的是对栈和队列特性的理解以及能否灵活组合基本结构解决问题。实际开发中当然不会这么用但思路值得掌握。10. 把数据结构用对代码质量会上一个台阶写了这么多核心就一句话数据结构的选择不是学术问题是工程问题。你不需要记住红黑树旋转的每一步但你需要知道什么时候该用TreeMap而不是HashMap什么时候SparseArray比HashMap更合适什么时候该给ArrayList指定初始容量。这些判断力来自实践。我建议你在写代码时多问自己一句这个容器选对了吗数据量大概多少是读多还是写多有没有并发想清楚这几个问题大部分选型错误都能避免。最后分享一个我自己的习惯在Review代码时我会特别关注集合的创建和使用。看到new HashMap()就会想能不能指定容量看到new ArrayList()就会想能不能预估大小看到在循环里做查找就会想能不能换成Map。这些小小的改动累积起来对App性能的提升是实实在在的。数据结构这门基础课值得每个Android开发者反复琢磨。 
长河君 · 2026/10/17 22:31:13 · 阅读 1.2k Android开发必备：数据结构选型与性能优化实战指南
1. 为什么Android开发者绕不开数据结构这道坎刚入行那会儿我总觉得数据结构是面试造火箭、工作拧螺丝的东西。直到有一次做一个列表页数据量刚过两千条滑动就开始明显掉帧排查了半天才发现是每次onBindViewHolder里都在做线性查找。把ArrayList换成HashMap之后帧率直接从四十多拉回六十。那一刻我才真正意识到数据结构不是背给面试官听的它是实实在在影响你App流畅度的东西。Android开发说到底就是在跟数据打交道。从网络请求回来的JSON到本地数据库查出来的Cursor再到UI层要渲染的List中间每一个环节都涉及数据的组织、查找、插入和删除。你选择用什么容器装这些数据直接决定了代码的运行效率、内存占用甚至决定了你的App在低端机上能不能跑得动。这篇文章我打算把Android开发中最常打交道的几种数据结构掰开揉碎讲一遍。不是教科书那种从红黑树旋转讲起的路子而是从实际开发场景出发说清楚每种结构在什么情况下该用、为什么该用、用了之后性能差多少。适合已经会写Android代码但想搞清楚底层原理的朋友也适合准备面试想系统梳理一遍的同学。核心关键词就一个Android基础中的数据结构但我会把它落到真实的业务场景里去。2. 数组与ArrayList最熟悉却也最容易用错的一对2.1 数组在Android里的真实定位数组是最基础的数据结构连续内存、随机访问、长度固定。在Android里数组最典型的应用场景其实是那些长度确定的场景比如自定义View里存放路径点坐标、颜色值数组、矩阵变换的float数组。Matrix类的底层就是9个float组成的数组Canvas.drawBitmap传的矩阵参数也是数组。数组最大的优势是内存连续CPU缓存命中率高。你在做图像处理、音视频解码这类对性能敏感的操作时数组几乎是唯一选择。但它的短板也很明显长度一旦确定就不能改。你声明了int[] arr new int[10]想塞第11个元素就只能重新创建一个更大的数组然后拷贝过去。这里有个很多人忽略的细节数组的length是属性不是方法而ArrayList的size()是方法。面试里经常有人在这上面栽跟头写代码时arr.length()编译都过不了。2.2 ArrayList的扩容机制与性能陷阱ArrayList本质上就是对数组的封装它帮你处理了扩容的问题。默认构造函数创建的是一个空数组当你第一次add元素时才会分配容量默认是10。之后每次容量不够时扩容为原来的1.5倍。这个1.5倍是怎么来的源码里是newCapacity oldCapacity (oldCapacity 1)右移一位相当于除以2所以是1.5倍。为什么是1.5而不是2这是一个空间和时间的折中。扩太大浪费内存扩太小频繁拷贝。1.5倍在大多数场景下是个比较均衡的选择。但这里有个坑如果你事先知道要存多少数据一定要用new ArrayList(expectedSize)指定初始容量。我见过一个项目里有人往ArrayList里塞一万条数据从默认的10开始扩容中间经历了十几次数组拷贝每次拷贝都是O(n)的操作。如果一开始就指定容量这些拷贝全部省掉。// 不推荐默认容量10扩容十几次 ListData list new ArrayList(); for (int i 0; i 10000; i) { list.add(data[i]); } // 推荐一次性分配足够容量 ListData list new ArrayList(10000); for (int i 0; i 10000; i) { list.add(data[i]); }另一个容易踩的坑是在循环里做删除操作。你写for (int i 0; i list.size(); i) { list.remove(i); }结果会发现隔一个删一个。原因是remove之后后面的元素会前移索引i对应的元素已经变了。正确做法是用Iterator或者倒序遍历。2.3 什么时候该放弃ArrayListArrayList的查找是O(1)按索引但按值查找是O(n)插入和删除中间元素也是O(n)。如果你的场景是频繁在头部插入数据比如聊天记录倒序加载那ArrayList就不合适了。每次在索引0插入都要把后面所有元素后移一位。我做过一个消息列表一开始用ArrayList每次收到新消息就list.add(0, msg)消息多了之后明显卡顿。后来换成LinkedList插入变成O(1)问题就解决了。但LinkedList也不是银弹它的随机访问是O(n)如果你既要频繁插入又要频繁按索引读取那可能需要考虑其他方案。3. LinkedList与队列插入删除频繁时的正确选择3.1 LinkedList的双向链表本质LinkedList底层是双向链表每个节点除了存数据还存了前后两个指针。这意味着它的内存开销比ArrayList大因为每个元素都要额外存两个引用。但在插入和删除操作上它只需要改变指针指向不需要移动元素。在Android开发中LinkedList的典型应用场景是实现栈和队列。LinkedList同时实现了Deque接口所以它既可以当栈用push/pop也可以当队列用offer/poll。比如你要做一个撤销重做功能用LinkedList当栈就很合适。// 用LinkedList实现简单的撤销栈 LinkedListAction undoStack new LinkedList(); // 执行操作时入栈 undoStack.push(action); // 撤销时出栈 if (!undoStack.isEmpty()) { Action lastAction undoStack.pop(); lastAction.undo(); }3.2 ArrayDeque为什么比LinkedList更适合做队列虽然LinkedList可以做队列但如果你只是需要队列功能ArrayDeque通常是更好的选择。ArrayDeque底层是循环数组没有LinkedList每个节点的额外对象开销内存更紧凑缓存友好度也更高。我实测过一个场景十万次入队出队操作ArrayDeque比LinkedList快了将近一倍。原因就在于LinkedList每次操作都要创建或销毁Node对象GC压力大。而ArrayDeque只是在数组上移动头尾指针。所以选择策略很清晰如果你需要频繁在中间插入删除用LinkedList如果只是两端操作队列或栈优先ArrayDeque。LinkedList在Android里还有一个隐性成本就是每个Node对象都会增加内存占用在内存紧张的设备上可能触发更频繁的GC。3.3 阻塞队列在Android中的特殊价值Android里有个特殊的场景是生产者消费者模式比如一个线程下载图片另一个线程负责解码显示。这种场景下BlockingQueue就派上用场了。它的put和take方法在队列满或空时会自动阻塞省去了手动写wait/notify的麻烦。LinkedBlockingQueue和ArrayBlockingQueue是最常用的两个实现。前者基于链表容量可选不指定就是Integer.MAX_VALUE后者基于数组必须指定容量。在Android的线程池实现里ThreadPoolExecutor的workQueue参数就是一个BlockingQueue。注意在Android主线程上绝对不要调用BlockingQueue的take方法它会阻塞主线程导致ANR。这类操作必须放在子线程。4. HashMap与HashSet键值对存储的性能密码4.1 HashMap的哈希碰撞与扩容HashMap是Android开发中使用频率最高的数据结构之一没有之一。从缓存图片到存储用户配置到处都有它的身影。它的核心思想是通过哈希函数把key映射到数组的某个位置从而实现O(1)的平均查找时间。但哈希碰撞是不可避免的。两个不同的key可能算出相同的哈希值这就是碰撞。JDK1.8之前HashMap用链表解决碰撞碰撞多了查找就退化成O(n)。JDK1.8之后引入了红黑树当链表长度超过8且数组长度大于等于64时链表会转为红黑树查找复杂度降到O(log n)。Android的HashMap实现和JDK略有不同但核心思想一致。这里要提醒的是作为key的对象必须正确重写hashCode()和equals()方法。我见过有人用自定义对象当key只重写了equals没重写hashCode结果两个相等的对象算出了不同的哈希值存进去就找不回来了。// 正确的key对象写法 public class UserKey { private String userId; private int type; Override public int hashCode() { return Objects.hash(userId, type); } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; UserKey userKey (UserKey) o; return type userKey.type Objects.equals(userId, userKey.userId); } }4.2 初始容量与负载因子怎么定HashMap默认初始容量是16负载因子是0.75。意思是当元素数量超过容量乘以0.75时就会扩容每次扩容为原来的两倍。扩容时需要重新计算所有元素的哈希位置这是一个O(n)的操作。如果你要存1000个元素默认容量16的话会经历多次扩容。正确的做法是预估元素数量除以0.75再加1然后向上取到2的幂次。1000除以0.75约等于1334向上取2的幂次就是2048。所以new HashMap(2048)比默认构造少扩容好几次。// 预估存1000个元素 int expectedSize 1000; int initialCapacity (int) (expectedSize / 0.75f) 1; // 2048是大于1334的最小2的幂次 MapString, Data map new HashMap(2048);负载因子0.75是时间和空间的折中。调高会减少内存但增加碰撞概率调低则相反。大多数场景下不需要改这个值除非你有特殊的性能要求。4.3 SparseArrayAndroid特有的优化容器Android提供了一个专门优化过的容器叫SparseArray它用int作为key避免了Integer的自动装箱。在Android这种内存敏感的环境里自动装箱产生的临时对象会加重GC负担。SparseArray内部用两个数组一个存keyint[]一个存valueObject[]。查找时用二分查找复杂度是O(log n)。虽然比HashMap的O(1)慢但在元素数量不多几百个以内时省去装箱带来的收益更大。类似的还有SparseIntArray、SparseBooleanArray、LongSparseArray等。在Android开发中如果你的key是int或long优先考虑这些容器。我做过一个对比测试存500个int到String的映射SparseArray比HashMap节省了大约30%的内存插入速度也更快。容器key类型查找复杂度内存开销适用场景HashMap任意对象O(1)平均较高装箱Node通用场景SparseArrayintO(log n)低key为int数量1000LongSparseArraylongO(log n)低key为longArrayMap任意对象O(log n)较低数量少频繁遍历ArrayMap是另一个值得关注的容器它比HashMap更省内存适合元素数量少且需要频繁遍历的场景。但它的插入和删除是O(n)因为要移动数组。所以选择哪个容器关键看你的操作模式。5. 树结构在Android中的落地场景5.1 二叉树与递归遍历的实际应用树结构在Android里最典型的应用是View的层级结构。每个ViewGroup包含若干子View子View又可以是ViewGroup天然就是一棵多叉树。当你调用requestLayout时系统会从根View开始递归遍历整棵树测量、布局、绘制。理解树的遍历对自定义View非常重要。比如你要写一个遍历所有子View的方法递归是最自然的实现// 递归遍历View树 private void traverseViewTree(View view) { if (view instanceof ViewGroup) { ViewGroup group (ViewGroup) view; for (int i 0; i group.getChildCount(); i) { View child group.getChildAt(i); // 处理child traverseViewTree(child); } } }但递归有个问题层级太深会栈溢出。Android的View层级官方建议不超过10层除了性能考虑也是为了避免递归深度过大。如果确实需要处理很深的树可以改用迭代加栈的方式。5.2 红黑树与TreeMap的有序特性TreeMap底层是红黑树它保证了key的有序性。在Android里TreeMap的典型应用是需要按key排序的场景比如按时间戳排序的事件队列、按优先级排序的任务列表。红黑树是一种自平衡二叉查找树它通过颜色标记和旋转操作保证树的高度始终在O(log n)级别。这意味着插入、删除、查找都是稳定的O(log n)不会像普通二叉查找树那样在极端情况下退化成链表。// 用TreeMap按时间戳排序存储事件 TreeMapLong, Event eventMap new TreeMap(); // 插入时自动按key排序 eventMap.put(System.currentTimeMillis(), event); // 获取最早的事件 Map.EntryLong, Event earliest eventMap.firstEntry(); // 获取某个时间点之后的所有事件 SortedMapLong, Event laterEvents eventMap.tailMap(timestamp);TreeMap的key必须实现Comparable接口或者在构造时传入Comparator。如果key是自定义对象又没有实现Comparable运行时会抛ClassCastException。5.3 堆与优先队列从图片加载说起堆是一种特殊的完全二叉树分为大顶堆和小顶堆。大顶堆的父节点大于等于子节点小顶堆反之。堆最典型的应用是优先队列PriorityQueue就是基于堆实现的。在Android里优先队列的一个典型场景是图片加载框架的任务调度。比如Glide内部就用优先队列来管理加载任务优先级高的任务先执行。你可以给每个请求设置优先级框架会根据优先级决定先加载哪张图。// 按优先级排序的任务队列 PriorityQueueLoadTask taskQueue new PriorityQueue( (t1, t2) - t2.priority - t1.priority // 优先级高的排前面 ); taskQueue.offer(new LoadTask(url1, Priority.HIGH)); taskQueue.offer(new LoadTask(url2, Priority.LOW)); // 总是取出优先级最高的任务 LoadTask next taskQueue.poll();堆的插入和删除都是O(log n)取最值是O(1)。如果你需要频繁获取最大或最小元素同时又要不断插入新元素优先队列是最合适的选择。6. 数据结构选型中的几个实战判断6.1 从数据量级判断该用什么容器数据量是选型的第一判断依据。我一般按这个标准来分10个以内随便用什么性能差异可以忽略优先考虑代码可读性10到1000考虑内存开销int key用SparseArray对象key用ArrayMap1000以上考虑时间复杂度查找多用HashMap插入删除多用LinkedList10000以上必须仔细评估考虑初始容量、负载因子、是否需要并发容器这个分界不是绝对的但能帮你快速缩小选择范围。比如你要存一个配置项列表可能就十几条那用ArrayList遍历查找完全没问题没必要上HashMap。6.2 并发场景下的容器选择Android开发中子线程和主线程同时访问一个集合是常见场景。如果多个线程同时修改ArrayList会抛ConcurrentModificationException甚至可能导致数据错乱。ConcurrentHashMap是并发场景下的首选。它用分段锁JDK1.7或CASsynchronizedJDK1.8来保证线程安全性能比Collections.synchronizedMap好很多。CopyOnWriteArrayList适合读多写少的场景每次写操作都会复制整个数组写性能差但读性能极好。// 读多写少的场景 CopyOnWriteArrayListListener listeners new CopyOnWriteArrayList(); // 多线程频繁读写的场景 ConcurrentHashMapString, Cache cacheMap new ConcurrentHashMap();注意即使在主线程单线程操作集合如果这个集合会被传到子线程遍历也要考虑并发问题。我踩过一次坑主线程在遍历一个List的同时子线程在往里面add结果偶发崩溃排查了很久才定位到。6.3 内存与性能的权衡取舍数据结构选型本质上是在内存和性能之间做权衡。HashMap快但费内存SparseArray省内存但慢一点。没有绝对的最优解只有最适合当前场景的选择。我的经验是先保证功能正确再考虑性能优化。不要一上来就过度设计用最复杂的结构去解决一个简单问题。等真正遇到性能瓶颈了再用Profiler工具定位针对性地替换数据结构。大多数情况下代码可读性比微小的性能差异更重要。但有几个场景是必须提前考虑的列表页的数据容器、图片缓存、频繁调用的查找逻辑。这些地方的数据结构选型会直接影响用户体验值得在编码前就想清楚。7. 我踩过的那些数据结构相关的坑7.1 在遍历中修改集合的经典错误这个坑我踩过不止一次。写代码时顺手在for-each循环里remove元素运行时报ConcurrentModificationException。原因是for-each底层用的是Iterator而ArrayList的Iterator是fail-fast的检测到集合被修改就抛异常。正确的做法有三种用Iterator的remove方法、用倒序for循环、或者用removeIf方法。我一般推荐removeIf代码最简洁// 错误写法 for (Data data : list) { if (data.isExpired()) { list.remove(data); // 抛异常 } } // 正确写法一Iterator IteratorData it list.iterator(); while (it.hasNext()) { if (it.next().isExpired()) { it.remove(); } } // 正确写法二removeIf list.removeIf(Data::isExpired);7.2 自定义对象作为key的陷阱前面提过hashCode和equals要一起重写这里再强调一个细节如果对象是可变的用它当key会很危险。你存进去之后修改了对象的某个字段哈希值变了再想get就找不到了。我见过一个项目里用Entity对象当HashMap的key后来Entity的某个字段被更新了导致缓存全部失效。正确的做法是用不可变对象当key比如String、Integer或者用对象的唯一ID。7.3 自动装箱带来的性能损耗Android对自动装箱特别敏感因为每次装箱都会创建新对象加重GC负担。HashMapInteger, String在存取时都会自动装箱拆箱而SparseArrayString直接用int省去了这个过程。在循环里做大量装箱操作时这个差异会被放大。我做过一个测试一百万次存取操作SparseArray比HashMap快了大约40%。所以在Android里能用基本类型就用基本类型能用SparseArray就别用HashMap。7.4 初始容量设置不当导致的性能问题前面讲了ArrayList和HashMap的扩容机制这里补充一个实际案例。有个朋友做的一个页面每次打开都要加载几千条数据到ArrayList里页面打开速度很慢。我看了代码发现他用的是默认构造函数扩容了十几次。改成指定初始容量后加载时间从800毫秒降到了500毫秒。这个优化成本极低只需要在创建容器时多写一个参数但收益很明显。养成预估数据量的习惯能避免很多不必要的性能损耗。8. 从源码角度看几个关键实现细节8.1 ArrayList的grow方法到底做了什么ArrayList的扩容逻辑在grow方法里。核心代码是计算新容量然后调用Arrays.copyOf创建新数组并拷贝元素。Arrays.copyOf底层用的是System.arraycopy这是一个native方法比手动for循环拷贝快得多。// ArrayList.grow的简化逻辑 private Object[] grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } return elementData Arrays.copyOf(elementData, newCapacity); }注意这里有个边界处理如果1.5倍还不够就直接用需要的最小容量。这种情况出现在一次性add大量元素时比如addAll一个很大的集合。8.2 HashMap的putVal流程拆解HashMap的put操作看起来简单内部逻辑其实挺复杂。简化后的流程是计算key的哈希值定位到数组下标如果该位置为空就直接放如果不为空就遍历链表或红黑树找到相同的key就覆盖找不到就追加。// HashMap.putVal的简化逻辑 final V putVal(int hash, K key, V value) { NodeK,V[] tab; NodeK,V p; int n, i; if ((tab table) null || (n tab.length) 0) n (tab resize()).length; if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { // 遍历链表或红黑树找到则覆盖找不到则追加 // 链表长度超过8且数组长度64时转红黑树 } if (size threshold) resize(); // 扩容 return null; }这里有个细节(n - 1) hash等价于hash % n但位运算比取模快得多。这就是为什么HashMap的容量必须是2的幂次只有2的幂次减1的二进制才是全1位运算才能正确映射。8.3 SparseArray的二分查找实现SparseArray的查找用的是二分查找因为它的key数组是有序的。每次put新key时会先二分查找确定插入位置然后移动数组插入。这也是为什么SparseArray的插入是O(n)因为要移动元素。// SparseArray的二分查找 private static int binarySearch(int[] array, int size, int value) { int lo 0; int hi size - 1; while (lo hi) { final int mid (lo hi) 1; final int midVal array[mid]; if (midVal value) { lo mid 1; } else if (midVal value) { hi mid - 1; } else { return mid; } } return ~lo; // 没找到时返回插入点的反码 }返回~lo这个技巧很巧妙既表示了没找到又告诉了调用者应该插入到哪个位置。这种设计在源码里很常见值得学习。9. 面试中高频出现的数据结构问题9.1 ArrayList和LinkedList的区别怎么答这个问题几乎每场面试都会问。标准答案是从底层结构、时间复杂度、内存占用三个维度对比。但如果你想答得出彩可以补充实际开发中的选择经验。我的答法是ArrayList基于数组随机访问O(1)中间插入删除O(n)内存连续缓存友好LinkedList基于双向链表随机访问O(n)插入删除O(1)但每个节点有额外指针开销。实际开发中大多数场景用ArrayList就够了因为随机访问比插入删除更常见。只有在频繁在头部插入的场景比如消息列表才会考虑LinkedList。而且如果只是两端操作ArrayDeque比LinkedList更合适。9.2 HashMap的线程安全问题HashMap不是线程安全的多线程同时put可能导致数据丢失甚至死循环JDK1.7的扩容问题。JDK1.8修复了死循环问题但数据丢失仍然存在。解决方案有三个用Collections.synchronizedMap包装、用ConcurrentHashMap、或者自己加锁。推荐用ConcurrentHashMap它的分段锁或CAS机制性能更好。但要注意ConcurrentHashMap的size()方法返回的是近似值不是精确值。9.3 如何用两个栈实现一个队列这是道经典算法题。思路是用一个栈负责入队另一个栈负责出队。入队时直接压入stack1出队时如果stack2为空就把stack1的所有元素依次弹出压入stack2然后从stack2弹出。这样出队的顺序就反过来了实现了先进先出。class QueueWithTwoStacksT { private StackT stack1 new Stack(); // 入队 private StackT stack2 new Stack(); // 出队 public void enqueue(T item) { stack1.push(item); } public T dequeue() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.isEmpty() ? null : stack2.pop(); } }这道题考察的是对栈和队列特性的理解以及能否灵活组合基本结构解决问题。实际开发中当然不会这么用但思路值得掌握。10. 把数据结构用对代码质量会上一个台阶写了这么多核心就一句话数据结构的选择不是学术问题是工程问题。你不需要记住红黑树旋转的每一步但你需要知道什么时候该用TreeMap而不是HashMap什么时候SparseArray比HashMap更合适什么时候该给ArrayList指定初始容量。这些判断力来自实践。我建议你在写代码时多问自己一句这个容器选对了吗数据量大概多少是读多还是写多有没有并发想清楚这几个问题大部分选型错误都能避免。最后分享一个我自己的习惯在Review代码时我会特别关注集合的创建和使用。看到new HashMap()就会想能不能指定容量看到new ArrayList()就会想能不能预估大小看到在循环里做查找就会想能不能换成Map。这些小小的改动累积起来对App性能的提升是实实在在的。数据结构这门基础课值得每个Android开发者反复琢磨。