簡介

集合和數(shù)組的區(qū)別：

數(shù)組存儲基礎(chǔ)數(shù)據(jù)類型，且每一個數(shù)組都只能存儲一種數(shù)據(jù)類型的數(shù)據(jù)，空間不可變。

集合存儲對象，一個集合中可以存儲多種類型的對象?？臻g可變。

嚴格地說，集合是存儲對象的引用，每個對象都稱為集合的元素。根據(jù)存儲時數(shù)據(jù)結(jié)構(gòu)的不同，分為幾類集合。但對象不管存儲到什么類型的集合中，既然集合能存儲任何類型的對象，這些對象在存儲時都必須向上轉(zhuǎn)型為Object類型，也就是說，集合中的元素都是Object類型的對象。

既然是集合，無論分為幾類，它都有集合的共性，也就是說雖然存儲時數(shù)據(jù)結(jié)構(gòu)不一樣，但該有的集合方法還是得有。在java中，Collection接口是集合框架的根接口，所有集合的類型都實現(xiàn)了此接口或從其子接口中繼承。

Collection接口

根據(jù)數(shù)據(jù)結(jié)構(gòu)的不同，一些collection允許有重復(fù)的元素，而另一些則不允許。一些collection是有序的，而另一些則是無序的。

Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的"子接口"如List和Set。也就是說，無法直接new一個collection對象，而是只能new一個實現(xiàn)Collection類的子接口的對象，如new ArrayList();。

所有的Collection類都必須至少提供兩個構(gòu)造方法：無參數(shù)構(gòu)造方法構(gòu)造一個空集合；帶Collection參數(shù)的構(gòu)造方法構(gòu)造一個包含該Collection內(nèi)容的集合。例如，ArrayList就有3個構(gòu)造方法，其中之二就滿足這兩個構(gòu)造方法的要求。

Collection是java.util包中的類，因此要實現(xiàn)集合的概念，需要先導(dǎo)入該包。

ArrayList繼承自List接口，List接口又繼承自Collection接口。ArrayList類存儲的集合中，元素有序、可重復(fù)。

import java.util.*;
Collection coll = new ArrayList();

因為Collection接口不允許直接實現(xiàn)，因此需要通過實現(xiàn)它的子類來實現(xiàn)集合的概念，此處創(chuàng)建的是ArrayList對象，使用了父類引用，好處是擴展性較好。

Collection有一些集合的通用性操作方法，分為兩類：一類是普通方法；一類是帶有All的方法，這類方法操作的是集合。

add()：向集合的尾部插入元素，返回值類型為boolean，插入成功返回true。注意集合只能存儲對象(實際上是對象的引用)。

import java.util.*;
//
public class TestColl {
	public static void main(String[] args) {
		Collection coll = new ArrayList();
		coll.add("abcd");
		//插入字符串對象
		coll.add(123);
		//插入Int對象
		coll.add(123);
		coll.add(new Student("Gaoxiaof",23));
		//插入Student對象
		coll.add(new Student("Gaoxiaof",23));
		//插入另一個Student對象
		System.out.println(coll);
		//直接輸出集合中的元素，得到結(jié)果[abcd,123,123,Gaoxiaof 23,Gaoxiaof 23]
	}
}
//
class Student {
	private String name;
	private int age;
	Student(String name,int n) {
		this.name = name;
		this.age = n;
	}
	public String getName() {
		return this.name;
	}
	public int getAge() {
		return this.age;
	}
	public String toString() {
		return this.name + " " + this.age;
	}
}

上面插入的"abcd"和"123"都是經(jīng)過自動裝箱轉(zhuǎn)換為對象后存儲在集合中的。其中兩個add(123)是重復(fù)的對象元素，因為判斷集合中的元素是否重復(fù)的唯一方法是equals方法是否返回0。Integer已經(jīng)重寫過equals()。而后面的兩個Student對象是不同對象，因為Student類中沒有重寫equals()方法，所以它們是不重復(fù)的元素。

remove()：刪除集合中首次出現(xiàn)的元素。確定是否能刪除某個元素，唯一的方法是通過equals()方法確定對象是否相等，相等時刪除才返回true。

