容器深入

Java编程

高级语言中的容器实在是个很神奇的东西，有必要深入了解下。感觉Java虚拟机有必要找时间仔细看看。

容器的填充

容器的填充仍然像java.util.Arrays一样面临同样的不足。Collections类的fill()方法也只是复制同一个对象引用来填充整个容器的。

class StringAddress{
    private String s;
    public StringAddress(String s){this.s=s;}
    public String toString(){
        return super.toString()+" "+s;
    }
}
public class FillingLists{
    public static void main(Stringp[] args){
        List<StringAddress> list=new ArrayList<StringAddress>(Collections.nCopies(4,new StringAddress("Hello")));
        System.out.println(list);
        Collections.fill(list,new StringAddress("World!"));
        System.out.println(list);
    }
}

这个示例展示了两种用对单个对象的引用来填充Collection的方式，第一种是使用Collections.nCopies()创建传递给构造器的List,这里填充的是ArrayList。fill()方法的用处更有限，因为它只能替换已经在List中存在的元素，而不能添加新的元素。

事实上，所有的Collection子类型都有接收另一个Collection对象的构造器，用所接收的Collection对象中的元素来填充新的容器。构建接收Generator和quantity数值并将它们作为构造器参数的类:

public class CollectionData<T>extends ArrayList<T>{
    public CollectionData(Generator<T> gen,int quantity){
        for(int i=0;i<quantity;i++)
            add(gen.next());
    }
    public static <T> CollectionsData<T> list(Generator<T> gen,int quantity){
        return  new CollectionData<T>(gen,quantity);
    }
}

Map生成器

我们可以对Map也使用Generator的解决方法。但是这需要有一个Pari类，因为为了组装Map，每次调用Generator。

Collection的功能方法

Set和存储顺序

Set需要一种方式来维护存储顺序，而存储顺序如何维护，则是在Set的不同实现之间会有所变化。因此，不同的Set实现不仅具有不同的行为,而且它们对于可以在特定的Set中放置的元素的类型也有不同的要求:

Set(interface) 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保护维护元素的次序
HashSet* 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()
TreeSet 保持次序的Set,底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口
LinkedHashSet 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。元素也必须定义hashCode()方法

使用特定的Set实现类型必须定义的方法:

class SetType{
    int i;
    public SetType(int n){i=n;}
    public boolean equals(Object o){
        return o instanceof SetType&&(i==((SetType)o).i);
    }
    public String toString(){return Integer.toString(i);}
}
class HashType extends SetType{
    public HashType(int n){super(n);}
    public int hashCode(){return i;}
}
class TreeType extends SetType implements Comparable<TreeType>{
    public TreeType(int n){super(n);}
    public int compareTo(TreeType arg){
        return (arg.i<i?-1:(arg.i==i?0:1));
    }
}
public class TypeForSets{
    static<T> Set<T> fill(Set<T> set,Class<T> type){
        try{
            for(int i=0;i<10;i++){
                set.add(type.getConstructor(int.class).newInstance(i));
                }
        }catch(Exception e){
            throw new RuntimeException(e);
        }
        return set;
    }
    static <T> void test(Set<T> set,Class<T> type){
        fill(set,type);
        fill(set,type);
        fill(set,type);
        System.out.println(set);
    }
    public static void main(String[] args){
        test(new HashSet<HashType>(),HashType.class);
        test(new LinkedHashSet<HashType>(),HashType.class);
        test(new TreeSet<TreeType>(),TreeType.class);
        test(new HashSet<SetType>(),SetType.class);
        test(new HashSet<TreeType>(),TreeType.class);
        test(new LinkedHashSet<SetType>(),SetType.class);
        test(new LinkedHashSet<TreeType>(),TreeType.class);
        try{
            test(new TreeSet<SetType>(),SetType.class);
        }catch(Exception e){
            System.out.println(e.getMessage());
        }
        try{
            test(new TreeSet<HashType>(),HashType.class);
        }catch(Exception e){
            System.out.println(e.getMessage());
        }
    }
}

基类SetType只存储一个int,并且通过toString()方法产生它的值。因为所有在Set中存储的类都必须具有equals()方法，因此在基类中也有该方法。其等价性是基于这个int类型的i的值确定。
HashType继承自SetType,并且添加了hashCode()方法，该方法对于放置到Set的散列实现中的对象来说是必需的。

