容器的深入研究

一.完整的容器分类法

集合框架

二.collection接口

1.boolean add（T）确保容器持有具有泛型类型T的参数，如果没有将此参数添加进容器，则返回false
2.boolean addAll（Collection <? extends T>）添加参数中的所有元素，只要添加了任意元素就返回true
3.void clear（） 移除容器中的所有元素
4.boolean contains（T） 如果容器中已经持有泛型类型T此参数，则返回true
5.Boolean containsAll（Collection<?>）如果容器持有此参数中的所有元素,则返回true
6.boolean isEmpty() 容器中没有元素时返回true
7.Iterator<T> iterator() 返回一个Iterator<T> , 可以用来遍历容器中的元素
8.Boolean remove(Object) 如果参数在容器中,则移除此元素的一个实例,如果做了一处操作,则返回true
9.boolean removeAll(Collection<?>) 移除参数中的所有元素,只要有移除动作就返回true
11.Boolean retainAll(Collection<?>) 只保存参数中的元素,只要Collection发生了改变就返回true
12.int size() 返回容器中元素的数目
13.Object[] toArray() 返回一个数组,该数组包含容器中的所有元素
14.<T> T[] toArray(T[] a)返回一个数组该数组包含容器中的所有元素,返回结果的运行时类型参数与参数数组a的类型相同,而不是单纯的Object

三.UnsupportedOperationException(未获支持的操作) 异常

List list = Arrays.asList(array) 当对list 进行增删操作时 就会抛出UnsupportedOperationException异常
对于UnsupportedOperationException 异常：
1.它必须是一个罕见的事件
2.如果一个操作时未获支持的,那么在实现接口的时候可以抛出这个异常
3.它只能在运行时才能被检测到

四.List功能方法

五.Set和存储顺序

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

public class SetType {
    int i;
    public SetType(int n){
        this.i = n;
    }
    public boolean equals(Object obj){
        return obj instanceof SetType && (i == ((SetType)obj).i);
    }
    public String toString(){
        return Integer.toString(i);
    }
}


 public class HashType extends SetType{
    public HashType(int n){ super(n);}
    public int hashCode(){return i;}
}

 public class TreeType extends SetType implements Comparable<TreeType>{
    public TreeType(int n) {
        super(n);
    }
    @Override
    public int compareTo(TreeType type) { 
        return (type.i < i ? -1 : (type.i == i ? 0 : 1));
    }
}

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class TypesForSet {
    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 ex){
            throw new RuntimeException();
        }
        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);
    }
}

从输出可以看出，HashSet以某种神秘的顺序白痴所有的元素，LinkedHashSet按照元素的插入顺序保存元素，而TreeSet按照排序顺序维护顺序(按照CompareTo()的实现形式，这里维护的 降序)

• SortedSet：
  1.Comparator comparator（）返回当前set使用的Comparator，或者返回null，表示自然方式排序
  2.Object first（）返回容器总的第一个元素
  3.Object last（）返回容器中的最末一个元素
  4.SortedSet subSet（fromElement， toElement）生成此Set的自己，范围从fromElement（包含）到toElement（不包含）
  5.SortedSet headSet（toElement）生成此Set的子集，由小于toElement的元素组成
  6.SortedSet tailSet（fromElement）生成此Set的子集，由大于或等于fromElement的元素组成

六.队列

• Queue在java se5中只有两个实现，LinkedList和PriorityQueue，他们的差异在排序行为
  PriorityQueue的排序也是通过Comparable而进行控制
• 双向队列：
  就像是一个队列，但是可以在任何一段添加或移除元素，在LinkedList中包含支持双向队列的方法，但是在java标准类库中没有任何显式地用于双向队列的接口。因此可以使用组合来创建一个Deque类，并直接从LinkedList中暴露

七.Map

• 实现一个简单的Map

  package com.zlb.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 ArrayIndexOutOfBoundsException();
        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(){
        StringBuffer stu = new StringBuffer();
        for(int i=0;i<index;i++){
            stu.append(pairs[i][0].toString());
            stu.append(" ： ");
            stu.append(pairs[i][1].toString());
            if(i < index - 1)
                stu.append("\n");
        }
        return stu.toString();
    }
    public static void main(String[] args) {
        AssociativeArray<String,String> map = new       AssociativeArray<String,String>(6);  
        map.put("name", "zhoulibin");
        map.put("age", "22");
        map.put("sex", "man");
        System.out.println(map);
        System.out.println(map.get("name"));
    }
}