Collection coll = new ArrayList();
coll.add("abcd");
coll.add(new Integer(128));
coll.add(new Student("Gaoxiaofang",23));
System.out.println(coll.remove(new Integer(128))); //true
coll.remove(new Student("Gaoxiaofang",23));     //false，因為沒有重寫equals()
System.out.println(coll);  //return: [abcd,Gaoxiaofang 23]

clear()：清空該集合中的所有元素。
contains(object obj)：是否包含某對象元素。判斷的依據(jù)仍然是equals()方法。

Collection coll = new ArrayList();
coll.add(new Integer(128));
System.out.println(coll.contains(new Integer(128))); //true

isEmpty()：集合是否不包含任何元素。
size()：返回該集合中元素的個數(shù)。
equals(Object obj)：比較兩個集合是否完全相等。依據(jù)是集合中的所有元素都能通過各自的equals得到相等的比較。
addAll(Collection c)：將整個集合c中的元素都添加到該集合中。
containsAll(Collection c)：該集合是否包含了c集合中的所有元素，即集合c是否是該集合的子集。
removeAll(Collection c)：刪除該集合中那些也包含在c集合中的元素。即刪除該集合和c集合的交集元素。
retainAll(Collection c)：和removeAll()相反，僅保留該集合中和集合c交集部分的元素。
iterator(Collection c)：返回此集合中的迭代器，注意返回值類型為Iterator。迭代器用于遍歷集合。見下文。

Iterator通用迭代器

因為不同類型的集合存儲數(shù)據(jù)時數(shù)據(jù)結(jié)構(gòu)不同，想要寫一個通用的遍歷集合的方法是不現(xiàn)實的。但無論是哪種類型的集合，只有集合自身對集合中的元素是最了解的，因此在實現(xiàn)Collection接口時，不同集合類都實現(xiàn)了自己獨有的遍歷方法，這稱為集合的迭代器Iterator。其實Collection繼承了java.lang.Iterable接口，該接口只提供了一個方法：iterator()，只要是實現(xiàn)了這個接口的類就表示具有迭代的能力，也就具有foreach增強遍歷的能力。

迭代器自身是一個接口，通過Collection對象的iterator()方法就可以獲取到對應(yīng)集合類型的迭代器。例如：

Collection coll = new ArrayList();
Iterator it = coll.iterator(); //獲取對應(yīng)類型的集合的迭代器

Iterator接口提供了3個方法：

hasNext()：判斷是否有下一個元素。
Next()：獲取下一個元素。注意它返回的是Object(暫不考慮泛型)類型。
remove()：移除迭代器最后返回的一個元素。此方法為Collection迭代過程中修改元素的唯一安全的方法。

雖然有不同種類型的集合，但迭代器的迭代方法是通用的。例如，要遍歷coll集合中的元素。

import java.util.*;
public class TestColl {
  public static void main(String[] args) {
    Collection coll = new ArrayList();
    coll.add("abcd");
    coll.add(new Integer(129));
    coll.add(new Student("Gaoxiaofang",23));
    Iterator it = coll.iterator();  
     while (it.hasNext()) {       //Iterator遍歷的方法
      System.out.println(it.next()); //return:abcd,129,Gaoxiaofang 23
    } 
  }
}
class Student {
  private String name;
  private int age;
  Student(String name,int n) {
    this.name = name;
    this.age = n;
  }
  public String getName() {
    return this.name;
  }
  public int getAge() {
    return this.age;
  }
  public String toString() {
    return this.name + " " + this.age;
  }
}

但是通常來說，上面的遍歷方式雖然正確，但下面的遍歷方式更佳。因為it對象只用于集合遍歷，遍歷結(jié)束后就應(yīng)該消失，所以將其放入到for循環(huán)的內(nèi)部，由于for循環(huán)的第三個表達式缺失，所以不斷地循環(huán)第二個表達式即可。

for (Iterator it = coll.iterator();it.hasNext();) {
System.out.println(it.next());
}