理解Map

映射表的基本思想是它维护的是键-值(对)关联。Map的几种实现:HashMap,TreeMap,LinkedHashMap,WeakHashMap,ConcurrentHashMap,IdentityHashMap。它们拥有同样的基本接口，但是行为特性各不相同，这表现在效率，键值对的保存及呈现次序，对象的保存周期，映射表如何在多线程中工作和判定"键"等价的策略等方面。
Map的简单实现:

public class AssociativeArray<K,V>{
    private Object[][] pairs;
    private int index;
    public AssociativeArray(int length){
        pairs=new Object[length][2];
    }
    public void put(K key,V value){
        if(index>=pairs.length)
            throw new ArrayIndexOutOfBoundException();
        pairs[index++]=new Object[]{key,value};
    }
    @SuppressWarnings("unchecked")
    public V get(K key){
        for(int i=0;i<index;i++)
            if(key.equals(pairs[i][0]))
                return (V)pairs[i][1];
        return null;
    }
    public String toString(){
        StringBuilder result=new StringBuilder();
        for(int i=0;i<index;i++){
            result.append(pairs[i][0].toString());
            result.append("　:　");
            result.append(pairs[i][1].toString());
            if(i<index-1)
                result.append("\n");
        }
        return result.toString();
    }
    public static void main(String[] args){
        AssociativeArray<String,String> map=new AssociativeArray<String,String>(6);
        map.put("sky","blue");
        map.put("grass","blue");
        try{
            map.put("extra","object");
        }catch(ArrayIndexOutOfBoundException e){
            print("Too many objects!");
        }
        print(map);
        print(map.get("ocean"));
    }
}

性能

性能是映射表中的一个重要问题，当在get()中使用线性搜索时，执行速度会相当的慢，而这正是HashMap提高速度的地方。HashMap使用了特殊的值，称作散列码，来取代对键的缓慢搜索。散列码是"相对唯一"的，用以代表对象的int值，它是通过将该对象的某些信息进行转换而生成的。

SortedMap

使用SortedMap,可以确保键处于排序状态。这使得它具有额外的功能。键值对是按键的次序排列的。TreeMap中的次序是有意义的，因此"位置"的概念才有意义，所以才能取得第一个和最后一个元素，并且可以提取Map的子集。

LinkedHashMap

为了提高速度,LinkedHashMap散列化所有的元素，但是在遍历键值对时，却又以元素的插入顺序返回键值对。此外，可以在构造器中设定LinkedHashMap,使之采用基于访问的最近最少使用(LRU)算法,于是没有被访问过的元素就会出现在队列的前面。对于需要定期清理元素以节省空间的程序来说，此功能使得程序很容易得以实现。

散列与散列码

HashMap使用equals()判断当前的键是否与表中存在的键相同。
正确的equals()方法必须满足下列5个条件:

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,z,如果有x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定要返回true。
5.对任何不是null的x,x.equals(null)一定返回false。

理解hashCode()

使用散列的目的在于:想要使用一个对象来查找另一个对象。
散列的价值在于速度:散列使得查询得以快速进行。
存储一组元素最快的数据结构是数组，所以使用它来表示键的信息(不是键本身)。但是数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由hashCode()方法生成。为解决数组容量固定的问题，不同的键可以产生相同的下标。
通常，散列冲突由外部链接处理:数组并不直接保存值，而是保存值的list。然后对list中的值使用equals()方法进行线性的查询。这部分的查询自然会比较慢，但是如果散列函数好的话，数组的每个位置就只有较少的值。因此，不是查询整个list,而是快速地跳到数组的某个位置，只对很少的元素进行比较。这便是HashMap会如此快的原因。

选择接口的不同实现

从容器分类图中可以看出，Hashtable,Vector和Stack的"特征是"，它们是过去遗留下来的类，目的只是为了支持老的程序。
LinkedList:经常性的需要在表中插入或删除元素；
ArrayList:不需要经常插入删除，就可以用速度更快的ArrayList；
HashSet:查询速度最快，常用；
LinkedHashSet：保持元素的插入的次序；
TreeSet:生成一个总是处于排序状态的Set;
有时某个特定容器的不同实现会拥有一些共同的操作,但是这些操作的性能却并不相同。在这种情况下，你可以基于使用某个特定操作的频率，以及你需要的执行速度来在它们中间进行选择。