806
Java 筆記05
集合（從本部分開始涉及API）
集合是指一個對象容納了多個對象，這個集合對象主要用來管理維護一係列相似的對象。
數組就是一種對象。（練習：如何編寫一個數組程序，並進行遍曆。）
java.util.*定義了一係列的接口和類，告訴我們用什麼類NEW出一個對象，可以進行超越數組的操作。
（注：JAVA1.5對JAVA1.4的最大改進就是增加了對範型的支持）
集合框架接口的分類：（分collection接口 和 map接口）
Collection接口 Map接口
List接口 Set接口 SortedMap接口
SortedSet接口
JAVA中所有與集合有關的實現類都是這六個接口的實現類。
Collection接口：集合中每一個元素為一個對象，這個接口將這些對象組織在一起，形成一維結構。
List接口代表按照元素一定的相關順序來組織（在這個序列中順序是主要的），List接口中數據可重複。
Set接口是數學中集合的概念：其元素無序，且不可重複。（正好與List對應）
SortedSet會按照數字將元素排列，為“可排序集合”。
Map接口中每一個元素不是一個對象，而是一個鍵對象和值對象組成的鍵值對（Key-Value）。
Key-Value是用一個不可重複的key集合對應可重複的value集合。（典型的例子是字典：通過頁碼的key值找字的value值）。
例子：
key1—value1;
key2—value2;
key3—value3.
SortedMap：如果一個Map可以根據key值排序，則稱其為SortedMap。（如字典）
!!注意數組和集合的區別：數組中隻能存簡單數據類型。Collection接口和Map接口隻能存對象。
以下介紹接口：
List接口：（介紹其下的兩個實現類：ArrayList和LinkedList）
ArrayList和數組非常類似，其底層①也用數組組織數據，ArrayList是動態可變數組。
① 底層：指存儲格式。說明ArrayList對象都是存在於數組中。
注：數組和集合都是從下標0開始。
ArrayList有一個add(Object o)方法用於插入數組。
ArrayList的使用：（完成這個程序）
先import java.util.*；
用ArrayList在一個數組中添加數據，並遍曆。
ArrayList中數組的順序與添加順序一致。
隻有List可用get和size。而Set則不可用（因其無序）。
Collection接口都是通過Iterator()（即迭代器）來對Set和List遍曆。
通過語句：Iterator it=c.iterator(); 得到一個迭代器，將集合中所有元素順序排列。然後可以通過interator方法進行遍曆，迭代器有一個遊標（指針）指向首位置。
Interator有hasNext()，用於判斷元素右邊是否還有數據，返回True說明有。然後就可以調用next動作。Next()會將遊標移到下一個元素，並把它所跨過的元素返回。（這樣就可以對元素進行遍曆）
練習：寫一個程序，輸入對象信息，比較基本信息。
集合中每一個元素都有對象，如有字符串要經過強製類型轉換。
Collections是工具類，所有方法均為有用方法，且方法為static。
有Sort方法用於給List排序。
Collections.Sort()分為兩部分，一部分為排序規則；一部分為排序算法。
規則用來判斷對象；算法是考慮如何排序。
對於自定義對象，Sort不知道規則，所以無法比較。這種情況下一定要定義排序規則。方式有兩種：
① java.lang下麵有一個接口：Comparable（可比較的）
可以讓自定義對象實現一個接口，這個接口隻有一個方法comparableTo(Object o)
其規則是當前對象與o對象進行比較，其返回一個int值，係統根據此值來進行排序。
如 當前對象>o對象，則返回值>0；（可將返回值定義為1）
如 當前對象=o對象，則返回值=0；
如 當前對象<o對象，則返回值〈0。（可將返回值定義為-1）
看TestArraylist的java代碼。
我們通過返回值1和-1位置的調換來實現升序和降序排列的轉換。
② java.util下有一個Comparator(比較器)
它擁有compare()，用來比較兩個方法。
要生成比較器，則用Sort中Sort（List,List(Compate)）
第二種方法更靈活，且在運行的時候不用編譯。
注意：要想實現comparTo()就必須在主方法中寫上implement comparable.
練習：生成一個EMPLOYEE類，然後將一係列對象放入到ArrayList。用Iterator遍曆，排序之後，再進行遍曆。
集合的最大缺點是無法進行類型判定（這個缺點在JAVA1.5中已經解決），這樣就可能出現因為類型不同而出現類型錯誤。
解決的方法是添加類型的判斷。
LinkedList接口（在代碼的使用過程中和ArrayList沒有什麼區別）
ArrayList底層是object數組，所以ArrayList具有數組的查詢速度快的優點以及增刪速度慢的缺點。
而在LinkedList的底層是一種雙向循環鏈表。在此鏈表上每一個數據節點都由三部分組成：前指針（指向前麵的節點的位置），數據，後指針（指向後麵的節點的位置）。最後一個節點的後指針指向第一個節點的前指針，形成一個循環。
雙向循環鏈表的查詢效率低但是增刪效率高。所以LinkedList具有查詢效率低但增刪效率高的特點。
ArrayList和LinkedList在用法上沒有區別，但是在功能上還是有區別的。
LinkedList經常用在增刪操作較多而查詢操作很少的情況下：隊列和堆棧。
隊列：先進先出的數據結構。
堆棧：後進先出的數據結構。
注意：使用堆棧的時候一定不能提供方法讓不是最後一個元素的元素獲得出棧的機會。
LinkedList提供以下方法：（ArrayList無此類方法）
addFirst();
removeFirst();
addLast();
removeLast();
在堆棧中，push為入棧操作，pop為出棧操作。
Push用addFirst()；pop用removeFirst()，實現後進先出。
用isEmpty()--其父類的方法，來判斷棧是否為空。
在隊列中，put為入隊列操作，get為出隊列操作。
Put用addFirst()，get用removeLast()實現隊列。
List接口的實現類（Vector）（與ArrayList相似，區別是Vector是重量級的組件，使用使消耗的資源比較多。）
結論：在考慮並發的情況下用Vector（保證線程的安全）。
在不考慮並發的情況下用ArrayList（不能保證線程的安全）。
麵試經驗（知識點）：
java.util.stack（stack即為堆棧）的父類為Vector。可是stack的父類是最不應該為Vector的。因為Vector的底層是數組，且Vector有get方法（意味著它可能訪問到並不屬於最後一個位置元素的其他元素，很不安全）。
對於堆棧和隊列隻能用push類和get類。
Stack類以後不要輕易使用。
！！！實現堆棧一定要用LinkedList。
（在JAVA1.5中，collection有queue來實現隊列。）
Set-HashSet實現類：
遍曆一個Set的方法隻有一個：迭代器（interator）。
HashSet中元素是無序的（這個無序指的是數據的添加順序和後來的排列順序不同），而且元素不可重複。
在Object中除了有final()，toString()，equals()，還有hashCode()。
HashSet底層用的也是數組。
當向數組中利用add(Object o)添加對象的時候，係統先找對象的hashCode：
inthc=o.hashCode(); 返回的hashCode為整數值。
Int I=hc%n;（n為數組的長度），取得餘數後，利用餘數向數組中相應的位置添加數據，以n為6為例，如果I=0則放在數組a[0]位置，如果I=1,則放在數組a[1]位置。如果equals()返回的值為true，則說明數據重複。如果equals()返回的值為false，則再找其他的位置進行比較。這樣的機製就導致兩個相同的對象有可能重複地添加到數組中，因為他們的hashCode不同。
如果我們能夠使兩個相同的對象具有相同hashcode，才能在equals()返回為真。
在實例中，定義student對象時覆蓋它的hashcode。
因為String類是自動覆蓋的，所以當比較String類的對象的時候，就不會出現有兩個相同的string對象的情況。
現在，在大部分的JDK中，都已經要求覆蓋了hashCode。
結論：如將自定義類用hashSet來添加對象，一定要覆蓋hashcode()和equals()，覆蓋的原則是保證當兩個對象hashcode返回相同的整數，而且equals()返回值為True。
如果偷懶，沒有設定equals()，就會造成返回hashCode雖然結果相同，但在程序執行的過程中會多次地調用equals()，從而影響程序執行的效率。
我們要保證相同對象的返回的hashCode一定相同，也要保證不相同的對象的hashCode盡可能不同（因為數組的邊界性，hashCode還是可能相同的）。例子：
public int hashCode(){
return name.hashcode()+age;
}
這個例子保證了相同姓名和年齡的記錄返回的hashCode是相同的。
使用hashSet的優點：
hashSet的底層是數組，其查詢效率非常高。而且在增加和刪除的時候由於運用的hashCode的比較開確定添加元素的位置，所以不存在元素的偏移，所以效率也非常高。因為hashSet查詢和刪除和增加元素的效率都非常高。
但是hashSet增刪的高效率是通過花費大量的空間換來的：因為空間越大，取餘數相同的情況就越小。HashSet這種算法會建立許多無用的空間。
使用hashSet接口時要注意，如果發生衝突，就會出現遍曆整個數組的情況，這樣就使得效率非常的低。
練習：new一個hashset，插入employee對象，不允許重複，並且遍曆出來。
添加知識點：
集合對象存放的是一係列對象的引用。
例：
Student S
Al.add(s);
s.setName(“lucy”);
Students2=(Student)(al.get(o1));
可知s2也是s。
最後更新：2017-04-02 16:47:44