通過Iterator遍歷到的元素是集合中的一個對象，對象也是有屬性的。如何引用這些屬性？只需將遍歷出的元素作為對象來使用即可，但由于next()返回的元素都是Object對象，直接操作這個元素對象無法獲取對應(yīng)元素中的特有屬性。因此必須先強制對象類型轉(zhuǎn)換。

例如，獲取coll中為Student對象元素的name屬性，并刪除非Student對象的元素。

Collection coll = new ArrayList();
coll.add("abcd");
coll.add(new Integer(129));
coll.add(new Student("Gaoxiaofang",23));

for (Iterator it = coll.iterator();it.hasNext();) {
  Object obj = it.next();
  if (obj instanceof Student) {
    Student s = (Student)obj;
    System.out.println(s.getName()); //return: Gaoxiaofang
  } else {
    it.remove();
  }
}
System.out.println(coll);        //return: [Gaoxiaofang 23]

因為集合中有些非Student對象元素，因此需要判斷it.next()是否滿足instanceof的要求，但不能直接寫為下面的代碼：

for (Iterator it = coll.iterator();it.hasNext();) {
  if (it.next() instanceof Student) {
    Student s = (Student)it.next();
    System.out.println(s.getName());
  }
}

因為每執(zhí)行一次it.next()，元素的游標指針就向下滑動1，在這個寫法中if判斷表達式中使用了一次it.next()，在if的代碼塊中又調(diào)用了一次it.next()。所以應(yīng)該將it.next()保存到對象變量中。而it.next()返回的類型是Object類型，因此定義Object obj = it.next()。

只有remove()方法是Iterator迭代器迭代過程中修改集合元素且安全的方法。以迭代時add()為例，當(dāng)開始迭代時，迭代器線程獲取到集合中元素的個數(shù)，當(dāng)?shù)^程中執(zhí)行add()時，它將采用另一個線程來執(zhí)行(因為add()方法不是Iterator接口提供的方法)，結(jié)果是元素個數(shù)就增加了，且導(dǎo)致新增的元素?zé)o法確定是否應(yīng)該作為迭代的一個元素。這是不安全的行為，因此會拋出ConcurrentModificationException異常。而remove()方法是迭代器自身的方法，它會使用迭代器線程來執(zhí)行，因此它是安全的。

對于List類的集合來說，可以使用Iterator的子接口ListIterator來實現(xiàn)安全的迭代，該接口提供了不少增刪改查List類集合的方法。

List接口

List接口實現(xiàn)了Collection接口。

List接口的數(shù)據(jù)結(jié)構(gòu)特性是：

1.有序列表，且?guī)饕齣ndex。所謂有序指先后插入的順序，即Index決定順序。而向Set集合中插入數(shù)據(jù)會被打亂
2.大小可變。
3.數(shù)據(jù)可重復(fù)。
4.因為有序和大小可變，使得它除了有Collection的特性，還有根據(jù)index精確增刪改查某個元素的能力。
5.實現(xiàn)List接口的兩個常用類為：
(1).ArrayList：數(shù)組結(jié)構(gòu)的有序列表；
1).長度可變，可變的原因是在減少或添加元素時部分下標整體減一或加一，如果已分配數(shù)組空間不夠，則新創(chuàng)建一個更大的數(shù)組，并拷貝原數(shù)組的內(nèi)存(直接內(nèi)存拷貝速度極快)；
2).查詢速度快，增刪速度慢。查詢快是因為內(nèi)存空間連續(xù)，增刪速度慢是因為下標移動。
3).除了ArrayList是不同步列表，它幾乎替代了Vector類。
(2).LinkedList：鏈表結(jié)構(gòu)的有序列表；
1).不同步；
2).增刪速度快，查詢速度慢。增刪速度快的原因是只需修改下鏈表中前后兩個元素的索引指向即可；
3).能夠?qū)崿F(xiàn)堆棧(后進先出LIFO,last in first out)、隊列(queue,通常是FIFO,first in first out)和雙端隊列(double ends queue)。

ArrayList類的方法和List方法基本一致，所以下面介紹了List通用方法和ListIterator就沒必要介紹ArrayList。但LinkedList比較特殊，所以獨立介紹。

