Android 开发中 常见的数据结构有哪些？

数组

ArrayList

ArrayList 基于动态数组实现，提供了一个基于数组的，动态增长的列表。由于基于数组实现，查增删改时间复杂度为下

• get O(1): 基于数组实现，可以通过索引直接访问元素
• add 平均复杂度为O(1), 多数情况下，插入元素到ArrayList末尾是常数时间，但在需要扩容的情况下，需要O（n）的大小
• remove 平均情况为O（n）, 需要对元素和后续元素向前移动，最坏要移动整个数组的元素
• set O(1), 可以直接通过索引修改数组元素的值

优点：

• 查询修改都是O（1），适用于查询和修改较多，数据较大时删除元素操作较少的情况

缺点：

• 大量数据时且需要频繁插入和删除，删除和插入需要对数组进行复制，会影响性能，可以使用LinkedList代替

LinkedList

LinkedList 是Java的双链表实现，每个元素都包含前一个和后一个元素的引用，可以高效的在列表中进行插入和删除操作。

• get O(n), 必须从链表头部或尾部开始遍历，直到找到目标位置
• add O(1), 平均情况下只需要更新前后节点的引用
• remove O(1), 平均情况下只需要更新前后节点的引用
• set O(n), 需要先查询，再修改，复杂度为O(n)

优点：

• 对插入和删除操作有较好的性能

缺点：

• 查询和修改都需要遍历列表

HashMap

Java中哈希表集合实现，用于存储键值对，常用于快速查找和存储键值对数据

• get 平均情况下为 O(1), 理想情况下，哈希算法时没有冲突的，可以通过hash值，直接找到对应的桶，极端情况下，hash值都会冲突，导致退化到O（n）（单链表实现）或者 O（logn）红黑树实现。
• put 平均 O（1）, 理想情况下，没有冲突直接插入，在冲突的情况下，复杂度为O（n）, 为链表长度或树的高度
• remove 平均 O（1）, 理想情况下，没有冲突直接插入，在冲突的情况下，复杂度为O（n）, 为链表长度或树的高度

HashMap并不是线程安全的，有线程安全的考虑时，可以使用，Hashtable ConcurrentHashMap CopyOnWriteHashMap

HashSet

HastSet 基于 HashMap实现，不存储重复元素，HashSet 通过调用元素的hashCode()方法获取hash码，用于确定元素在哈希表中的位置，随后对数据取模，保证落在数组索引范围内。

SparseArray

SparseArray 是Android 提供的一种优化的数组映射结构，适用于存储稀疏数据，及大多数数据都是默认值。

• get O（logn）, 使用二分查找，且索引数组有序，适用于二分查找
• put O (logn), 插入操作需要维护索引数组有序性
• remove O（logn）, 需要先查找，再删除
• set O (logn), 同样需要查找和删除

什么是稀疏数据？

• 稀疏数据是指大部分元素具有默认值（通常为零或空），而只有一小部分元素具有非默认值。

适用场景：

• ListView 或 RecyclerView中存储列表项的状态，其中大多数列表项可能处于默认状态

ArrayDeque

ArrayDeque 是Java中双端队列的实现，基于数组，并提供了高效的头部和尾部操作。

• addLast, offerLast, addFirst offerFirst, remove 和 getLast都是O（1）的时间复杂度

优点：

• ArrayDeque 提供了在两端高效（常数级别）执行添加，移除和获取操作的能力。
• 基于数组实现，相较于链表的实现，随机访问元素性能更好

缺点：

• 非线程安全的
• 无法在中间插入或删除元素

LinkedHashMap

LinkedHashMap 保留了元素的插入顺序，并提供快速查找的操作，使用哈希表存储键值对，同时使用一个双向链表维护插入顺序或访问顺序，具体取决于构造函数的参数。

• put 平均O(1), 默认末尾添加，在开头或中间添加，需要找到插入位置，最坏为O（n）
• remove O(1),哈希表和HashMap操作一样，链表删除为O（n）
• get O(1)

优点：

• 提供顺序值，在缓存等场景适用，比如LRU缓存

缺点：

• 需要维护一个链表结构，内存开销稍大

TreeMap

TreeMap 是 Java 中的一种基于红黑树（Red-Black Tree）实现的有序映射（SortedMap）。它实现了 NavigableMap 接口，因此提供了有序的键值对集合。

特性

• 有序，TreeMap可以按照键的顺序进行遍历
• 使用红黑树，插入，删除和查找时间复杂度都是O（logn）
• 键是唯一的， 必须实现Comparable
• 子映射和范围查询，允许获取子映射（submap）或进行范围查询

缺点：

• 大数据量时性能略低

CopyOnWirteXXX

基于读写锁

ConcurrentHashMap等

基于细粒度的segment，细粒度的读写访问，适用于数据量很大的时候