体系图

我们先来看下

再来看下集合框架体系图

Collection是最基本的集合接口

List

List比较常用的有ArrayList和LinkedList，还有一个比较类似的Vector。

1、ArrayList

内部是使用动态数组来实现的，对于数据的随机get和set或是少量数据的插入或删除，效率会比较高。ArrayList是线程不安全的，在不考虑线程安全的情况下速度也比较快的。ArrayList插入数据可以重复，也是有序的，按照插入的顺序来排序。

2、LinkedList

内部是使用链表的形式来实现的,在插入大量数据的时候效率比较快。 查询数据使用二分查找法。

3、Vector

Vector的使用方法和内部实现基本和ArrayList相同，只不过它在add(), remove(), get()等方法中都加了同步。所以它是线程安全的。但是使用效率上就不如ArrayList了。

Set

一般使用的有TreeSet和HashSet。

1、TreeSet

TreeSet是根据二叉树实现的，也就是TreeMap, 放入数据不能重复且不能为null,可以重写compareTo()方法来确定元素大小，从而进行升序排序。

public class DataType {    public static void main(String[] args){        Set
    
      treeSet = new TreeSet<>(new MyComparator());        treeSet.add(1);        treeSet.add(3);        treeSet.add(2);        for(Integer i : treeSet){            System.out.println(i);     //执行结果是： 1  2  3         }    }    static class MyComparator implements Comparator
     
      {        @Override        public int compare(Integer o1, Integer o2) {            if(o1 < o2 ){                return -1;            }            if(o1 == o2 ){                return 0;            }            if(o1 > o2 ){                return 1;            }            return 0;        }    }}
     
    

2、HashSet

HashSet是根据hashCode来决定存储位置的，是通过HashMap实现的，所以对象必须实现hashCode()方法，存储的数据无序不能重复，可以存储null,但是只能存一个。

public class DataType {    public static void main(String[] args){        Set
    
      set = new HashSet<>();        set.add("1");        set.add("2");        set.add(null);        set.add("1");        for(String s : set){            System.out.println(s);  //运算结果  null   1    2        }    }}
    

Map

1、HashMap

Map
    
      hashMap = new HashMap<>();        hashMap.put("1", "a");//存储        hashMap.put("2", "b");        hashMap.remove("1");//根据key来删除        hashMap.get("2");//根据key获取        //map的遍历,有很多方法遍历,这里只列举一种。        for(Map.Entry
     
       entry : hashMap.entrySet()){            entry.getKey();//获取key            entry.getValue();//获取value        }
     
    

HashMap是基于散列链表来实现的，简单的来说，根据key算出一个hash值，确定一个存放index,但是hash值有可能会冲突重复，所以如果冲突的hash值就需要以链表的形式在同一个index存放了。

2.TreeMap

TreeMap的使用大致跟HashMap类似，但是内部实现是根据红黑树来实现的。红黑树是一种平衡有序的二叉树，TreeMap的插入删除查询都是依据红黑树的规则来进行的。

3.Hashtable

先说下，HashMap和TreeMap都是线程不安全的，多线程操作的时候可能会造成数据错误。Hashtable是线程安全的。其他内部实现，与HashMap都是一样的。

对比 Vector、ArrayList和LinkedList

大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以：

如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List；

如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList；

如果在多线程条件下使用，可以考虑Vector；

对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

高效数据结构

在java2ee或者android中常用的数据结构有Map,List,Set，但android作为移动平台，也推出了更符合自己的api，比如SparseArray、ArrayMap用来代替HashMap在有些情况下能带来更好的性能提升。

>SparseArray

SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间。同时，SparseArray在存储和读取数据时候，使用的是二分查找法。

常用api

• public void put(int key, E value) ； //添加数据
• public void remove(int key)； or public void delete(int key) ； //删除数据。(remove内部还是通过调用delete来删除数据的)
• public E get(int key) ; or public E get(int key, E valueIfKeyNotFound); //获取数据。(后者可设置如果key不存在的情况下默认返回的value)
• public int keyAt(int index) ；//获取对应的key
• public E valueAt(int index) ; //获取对应的value：

SparseArray应用场景：

虽说SparseArray性能比较好，但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。

满足下面两个条件我们可以使用SparseArray代替HashMap：

• 数据量不大，最好在千级以内
• key必须为int类型，这中情况下的HashMap可以用SparseArray代替：

替换原则：

1> HashMap<Integer, Object> map = new HashMap<>();

用SparseArray代替: SparseArray<Object> array = new SparseArray<>();

2>如果用到了：HashMap<Integer, Boolean> hashMap = new HashMap<Integer, Boolean>

可以替换为：SparseBooleanArray array = new SparseBooleanArray();

3>如果用到了：HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>

可以替换为：SparseIntArray array = new SparseIntArray();

>ArrayMap

ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。

常用api

• public V put(K key, V value)
• public V get(Object key)
• public V remove(Object key)
• public K keyAt(int index)
• public V valueAt(int index)

ArrayMap应用场景

• 数据量不大，最好在千级以内
• 数据结构类型为Map类型

ArrayMap<Key, Value> arrayMap = new ArrayMap<>();

【注】：如果我们要兼容aip19以下版本的话，那么导入的包需要为v4包

import android.support.v4.util.ArrayMap;

总结

SparseArray和ArrayMap都差不多，使用哪个呢？

假设数据量都在千级以内的情况下：

1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用

2、如果key类型为其它的类型，则使用ArrayMap

参考链接：