List接口通用方法

除了因為繼承了Collection而具有的通用方法外，對于List接口也有它自己的通用方法。一般List的這些通用方法針對的是序列的概念。有了序列和下標索引值，可以精確地操控某個位置的元素，包括增刪改查。

(1).增：add(index,element)
(2).刪：remove(index)、remove(obj)刪除列表中第一個obj元素
(3).改：set(index,element)
(4).查：get(index)
(5).indexOf(obj)：返回列表中第一次出現(xiàn)obj元素的索引值，如不存在則返回-1
(6).lastIndexOf(obj)
(7).subList(start,end)：返回列表中從start到end(不包括end邊界)中間的元素組成列表。注意返回的是List類型。
(8).listIterator()：返回從頭開始遍歷的List類集合的迭代器ListIterator。
(9).listIterator(index)：返回從index位置開始遍歷的List結(jié)合迭代器ListIterator。
因為有了get()方法，除了Iterator迭代方式，還可以使用get()方法遍歷集合：

List l = new ArrayList();
for (int i=0;i<l.size();i++) {
  System.out.println(l.get(i));
}

但注意，這種方法不安全，因為l.size()是即時改變的，如果增刪了元素，size()也會隨之改變。

示例：

import java.util.*;
public class TestList {
	public static void main(String[] args) {
		List ls = new ArrayList();
		ls.add(new Student("Malong1",21));
		ls.add(new Student("Malong2",22));
		ls.add(1,new Student("Malong3",23));
		//[Malong1 21,Malong3 23,Malong2 22]
		System.out.println(ls.indexOf(new Student("Malong3",23)));
		// return:1
		ls.set(2,new Student("Gaoxiao1",22));
		//[Malong1 21,Malong3 23,Gaoxiao1 22]
		for (Iterator it = l.iterator();it.hasNext();) {
			//第一種迭代
			Student stu = (Student)it.next();
			if (stu.getAge() == 22) {
				it.remove();
				// the safe way to operate element
				//ls.add(new Student("Malong4",24)); //throw ConcurrentModificationException
			}
		}
		//[Malong1 21,Malong3 23]
		System.out.println(l+"\n---------------");
		for (int i=0;i<ls.size();i++) {
			//第二種迭代
			System.out.println(ls.get(i));
		}
	}
}
class Student {
	private String name;
	private int age;
	Student(String name,int n) {
		this.name = name;
		this.age = n;
	}
	public String getName() {
		return this.name;
	}
	public int getAge() {
		return this.age;
	}
	//override toString()
	public String toString() {
		return this.name + " " + this.age;
	}
	//override equals()
	public Boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (!(obj instanceof Student)) {
			throw new ClassCastException("Class error");
		}
		Student stu = (Student)obj;
		return this.name.equals(stu.name) && this.age == stu.age;
	}
}

上面的代碼中，如果將ls.add(new Student("Malong4",24));的注釋取消，將拋出異常，因為Iterator迭代器中唯一安全操作元素的方法是Iterator接口提供的remove()，而add()方法是List接口提供的，而非Iterator接口的方法。但對于List集合類來說，可以使用ListIterator迭代器，它提供的操作元素的方法更多，因為是迭代器提供的方法，因此它們操作元素時都是安全的。

List集合的迭代器ListIterator

通過listIterator()方法可以獲取ListIterator迭代器。該迭代器接口提供了如下幾種方法：

hasNext()：是否有下一個元素
hasPrevious()：是否有前一個元素，用于逆向遍歷
next()：獲取下一個元素
previour()：獲取前一個元素，用于逆向遍歷
add(element)：插入元素。注：這是迭代器提供的add()，而非List提供的add()
remove()：移除next()或previous()獲取到的元素。注：這是迭代器提供的remove()，而非List提供的remove()
set(element)：設(shè)置next()或previour()獲取到的元素。注：這是迭代器提供的set()，而非List提供的set()

例如：前文示例在Iterator迭代過程中使用List的add()添加元素拋出了異常，此處改用ListIterator迭代并使用ListIterator提供的add()方法添加元素。

