一同學 Java（三） 集合框架、數據構造、泛型

集合框架是一個用來代表和操縱集合的一致架構。一切的集合框架都包括如下內容：

• 接口：是代表集合的籠統數據類型。接口允許集合獨立操縱其代表的細節。在面向對象的言語，接口通常構成一個層次。
• 完成（類）：是集合接口的詳細完成。從實質上講，它們是可反復運用的數據構造。
• 算法：是完成集合接口的對象裡的辦法執行的一些有用的計算，例如：搜索和排序。這些算法被稱為多態，那是由於相反的辦法可以在類似的接口上有著不同的完成。

Collection 是最根本的集合接口，一個 Collection 代表一組 Object，Java不提供直接承繼自Collection的類，只提供承繼於的子接口(如List和set)。

List接口是一個有序的Collection，運用此接口可以准確的控制每個元素拔出的地位，可以經過索引(元素在List中地位，相似於數組的小標)來訪問List中的元素，而且允許有相反的元素。

Set 具有與 Collection 完全一樣的接口，只是行為上不同，Set 不保管反復的元素。

Java提供了一套完成了Collection接口的規范集合類。其中一些是詳細類，這些類可以直接拿來運用，而另外一些是籠統類，提供了接口的局部完成。

規范集合類匯總於下表：

該類完成了List接口，允許有null（空）元素。次要用於創立鏈表數據構造，該類沒有同步辦法，假如多個線程同時訪問一個List，則必需自己完成訪問同步，處理辦法就是在創立List時分結構一個同步的List。例如：

Listlist=Collections.synchronizedList(newLinkedList(...));

LinkedList 查找效率低。

該類也是完成了List的接口，完成了可變大小的數組，隨機訪問和遍歷元素時，提供更好的功能。該類也是非同步的,在多線程的狀況下不要運用。ArrayList 增長以後長度的50%，拔出刪除效率低。

該類完成了Set接口，不允許呈現反復元素，不保證集合中元素的順序，允許包括值為null的元素，但最多只能一個。

該類完成了Set接口，可以完成排序等功用。

在後面的教程中曾經討論經過java.util包中定義的類，如下所示：

該類和ArrayList十分類似，但是該類是同步的，可以用在多線程的狀況，該類允許設置默許的增長長度，默許擴容方式為原來的2倍。

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;

public class myArrayList {
    public static void main(String[] args){
        List<String> list = new ArrayList<String>();
        list.add("nick");
        list.add("jenny");
        list.add("Maria");
        
        //第一種遍歷辦法運用foreach遍歷List
        for (String str : list){
            System.out.println(str);
        }
        
        //第二種遍歷，把鏈表變為數組相關的內容停止遍歷
        String[] strArray = new String[list.size()];
        list.toArray(strArray);
        for (int i=0;i<strArray.length;i++){
            System.out.println(strArray[i]);
        }
        
        //第三種遍歷 運用迭代器停止相關遍歷
        Iterator<String> ite=list.iterator();
        while (ite.hasNext()){
            System.out.println(ite.next());
        }
    }
}

