java集合詳解

java集合詳解

1.java集合是什麼?

java集合實際上是一種經常被運用到的java類庫,其中提供了已經實作的的資料結構,省去了程式員再次編寫資料結構的事情.在Leetcode中經常會被用到,有很重要的作用.

集合體系

我們發現,無論是Set和List都是繼承于Collection接口,實作Collection之中的方法,而他們又衍生出了HashSet,LinkedList等等我們經常使用的資料結構.

但是真相并不是如此的簡單.

對于Collection接口的實作,其實是由AbstractCollection類完成的.

此類提供了 Collection 接口的骨幹實作，進而最大限度地減少了實作此接口所需的工作。

Collection中需要實作的的方法:

boolean add(E o) 確定此 collection 包含指定的元素（可選操作）。 boolean addAll(Collection<? extends E> c) 将指定 collection 中的所有元素都添加到此 collection 中（可選操作）。 void clear() 移除此 collection 中的所有元素（可選操作）。 boolean contains(Object o) 如果此 collection 包含指定的元素，則傳回 true。 boolean containsAll(Collection<?> c) 如果此 collection 包含指定 collection 中的所有元素，則傳回 true。 boolean equals(Object o) 比較此 collection 與指定對象是否相等。 int hashCode() 傳回此 collection 的哈希碼值。 boolean isEmpty() 如果此 collection 不包含元素，則傳回 true。 Iterator iterator() 傳回在此 collection 的元素上進行疊代的疊代器。 boolean remove(Object o) 從此 collection 中移除指定元素的單個執行個體，如果存在的話（可選操作）。 boolean removeAll(Collection<?> c) 移除此 collection 中那些也包含在指定 collection 中的所有元素（可選操作）。 boolean retainAll(Collection<?> c) 僅保留此 collection 中那些也包含在指定 collection 的元素（可選操作）。 int size() 傳回此 collection 中的元素數。 Object[] toArray() 傳回包含此 collection 中所有元素的數組。 T[] toArray(T[] a) 傳回包含此 collection 中所有元素的數組；傳回數組的運作時類型與指定數組的運作時類型相同。

AbstractCollection類實作的方法:

boolean add(E o) 確定此 collection 包含指定的元素（可選操作）。 boolean addAll(Collection<? extends E> c) 将指定 collection 中的所有元素添加到此 collection 中（可選操作）。 void clear() 從此 collection 中移除所有元素（可選操作）。 boolean contains(Object o) 如果此 collection 包含指定的元素，則傳回 true。 boolean containsAll(Collection<?> c) 如果此 collection 包含指定 collection 中的所有元素，則傳回 true。 boolean isEmpty() 如果此 collection 不包含元素，則傳回 true。 abstract Iterator iterator() 傳回在此 collection 中的元素上進行疊代的疊代器。 boolean remove(Object o) 從此 collection 中移除指定元素的單個執行個體（如果存在）（可選操作）。 boolean removeAll(Collection<?> c) 從此 collection 中移除包含在指定 collection 中的所有元素（可選操作）。 boolean retainAll(Collection<?> c) 僅在此 collection 中保留指定 collection 中所包含的元素（可選操作）。 abstract int size() 傳回此 collection 中的元素數。 Object[] toArray() 傳回包含此 collection 中所有元素的數組。 T[] toArray(T[] a) 傳回包含此 collection 中所有元素的數組；傳回數組的運作時類型是指定數組的類型。 String toString() 返

出了一個hashcode方法,AbstractCollection類實作了幾乎所有的功能.

而AbstractCollection類又有三個不同的子類AbstractList, AbstractQueue,AbstractSet.我們從名字就可以知道,這就是三種不同的資料結構.于是這樣基本就可以分析出來.

集合類的建構架構如下.

所有的集合都是依靠這種方式建構的,用一個抽象類實作接口,然後再用集合類去實作這些抽象類,來完成建構集合的目的.

這是完整的建構圖.

這其實是為了大家有一個思想,就是在Collection實作的方法,在繼承實作他的各個集合中也都會實作.

如下是本文的目錄:

(一) Iterator接口--疊代器

{ boolean hasNext() 如果仍有元素可以疊代，則傳回 true。 E next() 傳回疊代的下一個元素。 void remove() 删除 default void forEach 實作了疊代器接口的類才可以使用forEach }

