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