package three;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class mymap {
    public static void main(String[] args){
        Map<String, String> map = new HashMap<String, String>();
        map.put("name", "nick");
        map.put("age", "18");
        map.put("single", "singleDog");
        
        //第一種：普遍運用，二次取值
        for (String key : map.keySet()){
            System.out.println(key + " " + map.get(key));
        }
        
        //經過Map.entrySet運用iterator遍歷key和value
        Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, String> entry = it.next();
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
        
        //第三種：引薦，尤其是容量大時
        for (Map.Entry<String, String> entry : map.entrySet()){
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
        
        //經過Map.values()遍歷一切的value，但不能遍歷key
        for (String v : map.values()){
            System.out.println(v);
        }
    }
}

在Java中的數據構造次要包括以下幾種接口和類：

• 枚舉（Enumeration）
• 位集合（BitSet）
• 向量（Vector）
• 棧（Stack）
• 字典（Dictionary）
• 哈希表（Hashtable）
• 屬性（Properties）

Enumeration接口中定義了一些辦法，經過這些辦法可以枚舉（一次取得一個）對象集合中的元素。

這種傳統接口已被迭代器取代，雖然Enumeration 還未被遺棄，但在古代代碼中曾經被很少運用了。雖然如此，它還是運用在諸如Vector和Properties這些傳統類所定義的辦法中，除此之外，還用在一些API類，並且在使用順序中也普遍被運用。 下表總結了一些Enumeration聲明的辦法：

package three;

import java.util.Vector;
import java.util.Enumeration;

public class myEnumeration {
    public static void main(String[] args){
        Enumeration days;
        Vector dayNames = new Vector();
        dayNames.add("Sunday");
        dayNames.add("Monday");
        dayNames.add("Tuesday");
        dayNames.add("Wednesday");
        dayNames.add("Thursday");
        dayNames.add("Friday");
        dayNames.add("Saturday");
        days = dayNames.elements();
        while (days.hasMoreElements()){
           System.out.println(days.nextElement()); 
        }
    }
}

位集合類完成了一組可以獨自設置和肅清的位或標志。

該類在處置一組布爾值的時分十分有用，你只需求給每個值賦值一"位"，然後對位停止適當的設置或肅清，就可以對布爾值停止操作了。

一個Bitset類創立一種特殊類型的數組來保管位值。BitSet中數組大小會隨需求添加。這和位向量（vector of bits）比擬相似。

這是一個傳統的類，但它在Java 2中被完全重新設計。

BitSet定義了兩個結構辦法。

BitSet()    //第一個結構辦法創立一個默許的對象
BitSet(int size)    //第二個辦法允許用戶指定初始大小。一切位初始化為0。

BitSet中完成了Cloneable接口中定義的辦法如下表所列：

package three;


import java.util.BitSet;

public class myBitset {
    public static void main(String[] args){
        BitSet bits1 = new BitSet(16);
        BitSet bits2 = new BitSet(16);
        
        // set some bits
        for(int i=0; i<16; i++) {
            if((i%2) == 0) bits1.set(i);
            if((i%5) != 0) bits2.set(i);
        }
        System.out.println("Initial pattern in bits1: ");
        System.out.println(bits1);    // {0, 2, 4, 6, 8, 10, 12, 14}
        System.out.println("\nInitial pattern in bits2: ");
        System.out.println(bits2);    // {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}
        
        // AND bits
        bits2.and(bits1);
        System.out.println("\nbits2 AND bits1: ");
        System.out.println(bits1);    // {0, 2, 4, 6, 8, 10, 12, 14}
        System.out.println(bits2);    // {2, 4, 6, 8, 12, 14}
        
        // OR bits
        bits2.or(bits1);
        System.out.println("\nbits2 OR bits1: ");
        System.out.println(bits1);    // {0, 2, 4, 6, 8, 10, 12, 14}
        System.out.println(bits2);    // {0, 2, 4, 6, 8, 10, 12, 14}
        
        // XOR bits
        bits2.xor(bits1);
        System.out.println("\nbits2 XOR bits1: ");
        System.out.println(bits1);    // {0, 2, 4, 6, 8, 10, 12, 14}
        System.out.println(bits2);    // {}
    }
}

向量（Vector）類和傳統數組十分類似，但是Vector的大小能依據需求靜態的變化。

和數組一樣，Vector對象的元素也能經過索引訪問。

運用Vector類最次要的益處就是在創立對象的時分不用給對象指定大小，它的大小會依據需求靜態的變化。

Vector類完成了一個靜態數組。和ArrayList和類似，但是兩者是不同的：

• Vector是同步訪問的。
• Vector包括了許多傳統的辦法，這些辦法不屬於集合框架。

Vector次要用在事前不知道數組的大小，或許只是需求一個可以改動大小的數組的狀況。

Vector類支持4種結構辦法。

Vector()    //第一種結構辦法創立一個默許的向量，默許大小為10
Vector(int size)    //第二種結構辦法創立指定大小的向量
Vector(int size,int incr)    //第三種結構辦法創立指定大小的向量，並且增量用incr指定. 增量表示向量每次添加的元素數目
Vector(Collection c)    //第四中結構辦法創立一個包括集合c元素的向量

除了從父類承繼的辦法外Vector還定義了以下辦法：

package three;


import java.util.*;

public class myVector {
    public static void main(String[] args){
          Vector v = new Vector(3, 2);
          System.out.println(v.size());    // 0
          System.out.println(v.capacity());    // 3
          v.addElement(new Integer(1));
          System.out.println(v.capacity());    // 3
          v.addElement(new Integer(2));
          System.out.println(v.capacity());    // 3
          v.addElement(new Integer(3));
          System.out.println(v.capacity());    // 3
          
          v.addElement(new Integer(4));
          System.out.println(v.capacity());    // 5
          v.addElement(new Double(5.45));
          System.out.println(v.capacity());    // 5
          
          v.addElement(new Double(6.08));
          v.addElement(new Integer(7));
          System.out.println(v.capacity());    // 7
          v.addElement(new Float(9.4));
          v.addElement(new Integer(10));
          System.out.println(v.capacity());    // 9
          v.addElement(new Integer(11));
          v.addElement(new Integer(12));
          System.out.println(v.capacity());    // 11
          System.out.println((Integer)v.firstElement()); // 1
          System.out.println((Integer)v.lastElement());    // 12
          
          if(v.contains(new Integer(3)))
             System.out.println("Vector contains 3.");    //true
          
          // enumerate the elements in the vector.
          Enumeration vEnum = v.elements();
          System.out.println("\nElements in vector:");
          while(vEnum.hasMoreElements())
             System.out.print(vEnum.nextElement() + " ");
               // 1 2 3 4 5.45 6.08 7 9.4 10 11 12 
          System.out.println();
    }
}

棧（Stack）完成了一個後進先出（LIFO）的數據構造。

你可以把棧了解為對象的垂直散布的棧，當你添加一個新元素時，就將新元素放在其他元素的頂部。

當你從棧中取元素的時分，就從棧頂取一個元素。換句話說，最後進棧的元素最先被取出。

棧是Vector的一個子類，它完成了一個規范的後進先出的棧。

堆棧只定義了默許結構函數，用來創立一個空棧。 堆棧除了包括由Vector定義的一切辦法，也定義了自己的一些辦法。

Stack()

除了由Vector定義的一切辦法，自己也定義了一些辦法：

package three;

import java.util.*;

public class myStack {
       static void showpush(Stack st, int a) {
          st.push(new Integer(a));
          System.out.println("push(" + a + ")");
          System.out.println("stack: " + st);
       }

       static void showpop(Stack st) {
          System.out.print("pop -> ");
          Integer a = (Integer) st.pop();
          System.out.println(a);
          System.out.println("stack: " + st);
       }
       
       public static void main(String args[]) {
          Stack st = new Stack();
          System.out.println("stack: " + st);
          showpush(st, 42);
          showpush(st, 66);
          showpush(st, 99);
          showpop(st);
          showpop(st);
          showpop(st);
          try {
               showpop(st);
             } catch (EmptyStackException e) {
               System.out.println("empty stack");
          }
       }
       /*輸入後果:
        stack: []
        push(42)
        stack: [42]
        push(66)
        stack: [42, 66]
        push(99)
        stack: [42, 66, 99]
        pop -> 99
        stack: [42, 66]
        pop -> 66
        stack: [42]
        pop -> 42
        stack: []
        pop -> empty stack
        * */
}

字典（Dictionary） 類是一個籠統類，它定義了鍵映射到值的數據構造。

當你想要經過特定的鍵而不是整數索引來訪問數據的時分，這時分應該運用Dictionary。

由於Dictionary類是籠統類，所以它只提供了鍵映射到值的數據構造，而沒有提供特定的完成。

Dictionary 類是一個籠統類，用來存儲鍵/值對，作用和Map類類似。

給出鍵和值，你就可以將值存儲在Dictionary對象中。一旦該值被存儲，就可以經過它的鍵來獲取它。所以和Map一樣， Dictionary 也可以作為一個鍵/值對列表。

Dictionary定義的籠統辦法如下表所示：

Hashtable類提供了一種在用戶定義鍵構造的根底下去組織數據的手腕。

例如，在地址列表的哈希表中，你可以依據郵政編碼作為鍵來存儲和排序數據，而不是經過人名。

哈希表鍵的詳細含義完全取決於哈希表的運用情形和它包括的數據。

Hashtable是原始的java.util的一局部， 是一個Dictionary詳細的完成 。

但是，Java 2 重構的Hashtable完成了Map接口，因而，Hashtable如今集成到了集合框架中。它和HashMap類很類似，但是它支持同步。

像HashMap一樣，Hashtable在哈希表中存儲鍵/值對。當運用一個哈希表，要指定用作鍵的對象，以及要鏈接到該鍵的值。

然後，該鍵經過哈希處置，所失掉的散列碼被用作存儲在該表中值的索引。

Hashtable定義了四個結構辦法。

Hashtable()
Hashtable(int size)    //創立指定大小的哈希表
Hashtable(int size,float fillRatio)    //創立一個指定大小的哈希表，並且經過fillRatio指定填充比例。填充比例必需介於0.0和1.0之間，它決議了哈希表在重新調整大小之前的充溢水平
Hashtable(Map m)    //創立一個以M中元素為初始化元素的哈希表。哈希表的容量被設置為M的兩倍。

Hashtable中除了從Map接口中定義的辦法外，還定義了以下辦法：

package three;


import java.util.*;

public class myHashTable {
    public static void main(String args[]) {
          // Create a hash map
          Hashtable balance = new Hashtable();
          Enumeration names;
          String str;
          double bal;

          balance.put("Zara", new Double(3434.34));
          balance.put("Mahnaz", new Double(123.22));
          balance.put("Ayan", new Double(1378.00));
          balance.put("Daisy", new Double(99.22));
          balance.put("Qadir", new Double(-19.08));

          // Show all balances in hash table.
          names = balance.keys();
          while(names.hasMoreElements()) {
             str = (String) names.nextElement();
             System.out.println(str + ": " +
             balance.get(str));
          }
          System.out.println();
          // Deposit 1,000 into Zara's account
          bal = ((Double)balance.get("Zara")).doubleValue();
          balance.put("Zara", new Double(bal+1000));
          System.out.println("Zara's new balance: " +
          balance.get("Zara"));
       }
    
    /*輸入後果
    Qadir: -19.08
    Zara: 3434.34
    Mahnaz: 123.22
    Daisy: 99.22
    Ayan: 1378.0
    
    Zara's new balance: 4434.34
     * */
}

Properties 承繼於 Hashtable.Properties 類表示了一個耐久的屬性集.屬性列表中每個鍵及其對應值都是一個字符串。

Properties 類被許多Java類運用。例如，在獲取環境變量時它就作為System.getProperties()辦法的前往值。

Properties 定義如下實例變量.這個變量持有一個Properties對象相關的默許屬性列表。

Properties defaults;

Properties類定義了兩個結構辦法。

Properties()    //第一個結構辦法沒有默許值。
Properties(Properties propDefault)    //運用propDefault 作為默許值。
兩種狀況下，屬性列表都為空

除了從Hashtable中所定義的辦法，Properties定義了以下辦法：

package three;


import java.util.*;

public class myProperties {
       public static void main(String args[]) {
          Properties capitals = new Properties();
          Set states;
          String str;
          
          capitals.put("Illinois", "Springfield");
          capitals.put("Missouri", "Jefferson City");
          capitals.put("Washington", "Olympia");
          capitals.put("California", "Sacramento");
          capitals.put("Indiana", "Indianapolis");

          // Show all states and capitals in hashtable.
          states = capitals.keySet(); // get set-view of keys
          Iterator itr = states.iterator();
          while(itr.hasNext()) {
             str = (String) itr.next();
             System.out.println("The capital of " +
                str + " is " + capitals.getProperty(str) + ".");
          }
          System.out.println();

          // look for state not in list -- specify default
          str = capitals.getProperty("Florida", "Not Found");
          System.out.println("The capital of Florida is "
              + str + ".");
       }
       
       /*輸入後果
        * The capital of Missouri is Jefferson City.
        The capital of Illinois is Springfield.
        The capital of Indiana is Indianapolis.
        The capital of California is Sacramento.
        The capital of Washington is Olympia.
        
        The capital of Florida is Not Found.
        * */
}

Java 泛型（generics）是 JDK 5 中引入的一個新特性, 泛型提供了編譯時類型平安檢測機制，該機制允許順序員在編譯時檢測到合法的類型。 

泛型的實質是參數化類型，也就是說所操作的數據類型被指定為一個參數。

Java 言語中引入泛型是一個較大的功用加強。不只言語、類型零碎和編譯器有了較大的變化，以支持泛型，而且類庫也停止了大翻修，所以許多重要的類，比方集合框架，都曾經成為泛型化的了。這帶來了很多益處：

類型平安。 泛型的次要目的是進步 Java 順序的類型平安。經過知道運用泛型定義的變量的類型限制，編譯器可以在一個高得多的水平上驗證類型假定。沒有泛型，這些假定就只存在於順序員的頭腦中（或許假如僥幸的話，還存在於代碼正文中）。

Java 順序中的一種盛行技術是定義這樣的集合，即它的元素或鍵是公共類型的，比方“String 列表”或許“String 到 String 的映射”。經過在變量聲明中捕捉這一附加的類型信息，泛型允許編譯器施行這些附加的類型約束。類型錯誤如今就可以在編譯時被捕捉了，而不是在運轉時當作 ClassCastException 展現出來。將類型反省從運轉時挪到編譯時有助於您更容易找到錯誤，並可進步順序的牢靠性。

消弭強迫類型轉換。 泛型的一個附帶益處是，消弭源代碼中的許多強迫類型轉換。這使得代碼愈加可讀，並且增加了出錯時機。

雖然增加強迫類型轉換可以降低運用泛型類的代碼的羅嗦水平，但是聲明泛型變量會帶來相應的啰嗦。

你可以寫一個泛型辦法，該辦法在調用時可以接納不同類型的參數。依據傳遞給泛型辦法的參數類型，編譯器適外地處置每一個辦法調用。

上面是定義泛型辦法的規則：

• 一切泛型辦法聲明都有一個類型參數聲明局部（由尖括號分隔），該類型參數聲明局部在辦法前往類型之前（在上面例子中的<E>）。
• 每一個類型參數聲明局部包括一個或多個類型參數，參數間用逗號隔開。一個泛型參數，也被稱為一個類型變量，是用於指定一個泛型類型稱號的標識符。
• 類型參數能被用來聲明前往值類型，並且能作為泛型辦法失掉的實踐參數類型的占位符。
• 泛型辦法體的聲明和其他辦法一樣。留意類型參數只能代表援用型類型，不能是原始類型（像int,double,char的等）。

上面的例子演示了如何運用泛型辦法打印不同字符串的元素：

public class GenericMethodTest
{
   // 泛型辦法 printArray                         
   public static < E > void printArray( E[] inputArray )
   {
      // 輸入數組元素            
         for ( E element : inputArray ){        
            System.out.printf( "%s ", element );
         }
         System.out.println();
    }
 
    public static void main( String args[] )
    {
        // 創立不同類型數組： Integer, Double 和 Character
        Integer[] intArray = { 1, 2, 3, 4, 5 };
        Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 };
        Character[] charArray = { 'H', 'E', 'L', 'L', 'O' };
 
        System.out.println( "整型數組元素為:" );
        printArray( intArray  ); // 傳遞一個整型數組
 
        System.out.println( "\n雙精度型數組元素為:" );
        printArray( doubleArray ); // 傳遞一個雙精度型數組
 
        System.out.println( "\n字符型數組元素為:" );
        printArray( charArray ); // 傳遞一個字符型數組
    } 
}