List l = new ArrayList();
l.add(new Student("Malong1",21));
l.add(new Student("Malong2",22));
l.add(1,new Student("Malong3",23)); //[Malong1 21,Malong3 23,Malong2 22]
l.set(2,new Student("Gaoxiao1",22));//[Malong1 21,Malong3 23,Gaoxiao1 22]

for (ListIterator li = l.listIterator();li.hasNext();) {
  Student stu = (Student)li.next();
  if (stu.getAge() == 22) {
    //l.add(new Student("Malong4",24));  //throw ConcurrentModificationException
    li.add(new Student("Malong4",24));
  }
}

LinkedList集合

LinkedList類的數(shù)據(jù)結(jié)構(gòu)是鏈表類的集合。它可以實現(xiàn)堆棧、隊列和雙端隊列的數(shù)據(jù)結(jié)構(gòu)。其實實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)都是通過LinkedList提供的方法按照不同邏輯實現(xiàn)的。

提供的其中幾個方法如下：因為是實現(xiàn)了List接口，所以除了下面的方法，還有List接口的方法可用。

addFirst(element)：向鏈表的首部插入元素
addLast(element)：向鏈表的尾部插入元素
getFirst()：獲取鏈表的第一個元素
getLast()：獲取鏈表最后一個元素
removeFirst()：移除并返回第一個元素，注意返回的是元素
removeLast()：移除并返回最后一個元素，注意返回的是元素
LinkedList模擬隊列數(shù)據(jù)結(jié)構(gòu)

隊列是先進先出FIFO的數(shù)據(jù)結(jié)構(gòu)。封裝的隊列類MyQueue代碼如下：

import java.util.*;
class MyQueue {
	private LinkedList mylist;
	MyQueue() {
		mylist = new LinkedList();
	}
	// add element to queue
	public void add(Object obj) {
		mylist.addFirst(obj);
		//Fisrt In
	}
	//get element from queue
	public Object get() {
		return mylist.removeLast();
		//First Out
	}
	//queue is null?
	public Boolean isNull() {
		return mylist.isEmpty();
	}
	//the size of queue
	public int size() {
		return mylist.size();
	}
	//remove element in queue by index
	public Boolean remove(int index) {
		if(this.size()-1 < index) {
			throw new IndexOutOfBoundsException("index too large!");
		}
		mylist.remove(index);
		return true;
	}
	//remove the first appearance element in queue by Object
	public Boolean remove(Object obj) {
		return mylist.remove(obj);
	}
	public String toString() {
		return mylist.toString();
	}
}

操作該隊列數(shù)據(jù)結(jié)構(gòu)程序代碼如下：

import java.util.*;

public class FIFO {
  public static void main(String[] args) {
    MyQueue mq = new MyQueue();
    mq.add("Malong1");
    mq.add("Malong2");
    mq.add("Malong3");
    mq.add("Malong4");  //[Malong4,Malong3,Malong2,Malong1]
    System.out.println(mq.size()); //return:4
    mq.remove(2);          //[Malong4,Malong3,Malong1]
    mq.remove("Malong1");      //[Malong4,Malong3]
    System.out.println(mq);

    while (!mq.isNull()) {
      System.out.println(mq.get());
    }
  }
}

Set接口

Set接口也實現(xiàn)了Collection接口。它既然能單獨成類，它和List集合的數(shù)據(jù)結(jié)構(gòu)一定是大有不同的。

Set接口的數(shù)據(jù)結(jié)構(gòu)特性是：

