Java 从集合框架来的暗杀者

前言

　　　　集合框架就是提供一个存放东西的对象或叫容器，再说易懂一点就像是个数据库，提供了对数据的增删改查等功能，Java对集合框架有非常好的支持。都放在java.util里面，核心接口有Collection、Set、List、Map、SortedMap、SortedSet等，常用实现类有ArrayList、HashMap、HashSet等。

List

①

基本介绍：

　　　List接口是Collection的一个子接口，中文名可叫"列表"或"清单"，它的顺序和长度是固定的。数组结构和链表结构都是列表的一种特殊形式。

②

常用实现类：

　　ArrayList：它是一个基于数组的结构，里面的节点相互之间没有特别的联系，默认的大小是10，最大大小Integer.MAX_VALUE - 8。当大小不够时会自动增长，它可以通过get，set来直接获取、修改某一个节点数据。

　　 LinkedList:它是一个基于双向链表的结构，每一个节点都有两个指针来分别指向上一个节点和下一个节点。它是可变长度的。

　　这两个实现类的区别在于，ArrayList的get()/set()效率比LinkedList高，而LinkedList的add()/remove()效率比ArrayList高。

　　具体来说：数组申请一块连续的内存空间，是在编译期间就确定大小的，运行时期不可动态改变，但为什么ArrayList可以改变大小呢，因为在add如果超过了设定的大小就会创建一个新的更大的（增长率好像是0.5）ArrayList，然后将原来的list复制到新的list中，并将地址指向新的list，旧的list被GC回收，显然这是非常消耗内存而且效率非常低的。但是由于它申请的内存空间是连续的，可以直接通过下标来获取需要的数据，时间复杂度为O(1)，而链表则是O(n)，

　　而链表结构不一样，它可以动态申请内存空间。在需要加入的节点的上一个节点的指针解开并指向新加节点，再将新加节点的指针指向后一个节点即可。速度很快的。

　　　所以说ArrayList适合查询，LinkedList适合增删。

③

其他：

　　对List排序可以通过辅助工具Collections.sort()来完成，但是要注意对list里面对象的compare方法进行重写。下面是一个Java8下的引用例子。

package com.vogella.java.collections.list;import java.util.ArrayList;import java.util.List;public class ListSorter { public static void main(String[] args) {  System.out.println("Sorting with natural order");  List<String> l1 = createList();  l1.sort(null);  l1.forEach(System.out::println);    System.out.println("Sorting with a lamba expression for the comparison");  List<String> l2 = createList();  l2.sort((s1, s2) -> s1.compareToIgnoreCase(s2)); // sort ignoring case  l2.forEach(System.out::println);    System.out.println("Sorting with a method references");  List<String> l3 = createList();  l3.sort(String::compareToIgnoreCase);    l3.forEach(System.out::println);      }  private static List<String> createList() {  List<String> list = new ArrayList<>();  list.add("iPhone");  list.add("Ubuntu");  list.add("Android");  list.add("Mac OS X");  return list; }}

　　　　顺便介绍一下Collections这个类，相信大家做java基础面试题的时候碰到过collection和collections区别的问题，那么现在应该了解了，它们一个是集合框架的上层接口，List和set都是它的子接口，一个是集合框架的辅助类，除排序外，Collections还提供很多其他方法，比如copy(list,list)将一个list拷贝到另外一个list（注意这里和list = list）不一样，前者是在堆里有两个list，虽然内容是一样的，而后者在堆中只有一个list，只是栈中有两个引用指向它。还有reverse(list)，显然是将list反向，还有shuffle(list)打乱list的顺序，以及其他很多，所以很多时候需要对list的数据进行操作的时候，不要急着自己抓头挠腮地实现，先去Collections找找有没有已经写好的方法。

Set

①

基本介绍:

　　Set也是Collection的一个子接口。中文名可叫"集合"，学过高中数学的都知道，集合是数学上的概念，它有三个特性

　　确定性：集合中每一个元素都是确定的。

　　无序性：集合中的每个元素的位置都是任意的。

　　互异性：集合中每一个元素都不相同。｛1，a｝那么a就不能等于1；

　　那么在计算机领域，或者高级语言里面的集合也是拥有这三种特性。在Java里面就是Set。

　　确定性：就不用解释了。（最多有一个null值）

　　无序性：说明刚才的那个Collections.sort()对set无效，也从侧面说明了list顺序的重要性。

　　互异性：Set接口只继承了Collection的方法，并添加了互异约束，在Set中，是通过equals来判断元素是否相同的，这就要求Set的元素的equals和hashcode两个方法非常重要，有一点要清楚，如果两个set里面的元素是一样的，那么这两个set实例就是相同的。

    Set<String> stringSet = new HashSet<>();    stringSet.add("aaa");    stringSet.add("bbb");    stringSet.add("ccc");    stringSet.add("ddd");    stringSet.add("eee");    Set<String> stringSet1 = new TreeSet<>();    stringSet1.add("aaa");    stringSet1.add("bbb");    stringSet1.add("ccc");    stringSet1.add("ddd");    stringSet1.add("eee");    System.out.println(stringSet.equals(stringSet1));  
　　　　 /////
　　　　 Output>>true

②

常用实现类：

　　HashSet：它是一个非常优秀的Set实现类，是基于哈希表存储的，但它不保证返回的Iterator（迭代器）的顺序。

　　TreeSet：它是一个基于红黑树存储的，它将Set元素根据值来排序，效率相比HashSet慢了不少。

　　LinkedHashSet：它也是一个基于哈希表存储的，但是加上了一个链表，来保存它的元素插入顺序，也就是说循环输出它时，会根据插入的顺序来输出。那么显然的，为了达到这个效果，也是通过牺牲比较大的效率来实现的。

Map

①

基本介绍

　　map就是许多键值对的集合，因为它的原理和集合的数据结构不太一样，所有它不是继承自Collection，而且Map就是最高层接口。map的key不允许重复，而且每个key最多对应一个值。（值得注意的是Map接口取代了老版本的Dictionary抽象类）。Map提供了三个集合来遍历map，分别是keySet()、values()、entrySet()，要注意视图和元素集合副本的不同，前者的效率要高很多。

②

常用实现类

　　HashMap：*

　　TreeMap：*

　　LinkedHashMap：*

　　可以看到这几个Map和上面的Set几个常用类是一样的，为什么？其实在于Map的key其实就是就是用set来实现的，用什么类型的set，就是什么类型的map。那么map的顺序也就和上面的set一样。