集合是一種容器對象,是用來存儲對象的,或者說存儲的都是對象的引用,並不是直接存儲的對象,而是存儲的對象的記憶體地址。需要註意的是,集合中不能存儲基本數據類型,即使是代碼中往集合中添加了基本數據類型,那也是進行了自動裝箱之後才放入集合的。 需要註意的是,Java中每一種不同的集合,底層會對應不同的數據結 ...
集合是一種容器對象,是用來存儲對象的,或者說存儲的都是對象的引用,並不是直接存儲的對象,而是存儲的對象的記憶體地址。需要註意的是,集合中不能存儲基本數據類型,即使是代碼中往集合中添加了基本數據類型,那也是進行了自動裝箱之後才放入集合的。
需要註意的是,Java中每一種不同的集合,底層會對應不同的數據結構,所以應該根據實際情況選擇使用合適的集合類型。
所有的集合都在“java.util”中,導入的時候去util包里找即可。
註:集合的定義中會經常看到<E>等尖括弧表示的語法,這是泛型的定義,表示可以根據需要傳入自己需要的類型,如果不傳入,預設就是Object類型。即如果傳入指定的類型,則集合中只能存儲指定的類型,否則集合中可以存儲Object類的所有子類型。
1、Collection集合繼承結構
Collection類型的集合特點是以單個對象的個體方式存儲元素。
java.lang.Object --> java.util.AbstractCollection<E>這個類實現了以下兩個介面:
- Iterable<E>:這個介面用於獲取遍歷集合所需要的迭代器。
- Collection<E>:這是所有集合的超級父介面,裡面定義許多集合通用的方法。
Collection<E>介面中的常用方法:
- boolean add(E e):向集合末尾添加一個元素。
- int size():返回集合中元素的個數。註意,不是返回集合的容量,而是實際存儲的元素個數。
- void clear():清空集合中的所有元素。
- boolean contains(Object o):判斷當前集合中是否包含某個元素。這個方法其實是調用了元素o對象的equals方法來比較集合中的每個元素,如果有返回true的結果,則contains方法則返回true,否則返回false。
- boolean remove(Object o):刪除集合中的某個元素。這個方法也會調用o對象的equals方法來進行判斷。
- boolean isEmpty():判斷集合是否為空。
- Iterator<E> iterator():返回一個迭代器,需要註意的是,返回的迭代器一開始並沒有直接就指向了第一個元素。另一個需要註意的點,就是集合的結構或者內容發生改變時,迭代器也需要重新獲取,所以如果在迭代的過程中需要刪除元素,那麼就不能使用集合對象本身的remove方法,需要使用迭代器自身的remove方法。(返回的迭代器從原理上可以理解為當前集合狀態的一個快照,迭代的時候只是會參照這個快照進行迭代,所以如果集合本身發生了變化,那麼就和快照不一致了,此時再按照快照的狀態去迭代集合元素就會發生異常。)
- 註:因為contains和remove方法都會用到equals方法,所以需要保證往集合中添加的元素都已經重寫了equals方法,特別是自己定義的對象。
Iterator<E> iterator()中常用的方法:
- boolean hasNext():如果仍有元素可以迭代,則返回true,否則返回false。
- E next():返回迭代的下一個元素。這裡需要註意,如果沒有指定泛型,返回值類型是Object,雖然存儲數據的時候可能是別的具體類型,但是獲取數據的時候必須是Object。
- default void remove():刪除迭代器指向的當前元素,即next方法返回的那個元素。(原理可以理解是,先刪除快照中的當前元素,然後再同步刪除集合中對應的元素。)
- 註:通常先使用hasNext方法判斷是否可以繼續迭代,如果可以就使用next方法返回下一個元素, 註意,通過Iterator()方法剛返回的迭代器並沒有指向第一個元素,只有使用next方法之後才會指向第一個元素並往後迭代。)
Collection<E>介面下常用的子介面:
- List<E>:這個介面下的集合的特點是集合元素有序可重覆,並且可以通過下標訪問集合元素。實現這個介面的常用的類有ArrayList、LinkedList和Vector。
- Set<E>:這個介面下的集合的特點是集合元素無序不可重覆,並且不可以通過下標訪問集合元素。實現這個介面的常用的類有HashSet和TreeSet。
List<E>介面中的常用方法:
- boolean add(E e):在集合末尾添加一個元素。
- void add(int index, E element):在列表的指定位置添加一個元素。這個方法使用的較少,因為效率較低。
- E get(int index):獲取指定位置的元素。
- int indexOf(Object o):獲取某個元素第一次出現的索引。
- int lastIndexOf(Object o):獲取某個元素最後一次出現的索引。
- E remove(int index):刪除指定位置的元素。
- E set(int index, E element):修改指定位置的元素。
2、Map集合繼承結構
Map類型的集合特點是以key和value鍵值對的方式來存儲集合元素的,即一個鍵值對算作一個集合元素。
java.util.Map<K,V>介面中常用的方法:
- V put(K key, V value):向Map集合中添加一個鍵值對。
- V get(Object key):通過key獲取value。
- void clear():清空Map集合。
- boolean containsKey(Object key):判斷Map集合中是否包含某個key。註意底層方法都是調用的equals方法比對的。
- boolean containsValue(Object value):判斷Map集合中是否包含某個value。註意底層方法都是調用的equals方法比對的。
- boolean isEmpty():判斷Map集合中元素個數是否為0。
- Set<K> keySet():獲取Map集合中所有的key。
- Collection<V> values():獲取集合中所有的value。
- V remove(Object key):通過key刪除鍵值對。
- int size():獲取Map集合中鍵值對的個數。
- Set<Map.Entry<K, V>> entrySet():將Map集合轉換為Set集合,Set集合中元素的類型是“Map.Entry<K, V>”,相當於是將Map集合中每個元素的key和value聯合起來當成了Set集合中的一個元素了。
java.util.Map<K,V>介面的常用實現類:
- HashMap<K,V>:這是Map下常用的集合,特點是集合的key無序不可重覆,但是value可以重覆。
- Hashtable<K,V> --> Properties:Hashtable本身和HashMap的作用類似,但是Hashtable是線程安全的,由於這個線程安全的實現方式導致效率較低,所以用的較少了,用的較多的是它的子類Properties。
- SortedMap<K,V> --> TreeMap<K,V>:TreeMap<K,V>也是一個Map集合下常用的集合,特點是除了集合的key無序不可重覆外,由於實現了SortedMap<K,V>介面,集合的key在存放進去後會自動排序。
3、ArrayList<E>
特點:集合元素有序可重覆,可通過下標訪問集合元素,並且是非線程安全的。
方法:Collection<E>和List<E>介面中的方法ArrayList<E>都可以使用。
線程安全:如果想要將ArrayList<E>變為線程安全的,可以通過“java.util.Collections”的synchronizedList(yourList)方法將你的ArrayList對象傳入,之後的ArrayList就會變成線程安全的了。
底層原理:ArrayList底層採用的是Object類型數組的數據結構,創建對象時可以傳入數組的大小,如果沒有傳入數組大小,則會在初始化時創建一個空列表,然後在第一次往裡面添加數據時才會創建一個大小為10的數組。在往數組中添加數據時,如果容量滿了,那麼數組會自動進行擴容,並且擴容之後的數組容量為原容量的1.5倍。
優缺點:就和數組的優缺點一樣,查詢效率很快,往預設添加數據也很快,但是隨機增刪元素的效率較低,所以使用的使用應該儘量避免隨機增刪以及擴容的操作。
使用示例:
import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class GenericTest { public static void main(String[] args) { // 指定集合中的元素類型為Pet,不能存儲其它類型的元素 // 使用new的時候可以不用再傳入類型了,可以自動推斷,此時的表達式<>也稱為鑽石表達式 // 如果不指定泛型,也是可以的,預設就是Object類型 List<Pet> petList = new ArrayList<>(); Cat c = new Cat(); Dog d = new Dog(); petList.add(c); petList.add(d); // 迭代器的聲明也需要加上泛型的定義 Iterator<Pet> it = petList.iterator(); while (it.hasNext()) { // 原本next方法返回值的類型為Object,使用泛型之後返回的類型直接就是指定 // 的類型,不需要進行類型轉換了。 Pet p = it.next(); p.play(); // 當然,如果要使用具體的子類對象的方法,還是需要轉型之後才能調用 if (p instanceof Cat){ Cat myCat = (Cat)p; myCat.sleep(); } if (p instanceof Dog){ Dog myDog = (Dog)p; myDog.bark(); } } /* 輸出結果: 寵物在玩耍! 貓咪在睡覺! 寵物在玩耍! 狗子在嚎叫! */ } } class Pet { public void play() { System.out.println("寵物在玩耍!"); } } class Cat extends Pet { public void sleep() { System.out.println("貓咪在睡覺!"); } } class Dog extends Pet { public void bark() { System.out.println("狗子在嚎叫!"); } }
4、LinkedList<E>
特點:集合元素有序可重覆,可通過下標訪問集合元素。
方法:Collection<E>和List<E>介面中的方法ArrayList<E>都可以使用。
底層原理:底層採用的是雙向鏈表的數據結構,存儲的時候會將元素封裝到一個Node對象中,這個Node對象除了有元素本身外,還有兩個變數next和prev,用於下一個節點和上一個節點的地址,這樣就形成了一個“雙向”的鏈表了。雖然是鏈表,但是還是可以使用下標,但是不推薦使用下邊進行查詢,因為每次查詢都得從頭結點開始,效率較低。
優缺點:查詢效率較低,因為每次都要從頭結點開始查詢,但是隨機增刪元素的效率較高,因為只會涉及到上一個節點和下一個節點中變數next和prev的修改,不會像數組那樣會涉及到該元素之後的值的整體移動。所以在選擇使用上,如果隨機增刪的業務較多,應該使用LinkedList,如果需要往集合中頻繁的添加或查詢數據,就使用ArrayList。
容量:LinkedList因為是鏈表的數據結構,所以在記憶體空間上是沒有連續性的,並且也沒有容量的說法,剛開始都是空的,沒有任何元素。
5、Vector<E>
Vector和ArrayList一樣底層都是數組的數據結構,在使用上也是一樣的,區別在於Vector是線程安全的,但是也是因為這點,導致效率較低,而ArrayList可以使用其他更好的方法來保證線程安全,所以Vector已經使用的較少了。
6、HashSet<E>
特點:集合元素無序不可重覆,不可通過下標訪問集合元素。
方法:Collection<E>介面中的方法ArrayList<E>都可以使用。
底層原理:HashSet底層其實是採用HashMap類型來存儲元素的,不過只是用到了HashMap的key部分,value部分並沒有用到,HashMap的key本身就是無序不可重覆的,所以可以看成是HashMap所有的Key組成了一個HashSet。所以想要更好的理解HashSet,參見HashMap部分的筆記。
7、TreeSet<E>
特點:集合元素無序不可重覆,不可通過下標訪問集合元素,但是存放到集合中的數據都是按升序自動排好序的。
方法:Collection<E>介面中的方法ArrayList<E>都可以使用。
底層原理:由於TreeSet實現了SortedSet,所以存放進去的元素都是拍好序的,“無序不可重覆”中的無序指的是存入進去的順序和取出來的順序不一致,這和存入進去之後自動排序是不一樣的,不要搞混了。和HashSet類似,TreeSet底層其實使用Map下的TreeMap來存儲數據的,它也是只用到了TreeMap的key部分,沒有用到value部分,所以理解TreeSet,可以參見TreeMap部分的筆記。
自動排序:為了改變自動升序為自動降序排列,或者存儲自定義的類型的時候,需要重寫或自定義TreeSet的排序機制,特別是自定義的類型,如果沒有同時定義好排序機制的話是會報錯的,自定義排序機製為:給這個自定義的類實現“java.lang.Comparable”介面或者自定義一個比較器“java.util.Comparator”。示例如下:
import java.util.Comparator; import java.util.TreeSet; public class TreeSetTest { public static void main(String[] args) { User u1 = new User(10); User u2 = new User(30); User u3 = new User(20); // 預設使用無參構造方法,即比較器為null,此時需要在類中實現Comparable介面的compareTo方法 TreeSet<User> ts = new TreeSet<>(); // 也可以自定義一個比較器,傳入構造方法 // TreeSet<User> ts = new TreeSet<>(new UserComparator()); ts.add(u1); ts.add(u2); ts.add(u3); for (User u : ts){ System.out.println(u); } } } /* 如果是需要往TreeSet中添加,則需要實現Comparable介面,並重寫compareTo方法 */ class User implements Comparable<User>{ int age; public User(){ } public User(int age){ this.age = age; } /* 排序會根據compareTo方法返回大於0、小於0或者等於0三種情況進行排序 可根據自身需要根據三種結果進行自定義排序的規則的編寫 */ public int compareTo(User u){ return this.age - u.age; } public String toString(){ return "User: " + age; } } /* 構造器需要實現Comparator介面,並重寫compare方法 */ class UserComparator implements Comparator<User>{ public int compare(User u1, User u2){ return u1.age - u2.age; } }
8、HashMap<K,V>
特點:使用鍵值對存儲數據,key無序不可重覆,value是可以重覆的,並且是非線程安全的。
底層原理:HashMap的底層其實是哈希表或者說散列表的數據結構,而這個哈希表又是由數組和單向鏈表或者紅黑樹組成,初始化時它是單向鏈表,當添加的元素導致單向鏈表的節點數超過8個時,就會自動轉換為紅黑樹,而紅黑樹的節點數如果少於了6個,又會自動轉換為單向鏈表,之所以這樣實現,還是想要更加快速地對集合元素進行查詢。數組部分其實是一個Node類型的一位數組,每個元素都是一個Node對象,Node對象有“final int hash”、“final K key”、“V value”、“Node<K, V> next”四個基本屬性,其中hash表示是將key通過從Object重寫的hashCode方法返回的哈希值,並且這個hash值在底層可以通過另外的哈希演算法(這個演算法不需要關註)得到對應的數組下標,即這個hash值可以看成是和數組下標對應的,或者直接將他看成數組下標也行,next則表示下一個節點的記憶體地址。以最開始的數組和單向鏈表為例,使用put方法和get方法更加詳細的說明HashMap的原理。
put方法原理:當執行put方法將一個鍵值對存入HashMap集合時,會按照以下步驟執行:
- 第一步:先將key和value封裝到Node對象中,然後底層會調用key的hashCode方法(這個方法就是Object類中繼承來並重寫的方法)得到hash值,此時Node對象中有三個值已經初始化好了:key,value和hash值,另一個next為空。
- 第二步:將hash值通過底層另外的哈希演算法轉換為數組的下標,如果數組對應下標位置沒有任何元素,就把此Node對象添加到這個位置上。如果下標對應的位置上已經有了元素,那麼就會此Node對象的key去和此位置對應的鏈表從頭結點一個一個挨著去使用equals方法進行匹配,如果所有節點的equals方法都返回false,那麼就將此Node節點添加到鏈表的末尾,否則就將equals方法返回true的節點的value覆蓋掉。
get方法原理:當使用一個key值通過get方法獲取對應的value時,會按照以下步驟執行:
- 第一步:先調用key的hashCode()方法得出hash值,然後通過底層另外的哈希演算法得出數組的下標。
- 第二步:然後通過這個下標快速定位到數組的對應位置上,如果這個位置上什麼也沒有,則返回null。否則就會使用key在對應位置的單向鏈表上從頭結點開始一個節點一個節點的使用equals方法去比較對應節點的key,如果有一個節點的equals方法返回true,則返回對應的value,否則,如果所有的節點都返回false最後的結果就直接返回null。
hashCode()和equals()方法重寫:由以上put和get的實現原理可以看出,同一個數組位置的單向鏈表上的所有節點的hash值都是相同的,但是key的equals方法返回值肯定是不同的。同時也可以發現,使用HashMap時,key對象需要重寫兩個方法,hashCode()和equals()方法。重寫hashCode方法時需要註意以下內容:
- 如果hashCode方法固定返回一個值,那麼最終的結果就是只有一個單向鏈表,這種情況也稱之為散列分佈不均勻。
- 如果hashCode方法每一個對象都返回不同的值,那麼就導致數組的每個位置上都只有一個元素,這肯定也是不行的,變成了單純的一維數組了,沒有單向鏈表了。
- 重寫hashCode時應該儘量保證散列均勻,比如100個對象返回10個hashCode值,這就是散列均勻的。
- 註:但是不用擔心,hashCode()和equals()這兩個方法的重寫大部分情況都可以通過IDEA工具自動生成,不用我們手動編寫。
數組容量:HashMap集合的預設容量是16,預設載入因數是0.75,表示預設的數組長度為16,當實際的數組使用達到容量的75%時就會進行自動擴容,擴容之後的容量是原容量的2倍。也可以在初始化時指定容量大小,但是官方推薦初始化容量最好是2的倍數,不然會影響HashMap的執行效率。
使用示例:
import java.util.HashMap; import java.util.Map; import java.util.Set; public class MapTest { public static void main(String[] args) { Map<Integer, String> map = new HashMap<>(); map.put(1, "張三"); map.put(2, "李四"); // 通過key遍歷Map中的鍵值對 Set<Integer> keys = map.keySet(); for (Integer key : keys) { String value = map.get(key); System.out.println(key + "=" + value); } // 通過Set<Map.Entry<Integer, String>>直接遍歷Map中的鍵值對 // 如果記憶體允許,這種方式效率會比較高,適合大數據量的遍歷 Set<Map.Entry<Integer, String>> es = map.entrySet(); for (Map.Entry<Integer, String> node : es){ System.out.println(node.getKey() + "=" + node.getValue()); } } }
9、Hashtable<K,V> 和Properties
Hashtable和HashMap的使用相似的,區別在於Hashtable是線程安全的,而後者是非線程安全的,但是和Vector的情況一樣,Hashtable線程安全的實現方式導致了效率較低的問題,所以使用的較少了。
Hashtable的一個子類Properties相比而言要常用一點,Properties也是線程安全的,Properties對象也稱之為屬性對象,它的特點是key和value都只支持String類型。常用的方法有:
- Object setProperty(String key, String value):調用Hashtable的put方法。
- String getProperty(String key):獲取指定key的value,如果沒有則返回null。
- String getProperty(String key, String defualtValue):獲取指定key的value,如果沒有查找到則返回defualtValue。
10、TreeMap<K,V>
特點:使用鍵值對存儲數據,key無序不可重覆,value是可以重覆的,並且存入之後會按key升序自動排序。
底層原理:TreeMap實現了SortedMap<K,V>介面,並且底層其實是自平衡二叉樹的數據結構,這種數據結構遵循左小右大的原則存放數據。存入的key和value其實是封裝到了一個Entry<K,V>節點對象中,這個節點對象除了存入的key和value,還有三個變數left、right和parent用於存放左子節點、右子節點和父節點的記憶體地址,這樣就剛好形成一個二叉樹。遍歷這個二叉樹時,通常有三種方式:前序遍歷(根左右)、中序遍歷(左根右)和後序遍歷(左右根),這個“前中後”指的是根(節點)在“左右”的位置或者說遍歷中的順序,對於中序遍歷,特點是遍歷出來的數據自動就是從小到大排序的。
11、Collections工具類
這個類專門定義了一些方便集合操作的方法。常用的有:
- synchronizedList:將一個非線程安全的列表變為線程安全的。
- sort:將一個列表排序。註意,這個介面需要排序的元素實現了Comparable介面,不然會報錯。
- sort(List集合, 比較器):這種方式就不用實現Comparable介面了,但是需要提供一個比較器。