這幾個方法有着很重要的意義:

所有實作Collection接口(也就是大部分集合)都可以使用forEach功能.

通過反複調用next()方法可以通路集合内的每一個元素.

java疊代器查找的唯一操作就是依靠調用next,而在執行查找任務的同時,疊代器的位置也在改變.

Iterator疊代器remove方法會删除上次調用next方法傳回的元素.這也意味之remove方法和next有着很強的依賴性.如果在調用remove之前沒有調用next是不合法的.

這個接口衍生出了,java集合的疊代器.

java集合的疊代器使用

下面是疊代器的一個小栗子:

class test { public static void run() { List list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(3); Iterator iterator = list.iterator();//依靠這個方法生成一個java集合疊代器<--在Colletion接口中的方法,被所有集合實作. // iterator.remove();報錯java.lang.IllegalStateException iterator.next(); iterator.remove();//不報錯,删掉了1 System.out.println(list);//AbstractCollection類中實作的toString讓list可以直接被列印出來 while (iterator.hasNext()) {//疊代器,hasNext()集合是否為空 Integer a = iterator.next();//可以用next通路每一個元素 System.out.println(a);//2,3 ,3 } for (int a : list) {//也可以使用foreach System.out.println(a);//2,3,3 } } public static void main(String[] args) { run(); } }

當然你也會有點好奇，為什麼remove方法前面必須跟着一個next方法.其實這個隻能這麼解釋.

疊代器的next方法的運作方式并不是類似于數組的運作方式.

當然,這張圖主要是讓你了解一下.

數組的指針指向要操作的元素上面,而疊代器卻是将要操作的元素放在運動軌迹中間.

本質來講,疊代器的指針并不是指在元素上,而是指在元素和元素中間.

假設現在調用remove().被删除的就是2号元素.(被疊代器那個圓弧籠蓋在其中的那個元素).如果再次調用,就會報錯,因為圓弧之中的2号元素已經消失,那裡是空的,無法删除.

(二) Collection接口

這個對象是一個被LIst,Set,Queue的超類, 這個接口中的方法,構成了集合中主要的方法和内容.剩下的集合往往都是對這個接口的擴充.

方法如下:

boolean add(E o) 確定此 collection 包含指定的元素（可選操作）。 boolean addAll(Collection<? extends E> c) 将指定 collection 中的所有元素添加到此 collection 中（可選操作）。 void clear() 從此 collection 中移除所有元素（可選操作）。 boolean contains(Object o) 如果此 collection 包含指定的元素，則傳回 true。 boolean containsAll(Collection<?> c) 如果此 collection 包含指定 collection 中的所有元素，則傳回 true。 boolean isEmpty() 如果此 collection 不包含元素，則傳回 true。 abstract Iterator iterator() 傳回在此 collection 中的元素上進行疊代的疊代器。 boolean remove(Object o) 從此 collection 中移除指定元素的單個執行個體（如果存在）（可選操作）。 boolean removeAll(Collection<?> c) 從此 collection 中移除包含在指定 collection 中的所有元素（可選操作）。 boolean retainAll(Collection<?> c) 僅在此 collection 中保留指定 collection 中所包含的元素（可選操作）。 abstract int size() 傳回此 collection 中的元素數。 Object[] toArray() 傳回包含此 collection 中所有元素的數組。 T[] toArray(T[] a) 傳回包含此 collection 中所有元素的數組；傳回數組的運作時類型是指定數組的類型。 String toString() <--很重要 返

其實我們并不一定要把這些方法都記住

我們隻要記住Collection對象實作了這些種類的方法就可以了(可以現查API,不是..

但是确實,這些方法記住了有很大的用處.

添加元素(兩種) 添加一個元素,添加一個集合 删除元素(三種) 删除一個元素,删出一個集合,隻保留一個集合 判斷大小 變成數組 是否為空 清空

java集合的泛型使用

到這裡我們還要講解一個問題,就是除了Map的集合類型(看看上面的繼承表,map是單獨一個分支)都可以傳入Collection為參數的函數裡面去.

public class Test { public static void display(Collection<?> a){ System.out.println(a); } public static void main(String[] args) { List list=new LinkedList<>();//連結清單 list.add(1); list.add(2); list.add(4); list.add(3); display(list);//[1, 2, 4, 3] Set set=new TreeSet<>();//樹集 set.addAll(list); //在這裡之是以兩者輸出不同,是因為樹集有着一個自動排序的功能.其原因在于對于treeset内部結構的實作和LinkedList有所不同 display(set);//[1, 2, 3, 4] } }

java集合中使用泛型的好處

為什麼在java集合中經常使用泛型.除了為了防止輸入錯誤的資料,更重要的是如果用了泛型也會讓操作更加的友善,省去了強制轉化的過程.

以下兩個是準備

public class AppleAndOrangeWithOutGenerics { @SuppressWarnings("unchecked")//這個隻能抑制警告資訊,用它就不會有警告 public static void main(String args[]) { / 不用泛型 / // ArrayList apples=new ArrayList(); // for (int i = 0; i <3 ; i++) { // apples.add(new Apple()); //在ArrayList無論放進去之前是什麼,再放進去之後都會變成Object類型, // apples.add(new Orange()); //會報一個小小的warning,因為沒有使用泛型.<-隻有删掉這個句子執行才不報錯 // } // for (int j = 0; j 使用泛型 / ArrayList apples = new ArrayList(); for (int i = 0; i < 3; i++) { apples.add(new Apple()); // apples.add(new Orange());//在這裡直接就報錯了,讓這種錯誤在編譯期就被發現 } for (int j = 0; j < apples.size(); j++) { //用了檢討之後連強制轉換都不需要了 System.out.println(( apples.get(j)).id());//如果沒有泛型的攔截,輸入Orange類型根本不會被發現.非常的危險 } } }

是以使用泛型有很大的好處.

(三) List

List是一個有序集合,元素會增加到容器中特定的位置,可以采用兩種方式通路元素:使用疊代器通路或者使用一個整數索引通路.後一種方式稱為随機通路.

為此List接口多定義了一些方法,來實作這一點

void add(int index,E element);//這個和上面不同,帶了index. void remove(int index); E get(int index); E set(int index,E element);

我們知道實作LIST接口的類中有一個類叫做AbstractList,他的兩個子類分别是LinkedList和ArrayList這兩種.那麼問題是連結清單可不可以使用這個add方法.

答案是可以的.實際上連結清單使用随機通路,隻不過是慢了點而已.如果有可能,還是使用疊代器為好.

LIST主要有兩種類.一個是LinkedList一個是ArrayList.

LinkedList

我們就從一個程式看一看LinkedList到底怎麼用.

/* LinkedLIST也像ArrayList一揚實作了基本的List接口,但是他執行一些操作效率更高,比如插入. LIST為空就會抛出NoSuchElement-Exception Created by 22643 on 2020/4/17. */ public class LinkedListFeatures { public static void main(String[] args) { LinkedList pets=new LinkedList(Pets.arrayList(5));//後面括号中的意思是生成五個Pets對象 System.out.println("pets = [" + pets + "]"); System.out.println("pets.getFirst() "+pets.getFirst());//取第一個 System.out.println("pets.element "+pets.element());//也是取第一個,跟first完全相同. //如果清單為空如上兩個内容傳回NoSuchElement-Exception System.out.println("pets.peek()"+pets.peek());//peek跟上面兩個一揚,隻是在清單為空的時候傳回null System.out.println(pets.removeFirst()); System.out.println(pets.remove());//這兩個完全一樣,都是移除并傳回清單頭,清單空的時候傳回NoSuchElement-Exception System.out.println(pets.poll());//稍有差異,清單為空的時候傳回null pets.addFirst(new Rat());//addFirst将一個元素插入頭部,addLast是插到尾部 System.out.println(pets); pets.add(new Rat());//将一個元素插入尾部 System.out.println(pets); pets.offer(new Rat());//與上面一揚,将一個元素插入尾部 System.out.println(pets); pets.set(2,new Rat());//将替換為指定的元素 System.out.println(pets); } }

實際上LinkedList有非常多的方法,因為LinkedList是被用來實作多中資料結構的.不但可以實作隊列,甚至還有可以實作棧的相關方法.

我們對此進行分類:

棧相關的操作方法:

E poll() 找到并移除此清單的頭（第一個元素）。 peek() 找到但不移除此清單的頭（第一個元素）。 void addFirst(E o) 加入開頭可以當作add用

隊列操作方法:(LinkedList實作了Queue的接口,是以說可以操作用來建構隊列)

注意隊列是FIFO(先進先出)隊列,是以按照實作,從普通隊列是從隊列的尾部插入,從頭部移除,.

是以方法如下:

E element() 首元素 boolean offer(E o)将指定隊列插入桶 E peek() 檢索,但是不移除隊列的頭 E pool()檢索并移除此隊列的頭,為空傳回null. E remove()檢索并移除此隊列的頭

一般來講集合中的方法在移除方法都會有一個為空的時候傳回null的方法,和一個為空的時候傳回null的方法.類似于pool()和remove()

我們一會到Queue的時候還會将這些再将一次.

ArrayList

我們也從一個程式來看這個

public class ListFeatures { public static void main(String[] args) { Random rand=new Random(47);//相同的種子會産生相同的随機序列。 List list=new ArrayList<>(); list.add("demo3"); list.add("demo2"); list.add("demo1");//加入方法 System.out.println("插入元素前list集合"+list);//可以直接輸出 / /void add(int index, E element)在指定位置插入元素，後面的元素都往後移一個元素 / list.add(2,"demo5"); System.out.println("插入元素前list集合"+list); List listtotal=new ArrayList<>(); List list1=new ArrayList<>(); List list2=new ArrayList<>(); list1.add("newdemo1"); list1.add("newdemo2"); list1.add("newdemo2"); / boolean addAll(int index, Collection<? extends E> c) 在指定的位置中插入c集合全部的元素，如果集合發生改變，則傳回true，否則傳回false。 意思就是當插入的集合c沒有元素，那麼就傳回false，如果集合c有元素，插入成功，那麼就傳回true。 / boolean b=listtotal.addAll(list1); boolean c=listtotal.addAll(2,list2); System.out.println(b); System.out.println(c);//插入2号位置,list2是空的 System.out.println(list1); / E get(int index) 傳回list集合中指定索引位置的元素 / System.out.println(list1.get(1));//list的下标是從0開始的 / int indexOf(Object o) 傳回list集合中第一次出現o對象的索引位置，如果list集合中沒有o對象，那麼就傳回-1 / System.out.println(list1.indexOf("demo")); System.out.println(list1.indexOf("newdemo2")); //如果在list中有相同的數,也沒有問題. //但是如果是對象,因為每個對象都是獨一無二的.是以說如果傳入一個新的對象,indexof和remove都是無法完成任務的 //要是删除,可以先找到其位置,然後在進行删除. //Pet p=pets.get(2); //pets.remove(p); / 檢視contains檢視參數是否在list中 / System.out.println(list1.contains("newdemo2"));//true / remove移除一個對象 傳回true和false / //隻删除其中的一個 System.out.println(list1.remove("newdemo2"));//[newdemo1, newdemo2] System.out.println(list1); List pets=list1.subList(0,1);//讓你從較大的一個list中建立一個片段 //containall一個list在不在另一個list中 System.out.println(pets+"在list中嘛"+list1.containsAll(pets));//[newdemo1]在list中嘛true //因為sublist的背後就是初始化清單,是以對于sublist的修改會直接反映到原數組上面 pets.add("new add demo"); System.out.println(list1);//[newdemo1, new add demo, newdemo2] Collections.sort(pets); System.out.println( pets );//new add demo, newdemo1 System.out.println(list1.containsAll(pets));//true-----變換位置不會影響是否在list1中被找到. list1.removeAll(pets);//移除在參數list中的全部資料 / list1[newdemo1, new add demo, newdemo2] pets[new add demo, newdemo1] / System.out.println(list1);//[newdemo2] System.out.println(list1.isEmpty());//是否為空 System.out.println(list1.toArray());//将list變為數組 //list的addAll方法有一個重載的.可以讓他在中間加入 } }

這個比較适合非順序存儲.

(四)(五)Set

Set實際上也是一種映射關系的集合和Map比較像.但是它實作的依然是Collection的接口.

而且Set中的方法和Collection的方法幾乎完全一樣.

唯一的差別在于add方法不允許增加重複的元素.在調用equal時,如果兩個Set中的元素都相等,無論兩者的順序如何,這兩個Set都會相等.

set的特性

Set不儲存重複的元素. Set就是Collection,隻是行為不同. HashSet使用了散列,它列印的時候,輸出的元素不會正常排列 TreeSet使用了儲存在紅黑樹結構中,,是以輸出的元素會正常排列

當然Set最主要的工作就是判斷存在性,目的是看一個元素到底存不存在這個集合之中.

下面放上兩個Set的例子:

SortedSet（TreeSet）

public class SortedSetOfInteger { public static void main(String[] args) { Random random=new Random(47); SortedSet intset=new TreeSet<>(); for (int i = 0; i <100 ; i++) { intset.add(random.nextInt(30)); } System.out.println(intset);//set特性隻能輸入相同的數,别看輸入了100個數,但是實際上隻有30個進去了. //這個有序了.這就是treeset的功勞,因為内部的實作時紅黑樹,是以來說.這就簡單了一些 } }

HashSet

public class SetOfInteger { public static void main(String[] args) { Random rand=new Random(47); Set intset=new HashSet<>();//建立一個HashSet for (int i = 0; i <100 ; i++) { intset.add(rand.nextInt(30)); } System.out.println(intset);//set特性隻能輸入相同的數,别看輸入了100個數,但是實際上隻有30個進去了. } }

這裡要講一下HashSet。HashSet不在意元素的順序，根據屬性可以快速的通路所需要的對象。散清單為每個對象計算一個整數，成為散列碼...散列碼是執行個體産生的一個整數。

散清單（HashSet）散清單用連結清單數組實作。每個清單稱為通。想要查找表中對象的位置就計算它的散列碼。然後與通的總數取餘，得到的數就是儲存這個元素的通的索引。

但是桶總有被沾滿的一刻。

為了應對這種情況，需要用新對象與桶中所有對象比較，看是否存在。

為了控制性能就要能定義初始桶數，設定為要插入元素的75%-150%，最好為素數。

這個時候就要執行再散列，讓這個散清單獲得更多的内容。

再散列：

需要建立一個桶數更多的表，并将全部元素插入這個新表中。裝填因子絕對什麼時候在執行，如果裝填因子為0.75那麼就是在表中75%的位置被沾滿時，表會給如雙倍的桶數自動散列。

Queue

隊列是資料結構中比較重要的一種類型，它支援 FIFO，尾部添加、頭部删除（先進隊列的元素先出隊列），跟我們生活中的排隊類似。

但是在集合中的Queue并沒有單獨的實作類，而是用LinkedList實作的。其實你隻要看一眼LinkedList的方法就知道，他完全可以實作隊列的操作。

add()尾部添加 removeFirst()删除頭部元素 peek()檢視頭部元素

Queue主要有兩種不同的類型.

分别是優先級隊列和Deque隊列

PriorityQueue

優先級隊列中元素可以按照任意的順序插入，卻按照目标排序的順序進行檢索，也就是無論什麼時候調用remove移除的都是目前最小的元素。

優先級使用了一種堆，一個可以自我調節的二叉樹，對樹進行執行添加和删除。它可以讓最小的元素移動到跟，而不必花時間對其排序。

當然,你也可以自己對其進行排序.

小栗子:

import java.text.DecimalFormat; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; / @Author：sks @Description： @Date：Created in 10:39 2018/1/11 @Modified by： / //二維平面上一個點 class point { //坐标x double x; //坐标y double y; public point(double x, double y){ this.x = x; this.y = y; } } //排序函數 class PointComparator { private point pointOne; private point pointTwo; public double distance; public PointComparator(point pointOne,point pointTwo) { this.pointOne = pointOne; this.pointTwo = pointTwo; computeDistance(); } //計算兩點之間距離 private void computeDistance() { double val = Math.pow((this.pointOne.x - this.pointTwo.x),2) + Math.pow((this.pointOne.y - this.pointTwo.y),2); this.distance = Math.sqrt(val); } } public class PriorityQueuep_test { public static void main(String args[]){ Comparator OrderDistance = new Comparator(){ public int compare(PointComparator one, PointComparator two) { if (one.distance < two.distance) return 1; else if (one.distance > two.distance) return -1; else return 0; } }; //定義一個優先隊列,用來排序任意兩點之間的距離，從大到小排 Queue FsQueue = new PriorityQueue(10,OrderDistance); for (int i=0;i<6;i++){ java.util.Random r= new java.util.Random(10); point one =new point(i2+1,i3+2); point two =new point(i5+2,i6+3); PointComparator nodecomp = new PointComparator(one,two); DecimalFormat df = new DecimalFormat("#.##"); FsQueue.add(nodecomp); } DecimalFormat df = new DecimalFormat("#.###"); for (int i = 0;i<6;i++){ System.out.println(df.format(FsQueue.poll().distance)); } } }

Deque

deque也有些複雜,它可以用ArrayDeque實作,也可以用LinkedList實作.

線性集合，支援兩端的元素插入和移除。Deque是double ended queue的簡稱，習慣上稱之為雙端隊列。大多數Deque 實作對它們可能包含的元素的數量沒有固定的限制，但是該接口支援容量限制的deques以及沒有固定大小限制的deque。

作者：我是吸血鬼

連結：

https://www.jianshu.com/p/d78a7c982edb

來源：簡書

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

因為本身也是LinkedList實作的,是以其本身的方法和LinkedList差不了多少.

public class Main { public static void main(String[] args) { Deque deque = new LinkedList<>(); deque.offerLast("A"); // A deque.offerLast("B"); // B -> A deque.offerFirst("C"); // B -> A -> C System.out.println(deque.pollFirst()); // C, 剩下B -> A System.out.println(deque.pollLast()); // B System.out.println(deque.pollFirst()); // A System.out.println(deque.pollFirst()); // null } }

Stack

stack的名字大家都知道,就是棧.一個先進後出的資料結構,這裡我并不認為應該使用java集合中提供的棧集合.

而是應該使用LinkedList來建構集合:

一個小任務:

用LinkedList實作棧

public class Stack { private LinkedList storage=new LinkedList<>();//用LinkedList作為棧的核心 public void push(T v){ storage.addFirst(v);}// public T peek(){ return storage.getFirst();} public T pop(){return storage.removeFirst();} public boolean empty(){return storage.isEmpty();} public String toString(){return storage.toString();} }

這樣做有一個好處,就是這樣的棧可以有更多種的方法,可以采用更多種的方式.無疑這樣的棧會更好一些.

是以我推薦大家用棧的時候,用LinkedList來實作.

MAP

講了Collection接口實作的各種集合,我們就要講講非Collection的集合.這意味着你在Collection中記住的方法在這個裡面完全用不到了.

我們知道一些鍵的資訊,想要知道與之對應的元素.映射結構就是為此設計的,映射用來存放鍵值對,如提供了鍵就能查到值.

和Set一樣,HashMap要比TreeMap要快上一些,但是TreeMap有序.這與Set很相似,畢竟Set其實也是映射結構.

每當往映射加入對象是,必須同時提供一個鍵.

鍵是唯一的,不能對同一個鍵放兩個值.如果對同一個鍵調用兩次put方法,第二次調用會取代第一個.

要想處理所有的鍵和值,那就應該使用foreach

列子如下:

public class MapOfList { public static Map> people=new HashMap<>(); static { people.put(new Person("dawn"), Arrays.asList(new Cymric("Molly"),new Mutt("Spot"))); //就寫一個了,有點懶了. } public static void main(String[] args) { System.out.println(people.keySet());//傳回的是鍵組成的set System.out.println(people.values());//傳回的時值組成的set for (Person person:people.keySet() ) { System.out.println(person+"has :"); for (Pet pet:people.get(person) ) { System.out.println(pet); } } } }

下面還有一個HashMap使用的例子

public class PetMap { public static void main(String[] args) { Map petMap=new HashMap(); petMap.put("My Cat",new Cat("MALL")); petMap.put("My Dog",new Dog("DOGGY")); petMap.put("My Haster",new Hamster("Bosco")); System.out.println(petMap); Pet dog=petMap.get("My Dog"); System.out.println(dog); System.out.println(petMap.containsKey("My Dog"));// System.out.println(petMap.containsValue(dog));// } }

EOF

本文作者：Timothy Rasinski

本文連結：

https://www.cnblogs.com/yanzezhong/p/12808089.html