資訊專欄INFORMATION COLUMN
摘要：集合類簡介集合類包含在包下集合類存放的是對象的引用，而非對象本身。集合類型主要分為集，列表，映射。返回此有序集合中當前第一個最小的元素。集合中元素被訪問的順序取決于集合的類型。
Java集合類 1.簡介：
1.1 java集合類圖java集合類包含在java.util包下
集合類存放的是對象的引用，而非對象本身。
集合類型主要分為Set(集)，List(列表)，Map(映射)。
從上述類圖，自己整理出主要內容是如下：
2.集合詳解 2.1 HashSetHashSet是Set接口的一個子類
主要的特點是：
里面不能存放重復元素，元素的插入順序與輸出順序不一致
采用散列的存儲方法，所以沒有順序。
代碼實例：HashSetTest
package cn.swum;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class HashSetTest {
public static void main(String[] args) {
Set set = new HashSet();
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("f");
//插入重復元素，測試set是否可以存放重復元素
set.add("a");
set.add(null);
//插入重復null，看結果是否可以存放兩個null
set.add(null);
Iterator iter = set.iterator();
System.out.println("輸出的排列順序為：");
while (iter.hasNext()){
System.out.println( iter.next());
}
}
}
輸出結果：
小結：
2.2 LinkedHashSetHashSet存放的值無序切不能重復，可以存放null，但只能存放一個null值
HashSet 繼承AbstractSet，有兩個重要的方法，其中HashCode()和equals()方法,當對象被存儲到HashSet當中時，會調用HashCode()方法，獲取對象的存儲位置。
HashSet集合判斷兩個元素相等的標準是兩個對象通過equals方法比較相等，并且兩個對象的hashCode()方法返回值相等。
LinkedHashSet是HashSet的一個子類
只是HashSet底層用的HashMap，
而LinkedHashSet底層用的LinkedHashMap
LinkedHashSet代碼實例:
package cn.swum;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetTest {
public static void main(String[] args) {
Set set = new LinkedHashSet();
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
System.out.println("LinkedHashSet存儲值得排序為：");
for (Iterator iter = set.iterator();iter.hasNext();){
System.out.println(iter.next());
}
}
}
輸出結果：
小結：
2.3 SortedSet（接口）此時，LinkedHashSet中的元素是有序的
SortedSet是一個接口，里面（只有TreeSet這一個實現可用）的元素一定是有序的。
保證迭代器按照元素遞增順序遍歷的集合，
可以按照元素的自然順序（參見?Comparable）進行排序，?或者按照創建有序集合時提供的?Comparator進行排序
其源碼如下：
public interface SortedSet2.4 TreeSetextends Set {? //返回與此有序集合關聯的比較器，如果使用元素的自然順序，則返回 null。? Comparator comparator();? //返回此有序集合的部分元素，元素范圍從 fromElement（包括）到 toElement（不包括）。? SortedSet subSet(E fromElement, E toElement);? //用一個SortedSet, 返回此有序集合中小于end的所有元素。? SortedSet headSet(E toElement);? //返回此有序集合的部分元素，其元素大于或等于 fromElement。? SortedSet tailSet(E fromElement); //返回此有序集合中當前第一個（最小的）元素。? E first(); ? //返回此有序集合中最后一個（最大的）元素? E last(); }
TreeSet類實現Set?接口，該接口由TreeMap?實例支持，此類保證排序后的?set?按照升序排列元素，
?根據使用的構造方法不同，可能會按照元素的自然順序?進行排序（參見?Comparable或按照在創建?set?時所提供的比較器進行排序。
Set?接口根據?equals?操作進行定義，但?TreeSet?實例將使用其?compareTo（或?compare）方法執行所有的鍵比較
代碼實例TreeSetTest：
package cn.swum;
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetTest {
static class Person{
int id;
String name;
int age;
public Person(int id, String name, int age){
this.id = id;
this.name = name;
this.age = age;
}
public String toString(){
return "id:"+ this.id + " " + "name:" + this.name +" " + "age:" + this.age;
}
}
static class MyComparator implements Comparator {
@Override
public int compare(Person p1, Person p2) {
if(p1 == p2) {
return 0;
}
if(p1 != null && p2 == null) {
return 1;
}else if(p1 == null && p2 != null){
return -1;
}
if(p1.id > p2.id){
return 1;
}else if(p1.id < p2.id){
return -1;
}
return 0;
}
}
public static void main(String[] args) {
MyComparator myComparator = new MyComparator();
TreeSet treeSet = new TreeSet<>(myComparator);
treeSet.add(new Person(3,"張三",20));
treeSet.add(new Person(2,"王二",22));
treeSet.add(new Person(1,"趙一",18));
treeSet.add(new Person(4,"李四",29));
//增加null空對象
treeSet.add(null);
System.out.println("TreeSet的排序是：");
for (Person p : treeSet){
if(p == null){
System.out.println(p);
}else {
System.out.println(p.toString());
}
}
}
}
實例用TreeSet保存對象引用，并且實現Comparator中compare方法進行比較和排序
輸出結果：
表明TreeSet是可以按照自定義方法中的比較進行排序的，且可以有空值。
?2.5 VectorVector 類也是基于數組實現的隊列，代碼與ArrayList非常相似。
線程安全，執行效率低。
動態數組的增長系數
由于效率低，并且線程安全也是相對的，因此不推薦使用vector
2.6 StackStack 是繼承了Vector，是一個先進后出的隊列
Stack里面主要實現的有一下幾個方法：
| 方法名 | 返回類型 | 說明 |
|---|---|---|
| empty | boolean | 判斷stack是否為空 |
| peek | E | 返回棧頂端的元素 |
| pop | E | 彈出棧頂的元素 |
| push | E | 將元素壓入棧 |
| search | int | 返回最靠近頂端的目標元素到頂端的距離 |
代碼實例StackTest：
package cn.swum;
import java.util.Stack;
public class StackTest {
static class Person{
int id;
String name;
int age;
public Person(int id, String name, int age){
this.id = id;
this.name = name;
this.age = age;
}
public String toString(){
return "id:"+ this.id + " " + "name:" + this.name +" " + "age:" + this.age;
}
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(new Person(1,"趙一",18));
stack.push(new Person(2,"王二",19));
stack.push(new Person(3,"張三",20));
stack.push(new Person(4,"李四",21));
System.out.println("棧頂元素是:(" + stack.peek() + ")");
System.out.println("目標元素離棧頂多少距離:" + stack.search(stack.get(0)));
System.out.println("棧元素從棧頂到棧底的排序是:");
//此處先用size保存是因為pop時，size會減1，
// 如果直接stack.size放在循環中比較，只能打印一半對象
int size = stack.size();
for (int i = 0; i < size ; i++) {
Person p = (Person) stack.pop();
System.out.println(p.toString());
}
}
}
輸出結果：
Stack 是一個有序的棧，遵循先進后出原則。
2.7 ArrayListArrayList是List的子類，它和HashSet相反，允許存放重復元素，因此有序。
集合中元素被訪問的順序取決于集合的類型。
如果對ArrayList進行訪問，迭代器將從索引0開始，每迭代一次，索引值加1。
然而，如果訪問HashSet中的元素，每個元素將會按照某種隨機的次序出現。
雖然可以確定在迭代過程中能夠遍歷到集合中的所有元素，但卻無法預知元素被訪問的次序。
代碼實例：ArrayListTest
package cn.swum;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
public class ArrayListTest {
public static void main(String[] args) {
List arrayList = new ArrayList();
arrayList.add("a");
arrayList.add("b");
arrayList.add("c");
//添加重復值
arrayList.add("a");
arrayList.add("d");
arrayList.add("e");
//添加null
arrayList.add(null);
System.out.println("arrayList的輸出順序為:");
for (int i = 0; i < arrayList.size(); i++) {
System.out.println((i+1) + ":" +arrayList.get(i));
}
}
}
輸出結果：
ArrayList是一個有序且允許重復和空值的列表
2.8 LinkedListLinkedList是一種可以在任何位置進行高效地插入和刪除操作的有序序列。
代碼實例：LinkedListTest
package cn.swum;
import java.util.LinkedList;
/**
* @author long
* @date 2017/2/28
*/
public class LinkedListTest {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add("a");
linkedList.add("b");
linkedList.add("c");
linkedList.add("d");
linkedList.add("e");
linkedList.add(2,"2");
System.out.println("linkedList的輸出順序是:" + linkedList.toString());
linkedList.push("f");
System.out.println("push后，linkedList的元素順序:" + linkedList.toString());
linkedList.pop();
System.out.println("pop后，linkedList的所剩元素:" + linkedList.toString());
}
}
輸出結果：
LinkedList是有序的雙向鏈表，可以在任意時刻進行元素的插入與刪除，讀取效率低于ArrayList，插入效率高
pop和push操作都是在隊頭開始
2.9 HashMapHashMap的數據結構:
數組的特點是：尋址容易，插入和刪除困難；
而鏈表的特點是：尋址困難，插入和刪除容易。
哈希表結合了兩者的優點。
哈希表有多種不同的實現方法，可以理解將此理解為“鏈表的數組”
從上圖我們可以發現哈希表是由數組+鏈表組成的，一個長度為16的數組中，每個元素存儲的是一個鏈表的頭結點。那么這些元素是按照什么樣的規則存儲到數組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中:
12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數組下標為12的位置。然后每個線性的數組下存儲一個鏈表，鏈接起來。
首先HashMap里面實現一個靜態內部類Entry，其重要的屬性有 key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現的一個基礎bean.我們上面說到HashMap的基礎就是一個線性數組，這個數組就是Entry[]，Map里面的內容都保存在Entry[]里面。
HashMap的存取實現:
//存儲時: int hash = key.hashCode();// 這個hashCode方法這里不詳述,只要理解每個key的hash是一個固定的int值 int index = hash % Entry[].length; Entry[index] = value;
//取值時: int hash = key.hashCode(); int index = hash % Entry[].length; return Entry[index];
疑問：如果兩個key通過hash%Entry[].length得到的index相同，會不會有覆蓋的危險？
這里HashMap里面用到鏈式數據結構的一個概念。上面我們提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方，第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會后又進來一個鍵值對B，通過計算其index也等于0，現在怎么辦？
HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔心。也就是說數組中存儲的是最后插入的元素。
HashMapTest代碼實例，自我實現HashMap:
Entry.java
