如何优化基于ArrayList的时间线Activity数据操作时间复杂度？

我注意到你已经完成了一个基于RecyclerView的时间线Activity，用Firebase搭配RxJava从数据库拉取用户状态数据，适配器里用ArrayList来存储所有状态对象，通过状态UID执行增、删、改操作。目前遇到的问题很典型：插入操作因为是直接往列表末尾追加，时间复杂度是O(1)，但删除和更新得遍历整个列表找对应UID的对象，时间复杂度变成了O(n)，数据量到几千条的时候就会出现明显的性能瓶颈。

针对这个问题，我给你几个实用的优化方向：

• 改用键值对存储替代ArrayList：把ArrayList换成HashMap或者LinkedHashMap，用状态UID作为key，状态对象作为value。这样不管是增、删还是改操作，都能直接通过UID定位到目标对象，时间复杂度直接降到O(1)，彻底解决遍历带来的性能问题。
  • 如果需要保持时间线的展示顺序，推荐用LinkedHashMap——它能维持元素的插入顺序，刚好匹配时间线按发布顺序展示的需求；要是需要按时间戳排序，那可以额外维护一个有序的List<String>来保存UID的排序结果，刷新RecyclerView时，遍历这个有序UID列表，从HashMap里取出对应对象组成数据源即可。
• 结合RxJava和Firebase做数据映射：在从Firebase拉取数据的RxJava流里，直接把数据转换成HashMap的结构，这样每次数据库有实时更新时，你只需要更新HashMap里的对应项，再根据有序UID列表生成新的数据源通知适配器就行，不用再处理ArrayList的遍历逻辑。
• 配合RecyclerView局部更新：找到目标对象在有序列表里的位置后，调用notifyItemChanged(int position)、notifyItemRemoved(int position)这类局部更新方法，而不是全量刷新的notifyDataSetChanged()，进一步减少RecyclerView的重绘开销，让性能提升更明显。

其实几千条数据的情况下，HashMap的额外内存占用完全在移动端的承受范围内，和它带来的性能提升比起来，这点开销完全值得。

内容的提问来源于stack exchange，提问作者Mattwalk