一、集合類簡介
Java集合就像一種容器,可以把多個對象(實際上是對象的引用,但習慣上都稱對象)“丟進”該容器中。從Java 5 增加了泛型以後,Java集合可以記住容器中對象的數據類型,使得編碼更加簡潔、健壯。
Java集合大致可以分為兩大體系,一個是Collection,另一個是Map
- Collection :主要由List、Set、Queue接口組成,List代表有序、重複的集合;其中Set代表無序、不可重複的集合;Java 5 又增加了Queue體系集合,代表一種隊列集合實現。
- Map:則代表具有映射關係的鍵值對集合。
java.util.Collection下的接口和繼承類關係簡易結構圖:
java.util.Map下的接口和繼承類關係簡易結構圖:
其中,Java 集合框架中主要封裝的是典型的數據結構和算法,如動態數組、雙向鏈表、隊列、棧、Set、Map 等。
將集合框架挖掘處理,可以分為以下幾個部分
1) 數據結構
List
列表、Queue
隊列、Deque
雙端隊列、Set
集合、Map
映射
2) 比較器
Comparator
比較器、Comparable
排序接口
3) 算法
Collections
常用算法類、Arrays
靜態數組的排序、查找算法
4) 迭代器
Iterator
通用迭代器、ListIterator
針對 List
特化的迭代器
二、有序列表(List)
List集合的特點就是存取有序,可以存儲重複的元素,可以用下標進行元素的操作
List主要實現類:ArrayList、LinkedList、Vector、Stack。
2.1、ArrayList
ArrayList是一個動態數組結構,支持隨機存取,尾部插入刪除方便,內部插入刪除效率低(因為要移動數組元素);如果內部數組容量不足則自動擴容,因此當數組很大時,效率較低。
2.2、LinkedList
LinkedList是一個雙向鏈表結構,在任意位置插入刪除都很方便,但是不支持隨機取值,每次都只能從一端開始遍歷,直到找到查詢的對象,然後返回;不過,它不像 ArrayList 那樣需要進行內存拷貝,因此相對來說效率較高,但是因為存在額外的前驅和後繼節點指針,因此佔用的內存比 ArrayList 多一些。
2.3、Vector
Vector也是一個動態數組結構,一個元老級別的類,早在jdk1.1就引入進來類,之後在jdk1.2里引進ArrayList,ArrayList大部分的方法和Vector比較相似,兩者是不同的,Vector是允許同步訪問的,Vector中的操作是線程安全的,但是效率低,而ArrayList所有的操作都是異步的,執行效率高,但不安全!
關於Vector
,現在用的很少了,因為裏面的get
、set
、add
等方法都加了synchronized
,所以,執行效率會比較低,如果需要在多線程中使用,可以採用下面語句創建ArrayList對象
List<Object> list =Collections.synchronizedList(new ArrayList<Object>());
也可以考慮使用複製容器 java.util.concurrent.CopyOnWriteArrayList
進行操作,例如:
final CopyOnWriteArrayList<Object> cowList = new CopyOnWriteArrayList<String>(Object);
2.4、Stack
Stack是Vector的一個子類,本質也是一個動態數組結構,不同的是,它的數據結構是先進后出,取名叫棧!
關於Stack
,現在用的也很少,因為有個ArrayDeque
雙端隊列,可以替代Stack
所有的功能,並且執行效率比它高!
三、集(Set)
Set集合的特點:元素不重複,存取無序,無下標;
Set主要實現類:HashSet、LinkedHashSet和TreeSet。
3.1、HashSet
HashSet底層是基於 HashMap 的k
實現的,元素不可重複,特性同 HashMap。
3.2、LinkedHashSet
LinkedHashSet底層也是基於 LinkedHashMap 的k
實現的,一樣元素不可重複,特性同 LinkedHashMap。
3.3、TreeSet
同樣的,TreeSet也是基於 TreeMap 的k
實現的,同樣元素不可重複,特性同 TreeMap;
Set集合的實現,基本都是基於Map中的鍵做文章,使用Map中鍵不能重複、無序的特性;所以,我們只需要重點關注Map的實現即可!
四、隊列(Queue)
Queue是一個隊列集合,隊列通常是指“先進先出”(FIFO)的容器。新元素插入(offer)到隊列的尾部,訪問元素(poll)操作會返回隊列頭部的元素。通常,隊列不允許隨機訪問隊列中的元素。
Queue主要實現類:ArrayDeque、LinkedList、PriorityQueue。
4.1、ArrayDeque
ArrayQueue是一個基於數組實現的雙端隊列,可以想象,在隊列中存在兩個指針,一個指向頭部,一個指向尾部,因此它具有“FIFO隊列”及“棧”的方法特性。
既然是雙端隊列,那麼既可以先進先出,也可以先進后出,以下是測試例子!
先進先出
public static void main(String[] args) {
ArrayDeque<String> queue = new ArrayDeque<>();
//入隊
queue.offer("AAA");
queue.offer("BBB");
queue.offer("CCC");
System.out.println(queue);
//獲取但不出隊
System.out.println(queue.peek());
System.out.println(queue);
//出隊
System.out.println(queue.poll());
System.out.println(queue);
}
輸出結果:
[AAA, BBB, CCC]
AAA
[AAA, BBB, CCC]
AAA
[BBB, CCC]
先進后出
public static void main(String[] args) {
ArrayDeque<String> stack = new ArrayDeque<>();
//壓棧,此時AAA在最下,CCC在最外
stack.push("AAA");
stack.push("BBB");
stack.push("CCC");
System.out.println(stack);
//獲取最後添加的元素,但不刪除
System.out.println(stack.peek());
System.out.println(stack);
//彈出最後添加的元素
System.out.println(stack.pop());
System.out.println(stack);
}
輸出結果:
[CCC, BBB, AAA]
CCC
[CCC, BBB, AAA]
CCC
[BBB, AAA]
4.2、LinkedList
LinkedList是List接口的實現類,也是Deque的實現類,底層是一種雙向鏈表的數據結構,在上面咱們也有所介紹,LinkedList可以根據索引來獲取元素,增加或刪除元素的效率較高,如果查找的話需要遍歷整合集合,效率較低,LinkedList同時實現了stack、Queue、PriorityQueue的所有功能。
例子
public static void main(String[] args) {
LinkedList<String> ll = new LinkedList<>();
//入隊
ll.offer("AAA");
//壓棧
ll.push("BBB");
//雙端的另一端入隊
ll.addFirst("NNN");
ll.forEach(str -> System.out.println("遍歷中:" + str));
//獲取隊頭
System.out.println(ll.peekFirst());
//獲取隊尾
System.out.println(ll.peekLast());
//彈棧
System.out.println(ll.pop());
System.out.println(ll);
//雙端的後端出列
System.out.println(ll.pollLast());
System.out.println(ll);
}
輸出結果:
遍歷中:NNN
遍歷中:BBB
遍歷中:AAA
NNN
AAA
NNN
[BBB, AAA]
AAA
[BBB]
4.3、PriorityQueue
PriorityQueue也是一個隊列的實現類,此實現類中存儲的元素排列並不是按照元素添加的順序進行排列,而是內部會按元素的大小順序進行排列,是一種能夠自動排序的隊列。
例子
public static void main(String[] args) {
PriorityQueue<Integer> queue1 = new PriorityQueue<>(10);
System.out.println("處理前的數據");
Random rand = new Random();
for (int i = 0; i < 10; i++) {
Integer num = rand.nextInt(90) + 10;
System.out.print(num + ", ");
queue1.offer(num); // 隨機兩位數
}
System.out.println("\n處理后的數據");
for (int i = 0; i < 10; i++) { // 默認是自然排序 [升序]
System.out.print(queue1.poll() + ", ");
}
}
輸出結果:
處理前的數據
36, 23, 24, 11, 12, 26, 79, 96, 14, 73,
處理后的數據
11, 12, 14, 23, 24, 26, 36, 73, 79, 96,
五、映射表(Map)
Map是一個雙列集合,其中保存的是鍵值對,鍵要求保持唯一性,值可以重複。
Map 主要實現類:HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties。
5.1、HashMap
關於HashMap,相信大家都不陌生,繼承自AbstractMap,key 不可重複,因為使用的是哈希表存儲元素,所以輸入的數據與輸出的數據,順序基本不一致,另外,HashMap最多只允許一條記錄的 key 為 null。
5.2、LinkedHashMap
HashMap 的子類,內部使用鏈表數據結構來記錄插入的順序,使得輸入的記錄順序和輸出的記錄順序是相同的。LinkedHashMap與HashMap最大的不同處在於,LinkedHashMap輸入的記錄和輸出的記錄順序是相同的!
5.3、TreeMap
能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序,也可以指定排序的比較器,當用 Iterator 遍歷時,得到的記錄是排過序的;如需使用排序的映射,建議使用 TreeMap。TreeMap實際使用的比較少!
5.4、IdentityHashMap
繼承自AbstractMap,與HashMap有些不同,在獲取元素的時候,通過==
代替equals ()
來進行判斷,比較的是內存地址。
get方法源碼部分
public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
//用==比較k和元素是否相等
if (item == k)
return (V) tab[i + 1];
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
5.5、WeakHashMap
WeakHashMap繼承自AbstractMap,被稱為緩存Map,向WeakHashMap中添加元素,再次通過鍵調用方法獲取元素方法時,不一定獲取到元素值,因為WeakHashMap 中的 Entry 可能隨時被 GC 回收。
5.6、Hashtable
Hashtable,一個元老級的類,鍵值不能為空,與HashMap不同的是,方法都加了synchronized
同步鎖,是線程安全的,但是效率上,沒有HashMap快!
同時,HashMap 是 HashTable 的輕量級實現,他們都完成了Map 接口,區別在於 HashMap 允許K和V為空,而HashTable不允許K和V為空,由於非線程安全,效率上可能高於 Hashtable。
如果需要在多線程環境下使用HashMap,可以使用如下的同步器來實現或者使用併發工具包中的ConcurrentHashMap
類
Map<String, Object> map =Collections.synchronizedMap(new HashMap<>());
5.7、Properties
Properties繼承自HashTable,Properties新增了load()和和store()方法,可以直接導入或者將映射寫入文件,另外,Properties的鍵和值都是String類型。
六、比較器
Comparable和Comparator接口都是用來比較大小的,一般在TreeSet、TreeMap接口中使用的比較多,主要用於解決排序問題。
6.1、Comparable
Comparable:對實現它的每個類的對象進行整體排序
package java.lang;
import java.util.*;
public interface Comparable<T> {
public int compareTo(T o);
}
若一個類實現了Comparable 接口,實現 Comparable 接口的類的對象的 List 列表 ( 或數組)可以通過 Collections.sort(或 Arrays.sort)進行排序。
此外,實現 Comparable 接口的類的對象 可以用作 “有序映射 ( 如 TreeMap)” 中的鍵或 “有序集合 (TreeSet)” 中的元素,而不需要指定比較器。
使用例子:
/**
* 實體類Person實現Comparable接口
*/
public class Person implements Comparable<Person>{
private int age;
private String name;
public Person(String name, int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person o){
return this.age-o.age;
}
@Override
public String toString(){
return name+":"+age;
}
}
測試
public static void main(String[] args) {
Person person1 = new Person("張三",18);
Person person2 = new Person("李四",17);
Person person3 = new Person("王五",19);
List<Person> list = new ArrayList<>();
list.add(person1);
list.add(person2);
list.add(person3);
System.out.println(list);
Collections.sort(list);
System.out.println(list);
}
輸出:
[張三:18, 李四:17, 王五:19]
[李四:17, 張三:18, 王五:19]
6.2、Comparator
Comparator:也是對實現它的每個類的對象進行排序
package java.util;
import ***;
public interface Comparator<T> {
int compare(T o1, T o2);
......
}
如果我們的這個類Person
無法修改或者沒有繼承Comparable
接口,我們又要對其進行排序,Comparator就可以派上用場了。
將類Person
實現的Comparable
接口去掉
/**
* 實體類Person
*/
public class Person {
private int age;
private String name;
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Person(String name, int age){
this.name = name;
this.age = age;
}
@Override
public String toString(){
return name+":"+age;
}
}
測試類:
public static void main(String[] args) {
Person person1 = new Person("張三",18);
Person person2 = new Person("李四",17);
Person person3 = new Person("王五",19);
List<Person> list = new ArrayList<>();
list.add(person1);
list.add(person2);
list.add(person3);
System.out.println(list);
Collections.sort(list, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
if(o1 == null || o2 == null){
return 0;
}
//o1比o2小,返回負數
//o1等於o2,等於0
//o1大於o2,返回正數
return o1.getAge()-o2.getAge();
}
});
System.out.println(list);
}
輸出:
[張三:18, 李四:17, 王五:19]
[李四:17, 張三:18, 王五:19]
七、常用工具類
7.1、Collections類
java.util.Collections工具類為集合框架提供了很多有用的方法,這些方法都是靜態的,在編程中可以直接調用。整個Collections工具類源碼差不多有4000行,這裏只針對一些典型的方法進行闡述。
7.1.1、addAll
addAll:向指定的集合c中加入特定的一些元素elements
public static <T> boolean addAll(Collection<? super T> c, T… elements)
7.1.2、binarySearch
binarySearch:利用二分法在指定的集合中查找元素
#集合元素T實現Comparable接口的方式,進行查詢
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
#元素以外部實現Comparator接口的方式,進行查詢
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
7.1.3、sort
#集合元素T實現Comparable接口的方式,進行排序
public static <T extends Comparable<? super T>> void sort(List<T> list)
#元素以外部實現Comparator接口的方式,進行排序
public static <T> void sort(List<T> list, Comparator<? super T> c)
7.1.4、shuffle
shuffle:混排,隨機打亂原來的順序,它打亂在一個List中可能有的任何排列的蹤跡。
#方法一
public static void shuffle(List<?> list)
#方法二,指定隨機數訪問
public static void shuffle(List<?> list, Random rnd)
7.1.5、reverse
reverse:集合排列反轉
#直接反轉集合的元素
public static void reverse(List<?> list)
#返回可以使集合反轉的比較器Comparator
public static <T> Comparator<T> reverseOrder()
#集合的反轉的反轉,如果cmp不為null,返回cmp的反轉的比較器,如果cmp為null,效果等同於第二個方法.
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
7.1.6、synchronized系列
synchronized系列:確保所封裝的集合線程安全(強同步)
#同步Collection接口下的實現類
public static <T> Collection<T> synchronizedCollection(Collection<T> c)
#同步SortedSet接口下的實現類
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
#同步List接口下的實現類
public static <T> List<T> synchronizedList(List<T> list)
#同步Map接口下的實現類
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
#同步SortedMap接口下的實現類
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
7.2、Arrays類
java.util.Arrays工具類也為集合框架提供了很多有用的方法,這些方法都是靜態的,在編程中可以直接調用。整個Arrays工具類源碼有3000多行,這裏只針對一些典型的方法進行闡述。
7.2.1、asList
asList:將一個數組轉變成一個List,準確來說是ArrayList
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
注意:這個List是定長的,企圖添加或者刪除數據都會報錯java.lang.UnsupportedOperationException
7.2.2、sort
sort:對數組進行排序,適合byte,char,double,float,int,long,short等基本類型,還有Object類型
#基本數據類型,例子int類型數組
public static void sort(int[] a)
#Object類型數組
#如果使用Comparable進行排序,Object需要實現Comparable
#如果使用Comparator進行排序,可以使用外部比較方法實現
public static void sort(Object[] a)
7.2.3、binarySearch
binarySearch:通過二分查找法對已排序的數組進行查找。如果數組沒有經過Arrays.sort排序,那麼檢索結果未知。
適合byte,char,double,float,int,long,short等基本類型,還有Object類型和泛型。
#基本數據類型,例子int類型數組,key為要查詢的參數
public static int binarySearch(int[] a, int key)
#Object類型數組,key為要查詢的參數
#如果使用Comparable進行排序,Object需要實現Comparable
#如果使用Comparator進行排序,可以使用外部比較方法實現
public static int binarySearch(Object[] a, Object key)
7.2.4、copyOf
copyOf:數組拷貝,底層採用System.arrayCopy(native方法)實現。
適合byte,char,double,float,int,long,short等基本類型,還有泛型數組。
#基本數據類型,例子int類型數組,newLength新數組長度
public static int[] copyOf(int[] original, int newLength)
#T為泛型數組,newLength新數組長度
public static <T> T[] copyOf(T[] original, int newLength)
7.2.5、copyOfRange
copyOfRange:數組拷貝,指定一定的範圍,底層採用System.arrayCopy(native方法)實現。
適合byte,char,double,float,int,long,short等基本類型,還有泛型數組。
#基本數據類型,例子int類型數組,from:開始位置,to:結束位置
public static int[] copyOfRange(int[] original, int from, int to)
#T為泛型數組,from:開始位置,to:結束位置
public static <T> T[] copyOfRange(T[] original, int from, int to)
7.2.6、equals和deepEquals
equals:判斷兩個數組的每一個對應的元素是否相等(equals, 對於兩個數組的元素a和a2有a==null ? a2==null : a.equals(a2))
#基本數據類型,例子int類型數組,a為原數組,a2為目標數組
public static boolean equals(int[] a, int[] a2)
#Object數組,a為原數組,a2為目標數組
public static boolean equals(Object[] a, Object[] a2)
deepEquals:主要針對一個數組中的元素還是數組的情況(多維數組比較)
#Object數組,a1為原數組,a2為目標數組
public static boolean deepEquals(Object[] a1, Object[] a2)
7.2.7、toString和deepToString
toString:將數組轉換成字符串,中間用逗號隔開
#基本數據類型,例子int類型數組,a為數組
public static String toString(int[] a)
#Object數組,a為數組
public static String toString(Object[] a)
deepToString:當數組中又包含數組,就不能單純的利用Arrays.toString()了,使用此方法將數組轉換成字符串
#Object數組,a為數組
public static String deepToString(Object[] a)
八、迭代器
JCF的迭代器(Iterator)為我們提供了遍歷容器中元素的方法。只有容器本身清楚容器里元素的組織方式,因此迭代器只能通過容器本身得到。每個容器都會通過內部類的形式實現自己的迭代器。
ArrayList<String> list = new ArrayList<String>();
list.add(new String("a1"));
list.add(new String("a2"));
list.add(new String("a3"));
Iterator<String> it = list.iterator();//得到迭代器
while(it.hasNext()){
String obj = it.next();//訪問元素
System.out.println(obj);
}
JDK 1.5 引入了增強的for循環,簡化了迭代容器時的寫法
//使用增強for迭代
ArrayList<String> list = new ArrayList<String>();
list.add(new String("a1"));
list.add(new String("a2"));
list.add(new String("a3"));
for(String obj : list){
//enhanced for statement
System.out.println(obj);
}
九、總結
以上,主要是對java集合的整體架構進行簡單的介紹,如果有理解不當之處,歡迎指正。
十、參考
1、JDK1.7&JDK1.8 源碼
2、
3、
作者:炸雞可樂
原文出處:
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
※智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選
※評比南投搬家公司費用收費行情懶人包大公開