java 集合_Java集合詳解

SortedSet

TreeSet

HashSet 的背景有一個HashMap;初始化背景容量；隻不過生成一個HashSet的話，系統隻提供key的通路； 如果有兩個Key重複，那麼會覆寫之前的；

實作類 :

HashSet：equals傳回true，hashCode傳回相同的整數；哈希表；存儲的資料是無序的。

LinkedHashSet：此實作與HashSet的不同之外在于，後者維護着一個運作于所有條目的雙重連結清單。存儲的資料是有序的。

HashSet類

HashSet類直接實作了Set接口，其底層其實是包裝了一個HashMap去實作的。HashSet采用HashCode算法來存取集合中的元素，是以具有比較好的讀取和查找性能。

HashSet的特征:

不僅不能保證元素插入的順序，而且在元素在以後的順序中也可能變化(這是由HashSet按HashCode存儲對象(元素)決定的，對象變化則可能導緻HashCode變化)

HashSet是線程非安全的

HashSet元素值可以為NULL

HashSet常用方法:

public boolean contains(Object o) ：如果set包含指定元素，傳回true

public Iterator iterator()傳回set中元素的疊代器

public Object[] toArray() ：傳回包含set中所有元素的數組public Object[] toArray(Object[] a) ：傳回包含set中所有元素的數組，傳回數組的運作時類型是指定數組的運作時類型

public boolean add(Object o) ：如果set中不存在指定元素，則向set加入

public boolean remove(Object o) ：如果set中存在指定元素，則從set中删除

public boolean removeAll(Collection c) ：如果set包含指定集合，則從set中删除指定集合的所有元素

public boolean containsAll(Collection c) ：如果set包含指定集合的所有元素，傳回true。如果指定集合也是一個set，隻有是目前set的子集時，方法傳回true

實作Set接口的HashSet，依靠HashMap來實作的。

我們應該為要存放到散清單的各個對象定義hashCode()和equals()。

HashSet的equals和HashCode：

前面說過，Set集合是不允許重複元素的，否則将會引發各種奇怪的問題。那麼HashSet如何判斷元素重複呢？

HashSet需要同時通過equals和HashCode來判斷兩個元素是否相等，具體規則是，如果兩個元素通過equals為true，并且兩個元素的hashCode相等，則這兩個元素相等(即重複)。

是以如果要重寫儲存在HashSet中的對象的equals方法，也要重寫hashCode方法，重寫前後hashCode傳回的結果相等(即保證儲存在同一個位置)。所有參與計算 hashCode() 傳回值的關鍵屬性，都應該用于作為 equals() 比較的标準。

試想如果重寫了equals方法但不重寫hashCode方法，即相同equals結果的兩個對象将會被HashSet當作兩個元素儲存起來，這與我們設計HashSet的初衷不符(元素不重複)。

另外如果兩個元素哈市Code相等但equals結果不為true，HashSet會将這兩個元素儲存在同一個位置，并将超過一個的元素以連結清單方式儲存，這将影響HashSet的效率。

如果重寫了equals方法但沒有重寫hashCode方法，則HashSet可能無法正常工作，比如下面的例子。

import java.util.HashSet;

import java.util.Objects;

import java.util.Set;

public class R {

private int count;

public R(int count) {

this.count = count;

}

@Override

public String toString() {

return "R{" + "count=" + count + " # hashCode=" + this.hashCode() + '}';

}

@Override

public boolean equals(Object o) {

if (this == o) return true;

if (o == null || getClass() != o.getClass()) return false;

R r = (R) o;

return count == r.count;

}

// @Override

// public int hashCode() {

// return Objects.hash(count);

// }

public static void main(String[] args) {

Set set = new HashSet();

set.add(new R(5));

set.add(new R(-3));

set.add(new R(9));

set.add(new R(-2));

System.out.println(set.contains(new R(-3)));

System.out.println(set);

}

}

上面注釋了hashCode方法，是以你将會看到下面的結果。

false

