java集合（二）—集合框架與演算法詳解

java集合（一）－資料結構詳解：http://www.php.cn/java-article-354226.html

框架是指一個類別的集，在集中有很多超類別和接口，這些超類別中實現了許多高級的機制、功能和策略。框架的使用者可以建立子類別來實作和擴展超類，而不用來重新建立這些基本的機制。在日常工作中，我們用到的技術基本上都是框架，我們去使用那些包，去呼叫那些函數時都會用到這種框架的想法。在集合（一）分析完集合的資料結構，今天我們就一起來繼續討論集合的架構。

（一）集合資料結構回顧

##散列表HashMapMap用雜湊法存放的，鍵值映射的表#樹表TreeMapMap,NavigableMap,SortedMap 將鍵依照一定方法排序的表註：前六種（不包括Map）都實作了Collection和Iterator接口，因為篇幅限制沒有寫出。

（二）視圖

在集合類別庫中，我們已經用了非常大的比例來建立實作類別的接口，那麼這些接口有什麼用呢？如果我們直接把介面中方法寫在實作類別中不也起到一樣的效果麼？實際情況遠非我們想的這麼簡單，有很多複雜的東西需要我們透過這些介面來操作。例如，我們把某些類別的公有介面類型的物件稱為視圖物件。這些物件的類型並不是具體的某個實作類，而是一些實作類別的公有介面。視圖有很多作用，主要的有以下這幾點：

1. 視圖是輕量級的集包裝器

我們可以透過方法，將普通數組包裝成類型為List的視圖物件。這個視圖物件的型別是List，這聽起來可能有些不可思議，因為List是個接口，並不能實例化。但這就是視圖物件的優勢，這個視圖物件可以透過一定的方法被賦予到任何實作了List介面的集合類別中，例如常見的ArrayList、LinkedList等等，從而達到我們將一個普通類別包裝成集合類別的目的。

package SetViews;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;/**
 * 
 * @author QuinnNorris
 * 视图是一个轻量级的集包装器，下面有两个例子
 */public class Views {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub
        //-----------------------例1----------------------
        int[] arr = new int[10];        //创建一个普通的int数组
        Arrays.asList(arr);        //通过asList方法，我们将一个普通的数组转换成List类型的视图对象。

        //-----------------------例2-----------------------
        List<String> ll = new LinkedList<>(); 
        //创建一个LinkedList对象ll。
        ll.addAll(Collections.nCopies(10, "ok"));        
        //nCopies是Collections类的静态方法，可以将“ok”复制10次，并返回一个List类型的视图对象。
        //在这里我们不可以直接把Collections.nCopies的类型强转成LinkedList，因为语法不能上转下
        //我们通过addAll方法将这个内容填充到LinkedList对象ll中。

        ll.set(2, "no");        //我们看看它是否能正常工作，我们试着将第三个链表中的String换成no。
        //请注意，链表最好不要使用get和set方法，这里只是为了实验。
        for(String s : ll){
            System.out.println(s);
        }        //输出结果第三个是no，其他全是ok，没有任何问题。
    }

}

這就是視圖的一大優點，它是一個輕量級的陣列包裝器，將陣列包裝成集合類別庫中的類別物件。同樣的，我們可以把那些鍵值對、需要存放到Set中的資料…都透過視圖包裝起來傳入對應的類別中。所以，我們把這個視圖的功能叫做輕量級的集包裝器。

2.透過視圖分離出類別中的子範圍

可以為許多集合建立子範圍視圖，這些子範圍是原有集合的一個引用，如果修改了這些子範圍會影響到原有集合。如果不想有影響，我們需要用其他類似addAll的方法來做複製。在清單中，分例子範圍的方法很簡單。

package SetViews;import java.util.ArrayList;import java.util.Collections;import java.util.List;/**
 * 
 * @author QuinnNorris
 * 在列表中分例子范围，并进行操作
 */public class SubViews {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        List<Integer> al = new ArrayList<>();        //创建ArrayList对象al
        al.addAll(Collections.nCopies(15, 1));        //在al中设置15个1
        List subal = al.subList(5, 10);        
        //subList取出从第6个元素到第10个元素作为一个子范围，返回一个视图对象，我们将它存放到subal中。
        subal.set(0, 0);        //第6个数字改成0

        for(Integer i :al)
            System.out.println(i);        //除了第6个数字为0其他全为1

        subal.clear();//清除子范围

        for(Integer i :al)
            System.out.print(i);        //al列表中只有10个1，中间的五个被清除了
    }

}