/*輸入後果
整型數組元素為:
1 2 3 4 5 

雙精度型數組元素為:
1.1 2.2 3.3 4.4 

字符型數組元素為:
H E L L O 
* */

能夠有時分，你會想限制那些被允許傳遞到一個類型參數的類型品種范圍。例如，一個操作數字的辦法能夠只希望承受Number或許Number子類的實例。這就是有界類型參數的目的。

要聲明一個有界的類型參數，首先列出類型參數的稱號，後跟extends關鍵字，最後緊跟它的上界。

上面的例子演示了"extends"如何運用在普通意義上的意思"extends"（類）或許"implements"（接口）。該例子中的泛型辦法前往三個可比擬對象的最大值。

public class MaximumTest
{
   // 比擬三個值並前往最大值
   public static <T extends Comparable<T>> T maximum(T x, T y, T z)
   {                     
      T max = x; // 假定x是初始最大值
      if ( y.compareTo( max ) > 0 ){
         max = y; //y 更大
      }
      if ( z.compareTo( max ) > 0 ){
         max = z; // 如今 z 更大           
      }
      return max; // 前往最大對象
   }
   public static void main( String args[] )
   {
      System.out.printf( "%d, %d 和 %d 中最大的數為 %d\n\n",
                   3, 4, 5, maximum( 3, 4, 5 ) );
 
      System.out.printf( "%.1f, %.1f 和 %.1f 中最大的數為 %.1f\n\n",
                   6.6, 8.8, 7.7, maximum( 6.6, 8.8, 7.7 ) );
 
      System.out.printf( "%s, %s 和 %s 中最大的數為 %s\n","pear",
         "apple", "orange", maximum( "pear", "apple", "orange" ) );
   }
}

