Android中的数据结构

什么是数据结构？

简单说就是以某种方式把一堆数据组织起来。通常不同的组织方式会有不同的特性。Java中常见的数据结构有：数组、链表、List、Map等等。

为什么会有这么多数据结构？

不同的数据结构形式通常都有各自的使用场景。比如常见的ArrayList。使用ArrayList你可以方便添加和移除数据。但如果看过ArrayList源码的话会知道ArrayList底层还是使用数组。那为什么还要用ArrayList？严格来说Java最底层提供的数据结构方式只有基本类型、引用类型和数组。其他任何类型都是由这些基本的数据结构封装起来的，或者说其他任何Java数据结构，一层层往下拆最终都会变成这几个。比如ArrayList就是从数组封装过来的。那问题来了，数组能做到，那为什么还要用ArrayList？主要是因为ArrayList进行增删改查使用起来非常方便，但数组处理起来就要复杂多了。所以把这些常用的需求封装起来就出现了ArrayList。

List

大家在使用List的时候可能通常都会写下面这样的代码

List<String> list = new ArrayList<>();

Java中List是个接口，所以需要用它的实现类来实例化。那当你写下上面代码的时候有没有思考过一个问题，为什么要用ArrayList。Java里有没有其他的List实现类？当然有。AndroidStudio或者Intelij Idea可以找到List实现类，然后通过Ctrl+H看到所有的继承自List的类和接口。你可能会看到非常多，但比较常用的主要就是ArrayList，LinkedList和Vector。这三个都是List实现类。有没有想过一个问题，如果你需要用到List了，那么究竟应该用什么哪个类？就比如你写了一个RecyclerView的Adapter。有Adapter就一定会需要有个数据源。这时候应该选哪个实现类？其实明白这三者区别就很容易选了。

• ArrayList内部实现是个数组、有序存储。数组大家都知道长度不可变，那么append数据消耗可能会比较大，因为可能会需要resize，如果是insert或者remove数据消耗就会比较大，因为需要数组拷贝。但是get速度非常快，因为可以直接找到对应位置。

    private static List<String> add0(String[] array) {
        List<String> list = new ArrayList<>();
        for (String s : array) {
            list.add(s);
        }
        return list;
    }
    private static List<String> add1(String[] array) {
        List<String> list = new ArrayList<>();
        list.addAll(Arrays.asList(array));
        return list;
    }

    private static void remove0(List<String> list, int index, int count) {
        for (int i = 0; i < count; i++) {
            list.remove(index + i);
        }
    }

    private static void remove1(List<String> list, int index, int count) {
        list.subList(index, index + count).clear();
    }

add0和add1哪个写法好？remove0和remove1哪个写法好？add0一个个把数据add到ArrayList，最多ArrayList可能会发生array.length次数组resize。但是add1就最多只会发生一次数组resize。remove0和remove1也是一样。

• LinkedList 看名字就知道这是一个链表实现的List，内部不再有数组。那么对于链表来说添加数据就是打开链条，接上链条，再锁上链条的过程。如果是频发插入数据，比如数据从1条连续插入到10万条，效率可以认为是一样。但是要get数据就比较坑了，通过index并不能直接定位到数据，所以就需要遍历数据了。remove数据也一样，只要任何是设计到index的操作效率都会比较低，除了头和尾，因为LinkedList针对头尾做了缓存。
• Vector 平时见的会非常少，它内部实现也是用数组，但跟ArrayList不同的是它是线程安全的，你会发现它方法有synchronized关键字。除了这点其他特性可以认为是等同于ArrayList。

好，又回到前面老问题，RecyclerView的Adapter应该用什么数据结构？我们思考下Adapter的应用场景。通常Adapter不会非常频繁的添加数据，每次滑过RecyclerView都会触发onBindViewHolder，要bind就一定需要从数据源通过index取数据出来，取操作会比较频繁，那我们肯定不能用LinkedList了（但其实考虑到RecyclerView显示数据都是连续的，所以如果用链表来访问临近数据效率反而会更高），又因为Adapter基本上不会出现要去子线程操作数据源的情况。所以也不需要线程安全。剩下的就当然是ArrayList了，而且ArrayList取效率本来就非常高，完全符合需求。

Map

Map是一个键值对数据结构。Map的实现类也非常多，但主要是：HashMap、LinkedHashMap，TreeMap，HashTable，Android里又加了ArrayMap和SparseArray。Map跟List不一样的是不光能存数据了，还能额外多保存一个key。那有个问题，假如我新建一个下面这样的Data类。然后把所有键值对通过Data对象保存到List里，那我不是一样实现了键值对保存吗？

   public class Data<K,V>{
        private K mKey;
        private V mValue;

        public Data(K key, V value) {
            mKey = key;
            mValue = value;
        }

        public K getKey() {
            return mKey;
        }

        public void setKey(K key) {
            mKey = key;
        }

        public V getValue() {
            return mValue;
        }

        public void setValue(V value) {
            mValue = value;
        }
    }

那我为什么要用各种Map实现类呢？还是同样的问题，虽然功能上确实能实现但是效率上不同的实现方式差别会非常大。

• HashMap
  大家写Map可能绝大部分情况下都是使用HashMap。HashMap底层是通过数组加链表（Java1.8新加了红黑树）来实现。为什么要搞这么复杂呢？又是数组又是链表又是树的？其实还是为了提高效率。上面的把键值对封装成Data，加到List中。get效率跟HashMap比就会非常惨了。因为get只能一个个去遍历，但是HashMap就可以通过key的hashcode非常高效的get数据。
• LinkedHashMap
  看名字就知道多了个Linked，意思就是排序。LinkedHashMap本身就是继承自HashMap，所以增删改查方面和HashMap基本是一致的。区别主要就是通过entrySet遍历了。LinkedHashMap会保存元素的添加顺序然后按顺序遍历，但HashMap就是无序了。
• TreeMap
  TreeMap内部是个红黑树。从使用角度来看，它跟LinkedHashMap主要区别就LinkedHashMap保存的是元素的插入顺序，而TreeMap则是对key排序。遍历可以得到一个按key排序的结果。
• HashTable
  内部是个链表，另外就是线程同步。
• SparseArray
  SparseArray内部依然是使用数组来实现。但是限制了key只能int，而且没有装箱，HashMap的key只能是Integer。所以Sparse性能会更好，它内部做了数据压缩，来稀疏数组的数据，节省内存。
• ArrayMap
  ArrayMap内部也是使用数组。查找数据会通过二分法来提高效率，Google推荐用ArrayMap来代替HashMap。