除此之外，在其他的有序集和映射表中，我們可以使用排序順序而不是元素位置來建立子範圍。這些方法在SortedSet和SortedMap中都有聲明。

SortedSet headSet(E toElement)  
           傳回此 set 的部分視圖，其元素嚴格小於 toElement。

SortedSet subSet(E fromElement, E toElement)  
           傳回此 set 的部分視圖，其元素從 fromElement（包括）到 toElement（不包括）。

SortedSet tailSet(E fromElement)  
##            傳回此 set 的部分視圖，其元素大於等於 fromElement。

上面的三個方法是在SortedSet中宣告的方法，我們在TreeSet中是可用的。同理，如果把方法中所有的Set換成Map，我們就可以在TreeMap中使用類似的這三個方法，要注意的是，Map中所有的操作都是用鍵來進行的，而不是值。

3.不可修改的安全視圖

在現實生活中，如果你把你的集合物件傳入到你同事的方法中，結果發現他錯誤的把你的對象修改了，這一定會讓你惱火不已。那麼，我們要如何解決這類問題，讓我們的資料結構更安全呢？在視圖中，我們可以用不可修改視圖來為我們的物件上鎖，如果發現試圖對集合進行修改，就拋出一個異常，同時將這個集合還原回沒修改的狀態。

在Collections類別中，為我們提供了這麼多種獲得不可修改視圖的方法：

unmodifiableCollection   ： 返回指定 collection 的不可修改视图（下同）。  

   unmodifiableList  

   unmodifiableMap  

   unmodifiableSet 

   unmodifiableSortedMap  

   unmodifiableSortedSet

上面這些方法非常簡單清晰，我們來看一個具體的例子，看看這些方法是如何運作的。

package SetViews;import java.util.ArrayList;import java.util.Collections;import java.util.List;/**
 * 
 * @author QuinnNorris
 * 不可修改的安全视图举例
 */public class UnmodifaiableViews {

    //这个是调用列表的方法
    private static void changeList(List<String> al) {
        al.set(0, "change");        //error Exception in thread "main" java.lang.UnsupportedOperationException
    }    public static void main(String[] args) {        // TODO Auto-generated method stub

        List<String> al = new ArrayList<>();        //创建ArrayList对象al
        al.addAll(Collections.nCopies(10, "final"));        //前十个元素填充“final”字符串
        changeList(al);        //先直接调用changeList方法，没问题
        changeList(Collections.unmodifiableList(al));        
        //报错，说明在changeList中对al进行了修改，被阻止了，而且抛出了异常
    }

}

不可修改並不是指集合物件再也不能修改，而是當它在套用Collections的靜態方法時是不能被修改的。但是這樣有個隱含的問題，因為使用了靜態方法後，他的類型變成了視圖類型，這樣導致一些更細節的方法不能被使用。例如，一個ArrrayList物件在透過Collections.unmodifiableList( )包裝後，類型變成List，有一部分ArrayList特有的方法將不能被使用，這是需要注意的一點。

4.同步視圖

多執行緒在我們的日常工作中十分常見，如果由多個執行緒存取集合，就必須確保集合不會被意外的破壞。這裡也不想過多討論多線程的問題。在集合類別庫中，設計者使用了視圖機制來確保常規集合的執行緒安全。例如Collecions類別的靜態方法synchronizedMap就可以將作為參數傳入的Map實作類別的物件變成線程安全的Map。

Map<String,Integer> map = Collections.synchronizedMap(new HashMap<String,Integer>());

相似的方法還有一大堆，和第三點中的不可修改視圖是類似的，在這裡就不多討論了。

5.检查视图

有的时候，我们在使用类似ArrayList等数据结构时并不使用泛型，从而会导致一些难以发现的类型错误。这个时候，如果我们使用了视图机制，用一种方法来不断地检查我们的代码就可以直接判断出错误的原因。