1.Set集合中的元素?zé)o序。這里的無序是相對于List而言的，List的有序表示有下標Index的順序，而Set無需是指沒有index也就沒有順序。
2.Set集合中的元素不可重復(fù)。
3.因為無序，因此Set集合中取出元素的方法只有一種：迭代。
4.實現(xiàn)Set接口的兩個常見類為：
(1).HashSet：hash表數(shù)據(jù)結(jié)構(gòu)；
1).不同步；
2).查詢速度快；
3).判斷元素是否重復(fù)的唯一方法是：先調(diào)用hashcode()判斷對象是否相同，相同者再調(diào)用equals()方法判斷內(nèi)容是否相同。所以，要將元素存儲到此數(shù)據(jù)結(jié)構(gòu)的集合中，必須重寫hashcode()和equals()。
(2).TreeSet：二叉樹數(shù)據(jù)結(jié)構(gòu)；
1).二叉樹是用來排序的，因此該集合中的元素是有序的。這個有序和List的有序概念不同，此處的有序指的是存儲時對元素進行排序，例如按照字母順序，數(shù)字大小順序等，而非index索引順序。
2).既然要排序，而equals()方法只能判斷是否相等。因此數(shù)據(jù)存儲到TreeSet集合中時需要能夠判斷大小。
3).有兩種方法用于構(gòu)造有序的TreeSet集合：
a.待存儲對象的類實現(xiàn)Comparable接口并重寫它的compareTo()方法；
b.在構(gòu)造TreeSet集合時指定一個比較器comparator。這個比較器需要實現(xiàn)Comparator接口并重寫compare()方法。
(3).LinkedHashSet：鏈表形式的HashSet，僅在HashSet上添加了鏈表索引。因此此類集合有序(Linked)、查詢速度快(HashSet)。不過很少使用該集合類型。

HashSet集合

HashSet的用法沒什么可解釋的，方法都繼承自Set再繼承自Collection。需要說明的是它的無序性、不可重復(fù)性、計算hash值時的方法以及判斷重復(fù)性時的方法。

import java.util.*;

public class TestHashSet {
  public static void main(String[] args) {
    Set s = new HashSet();
    s.add("abcd4");
    s.add("abcd1");
    s.add("abcd2");
    s.add("abcd3");
    s.add("abcd1"); //重復(fù)

    for (Iterator it = s.iterator();it.hasNext();) {
      Object obj = it.next();
      System.out.println(obj);
    }
  }
}

得到的結(jié)果是無序且元素是不可重復(fù)的：

abcd2
abcd3
abcd4
abcd1

這里判斷字符串對象是否重復(fù)的方法是先調(diào)用String的hashcode()進行判斷，如果相同，再調(diào)用String的equals()方法。其中String的hashcode()方法在計算hash值時，是根據(jù)每個字符計算的，相同字符位置處的相同字符運算結(jié)果相同。

所以上面幾個字符串對象中，前綴"abcd"子串部分的hash運算結(jié)果相同，最后一個字符決定了這些字符串對象是否相同。插入時有兩個"abcd1"，所以總共調(diào)用了一次String的equals()方法。

如果是存儲自定義的對象，如Student對象，該對象定義方式如下：

class Student {
  String name;
  int age;
  Student(String name,int n) {
    this.name = name;
    this.age = n;
  }

  //override toString()
  public String toString() {
    return this.name + " " + this.age;
  }

  //override equals()
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (!(obj instanceof Student)) {
      return false;
    }
    Student stu = (Student)obj;
    return this.name.equals(stu.name) && this.age == age;
  }
}

即使重寫了equals()，插入屬性相同的Student對象到HashSet中時，也會認為不重復(fù)的。

import java.util.*;

public class TestHashSet {
  public static void main(String[] args) {
    Set s = new HashSet();
    s.add(new Student("Malong1",21));
    s.add(new Student("Malong1",21));
    s.add(new Student("Malong1",21));

    for (Iterator it = s.iterator();it.hasNext();) {
      Object obj = it.next();
      System.out.println(obj);
    }
  }
}

結(jié)果：

Malong1 21
Malong1 21
Malong1 21

這是因為HastSet集合的底層首先調(diào)用Student的hashcode()方法，而Student沒有重寫該方法，而是繼承自O(shè)bject，所以每個對象的hashcode()都不相同而直接插入到集合中。

因此，需要重寫Student的hashcode()方法。以下是一種重寫方法：

public int hashCode() {
  return this.name.hashCode() + age*31; //31可以是任意數(shù)，但不能是1或0。
}

