企业官网建设流程全解析

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，扩容十几次 List<Data> list = new ArrayList<>(); for (int i = 0; i < 10000; i++) { list.add(data[i]); } // 推荐：一次性分配足够容量 List<Data> 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 什么时候该放弃ArrayList

ArrayList的查找是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实现简单的撤销栈 LinkedList<Action> 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的幂次 Map<String, Data> map = new HashMap<>(2048);

负载因子0.75是时间和空间的折中。调高会减少内存但增加碰撞概率，调低则相反。大多数场景下不需要改这个值，除非你有特殊的性能要求。

4.3 SparseArray：Android特有的优化容器

Android提供了一个专门优化过的容器叫SparseArray，它用int作为key，避免了Integer的自动装箱。在Android这种内存敏感的环境里，自动装箱产生的临时对象会加重GC负担。

SparseArray内部用两个数组，一个存key（int[]），一个存value（Object[]）。查找时用二分查找，复杂度是O(log n)。虽然比HashMap的O(1)慢，但在元素数量不多（几百个以内）时，省去装箱带来的收益更大。

类似的还有SparseIntArray、SparseBooleanArray、LongSparseArray等。在Android开发中，如果你的key是int或long，优先考虑这些容器。我做过一个对比测试，存500个int到String的映射，SparseArray比HashMap节省了大约30%的内存，插入速度也更快。

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按时间戳排序存储事件 TreeMap<Long, Event> eventMap = new TreeMap<>(); // 插入时自动按key排序 eventMap.put(System.currentTimeMillis(), event); // 获取最早的事件 Map.Entry<Long, Event> earliest = eventMap.firstEntry(); // 获取某个时间点之后的所有事件 SortedMap<Long, Event> laterEvents = eventMap.tailMap(timestamp);

TreeMap的key必须实现Comparable接口，或者在构造时传入Comparator。如果key是自定义对象又没有实现Comparable，运行时会抛ClassCastException。

5.3 堆与优先队列：从图片加载说起

堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。大顶堆的父节点大于等于子节点，小顶堆反之。堆最典型的应用是优先队列，PriorityQueue就是基于堆实现的。

在Android里，优先队列的一个典型场景是图片加载框架的任务调度。比如Glide内部就用优先队列来管理加载任务，优先级高的任务先执行。你可以给每个请求设置优先级，框架会根据优先级决定先加载哪张图。

// 按优先级排序的任务队列 PriorityQueue<LoadTask> 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用ArrayMap
• 1000以上：考虑时间复杂度，查找多用HashMap，插入删除多用LinkedList
• 10000以上：必须仔细评估，考虑初始容量、负载因子、是否需要并发容器

这个分界不是绝对的，但能帮你快速缩小选择范围。比如你要存一个配置项列表，可能就十几条，那用ArrayList遍历查找完全没问题，没必要上HashMap。

6.2 并发场景下的容器选择

Android开发中，子线程和主线程同时访问一个集合是常见场景。如果多个线程同时修改ArrayList，会抛ConcurrentModificationException，甚至可能导致数据错乱。

ConcurrentHashMap是并发场景下的首选。它用分段锁（JDK1.7）或CAS+synchronized（JDK1.8）来保证线程安全，性能比Collections.synchronizedMap好很多。CopyOnWriteArrayList适合读多写少的场景，每次写操作都会复制整个数组，写性能差但读性能极好。

// 读多写少的场景 CopyOnWriteArrayList<Listener> listeners = new CopyOnWriteArrayList<>(); // 多线程频繁读写的场景 ConcurrentHashMap<String, 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 Iterator<Data> 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负担。HashMap<Integer, String>在存取时都会自动装箱拆箱，而SparseArray<String>直接用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) { Node<K,V>[] tab; Node<K,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 QueueWithTwoStacks<T> { private Stack<T> stack1 = new Stack<>(); // 入队 private Stack<T> 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开发者反复琢磨。