三、容器分类学

    容器内类系之间的关系可以通过简化的类系图表示：

    对于Collection,Map,List,Set的功能说明，就在这里进行说明，更为具体可以参看JDK的api文档 。我只在这里列出一些经典的用法。 

    List的功能，通常我们都用List的add()方法加入队象，用get()取对象和用iterator()方法获取这个序列的Iterator对象。有两种List：擅长对元素随机访问的、较常用的ArrayList，以及一个功能更为强大的LinkedList，由于它不是为随机访问设计的，所以用LinkedList做随机访问速度比较慢，但是它却有一些通用的方法。下面就是用LinkedList做了一个栈，“栈”也被称为“后进先出”（LIFO）容器，最后一个压入栈的东西，会第一个弹出来。用LinkedList可以直接实现栈的功能。下面这个类就通过使用LinkedList实现了栈的功能。

package test;
import java.util.*;

public class StackL {
    private LinkedList ll = new LinkedList();
    //将对象压入栈
    public void push(Object ob){
        ll.addFirst(ob);
    }
    //栈顶元素
    public Object top(){
        return ll.getFirst();
    }
    //栈顶元素弹出栈
    public Object pop(){
        return ll.removeFirst();
    }
    public static void main(String[] args){
        StackL sl = new StackL();
        //将integer对象压入栈中
        for(int i=0;i<10;i++)
            sl.push(new Integer(i));
        //列出栈顶对象
        System.out.println((Integer)sl.top());
        //将栈顶对象弹出
        System.out.println((Integer)sl.pop());
        //再次列出栈顶的对象
        System.out.println((Integer)sl.top());
    }
}

    用LinkedList还可以做一个队列（queue），队列是一个先进先出（FIFO）的容器。也就是说你从一端将东西放进去，从另一端将东西取出来。LinkedList有支持对列的功能方法，所以可以当作对列来用。

package test;
import java.util.*;

public class Queue {
    private LinkedList ll = new LinkedList();
    //在队列当中放入对象
    public void put(Object ob){
         ll.addFirst(ob);
    }
    //先被放入队列的对象被取出来
    public Object get(){
        return ll.removeLast();
    }
    //判断对列是否为空
    public boolean isEmpty(){
        return ll.isEmpty();
    }
    public static void main(String[] args) {
        Queue qe = new Queue();
        for(int i=0;i<10;i++)
            //在队列中放入对象
            qe.put(new Integer(i));
        //通过判断队列是否为空,输出对列中的对象
        while(!qe.isEmpty())
            System.out.println((Integer)qe.get());
    }
}

    Set的功能，Set的接口和Collection是一样的，实际上Set就是一个Collection，只不过行为方式不一样。 

    对于Set来说有一点需要特别注意：Set拒绝持有多个具有相同值的对象的实例。（对象的值由什么来决定的呢？）让我们带着这个问题继续下去。写自己定义的类的时候一定要注意，Set要有一个标准来判断以什么样的顺序将对象放到Set中区，也就是说你必须实现Comparable接口，并且定义了CompareTo()方法。当你把对象放入Set（无论是那种Set）的时候,都需要定义equals()方法，只有将对象放入HashSet的时候，才需要定义hashCode()，HashSet用了“专为快速查找设计的散列函数”，但是作为一种编程的风格，最好将equals()和hashCode()都覆写了。这里还有提到Set的另一个接口SortedSet,它下面只有一个实现TreeSet,使用 SortedSet shs = new TreeSet();SortedSet里面的元素是有序的，这使得SortedSet接口多了些有用的方法，例如：SortedSort.headSet(toElement),返回Set子集，其中的元素小于toElement。 

    SortedSort.tailSet(fromElement) 返回Set子集，其中的元素大于或等于fromElement。 

    Map的功能，ArrayList能让你将数字和对象关联起来，通过数字你可以在一个序列里进行选择。但是如果我们想根据其他条件在序列里选择呢？比如说我要根据一个对象来选取另一个对象，不用急，java里提供了专门的容器Map来支持。Java的标准类库里有好几Map:HashMap,TreeMap,LinkedHashMap等，他们都实现了Map的基本接口，但是在行为方式方面存在明显的差异，这些差异表现在效率，持有对象和表示对象pair顺序以及如何决定键的相等性方面。比如LinkedHashMap,它很像HashMap,但是在使用Iterator遍历的时候，它会按照插入的顺序或最近最少使用（least-recently-used order）的顺序输出对象, 这样还没有被访问过的对象就会排在最前边,利用这个特性写一个定时清理的程序会很简单。而查找对象则是HashMap的强项，因为它采用了一种被称为hash code的特殊值来查找， HashMap就是通过hash code进行查找，这样性能就大幅的提高了。 

    那么散列算法和产生的Hash数究竟是什么样的呢？它们之间有存在什么关系呢？下面为您揭开Hash数的神秘面纱。 

    散列（hash）是一种算法，它会从目标对象中提取一些信息，然后生成一个表示这个对象的相对独立的int值，hashCode()是Object根类的方法，因此所有的java对象都能生成hash code。一般情况下，我们在使用自己写的类作Map的键时，如果我们没有覆写Object根类的hashCode()方法，那么它就会使用Object根类的hashCode()方法，而产生的Hash数就是对象的内存地址，在这样的情况下，我们自己写的Person类。