如果不加上"age*31"，那么name部分的hash值有可能是相同的，但這很可能不是同一Student對象，所以應(yīng)該加上age屬性作為計算hash值的一部分元素。但不能直接加age，因為這樣會導(dǎo)致"new Student("lisi3",23)"和"new Student("lisi2",24)"的hashcode相同(3+23=2+24)，因此需要為age做一些修改，例如乘一個非0和1的整數(shù)。

在Student中重寫hashCode()后，再插入下面這些Student對象，就能相對精確地判斷是否為同一個Student元素。

s.add(new Student("lisi1",21));
s.add(new Student("lisi1",21)); //此處將調(diào)用equals()，且最終判斷為重復(fù)對象
s.add(new Student("lisi2",24));
s.add(new Student("lisi3",23)); //此處將調(diào)用equals()
s.add(new Student("Gaoxiao1",23));
s.add(new Student("Gaoxiao2",21));
s.add(new Student("Gaoxiao3",22));

結(jié)果：

lisi1 21
Gaoxiao1 23
Gaoxiao3 22
lisi2 24
lisi3 23
Gaoxiao2 21

LinkedHashSet集合

鏈表順序的HashSet集合，相比HashSet，只需多記錄一個鏈表索引即可，這就使得它保證了存儲順序和插入順序相同。實現(xiàn)方式除了new對象時和HashSet不一樣，其他任何地方都是一樣的。

import java.util.*;

public class TestHashSet {
  public static void main(String[] args) {
    Set s = new LinkedHashSet();

    s.add(new Student("lisi1",21));
    s.add(new Student("lisi1",21));
    s.add(new Student("lisi2",24));
    s.add(new Student("lisi3",23));
    s.add(new Student("Gaoxiao1",23));
    s.add(new Student("Gaoxiao3",21));
    s.add(new Student("Gaoxiao2",22)); 

    for (Iterator it = s.iterator();it.hasNext();) {
      Object obj = it.next();
      System.out.println(obj);
    }
  }
}

結(jié)果：

lisi1 21
lisi2 24
lisi3 23
Gaoxiao1 23
Gaoxiao3 21
Gaoxiao2 22

TreeSet集合

TreeSet集合以二叉樹數(shù)據(jù)結(jié)構(gòu)存儲元素。二叉樹保證了元素之間是排過序且相互唯一的，因此實現(xiàn)TreeSet集合最核心的地方在于對象之間的比較。

比較對象有兩種方式：一是在對象類中實現(xiàn)Comparable接口重寫compareTo()方法；二是定義一個專門用于對象比較的比較器，實現(xiàn)這個比較器的方法是實現(xiàn)Comparator接口并重寫compare()方法。其中Comparable接口提供的比較方法稱為自然順序，例如字母按照字典順序，數(shù)值按照數(shù)值大小順序。

無論是哪種方式，每個待插入的元素都需要先轉(zhuǎn)型為Comparable，確定了將要存儲在二叉樹上的節(jié)點位置后，然后再轉(zhuǎn)型為Object存儲到集合中。

插入String類對象。

由于String已經(jīng)重寫了compareTo()，因此下面插入String對象到TreeSet集合中沒有任何問題。

import java.util.*;
//
public class TestTreeSet {
 public static void main(String[] args) {
   Set t = new TreeSet();

   t.add("abcd2");
   t.add("abcd11");
   t.add("abcd3");
   t.add("abcd1");
   //t.add(23);
   //t.add(21);
   //t.add(21);

   for (Iterator it = t.iterator();it.hasNext();) {
     Object obj = it.next();
     System.out.println(obj);
   }
 }
}

但不能將上面"t.add(23)"等取消注釋，雖然Integer類也重寫了compareTo()，但在插入這些Integer類元素時，集合中已經(jīng)存在String類的元素，String類的compareTo()和Integer的compareTo()的比較方法不一樣，使得這兩類元素之間無法比較大小，也就無法決定數(shù)值類的元素插入到二叉樹的哪個節(jié)點。

插入實現(xiàn)了Comparable接口且重寫了compareTo()的自定義對象。
例如Student對象，如果沒有重寫compareTo()方法，將拋出異常，提示無法轉(zhuǎn)型為Comparable。