/*輸入後果
3, 4 和 5 中最大的數為 5

6.6, 8.8 和 7.7 中最大的數為 8.8

pear, apple 和 orange 中最大的數為 pear
*/

泛型類的聲明和非泛型類的聲明相似，除了在類名前面添加了類型參數聲明局部。

和泛型辦法一樣，泛型類的類型參數聲明局部也包括一個或多個類型參數，參數間用逗號隔開。一個泛型參數，也被稱為一個類型變量，是用於指定一個泛型類型稱號的標識符。由於他們承受一個或多個參數，這些類被稱為參數化的類或參數化的類型。

 如下實例演示了我們如何定義一個泛型類:

public class Box<T> {
   
  private T t;
 
  public void add(T t) {
    this.t = t;
  }
 
  public T get() {
    return t;
  }
 
  public static void main(String[] args) {
    Box<Integer> integerBox = new Box<Integer>();
    Box<String> stringBox = new Box<String>();
 
    integerBox.add(new Integer(10));
    stringBox.add(new String("嗨.."));
 
    System.out.printf("整型值為 :%d\n\n", integerBox.get());
    System.out.printf("字符串為 :%s\n", stringBox.get());
  }
}
/*
整型值為 :10

字符串為 :嗨..
*/

類型通配符普通是運用?替代詳細的類型參數

例如 List<?> 在邏輯上是List<String>,List<Integer> 等一切List<詳細類型實參>的父類。

package three;

import java.util.ArrayList;
import java.util.List;

public class GenericTest {
     public static void main(String[] args) {
            List<String> name = new ArrayList<String>();
            List<Integer> age = new ArrayList<Integer>();
            List<Number> number = new ArrayList<Number>();
            
            name.add("nick");
            age.add(18);
            number.add(530);
     
            getData(name);
            getData(age);
            getData(number);
           
//            getUperNumber(name);    //報錯
            getUperNumber(age);
            getUperNumber(number);
       }
     
       public static void getData(List<?> data) {
          System.out.println("getData :" + data.get(0));
       }
       
       public static void getUperNumber(List<? extends Number> data) {
              System.out.println("getUperNumber :" + data.get(0));
       }
}

/*輸入後果
 * getData :nick
getData :18
getData :530
getUperNumber :18
getUperNumber :530
 * */