[转] Java中的容器

在书写程序的时候，我们常常需要对大量的对象引用进行管理。为了实现有效的归类管理，我们常常将同类的引用放置在同一数据容器中。

由于数据容器中存放了我们随时可能需要使用到的对象引用，所以一般的数据容器要都要能能提供方便的查询、遍历、修改等基本接口功能。

早期的OOP语言都通过数组的方式来实现对引用集的集中管理和维护。

但是数组方式下，数组大小需要提前被确定，并不允许修改大小，导致其作为一种灵活的数据容器的能力的功能大为下降。

为了方便的利用数据容器进行引用的管理,Java中提供了丰富的数据容器以满足程序员多样化的需求。

JAVA的容器---List,Map,Set
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

！其中的Vector和Stack类现在已经极少使用。

从容器类图中可以发现，数据容器主要分为了两类：

Collection: 存放独立元素的序列。

Map：存放key-value型的元素对。（这对于一些需要利用key查找value的程序十分的重要！）

从类体系图中可以看出，Collection定义了Collection类型数据的最基本、最共性的功能接口，而List对该接口进行了拓展。

其中各个类的适用场景有很大的差别，在使用时，应该根据需要灵活的进行选择。此处介绍最为常用的四个容器：

LinkedList ：其数据结构采用的是链表，此种结构的优势是删除和添加的效率很高，但随机访问元素时效率较ArrayList类低。

ArrayList：其数据结构采用的是线性表，此种结构的优势是访问和查询十分方便，但添加和删除的时候效率很低。

HashSet: Set类不允许其中存在重复的元素（集），无法添加一个重复的元素（Set中已经存在）。HashSet利用Hash函数进行了查询效率上的优化，其contain（）方法经常被使用，以用于判断相关元素是否已经被添加过。

HashMap: 提供了key-value的键值对数据存储机制，可以十分方便的通过键值查找相应的元素，而且通过Hash散列机制，查找十分的方便。

该类图的理解，对于灵活的使用相应的数据容器十分的重要。

根据Oracle公司的官方文档：

1、Collection是对Iterable接口的拓展。故所有的Collection对象都可以使用foreach方式，对元素进行方便的遍历。

由于Iterable接口中定义了的唯一方法为：返回一个Iterator对象，故所有的Collection都可以用 对象名.iterator()的方式获取该collection的迭代器iterator对象（结合工厂方法和内部类的思想来理解，其作用十分大）

2、Map中提供了产生Collection的方法，以支持方便的对键值对的值域进行操作。

Collection<V> values()   Returns:a collection view of the values contained in this map.

从JAVA提供的数据容器来看，可以清晰的认识到面向对象的思想在类的架构设计中的重要性。

灵活的使用好各类容器类，以最大限度的提升程序的性能。由于类型过多，大多的基础操作都被抽象到了Collection中，熟练并利用好Collection提供的接口，已经可以解决大量的问题（即使是Map，其也提供了产生Collection对象的机制）。

Example:

public class TestContainer {
Collection<String> testList= new ArrayList<String>(Arrays.asList("i love you".split(" ")));
Map<Integer, String> testMap=new HashMap<Integer, String>();

TestContainer()
{
testMap.put(1, "I");
testMap.put(2, "love");
testMap.put(3, "you");


print(testMap);
print(testList);

print("Using Iterable Interface");
for(String str:testList)
{
print(str);
}

print("Geting the values collection of a Map");
Collection<String> mapValues= testMap.values();
for(String str:mapValues)
{
print(str);
}

print("Geting the Iterator of a collection");
Iterator i=mapValues.iterator();
while(i.hasNext())
{
print(i.next());
}
}
}

以上的例子中，TestContainer的实例会有连个数据成员：

1、ArrayList<String> testList

2、Map<Integer, String> testMap

为了对ArrayList进行遍历，此例中直接将ArrayList向上转型为了Collection类型（结合类图），并利用foreach遍历方式对其中的成员进行了遍历。

为了对Map中的value域进行访问，此处调用了Collection<String> mapValues= testMap.values(); ，使用Map的values（）方法返回了其value成员的Collection对象。

于是可以像操纵其它Collection一样，对该集合进行操作！

容器是用来保存多个对象的东西.严格来说是保存对象的引用.因为对象实际的数据是放在另外的地方的.放在容器中的只是指向那块内存区域的一个标识.

JAVA中内置了数组.数组和其它容器的区别主要有三个:效率,类型,和存放基本类型的能力.JAVA中的数组是一种效率最高的存储和随机访问对象引用序列的方式.它就是一个简单的线性序列,所以访问是非常快.但它也损失了其他的特性.当创建一个数组时,它的长度就被固定了.通常是创建一个固定大小的数组,在空间不足时,再创建一个大的数组,然后把旧数组中的所有引用移到新数组中.

这种机制被JAVA中的另一个容器:ArrayList采用.所以,ArrayList的效率要比数组低.JAVA中还有一些其他的容器:List,Set(每个对象只保存一份),Map(允许将一个对象和另一对象关联存储).它们都是针对Object来处理的.而Object是JAVA中所有类的基类,所以说这些容器可以存放所有JAVA类.注意:基本类型如:boolean char byte short long float double void..不继承Object,所以这些容器不能存放这些.如果要存进去必须用JAVA为这些类提供的包装类它们对应的包装类是: Boolean Character Byte Short Integer Long Float Double Void

容器的元素：

插入的是引用，需要new 一个对象放到容器中，而不要修改一个对象放进去。

import java.util.*;
 
public class TestArrayList{
      public static void main(String args[]){
            List<String> li=new ArrayList<String>();
            String s="hello";
            li.add(s);
            s="world";
            li.add(s);
            for(int i=0;i<li.size();i++){
                  System.out.println(li.get(i));
            }
      }
}