package SetViews;import java.util.ArrayList;import java.util.Collections;import java.util.Date;import java.util.List;/**
 * 
 * @author QuinnNorris
 * 动态类型安全视图是如何避免错误的发生举例
 */public class CheckViews {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        //--------------------发生错误的例子-----------------------

        ArrayList<String> al = new ArrayList<>();        //创建ArrayList对象al
        ArrayList errList = al;        //声明一个没有泛型的ArrayList，并把al赋值给它
        errList.add(new Date());        //这个列表本应该是String类型的，但是现在增加一个Date类型数据在编译运行时都不报错。
        //只有当对内部的数据进行操作时，编译器才有可能发现这个错误并抛出异常

        //-----------------动态类型安全视图机制----------------------

        List<String> safeAl = Collections.checkedList(al, String.class); 
        //调用Collections的静态方法checkedList，第一个参数是列表名，第二个参数是类型
        //这个方法返回一个List视图对象，如果要进行错误的操作，会抛出异常
        List errSafeAl = safeAl;        //再用无泛型的列表去引用检查视图的对象，因为al原本是ArrayList
        errSafeAl.add(new Date());        //现在运行时会报错，Attempt to insert class java.util.Date element into collection 
        //with element type class java.lang.String

    }

}

视图是个好机制，它为我们提供了很多方便快捷的转换，安全等方面的操作，让我们对整个集合类库的构架有了个初步的理解。那么谈完了宏观的概念，我们来看一下实际操作中集合框架的一些细节的特性和机制。

（三）批操作

集合就是许许多多的数据在一起构成的。在实际应用中，处理这些海量的数据让我们非常的头痛，而且一旦需要操作的复杂一些，几遍for循环的时空复杂度直接以次方形式增长，这是我们绝对不想看到的。为了方便集合类中数据的操作，集合框架提供类一种叫做批操作的概念。

package SetViews;import java.util.HashSet;import java.util.Set;/**
 * 
 * @author QuinnNorris
 * 批操作查找两个集合的交集
 */public class BulkViews {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Set<String> setA = new HashSet<>();
        Set<String> setB = new HashSet<>();        //创建集合A和集合B这是我们要比较的两个集合

        Set<String> result = new HashSet<>(setA);        //声明集合result存放结果，先用集合A来实例化这个集合

        result.retainAll(setB);        //调用retainAll方法，将B中与A相同的所有元素留下，达到查找交集的目的
    }

}

这是一个比较简单的例子，它省略了for循环，而是采用这种批操作的概念来完成交集的查找。但是方法毕竟有限，我们能处理的问题还是在少数，如果真的想广泛的运用批操作，那么结合视图机制是必须的。因为视图机制可以在一定程度上，可以非常简单的进行类型的转换，通过子视图等方法在复杂度较低的情况下达到自己的目的。

（四）集合类的类型转换

1.集合与数组之间的转换

由于java平台API中的大部分内容都是在集合框架创建之前设计的，所以，有的时候的确需要在传统的数组和现代的集合之间进行转换。我们可以通过asList方法和toArray方法来解决这个问题。

package SetViews;import java.util.Arrays;import java.util.HashSet;/**
 * 
 * @author QuinnNorris
 * 集合与数组之间的转换
 */public class TypeChange {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        //---------------------数组转集合---------------------------

        String[] values = {"a","b"};        //创建一个普通数组
        HashSet<String> hsValues = new HashSet<>(Arrays.asList(values));        
        //通过Arrays类中静态方法asList，将普通数组转换成List类型的视图对象并实例化

        //---------------------集合转数组---------------------------

        HashSet<String> hsValue = new HashSet<>();        //创建一个集合
        Object[] objValues = hsValue.toArray();        
        //如果调用无参toArray方法，则返回一个Object数组，此时不能类型强转否则出错
        String[] strValues = hsValue.toArray(new String[0]);        
        //有参数的toArray方法如果参数数组的长度小于所需长度的话，重新分配一个能放得下大小的数组
        //我们通过有参数的toArray方法巧妙的将集合对象转换成相应类型的
    }

}

2.Map和Set之间的转换

集合框架并没有把Map作为一个集合来看待，然而，我们可以获得映射表的视图，这个视图是一组实现了Collection接口的对象。大家都知道，Collection和Map是两个不相干的接口，如今Map的视图是Collection的对象，无疑是更加方便了我们的操作。Map接口为我们提供了三个方法，这三个方法返回三个不同的视图：

Set> entrySet()  
           返回此映射中包含的映射关系的 Set 视图。  
  Set keySet()  
           返回此映射中包含的键的 Set 视图。  
  Collection values()  
           返回此映射中包含的值的 Collection 视图。

这其中值得注意的是Map.Entry，很显然这是一个静态内部接口，这个接口中有几个最简单的方法：

K getKey()  
           返回与此项对应的键。  
  V getValue()  
           返回与此项对应的值。  
  V setValue(V value)  
           用指定的值替换与此项对应的值。

看完了这些方法，我们也就知道如何去将Map转型为其他，或者如何用V来获取K。