t.add(new Student("Malongshuai1",23));

結(jié)果：

Exception in thread "main" java.lang.ClassCastException: Student cannot be cast to java.lang.Comparable
   at java.util.TreeMap.compare(Unknown Source)
   at java.util.TreeMap.put(Unknown Source)
   at java.util.TreeSet.add(Unknown Source)
   at TestTreeSet.main(TestTreeSet.java:8)

所以，修改Student重寫compareTo()，在重寫應(yīng)該考慮哪個作為主排序?qū)傩裕膫€作為次要排序?qū)傩?。例如以name為主排序?qū)傩?，age為次排序?qū)傩?。compareTo()返回正數(shù)則表示大于，返回負數(shù)則表示小于，返回0則表示等于。如下：

class Student implements Comparable {
 String name;
 int age;
 Student(String name,int n) {
   this.name = name;
   this.age = n;
 }

 public String toString() {
   return this.name + " " + this.age;
 }

 public int compareTo(Object obj) {
   if (!(obj instanceof Student)) {
     throw new ClassCastException("Class cast wrong!");
   }
   Student stu = (Student)obj;
   // compare name first, then age
   int temp = this.name.compareTo(stu.name);
   return temp == 0 ? this.age - stu.age :temp; 
 }
}

于是插入Student時，將根據(jù)name中的字母順序，相同時再根據(jù)age大小順序，最后如果都相同，則認為元素重復(fù)，不應(yīng)該插入到集合中。

t.add(new Student("Malongshuai1",23));
t.add(new Student("Malongshuai3",21));
t.add(new Student("Malongshuai2",23));
t.add(new Student("Malongshuai1",23)); //重復(fù)
t.add(new Student("Malongshuai1",22));

結(jié)果：

Malongshuai1 22
Malongshuai1 23
Malongshuai2 23
Malongshuai3 21

使用比較器comparator實現(xiàn)排序。此時TreeSet的構(gòu)造方法為"TreeSet(Comparator comp)"。
當(dāng)使用了比較器后，插入數(shù)據(jù)時將默認使用比較器比較元素。

比較器是一個實現(xiàn)了java.util.Comparator接口并重寫了compare()方法的類，可以根據(jù)不同比較需求，創(chuàng)建不同的比較器。 例如創(chuàng)建一個根據(jù)age作為主排序?qū)傩?，name作為次排序?qū)傩缘谋容^器SortByAge，由于這個比較器是用來比較Student對象大小的，因此必須先轉(zhuǎn)型為Student。

import java.util.*;
//
public class SortByAge implements Comparator {
 public int compare(Object o1,Object o2) {
   //Cast to Student first
   if (!(o1 instanceof Student) || !(o2 instanceof Student)) {
     throw new ClassCastException("Wrong");
   }
   Student s1 = (Student)o1;
   Student s2 = (Student)o2;
   //compare age first, then name
   int temp = s1.age - s2.age;
   return temp == 0 ? s1.name.compareTo(s2.name) : temp;
 }
}

指定TreeSet的比較器為SortByAge，并插入一些Student對象：

public class TestTreeSet {
 public static void main(String[] args) {
   Set t = new TreeSet(new SortByAge());

   t.add(new Student("Malongshuai1",23));
   t.add(new Student("Malongshuai3",21));
   t.add(new Student("Malongshuai2",23));
   t.add(new Student("Malongshuai1",23)); //重復(fù)
   t.add(new Student("Malongshuai1",22));

   for (Iterator it = t.iterator();it.hasNext();) {
     Object obj = it.next();
     System.out.println(obj);
   }
 }
}

當(dāng)為TreeSet集合指定了比較器時，結(jié)果將先按照age順序再按照name排序的，盡管Student類中仍然重寫了compareTo()方法：

Malongshuai3 21
Malongshuai1 22
Malongshuai1 23
Malongshuai2 23

總結(jié)

以上就是本文關(guān)于集合框架(Collections Framework)詳解及代碼示例的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：

java集合中的list詳解

詳解java各種集合的線程安全

Java集合框架源碼分析之LinkedHashMap詳解

如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

最新評論