[R{count=9 # hashCode=2003749087}, R{count=5 # hashCode=1283928880}, R{count=-3 # hashCode=295530567}, R{count=-2 # hashCode=1324119927}]

取消注釋，則結果就正确了

true

[R{count=5 # hashCode=36}, R{count=9 # hashCode=40}, R{count=-3 # hashCode=28}, R{count=-2 # hashCode=29}]

如何達到不能存在重複元素的目的？

“鍵”就是我們要存入的對象，“值”則是一個常量。這樣可以確定，我們所需要的存儲的資訊是“鍵”。而“鍵”在Map中是不能重複的，這就保證了我們存入Set中的所有的元素都不重複。

HashSet如何過濾重複元素

調用元素HashCode獲得哈希碼--》判斷哈希碼是否相等，不相等則錄入

---》相等則判斷equals()後是否相等，不相等在進行 hashcode錄入，相等不錄入

LinkedHashSet的特征

LinkedHashSet是HashSet的一個子類，LinkedHashSet也根據HashCode的值來決定元素的存儲位置，但同時它還用一個連結清單來維護元素的插入順序，插入的時候即要計算hashCode又要維護連結清單，而周遊的時候隻需要按連結清單來通路元素。檢視LinkedHashSet的源碼發現它是樣的

public class LinkedHashSet

extends HashSet

implements Set, Cloneable, java.io.Serializable{

private static final long serialVersionUID = -2851667679971038690L;

public LinkedHashSet(int initialCapacity, float loadFactor){

super(initialCapacity, loadFactor, true);

}

....

在JAVA8中， LinkedHashSet沒有定義任何方法，隻有四個構造函數，它的構造函數調用了父類(HashSet)的帶三個參數的構造方法，父類的構造函數如下

HashSet(int initialCapacity, float loadFactor, boolean dummy) {

map = new LinkedHashMap<>(initialCapacity, loadFactor);

}

由此可知，LinkedHashSet本質上也是從LinkedHashMap而來，LinkedHashSet的所有方法都繼承自HashSet, 而它能維持元素的插入順序的性質則繼承自LinkedHashMap.

下面是一個LinkedHashSet維持元素插入順序的例子

import java.util.LinkedHashSet;

import java.util.Set;

public class LinkedHashSets {

public static void main(String[] args) {

Set set = new LinkedHashSet();

set.add("abc");

set.add("efg");

set.add("hjk");

System.out.println(set);

set.remove(new String("abc"));

set.add("abc");

System.out.println(set);

}

}

輸入如下

[abc, efg, hjk]

[efg, hjk, abc]

TreeSet類的特征

TreeSet實作了SortedSet接口，顧名思義這是一種排序的Set集合，檢視jdk源碼發現底層是用TreeMap實作的，本質上是一個紅黑樹原理。 正因為它是排序了的，是以相對HashSet來說，TreeSet提供了一些額外的按排序位置通路元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet().

TreeSet的排序分兩種類型，一種是自然排序，另一種是定制排序。

自然排序(在元素中寫排序規則)

TreeSet 會調用compareTo方法比較元素大小，然後按升序排序。是以自然排序中的元素對象，都必須實作了Comparable接口，否則會抛出異常。對于TreeSet判斷元素是否重複的标準，也是調用元素從Comparable接口繼承而來額compareTo方法，如果傳回0則是重複元素(兩個元素I相等)。Java的常見類都已經實作了Comparable接口，下面舉例說明沒有實作Comparable存入TreeSet時引發異常的情況。

import java.util.Set;

import java.util.TreeSet;

public class TestSets{

public static void main(String[] args) {

Set set = new TreeSet();

set.add(new Err());

set.add(new Err());

set.add(new Err());

System.out.println(set);

}

}

class Err{

}

運作程式會抛出如下異常

Exception in thread "main" java.lang.ClassCastException: clc.Err cannot be cast to java.lang.Comparable

at java.util.TreeMap.compare(TreeMap.java:1294)

at java.util.TreeMap.put(TreeMap.java:538)

at java.util.TreeSet.add(TreeSet.java:255)

at clc.TestSets.main(TestSets.java:17)

将上面的Err類實作Comparable接口之後程式就能正常運作了

class Err implements Comparable{

@Override

public int compareTo(Object o) {

return 0;

}

}

還有個重要問題是，因為TreeSet會調用元素的compareTo方法，這就要求所有元素的類型都相同，否則也會發生異常。也就是說，TreeSet隻允許存入同一類的元素。例如下面這個例子就會抛出類型轉換異常

public static void main(String[] args) {

Set set = new TreeSet();

set.add(1);

set.add("2");

System.out.println(set);

}

運作結果

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.util.Date

at java.util.Date.compareTo(Date.java:131)

at java.util.TreeMap.put(TreeMap.java:568)

at java.util.TreeSet.add(TreeSet.java:255)

at clc.TestSets.main(TestSets.java:19)

定制排序(在集合中寫排序規則)

TreeSet還有一種排序就是定制排序，定制排序時候，需要關聯一個Comparator對象，由Comparator提供排序邏輯。下面就是一個使用Lambda表達式代替Comparator對象來提供定制排序的例子。下面是一個定制排序的列子

import java.util.Comparator;

import java.util.Set;

import java.util.TreeSet;

public class TestSets {

public static void main(String[] args) {

Set set = new TreeSet(new MyCommpare());

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

}

class M {

int age;

public M(int age) {

this.age = age;

}

}

class MyCommpare implements Comparator {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

}

當然将Comparator直接寫入TreeSet初始化中也可以。如下。

import org.junit.Test;

import java.util.Comparator;

import java.util.Set;

import java.util.TreeSet;

public class TestSets {

public static void main(String[] args) {

Set set = new TreeSet(new MyCommpare());

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

@Test

public void testTreeSet() {

Set set = new TreeSet(new Comparator() {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

});

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

@Test

public void testTreeSetLam() {

Set set = new TreeSet((o1, o2) -> {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

});

set.add(new M(5));

set.add(new M(3));

set.add(new M(9));

System.out.println(set);

}

}

class M {

int age;

public M(int age) {

this.age = age;

}

}

class MyCommpare implements Comparator {

@Override

public int compare(Object o1, Object o2) {

M m1 = (M) o1;

M m2 = (M) o2;

return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0;

}

}

class Err implements Comparable {

@Override

public int compareTo(Object o) {

return 0;

}

TreeSet是依靠TreeMap來實作的。

TreeSet是一個有序集合，TreeSet中元素将按照升序排列，預設是按照自然順序進行排列，意味着TreeSet中元素要實作Comparable接口。

我們可以在構造TreeSet對象時，傳遞實作了Comparator接口的比較器對象。

Comparable和Comparator

Comparable 接口以提供自然排序順序。

對于那些沒有自然順序的類、或者當您想要一個不同于自然順序的順序時，您可以實作Comparator 接口來定義您自己的排序函數。可以将Comparator傳遞給Collections.sort或Arrays.sort。

Comparator接口

當一個類并未實作Comparable，或者不喜歡預設的Comaparable行為。可以實作Comparator接口

直接實作Comparator的compare接口完成自定義比較類。

例：Arrays.sort(results, new Comparator() 數組排序 RepDataQueryExecutor

例：Collections.sort(lst,new Comparator()

EnumSet特征

EnumSet顧名思義就是專為枚舉類型設計的集合，是以集合元素必須是枚舉類型，否則會抛出異常。 EnumSet集合也是有序的，其順序就是Enum類内元素定義的順序。 EnumSet存取的速度非常快，批量操作的速度也很快。EnumSet主要提供以下方法，allOf, complementOf, copyOf, noneOf, of, range等。注意到EnumSet并沒有提供任何構造函數，要建立一個EnumSet集合對象，隻需要調用allOf等方法，下面是一個EnumSet的例子。

import java.util.EnumSet;

public class EnumSets {

public static void main(String[] args) {

EnumSet es1 = EnumSet.allOf(Season.class);

System.out.println(es1);

EnumSet es2 = EnumSet.noneOf(Season.class);

es2.add(Season.WINTER);

es2.add(Season.SUMER);

System.out.println(es2);

EnumSet es3 = EnumSet.of(Season.WINTER, Season.SUMER);

System.out.println(es3);

EnumSet es4 = EnumSet.range(Season.SUMER,Season.WINTER );

System.out.println(es4);

EnumSet es5 = EnumSet.complementOf(es4);

System.out.println(es5);

}

}

enum Season {

SPRING, SUMER, FALL, WINTER

}

執行結果

[SPRING, SUMER, FALL, WINTER]

[SUMER, WINTER]

[SUMER, WINTER]

[SUMER, FALL, WINTER]

[SPRING]

幾種Set的比較：

HashSet外部無序地周遊成員。

成員可為任意Object子類的對象，但如果覆寫了equals方法，同時注意修改hashCode方法。

TreeSet外部有序地周遊成員；

附加實作了SortedSet, 支援子集等要求順序的操作

成員要求實作Comparable接口，或者使用Comparator構造TreeSet。成員一般為同一類型。

LinkedHashSet外部按成員的插入順序周遊成員

成員與HashSet成員類似

HashSet是基于Hash算法實作的，其性能通常都優于TreeSet。我們通常都應該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。

HashSet的元素存放順序和我們添加進去時候的順序沒有任何關系，而LinkedHashSet 則保持元素的添加順序。TreeSet則是對我們的Set中的元素進行排序存放。

一般來說，當您要從集合中以有序的方式抽取元素時，TreeSet實作就會有用處。為了能順利進行，添加到 TreeSet 的元素必須是可排序的。 而您同樣需要對添加到TreeSet中的類對象實作 Comparable 接口的支援。一般說來，先把元素添加到 HashSet，再把集合轉換為 TreeSet 來進行有序周遊會更快。

各種Set集合性能分析

HashSet和TreeSet是Set集合中用得最多的I集合。HashSet總是比TreeSet集合性能好，因為HashSet不需要額維護元素的順序。

LinkedHashSet需要用額外的連結清單維護元素的插入順序，是以在插入時性能比HashSet低，但在疊代通路(周遊)時性能更高。因為插入的時候即要計算hashCode又要維護連結清單，而周遊的時候隻需要按連結清單來通路元素。

EnumSet元素是所有Set元素中性能最好的，但是它隻能儲存Enum類型的元素

Map

集合架構的第二類接口樹。

它提供了一組鍵值的映射。其中存儲的每個對象都有一個相應的關鍵字(key)，關鍵字決定了對象在Map中的存儲位置。

關鍵字應該是唯一的，每個key 隻能映射一個value。

實作類：

HashMap、TreeMap、LinkedHashMap、Hashtable等

HashMap：鍵值對，key不能重複，但是value可以重複；key的實作就是HashSet；value對應着放；允許null的鍵或值；

Hashtable：線程安全的，不允許null的鍵或值；

Properties:：key和value都是String類型，用來讀配置檔案；

TreeMap：對key排好序的Map; key 就是TreeSet, value對應每個key; key要實作Comparable接口或TreeMap有自己的構造器；

LinkedHashMap： 此實作與HashMap的不同之處在于，後者維護着一個運作于所有條目的雙重連結清單。存儲的資料是有序的。

HashMap：

Map 主要用于存儲鍵(key)值(value)對，根據鍵得到值，是以鍵不允許重複,但允許值重複。

HashMap 是一個最常用的Map,它根據鍵的HashCode值存儲資料,根據鍵可以直接擷取它的值，具有很快的通路速度。

HashMap最多隻允許一條記錄的鍵為Null;允許多條記錄的值為 Null;

HashMap不支援線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導緻資料的不一緻。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

HashMap實作原理---散列

Hash雜湊演算法的意義在于提供了一種快速存取資料的方法,它用一種算法建立鍵值與真實值之間的對應關系。散清單又稱為哈希表。散清單算法的基本思想是：以結點的關鍵字為自變量，通過一定的函數關系(散列函數)計算出對應的函數值，以這個值作為該結點存儲在散清單中位址。

當散清單中的元素存放太滿，就必須進行再散列，将産生一個新的散清單，所有元素存放到新的散清單中，原先的散清單将被删除。在Java語言中，通過負載因子(load factor)來決定何時對散清單進行再散列。例如：如果負載因子0.75，當散清單中已經有75%位置已經放滿，那麼将進行再散列。

負載因子越高(越接近1.0)，記憶體的使用效率越高，元素的尋找時間越長。負載因子越低(越接近0.0)，元素的尋找時間越短，記憶體浪費越多。

何時需重寫equals？

當一個類有自己特有的“邏輯相等”概念(不同于對象身份的概念)；

Object類僅僅提供了一個對引用的比較，如果兩個引用不是同一個那就傳回false，這是無法滿足大多數對象比較的需要的，是以要覆寫；

使用==操作符檢查實參是否為指向對象的引用”

使用instanceof操作符檢查實參是否為正确的類型

把實參轉換到正确的類型；

對于該類中每一個“關鍵”域，檢查實參中的域與目前對象中對應的域值是否比對。對于既不是float也不是double類型的基本類型的域，可以使用==操作符進行比較；對于對象引用類型的域，可以遞歸地調用所引用的對象的equals方法，對于float和double類型的域，先轉換成int或long類型的值，然後使用==操作符比較；

當你編寫完成了equals方法之後，應該問自己三個問題：它是否是對稱的、傳 遞的、一緻的？ 如果答案是否定的，那麼請找到 這些特性未能滿足的原因，再修改equals方法的代碼

equals()和hashCode()同時覆寫

尤其強調當一個對象被當作鍵值(或索引)來使用的時候要重寫這兩個方法；

覆寫equals後，兩個不同執行個體可能在邏輯上相等，但是根據Object.hashCode方法卻産生不同的散列碼，違反“相等的對象必須具有相等的散列碼”。

導緻，當你用其中的一個作為鍵儲存到hashMap、hasoTable或hashSet中，再以“相等的”找另 一個作為鍵值去查找他們的時候，則根本找不到

不同類型的hashCode取值

如果該域是布爾型的，計算(f？0：1)

如果是char,short,byte或int，計算(int)f

如果是long類型，計算(int)(f^(f>>>32))

如果是float類型，計算Float.floatToIntBits(f)

如果是double類型，計算Dobule.doubleToLongBits(f)

如果該域是一個對象引用，遞歸調用hashCode

如果該域是一個數組，則把每個元素當做單獨的域來處理，對每個重要的元素計算一個散列碼

Map集合比較：

HashMap的存入順序和輸出順序無關。

LinkedHashMap 則保留了鍵值對的存入順序。

TreeMap則是對Map中的元素進行排序。

因為HashMap和LinkedHashMap 存儲資料的速度比直接使用TreeMap 要快，存取效率要高。

當完成了所有的元素的存放後，我們再對整個的Map中的元素進行排序。這樣可以提高整個程式的運作的效率，縮短執行時間。

注意：TreeMap中是根據鍵(Key)進行排序的。而如果我們要使用TreeMap來進行正常的排序的話，Key 中存放的對象必須實作Comparable 接口。

Map常用方法：

Object put(Object key,Object value)：用來存放一個鍵-值對Map中

Object remove(Object key)：根據key(鍵)，移除鍵-值對，并将值傳回

void putAll(Map mapping) ：将另外一個Map中的元素存入目前的Map中

void clear() ：清空目前Map中的元素

Object get(Object key) ：根據key(鍵)取得對應的值

boolean containsKey(Object key) ：判斷Map中是否存在某鍵(key)

boolean containsValue(Object value):判斷Map中是否存在某值(value)

public Set keySet() ：傳回所有的鍵(key)，并使用Set容器存放

public Collection values() ：傳回所有的值(Value)，并使用Collection存放

public Set entrySet() ：傳回一個實作 Map.Entry 接口的元素 Set

集合周遊

增強for循環 for(Obj o:c){syso(o)}

使用iterator ， Iterator it=c.iterator;

while(it.hasNext()){Object o = it.next()}

普通循環：for(Iterator it=c.iterator();it.hasNext();){it.next() }

總結

ArrayList: 元素單個，效率高，多用于查詢

Vector: 元素單個，線程安全，多用于查詢

LinkedList:元素單個，多用于插入和删除

HashMap: 元素成對，元素可為空

shTable: 元素成對，線程安全，元素不可為空

HashMap和Hashtable的差別：

HashMap和Hashtable都是java的集合類，都可以用來存放java對象，這是他們的相同點

以下是他們的差別：

曆史原因：

Hashtable是基于陳舊的Dictionary類的，HashMap是java 1.2引進的Map接口的一個現實。

同步性：

hashtable是同步的，這個類中的一些方法保證了Hashtable中的對象是線程安全的，而HashMap則是異步的，是以HashMap中的對象并不是線程安全的，因為同步的要求會影響執行的效率，是以如果你不需要線程安全的結合那麼使用HashMap是一個很好的選擇，這樣可以避免由于同步帶來的不必要的性能開銷，進而提高效率，我們一般所編寫的程式都是異步的，但如果是伺服器端的代碼除外。

值：

HashMap可以讓你将空值作為一個表的條目的key或value

Hashtable是不能放入空值(null)的

ArrayList和Vector的差別：

ArrayList與Vector都是java的集合類，都是用來存放java對象，這是他們的相同點，

差別：

同步性：

Vector是同步的，這個類的一些方法保證了Vector中的對象的線程安全的，而ArrayList則是異步的，是以ArrayList中的對象并不 是線程安全的，因為同步要求會影響執行的效率，是以你不需要線程安全的集合那麼使用ArrayList是一個很好的選擇，這樣可以避免由于同步帶來的不必 要的性能開銷。

資料增長：

從内部實作的機制來講，ArrayList和Vector都是使用數組(Array)來控制集合中的對象，當你向兩種類型中增加元素的時候，如果元素的數目超過了内部數組目前的長度他們都需要擴充内部數組的長度，Vector預設情況下自動增長原來一倍的數組長度，ArrayList是原來的50%，是以最後你獲得的這個集合所占的空間總是比你實際需要的要大，是以如果你要在集合中儲存大量的資料，那麼使用Vector有一些優勢，因為你可以通過設定集合的初始大小來避免不必要的資源開銷。

總結：

如果要求線程安全，使用Vector，Hashtable

如果不要求線程安全，使用ArrayList，LinkedList，HashMap

如果要求鍵值對，則使用HashMap，Hashtable

如果資料量很大，又要求線程安全考慮Vector

arraylist和linkedlist聯系與差別

ArrayList是實作了基于動态數組的資料結構，LinkedList基于連結清單的資料結構。

對于随機通路get和set，ArrayList覺得優于LinkedList，因為LinkedList要移動指針。

對于新增和删除操作add和remove，LinedList比較占優勢，因為ArrayList要移動資料。 這一點要看實際情況的。若隻對單條資料插入或删除，ArrayList的速度反而優于LinkedList。但若是批量随機的插入删除資料，LinkedList的速度大大優于ArrayList. 因為ArrayList每插入一條資料，要移動插入點及之後的所有資料。

HashMap與TreeMap聯系與差別

HashMap通過hashcode對其内容進行快速查找，而TreeMap中所有的元素都保持着某種固定的順序，如果你需要得到一個有序的結果你就應該使用TreeMap(HashMap中元素的排列順序是不固定的)。

在Map 中插入、删除和定位元素，HashMap是最好的選擇。但如果您要按自然順序或自定義順序周遊鍵，那麼TreeMap會更好。使用HashMap要求添加的鍵類明确定義了hashCode()和 equals()的實作。

兩個map中的元素一樣，但順序不一樣，導緻hashCode()不一樣。

同樣做測試：

在HashMap中，同樣的值的map,順序不同，equals時，false;

而在treeMap中，同樣的值的map,順序不同,equals時，true，說明，treeMap在equals()時是整理了順序了的。