public class Person {
 protected String idCard;
 public Person(String sidCard){
     idCard = sidCard;
 }
 public String toString(){
   return "Persion's idcard is "+ idCard;
 }
}

    注意：Person(“139898988967664788”)和另一个实例Person(“139898988967664788”)却是不相等的。 

    这样我们使用同一个类的不同实例来查找，也不会找到Map的键值的。因为我们没有覆写hashCode()方法，注意:在覆写键类的hashCode()方法的同时，也应该将equlas()覆写了，HashMap要用equals()来判断查询的键是不是与表里的其他值相等。一个合适的equals()必须做到以下几点：

1.自反性：对任何x,x.equals(x)返回的值一定为true;

2.对称性：对任何x、y,当且仅当y.equals(x)为true时，x.equals(y)也一定为true;

3.传递性：对任何x、y、z,当x.equals(y)为true,且y.equals(z)为true时，x.equals(z)也为true;

4.一致性：对任何x、y，如果用于equals()方法比较的对象的信息没有被修改，那么调用多少次x.equals(y)都会一致返回true或false;

5.非空性：对于任何非空的x,那么x.equals(null)一定是false; 

    默认的Object.equals()只是简单比较两个对象的地址，所以在使用自己写的类作HashMap的键的话，你就必须把hashCode()和equals()都给覆写了。讲到这里我们还不知道散列数据结构是怎么运行的？散列可以帮你把键存到某个你能很快找到的地方。正如前面所说的数组是最快的数据结构，所以散列也用数组表示键的信息（注：是键的信息，而不是键本身）。 

    此外，数组一经分配就不能调整大小了，而Map要能存储任意数量的Pair，键的数量不是受到数组大小的限制了吗？答案就是，不用数组来存储键本身，键对象会生成一个数字，我们要用这个数字（这就是所谓得hash数，它是由对象的hashCode()散列函数生成的。）作为下标来访问数组，而解决定长数组的问题就得允许许多键生成同一个hash数，也就是说会有不同的键对象产生冲突。这样数组的大小就无关紧要了，每个键对象都会落到数组的某个位置上。而散列解决冲突的办法是通过“外部链”，数组并不是直接指向对象，而是指向一个对象的列表，然后再用equals方法在这个对象列表中一个一个的找。这一步是比较慢的，但是如果你得散列函数定义的好，一个以这个hash数作为下标的数组成员对应的对象列表，只包含几个对象。这也是散列数据结构为什么这么快的原因。 

    上面我们说了散列数据结构的原理，不用我再说什么大家都会影响HashMap散列性能的因素,不过这里介绍几个术语： 

    Capacity:hash表里bucket的数量。 

    Initial Capacity:创建hash表时，bucket的数量。HashMap和HashSet都要让你指定Initial Capacity的构造函数。 

    Size：当前hash表记录的数量。 

    Load factor:当Load factor达到某个设定的阙值后，容器会自动将Capacity扩大大约一倍，然后将现有对象的分配到新的bucket中去。HashMap和HashSet都要让你指定Load factor的构造函数。默认的情况下HashMap的Load factor为0.75。 

    因此，我们在自己写的类中覆写hashCode（）方法时候，就应该注意了，首先，你控制的不是在bucket数组里进行检索的值，这个值是随散列数据结构（如：HashMap）的Capacity，Size，Load factor变化而变化的。hashCode()返回的值还要做进一步处理才能得到bucket数组的下标。要想让hashCode()充分发挥作用，它必须既快还有意义，也就是说必须根据其内容生成值，由于hashCode()返回的值还要做进一步处理，所以它的取值范围并不重要；只要是int就可以了。java的牛人Joshua Block给出了hash数一个好的算式：

hash值= 37*result+c;

    result是一个非零的常量，如17。对于每个重要的数据成员f(equals()要用得所有数据成员)，分别计算其int型的hash值C。