s指向的内容改变，容器里面保存的是引用，为什么不跟着改变？怎么输出还是“hello”、“world”？
为什么不是“world”、“world”？

第一次加的是"hello"对象的引用
第二次加的是“world”对象的引用，和变量s的名字无关

容器的选择:

容器实际上只有三种:Map , List, Set;但每种接口都有不同的实现版本.它们的区别可以归纳为由什么在背后支持它们.也就是说,你使用的接口是由什么样的数据结构实现的.

List的选择:

比如:ArrayList和LinkedList都实现了List接口.因此无论选择哪一个,基本操作都一样.但ArrayList是由数组提供底层支持.而LinkedList是由双向链表实现的.所以,如果要经常向List里插入或删除数据,LinkedList会比较好.否则应该用速度更快的 ArrayList.

Set的选择

HashSet总是比TreeSet 性能要好.而后者存在的理由就是它可以维持元素的排序状态.所以,如果需要一个排好序的Set时,才应该用TreeSet

Map选择:

同上,尽量选择HashMap,只要需要排好序的确Map时才用Treemap;

容器API：

　　1、Collection接口------定义了存储一组对象的方法，其子接口Set和List分别定义了存储的方式。

　　　　①、Set中的数据对象没有顺序且不可以重复。

　　　　②、List中的数据对象有顺序且可以重复。

　　2、Map接口定义了存储“键（key）---值（value）映射对”的方法。

Collection接口：

　　Collection接口中定义的方法（意思就是只要你实现了Collection接口，你将拥有下面所有方法）：

Collection方法举例：

这里要说明的就是集合里面只能装引用类型的数据。

import java.util.*;
public class TestCollection{
    public static void main (String args[]){
        Collection collection = new ArrayList();
        //可以放入不同类型的对象
        collection.add("hello");
        collection.add(new Person("f1",18));
        collection.add(new Integer(100));
        System.out.println(collection.size());
        System.out.println(collection);
    }
}
class Person{
    private String name; 
    private int age;
    public Person(String name,int age){
        this.name = name;
        this.age = age;
    }
}

接下来，我们继续使用上面的例子，说说Collection里面remove（）方法的使用：

import java.util.*;
public class TestCollection{
    public static void main (String args[]){
        Collection collection = new HashSet();
        //可以放入不同类型的对象
        collection.add("hello");
        collection.add(new Person("f1",18));
        collection.add(new Integer(100));
        
        collection.remove("hello");
        collection.remove(new Integer(100));
        
        System.out.println(collection.remove(new Person("f1",18)));
        System.out.println(collection);
    }
}
class Person{
    private String name; 
    private int age;
    public Person(String name,int age){    
        this.name = name;
        this.age = age;
    }
    public String getName(){
        return name;
    }
    public int getAge(){
        return age;
    }
    /*public boolean equals(Object obj){
        if(obj instanceof Person){
            Person person = (Person)obj;
            return (name.equals(person.name) && age == person.age);
        }
        return super.equals(obj);
    }
    public int hashCode(){
        return name.hashCode();
    }*/
}

执行上面的例子，你会发现我们插入的数据”hello“和new Integer(100)都可以用remove()方法直接删除，但是对于new person("f1",18)这对象可以用remove（）方法直接删除吗？答案是不可以的....

容器类对象在调用remove、contains等方法时需要比较对象是否相等，这会涉及到对象类型的equals方法和hashCode方法；对于自定义的类型，需要重写equals方法和hashCode方法以实现自定义对象相等规则。

　　注意，相等的对象应该具有相等的hash Codes

Ieterator接口（简单说：Iterator就是一个统一的遍历我们集合中所有元素的方法）

　　1、所有实现了Collection接口的容器类都有一个iterator方法用以返回一个实现了Iterator接口的对象。

　　2、Iterator对象称作迭代器，用以方便的实现对容器元素的遍历实现。

　　3、Iterator实现了下列方法：

下面我们写一个用Iterator遍历集合元素的方法。（注：程序运行信息输出顺序可能跟我们输入的顺序不一致，这就是Set集合无序的效果）

import java.util.*;
public class TestCollection{
    public static void main (String args[]){
        Collection collection = new HashSet();
        
        collection.add(new Person("zhang",1));
        collection.add(new Person("gao",2));
        collection.add(new Person("wang",3));
        collection.add(new Person("du",4));
        collection.add(new Person("liang",5));
        collection.add(new Person("li",6));
        
        Iterator iterator = collection.iterator();
        while(iterator.hasNext()){
            //next()的返回值类型是Object类型，需要转换为相应类型
            Person person = (Person)iterator.next();
            System.out.println(person.name);
        }
    }
}
class Person{
    public String name; 
    private int age;
    public Person(String name,int age){    
        this.name = name;
        this.age = age;
    }
    public String getName(){
        return name;
    }
    public int getAge(){
        return age;
    }
}

Set接口

　　1、Set接口是Collection的子接口，Set接口没有提供的额外方法，但实现Set接口的容器类中的元素是没有顺序的，而且不可以重复

　　2、Set接口可以与数学中”集合“的概念相对应。

　　3、J2SDK　API中所提供的容器类有HashSet、TreeSet等...

Set方法举例：

List接口：

　　1、List接口是Collection的子接口，实现List接口的容器类中元素是有顺序的，而且可以重复。

　　2、List容器中元素都对应一个整数型的序号记载其在内容中的位置，可以根据序号存取容器中的元素。

　　3、L2SDK所提供的List容器类有ArrayList，LinkedList等...

List 方法举例：

　　List常用算法：

List常用算法举例：