容器深入

标签(空格分隔): 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的功能方法

项目 数量
boolean add(T) 确保容器持有具有泛型类型T的参数,如果没有将此参数添加进容器,则返回false
boolean adAll(Collection<?extends T>) 添加参数中的所有元素。只要添加了任意元素就返回true
void clear() 移除容器中所有的元素
boolean contains(T) 如果容器已经持有具体泛型类型T此参数,则返回true
Boolean containsAll(Collection<?>) 如果容器持有此参数中的所有元素,则返回true
boolean isEmpty() 容器中没有元素时返回true
Iterator iterator() 返回一个Iterator,可以用来遍历容器中的元素
Boolean remove(Object) 如果参数在容器中,则移除此元素的一个实例。如果做了移除动作,则返回true
boolean removeAll(Collection<?>) 移除参数中的所有元素。只要有移除动作发生就返回true
boolean retainAll(Collection<?>) 只保存参数中的元素(应用集合类交集概念)。只要Collection发生了改变就返回true
int size() 返回容器中元素的数目
Object[] toArray() 返回一个数组,该数组包含容器中的所有元素
T[] toArray(T[]a) 返回一个数组,该数组包含容器中的所有元素

##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;
有时某个特定容器的不同实现会拥有一些共同的操作,但是这些操作的性能却并不相同。在这种情况下,你可以基于使用某个特定操作的频率,以及你需要的执行速度来在它们中间进行选择。

————没有什么是停不下来的,除了时间