集合java.util.*
一個對象，容納多個對象，用于維護一系列相似對象。數組是一種簡單集合。
程序中，如何管理數據，需要一種數據結構。（數組是一種線形結構）。
Java的集合框架是通過一系列接口和一些層級類形成的一套體系。
通過接口來查看整個集合框架，并分類來進行學習和研究。
概述：
Collection接口的一個對象會把數據按照一維線形組織。里面都是對象。
List代表，會按照元素的相應順序來組織，元素的順序有關系有意義。元素可重復。
Set是數學中集合的概念，順序無關不可重復。
SortedSet特殊按照元素數值把元素進行排序，添加元素自動排序。
Map是由鍵對象和值對象組成的鍵-值對兒的集合。
用不可重復的鍵值，去對應一個value值的集合。
SortedMap 如果可以根據key值排序，可以是一個SortedMap
============================================
常用實現類
List接口實現類
java.util.ArrayList
長度可變數組，內部采用數組實現（一種組合關系，內部有一個object[]），有一個增長因子來控制增幅。
ArrayList遍歷時，并不丟失順序信息，就是添加順序。
兩種遍歷方式，
非通用方式，通過size()方法，for循環。
ArrayList al = new ArrayList();
al.add(new Integer(10000));
al.add(new Integer(200000));
al.add(new Integer(1000000));
for(int i = 0; i < al.size(); i++)
{
System.out.println(al.get(i));
}
通用方式，迭代器。
printCollection(Collection c){
Iterator it = c.iterator();
while(it.hasNext())
{
it.next();
}
}
記住iterator()方式是在Collection接口中定義的，也就是說所有Collection接口的實現類都要實現這個方法。都可以通過它來遍歷，Set也一樣。
java.util.Collections是一個工具類，里面有很多靜態方法。
有一個給List排序的方法sort，static sort(List list)，另外一種重載形式static sort(List list,Comparator c)。記住可是對List接口的對象排序。
一個ArrayList內部是字符串的話，調用Collections.sort(al); 元素按照字母升序規則進行排序。如果是數字，從大到小。
排序這件事，由兩個部分組成，1，排序規則，2，算法。
算法，數據結構學過的幾種常見排序算法，冒泡，二叉樹，等，在Java中封裝了很多算法，不需要自己實現。
而規則，絕對需要自己來定義，尤其對于自定義類的對象的排序規則，也就是對象大小的依據。
兩種方式：
1自定義類實現java.lang.Comparable接口。覆蓋其public int compareTo(Object o)方法。
public int compareTo(Object o)
{
Student s = (Student)o;
if(this.age > s.age) return 1;
else if(this.age == s.age) return 0;
else return -1;
}或者對String 類型屬性，可以：
return this.name.compareTo(((Student)o).name);
2再寫一個類實現java.util.Comparator，比較器接口，實現自己的比較器。
實現public int compare(Object o1,Object o2)方法。
o1 > o2 返回正數
o1 = o2 返回0
o1 < o2 返回負數
還有一個boolean equals(Object obj)，用自己寫么？不用！從Object繼承就有了。
class MyComparator1 implements Comparator{
public int compare(Object o1, Object o2)
{
Student s1 = (Student)o1;
Student s2 = (Student)o2;
return s1.age - s2.age;
}
}
Collections.sort(List list, Comparator c)
這種方式可以定義多個排序規則，分別按照對象不同屬性排序。
第一種方式，在更改排序規則時，需要更改代碼，而第二種是一種擴展的方式。
使用比較器的方式，開發中很常見。
注意MyComparator1與Student類聯系很緊密，可以采用內部類的方式來實現。
import java.util.Comparator;
public class Employee {
public Employee() {
super();
}
public Employee(String name, int id, double salary)
{
this.name = name;
this.id = id;
this.salary = salary;
}
@Override
public boolean equals(Object o)
{
if(this == o)
return true;
if(o == null)
return false;
if(!(o instanceof Employee))
return false;
Employee e = (Employee)o;
if(this.name.equals(e.name)&& this.id == e.id && this.salary == e.salary)
return true;
else return false;
}
@Override
public String toString(){
return "Name: " + this.name + " ID: " + this.id;
}
public Comparator getNameCmp()
{
return new NameSorter();
}
public Comparator getIdCmp()
{
return new IdSorter();
}
private class NameSorter implements Comparator{
NameSorter(){}
public int compare(Object o1, Object o2) {
return ((Employee)o1).name.compareTo(((Employee)o2).name);
}
}
private class IdSorter implements Comparator{
IdSorter(){}
public int compare(Object o1, Object o2)
{
return ((Employee)o1).id - ((Employee)o2).id;
}
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getSalary() {
return salary;
}
public void setSalary(double salary) {
this.salary = salary;
}
private String name;
private int id;
private double salary;
}
import java.util.*;
public class TestSortEmployee {
public TestSortEmployee() {
super();
// TODO Auto-generated constructor stub
}
public static void main(String[] args)
{
List<Employee> l = new ArrayList<Employee>();
l.add(new Employee("HAC",6,2323.0));
l.add(new Employee("ABC",3,3244.0));
l.add(new Employee("FSA",7,5633.0));
Iterator<Employee> it = l.iterator();
System.out.println("before sort");
while(it.hasNext()){
Employee e = it.next();
System.out.println(e);
}
Collections.sort(l,new Employee().getNameCmp());
System.out.println("after sort");
for(Employee e : l)
{
System.out.println(e);
}
}
}
構建裝入固定類型的ArrayList。
public class MyArrayList extends ArrayList{
public boolean add(Object o){
if(o instanceof String)
return super.add(o);
else ruturn false;
}
}
JDK 5.0以后，可以使用范型來解決這個問題。很清楚，很方便，很安全。
LinkedList
底層為雙向循環鏈表
可以雙向找到前后的節點，最后頭尾鏈接，形成一個環狀。
特點：查尋效率低（從頭節點遍歷），插入刪除效率高。
ArrayList
底層為數組，刪除插入效率低，查詢效率高。
LinkedList，可用于構建堆棧，或者隊列。
import java.util.*;
class MyStack
{
private LinkedList ll=new LinkedList();
public void push(Object o)
{
ll.addFirst(o);
}
public Object pop()
{
return ll.removeFirst();
}
public boolean empty()
{
return ll.isEmpty();
}
public static void main(String[] args)
{
MyStack ms=new MyStack();
ms.push("one");
ms.push("two");
ms.push("three");
System.out.println(ms.pop());
System.out.println(ms.pop());
System.out.println(ms.empty());
}
}
只使用LinkedList的一端。
注意：java.util.Stack，這個現成的類，不要用，因為其父類是java.util.Vector，效率較低下。
import java.util.*;
class MyQueue
{
private LinkedList ll=new LinkedList();
public void put(Object o)
{
ll.addLast(o);
}
public Object get()
{
return ll.removeFirst();
}
public boolean empty()
{
return ll.isEmpty();
}
public static void main(String[] args)
{
MyQueue mq=new MyQueue();
mq.put("one");
mq.put("two");
mq.put("three");
System.out.println(mq.get());
System.out.println(mq.get());
System.out.println(mq.get());
System.out.println(mq.empty());
}
}
注意JDK 5.0中，已經提供現成的隊列類，無需自己實現。
Set接口有一個實現類，HashSet。
可以使用迭代器進行遍歷。
對于其中元素：
1.無序，增加的順序與遍歷結果順序無關。（實際有序，后面說）
2.元素不可重復。
HashSet，底層也是數組，它是如何插入數據的呢？
數組有一個長度，假設為6，hs.add(Object obj)操作進行時，先獲得obj的哈希碼，然后%6，也就是hashcode模數組長度，來決定該obj對象放入數組哪個位置。
如果恰巧兩個對象的hashcode模長度得到相同的值，那么就會先判斷這兩個對象是否相等，也就是調用對象的equals方法。如果真的不同，通過某種算法將后面的對象找一個新的位置放置。
所以對于自定義類，需要同時覆蓋hashCode()方法和equals方法。
兩個原則，1，保證相同對象的hashCode一定相同,(保證肯定要真正調用equals比較，否則直接就放入了)
2, 不同對象的hashCode盡可能不同。(hashCode相同情況出現，會使得HashSet效率急劇下降)
public int hashCode(){
return name.hashCode() + age;
}
public boolean equals(Object o)
{
...
}
HashSet特點，查詢效率高，插入效率高，刪除效率高。抱著這些的是犧牲了空間，因為那個底層的數組為保證不沖突，可能初始開辟一個極其大的長度。
問題：1無序（遍歷出來的順序是那個底層數組存放的順序）
2.明顯用空間換時間。
hashCode和equals覆蓋，缺一不可。
SortedSet子接口有一個實現類TreeSet，自動對元素排序。
可用迭代器遍歷。
不允許元素重復。
增加元素自動排序。
注意，不再需要hashCode+equals方法來判斷對象重復了，而是使用比較器，或者實現Comparable接口的compareTo()方法。
Map接口 與Collection接口無關系，它表示的集合，內部每個元素是一個鍵-值對。
把一系列對象通過一個關鍵字來存放，key不能重復，value可重復。
Map m = new HashMap();
put(Object key, Object value)存放鍵和值,返回值為Object。
遍歷方法，通過Map接口提供的keySet()方法，會返回一個Set類型無序集合，存放著key對象（KEY不重復阿，所以是一個Set）。
Set s = m.keySet();
Iterator it = s.iterator();
while(it.hasNext()){
Object key = it.next();
Object value = m.get(key);
}
如果key值被認定重復，后面添加的key重復的紀錄會覆蓋前面的紀錄，不報錯，并把替換掉的value對象作為返回值返回，key不重復時，返回為null。
那么又會有一問題，Map是如何判斷key對象是否重復的呢？尤其對于自定義類的對象。
HashMap底層也是數組。
說到這，得先回過去，說說HashSet，因為實際上察看源碼發現，它的內部實際上有一個HashMap作為支持，實現元素的不可重復。只不過它使用key部分，value部分為一個final的Object()。（TreeSet與TreeMap也是這樣）。
所以，如果key對象為自定義類對象，那么它需要覆蓋equals()和hashCode()。
一個接口，有很多實現類，如何選擇，在于人的編程經驗。
List（有序）vs Set(無序) vs Map(鍵值)
對于TreeMap和TreeSet，只在需要排序時，使用一下，因為他們每次插入新元素，都會重新排序。
Hashtable，1.3以前使用，使用Enumeration遍歷，線程安全，重量級組建。
TreeMap對于元素排序，是需要該類實現Comparable接口，實現compareTo方法的。它可以通過該方法判斷倆個自定義類對象是否相同，并且進行排序。
=========================================
開發經驗，一旦程序中使用，HashMap，Key放入的自定義類的對象，一定要覆蓋hashCode和equals方法，因為取數據，也需要這兩個方法。
posted on 2005-12-06 23:13
北國狼人的BloG 閱讀(915)
評論(1) 編輯 收藏 所屬分類:
達內學習總結