package SetViews;import java.util.HashMap;import java.util.Map;import java.util.Set;/**
 * 
 * @author QuinnNorris
 * 集合和映射表之间的转换
 */public class SetMap {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Map<String, Integer> map = new HashMap<String, Integer>();        //创建一个Map对象
        Set<String> set = map.keySet();        //set是包含着map中所有键的内容的集合

        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();        
        //entrySet是包含着Map中静态内部接口Entry的类对象的集合

        for (Map.Entry<String, Integer> es : entrySet)
            System.out.println(es.getKey() + ":" + es.getValue());        
            //循环输出，或者也可以进行，按照Key查Value的操作
    }

}

（五）算法与Collections类

一提到算法大家想到的可能是c语言中各式各样的排序，查找，二分等算法。但是在java集合类库中，并不需要这么麻烦。我们在Collections这个类中实现了几乎所有的简单算法，为了让程序员不会因为每次要实用算法时，都要自己编写一遍而感到苦恼。Collections这个类在上面也多次出现过了，这个类全部都是静态方法，而且它也确实只是在做一些包装性质的工作。这个类和视图密不可分。我们就来看一下Collections中的方法。

static <T> Queue<T> 
 asLifoQueue(Deque<T> deque) 
//以后进先出 (Lifo) Queue 的形式返回某个 Deque 的视图。 static <T> int 
 binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 
//使用二分搜索法搜索指定列表，以获得指定对象。 如果没有找到对象，则返回一个i，应该插入的位置是-i-1static <T> void 
 copy(List<? super T> dest, List<? extends T> src) 
//将第二个参数列表的内容复制到第一个参数列表中，要保证第一个参数列表的长度是足够的static boolean disjoint(Collection<?> c1, Collection<?> c2) 
//如果两个指定 collection 中没有相同的元素，则返回 true。 static <T> void 
 fill(List<? super T> list, T obj) 
//使用指定元素替换指定列表中的所有元素。 static int frequency(Collection<?> c, Object o) 
//返回指定 collection 中等于指定对象的元素数。 static int indexOfSubList(List<?> source, List<?> target) 
//返回指定源列表中第一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回 -1。 static int lastIndexOfSubList(List<?> source, List<?> target) 
//返回指定源列表中最后一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回 -1。 static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) 
//根据指定比较器产生的顺序，返回给定 collection 的最大元素。 static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) 
//根据指定比较器产生的顺序，返回给定 collection 的最小元素。 static <T> List<T> nCopies(int n, T o) 
//返回由指定对象的 n 个副本组成的不可变列表。 static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) 
//使用另一个值替换列表中出现的所有某一指定值。 static void reverse(List<?> list) 
//反转指定列表中元素的顺序。 static <T> Comparator<T> reverseOrder(Comparator<T> cmp) 
//返回一个比较器，它强行逆转指定比较器的顺序。 static void shuffle(List<?> list) 
//使用默认随机源对指定列表进行置换。 static <T> void sort(List<T> list, Comparator<? super T> c) 
//根据指定比较器产生的顺序对指定列表进行排序。 static void swap(List<?> list, int i, int j) 
//在指定列表的指定位置处交换元素。

（六）总结

两篇集合的文章，从前到后系统的总结了一遍java集合类库的林林总总，感觉学习了很多。尤其是java这种框架的概念，框架把原本分散的一些有关联的东西整合起来，并且给了很多实用的方法，整体上给人一种有血有肉很饱满的感觉。我们在日常使用框架的时候也很有必要去研究一下框架是如何搭建起来的，不仅可以让我们更加熟练的运用，而且能学到设计者的一些优秀的思想。

 以上就是java集合（二）—集合框架与算法详解的内容，更多相关内容请关注PHP中文网（www.php.cn）！

#基本	類型	實作接口	說明
List	鍊錶LinkedList	Deque,List,Queue	透過存放前後結點的引用，實現雙向鍊錶
	數組清單ArrayList	List,RandomAccess	資料傳入動態數組中，自動擴充數組大小
Set	散列集HashSet	Set	哈希法儲存數據，無序但尋找時效率高
	樹集TreeSet	NavigableSet,Set,SortedSet	依照一定方法排序，輸出有順序的集合
Queue	優先權佇列PriorityQueue	#Queue	#依照堆疊排序的方法排序的佇列樹
	雙端佇列ArrayDeque	Deque, Queue	可以在兩端新增和刪除，不能操作中間的佇列
Map