2016.7.29
| List | 顺序 |
|---|---|
| ArrayList | 插入顺序 |
| LinkedList | 插入顺序 |
ArrayList
ArrayList底层是数组实现，查询上是线性的，有索引可循，而LinkedList是链表，每一个元素是一个节点，迭代下一个元素是寻址，查询比ArrayList慢，数据更新也要先查询到位置所有也是ArrayList较优
末尾（附近）添加元素比LinkedList快很多（1E6次循环时18:901）
数据查询和数据更新较优
LinkedList
LinkedList底层是链表，插入和删除数据只需要改变链接的指向就行，而ArrayList则需将新数据或被删数据后的所有数据全部后移或前移
在开头添加元素比ArrayList快很多（1E5次循环时6:4484）
在元素中存放下一个元素的位置指向，寻址较慢
在开头（附近）和末尾插入元素很快，开头是因为改变链接的指向就行，遍历的次数也少，末尾是因为有一个last专门存放末尾元素，直接末尾的链接指向新元素，在将新元素设为last即可。
数据插入数据删除较优
| Set | 顺序 |
|---|---|
| HashSet | 无序 |
| LinkedHashSet | 插入顺序 |
| TreeSet | 自然顺序 |
HashSet
HasSet根据对象的hashCode值来决定该对象在HashSet中存储位置。
哈希表是通过使用称为散列法的机制来存储数据的，元素并没有以某种特定顺序来存放。
对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层采用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
HashSet有5个构造函数，4个调用了HashMap的构造函数，1个调用了LinkedHashMap构造函数。
LinkedHashSet
LinkedHashSet继承HashSet
LinkedHashSet同样根据对象的hashCode值来决定该对象在HashSet中存储位置，但它同时使用链表维护元素的次序。
这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。
有4个构造函数，全部调用了HashSet那个使用了LinkedHashMap的构造函数
TreeSet
提供一个使用树结构存储Set接口的实现，对象以升序顺序存储，访问和遍历的时间很快。
TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。
TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。
向TreeSet中加入的应该是同一个类的对象。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。
obj1.compareTo(obj2)方法如果返回0，则说明被比较的两个对象相等，如果返回一个正数，则表明obj1大于obj2，如果是 负数，则表明obj1小于obj2。
如果我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0。
定制排序
自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法。
| Map | 顺序 |
|---|---|
| HashMap | 无序 |
| LinkedHashMap | 插入顺序 |
| TreeMap | 自然顺序 |
HashMap
插入时平均。
HashMap提供了三个构造函数：
HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认初始容量为16，负载因子为0.75，一般情况下我们是无需修改的。
当插入数据超过（初始容量*加载因子）时，会自动调用resize()扩容，将容量扩大一倍。
若你一开始就知道了大概的数据量，建议直接定义初始容量为你所知道的数据量。不然插入数据一旦达到限度，自动扩容又要申请新的存储空间，还要把之前的数据全部copy一遍，浪费时间也浪费空间。
LinkedHashMap
遍历是平均最快，插入键值对量巨大时平均速度最快。
继承HashMap，也是使用链表维护元素的次序。
是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
TreeMap
插入键值对量巨大时平均速度最慢，因为排序要花很长的时间。
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