集合名称	集合说明
HashMap*	Map基于散列表的实现(他取代了HashTable)，插入和查询"键值对"的开销是固定的。可以通过构造器设置容量和负载因子，已调整容器的性能
LinkedHashMap	类似于HashMap,但是迭代遍历它时，取得"键值对"的顺序是器插入次序，或者是最近少使用(LRU)的次序。只比HashMap慢点;而在迭代访问时更快，因为它使用链表维护内部次序
TreeMap	基于红黑树的实现。查看"键"或"键值对"时，他们会被排序(次序由Comparable或Comparator决定)。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map
WeakHashMap	弱键映射，允许释放映射所指向的对象
CurrentHashMap	一种线程安全的Map,它不涉及同步加锁，并发用的较多
IdentityHashMap	使用==代替equals()对"键"进行比较的散列映射

对Map中使用的键的要求与对Set中的元素的要求一样，任务键都必须具有一个equals()方法，如果键被用于散列Map，那么他必须还具有恰当的hashCode()方法，如果键被用于TreeMap,那么他必须实现Comparable

八.散列与散列码

 package com.zlb.hashcode;
public class Groundhog {
    protected int number;
    public Groundhog(int n){number = n;}
    public String toString(){
        return "Groundhod # "+ number;
    }
}

package com.zlb.hashcode;
import java.util.Random;
public class Prediction {
    private static Random random = new Random(47);
    private boolean shadow = random.nextDouble() > 0.5;
    public String toString(){
        if(shadow)
            return "Six more weeks";
        else 
            return "Spring";
    }
}

 package com.zlb.hashcode;
import java.lang.reflect.Constructor;
import java.util.HashMap;
import java.util.Map;
public class SpringDector {
    public static <T extends Groundhog> void detectSpring(Class<T> type) throws Exception{
        Constructor<T> ghog = type.getConstructor(int.class);
        Map<Groundhog,Prediction> map = new HashMap<Groundhog,Prediction>();
        for(int i=0;i<10;i++){
            map.put(ghog.newInstance(i), new Prediction());
        }
        System.out.println("map："+map);
        Groundhog gh = ghog.newInstance(3);
        System.out.println("looke up f or："+gh);
        if(map.containsKey(gh)){
            System.out.println(map.get(gh));
        }else{
            System.out.println("key not found：" + gh);
        }
    }
    public static void main(String[] args) throws Exception {
        detectSpring(Groundhog.class);
    }
}

从输出的结果看，数字3的键无法找到，因为Groundhog自动继承Object类，使用了Object累的hashCode()方法生成了散列码，而它默认使用对象的地址计算散列码，因此，由Groundhog(3)生成的第一个实例的散列码与由Groundhog(3)生成的散列码是不同的，所以找不到
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.一致性。
5.对任何不是null的x,x.equals(null)一定返回false

• 理解hashCode()
  hashCode()特点：
  1.无论何时，对同一个对象调用hashCode()都应该生成同样的值。
  2.hashCode()不能依赖于具有唯一性的对象信息，应该使用对象内有意义的识别信息。
  3.对于String类，hashCode()是基于String的内容的；
  4.散列码不必是独一无二的，应该更关注速度，而不是唯一性，通过hashCode()和equals()，必须能够完全确定对象的身份。
  5.好的hashCode()应该产生分布均匀的散列码。

• 为速度而散列
  1.散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于键的查询速度，因此解决方案之一就是保持键的排序状态。
  2.存储一组元素最快的数据结构是数组，因此用数组保存键的信息。数组并不保证键的本身，而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码
  3.查询一个值的过程就是首先计算散列码，然后使用散列码查询数组，如果能保证没有冲突，那可就有了一个完美的散列函数，但是这种情况只是特例。通常情况下，冲突由**外部链接
  **处理：数组并不保存值，而是保存值的list。然后对list中的值使用equals（）方法进行线性查询。这部分的查询会比较慢，如果散列函数好的话，数组的每个位置就只有很少的值。因此，不是查询整个list,而是快速跳转到数组的某个位置，对很少的元素进行比较，这就是HashMap会如此快的原因

以下实现一个简单的HashMap:

 package com.zlb.hashcode;
import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
    static final int SIZE = 997;
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
        for (LinkedList<MapEntry<K, V>> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            for (MapEntry<K, V> mpair : bucket) {
                set.add(mpair);
            }
        }
        return set;
    }
    public V put(K key, V value) {
        V oldValue = null;
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<MapEntry<K, V>>();
        }
        LinkedList<MapEntry<K, V>> bucket = buckets[index];
        MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K, V>> it = bucket.listIterator();
        while (it.hasNext()) {
            MapEntry<K, V> iPair = it.next();
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        if (!found) {
            buckets[index].add(pair);
        }
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets[index] == null)
            return null;
        for (MapEntry<K, V> iPair : buckets[index])
            if (iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public static void main(String[] args) {
        SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
        m.put("firstName", "zhou");
        m.put("lastName", "libin");
        System.out.println(m);
        System.out.println(m.get("lastName"));
        System.out.println(m.entrySet());
    }
}