Java集合類(lèi)怎么使用

這篇文章主要講解了“Java集合類(lèi)怎么使用”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“Java集合類(lèi)怎么使用”吧！

初始容量

集合是我們?cè)贘ava編程中使用非常廣泛的，它就像大海，海納百川，像萬(wàn)能容器，盛裝萬(wàn)物，而且這個(gè)大海，萬(wàn)能容器還可以無(wú)限變大（如果條件允許）。當(dāng)這個(gè)海、容器的量變得非常大的時(shí)候，它的初始容量就會(huì)顯得很重要了，因?yàn)橥诤?、擴(kuò)容是需要消耗大量的人力物力財(cái)力的。

同樣的道理，Collection的初始容量也顯得異常重要。所以：對(duì)于已知的情景，請(qǐng)為集合指定初始容量。

public static void main(String[] args) {
    StudentVO student = null;
    long begin1 = System.currentTimeMillis();
    List<StudentVO> list1 = new ArrayList<>();
    for(int i = 0 ; i < 1000000; i++){
        student = new StudentVO(i,"chenssy_"+i,i);
        list1.add(student);
    }
    long end1 = System.currentTimeMillis();
    System.out.println("list1 time：" + (end1 - begin1));
    
    long begin2 = System.currentTimeMillis();
    List<StudentVO> list2 = new ArrayList<>(1000000);
    for(int i = 0 ; i < 1000000; i++){
        student = new StudentVO(i,"chenssy_"+i,i);
        list2.add(student);
    }
    long end2 = System.currentTimeMillis();
    System.out.println("list2 time：" + (end2 - begin2));
}

上面代碼兩個(gè)list都是插入1000000條數(shù)據(jù)，只不過(guò)list1沒(méi)有沒(méi)有申請(qǐng)初始化容量，而list2初始化容量1000000。那運(yùn)行結(jié)果如下：

list1 time：1638
list2 time：921

從上面的運(yùn)行結(jié)果我們可以看出list2的速度是list1的兩倍左右。在前面LZ就提過(guò)，ArrayList的擴(kuò)容機(jī)制是比較消耗資源的。我們先看ArrayList的add方法：

public boolean add(E e) {  
        ensureCapacity(size + 1);   
        elementData[size++] = e;  
        return true;  
    }  
public void ensureCapacity(int minCapacity) {  
    modCount++;         //修改計(jì)數(shù)器
    int oldCapacity = elementData.length;    
    //當(dāng)前需要的長(zhǎng)度超過(guò)了數(shù)組長(zhǎng)度，進(jìn)行擴(kuò)容處理
    if (minCapacity > oldCapacity) {  
        Object oldData[] = elementData;  
        //新的容量 = 舊容量 * 1.5 + 1
        int newCapacity = (oldCapacity * 3)/2 + 1;  
            if (newCapacity < minCapacity)  
                newCapacity = minCapacity;  
      //數(shù)組拷貝，生成新的數(shù)組 
      elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
}

ArrayList每次新增一個(gè)元素，就會(huì)檢測(cè)ArrayList的當(dāng)前容量是否已經(jīng)到達(dá)臨界點(diǎn)，如果到達(dá)臨界點(diǎn)則會(huì)擴(kuò)容1.5倍。然而ArrayList的擴(kuò)容以及數(shù)組的拷貝生成新的數(shù)組是相當(dāng)耗資源的。所以若我們事先已知集合的使用場(chǎng)景，知道集合的大概范圍，我們最好是指定初始化容量，這樣對(duì)資源的利用會(huì)更加好，尤其是大數(shù)據(jù)量的前提下，效率的提升和資源的利用會(huì)顯得更加具有優(yōu)勢(shì)。

asList的缺陷

在實(shí)際開(kāi)發(fā)過(guò)程中我們經(jīng)常使用asList講數(shù)組轉(zhuǎn)換為L(zhǎng)ist，這個(gè)方法使用起來(lái)非常方便，但是asList方法存在幾個(gè)缺陷：

避免使用基本數(shù)據(jù)類(lèi)型數(shù)組轉(zhuǎn)換為列表

使用8個(gè)基本類(lèi)型數(shù)組轉(zhuǎn)換為列表時(shí)會(huì)存在一個(gè)比較有味的缺陷。先看如下程序：

public static void main(String[] args) {
        int[] ints = {1,2,3,4,5};
        List list = Arrays.asList(ints);
        System.out.println("list'size：" + list.size());
    }
------------------------------------
outPut：
list'size：1

程序的運(yùn)行結(jié)果并沒(méi)有像我們預(yù)期的那樣是5而是逆天的1，這是什么情況？先看源碼：

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

asList接受的參數(shù)是一個(gè)泛型的變長(zhǎng)參數(shù)，我們知道基本數(shù)據(jù)類(lèi)型是無(wú)法發(fā)型化的，也就是說(shuō)8個(gè)基本類(lèi)型是無(wú)法作為asList的參數(shù)的， 要想作為泛型參數(shù)就必須使用其所對(duì)應(yīng)的包裝類(lèi)型。但是這個(gè)這個(gè)實(shí)例中為什么沒(méi)有出錯(cuò)呢？

因?yàn)樵搶?shí)例是將int類(lèi)型的數(shù)組當(dāng)做其參數(shù)，而在Java中數(shù)組是一個(gè)對(duì)象，它是可以泛型化的。所以該例子是不會(huì)產(chǎn)生錯(cuò)誤的。既然例子是將整個(gè)int類(lèi)型的數(shù)組當(dāng)做泛型參數(shù)，那么經(jīng)過(guò)asList轉(zhuǎn)換就只有一個(gè)int 的列表了。如下：

public static void main(String[] args) {
    int[] ints = {1,2,3,4,5};
    List list = Arrays.asList(ints);
    System.out.println("list 的類(lèi)型:" + list.get(0).getClass());
    System.out.println("list.get(0) == ints：" + list.get(0).equals(ints));
}

outPut: list 的類(lèi)型:class [I list.get(0) == ints：true 從這個(gè)運(yùn)行結(jié)果我們可以充分證明list里面的元素就是int數(shù)組。弄清楚這點(diǎn)了，那么修改方法也就一目了然了：將int 改變?yōu)镮nteger。

public static void main(String[] args) {
        Integer[] ints = {1,2,3,4,5};
        List list = Arrays.asList(ints);
        System.out.println("list'size：" + list.size());
        System.out.println("list.get(0) 的類(lèi)型:" + list.get(0).getClass());
        System.out.println("list.get(0) == ints[0]：" + list.get(0).equals(ints[0]));
    }
----------------------------------------
outPut:
list'size：5
list.get(0) 的類(lèi)型:class java.lang.Integer
list.get(0) == ints[0]：true

asList產(chǎn)生的列表不可操作

對(duì)于上面的實(shí)例我們?cè)僮鲆粋€(gè)小小的修改：

public static void main(String[] args) {
        Integer[] ints = {1,2,3,4,5};
        List list = Arrays.asList(ints);
        list.add(6);
    }

該實(shí)例就是講ints通過(guò)asList轉(zhuǎn)換為list 類(lèi)別，然后再通過(guò)add方法加一個(gè)元素，這個(gè)實(shí)例簡(jiǎn)單的不能再簡(jiǎn)單了，但是運(yùn)行結(jié)果呢？打出我們所料：

Exception in thread "main" java.lang.UnsupportedOperationException
    at java.util.AbstractList.add(Unknown Source)
    at java.util.AbstractList.add(Unknown Source)
    at com.chenssy.test.arrayList.AsListTest.main(AsListTest.java:10)

運(yùn)行結(jié)果盡然拋出UnsupportedOperationException異常，該異常表示list不支持add方法。這就讓我們郁悶了，list怎么可能不支持add方法呢？難道jdk腦袋堵塞了？我們?cè)倏碼sList的源碼：

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

asList接受參數(shù)后，直接new 一個(gè)ArrayList，到這里看應(yīng)該是沒(méi)有錯(cuò)誤的??？別急，再往下看:

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable{
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;
        ArrayList(E[] array) {
            if (array==null)
                throw new NullPointerException();
            a = array;
        }
        //.................
    }

這是ArrayList的源碼,從這里我們可以看出,此ArrayList不是java.util.ArrayList，他是Arrays的內(nèi)部類(lèi)。

該內(nèi)部類(lèi)提供了size、toArray、get、set、indexOf、contains方法，而像add、remove等改變list結(jié)果的方法從AbstractList父類(lèi)繼承過(guò)來(lái)，同時(shí)這些方法也比較奇葩，它直接拋出UnsupportedOperationException異常：

public boolean add(E e) {
        add(size(), e);
        return true;
    }
    
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
    
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }

通過(guò)這些代碼可以看出asList返回的列表只不過(guò)是一個(gè)披著list的外衣，它并沒(méi)有l(wèi)ist的基本特性（變長(zhǎng)）。該list是一個(gè)長(zhǎng)度不可變的列表，傳入?yún)?shù)的數(shù)組有多長(zhǎng)，其返回的列表就只能是多長(zhǎng)。所以：：不要試圖改變asList返回的列表，否則你會(huì)自食苦果。

subList的缺陷

我們經(jīng)常使用subString方法來(lái)對(duì)String對(duì)象進(jìn)行分割處理，同時(shí)我們也可以使用subList、subMap、subSet來(lái)對(duì)List、Map、Set進(jìn)行分割處理，但是這個(gè)分割存在某些瑕疵。

subList返回僅僅只是一個(gè)視圖

首先我們先看如下實(shí)例：

public static void main(String[] args) { List list1 = new ArrayList(); list1.add(1); list1.add(2);

    //通過(guò)構(gòu)造函數(shù)新建一個(gè)包含list1的列表 list2
    List<Integer> list2 = new ArrayList<Integer>(list1);
    
    //通過(guò)subList生成一個(gè)與list1一樣的列表 list3
    List<Integer> list3 = list1.subList(0, list1.size());
    
    //修改list3
    list3.add(3);
    
    System.out.println("list1 == list2：" + list1.equals(list2));
    System.out.println("list1 == list3：" + list1.equals(list3));
}

這個(gè)例子非常簡(jiǎn)單，無(wú)非就是通過(guò)構(gòu)造函數(shù)、subList重新生成一個(gè)與list1一樣的list，然后修改list3，最后比較list1 == list2?、list1 == list3?。

按照我們常規(guī)的思路應(yīng)該是這樣的：因?yàn)閘ist3通過(guò)add新增了一個(gè)元素，那么它肯定與list1不等，而list2是通過(guò)list1構(gòu)造出來(lái)的，所以應(yīng)該相等，所以結(jié)果應(yīng)該是：

list1 == list2：true
list1 == list3: false

首先我們先不論結(jié)果的正確與否，我們先看subList的源碼：

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
}

subListRangeCheck方式是判斷fromIndex、toIndex是否合法，如果合法就直接返回一個(gè)subList對(duì)象，注意在產(chǎn)生該new該對(duì)象的時(shí)候傳遞了一個(gè)參數(shù) this ，該參數(shù)非常重要，因?yàn)樗碇糽ist。

/** * 繼承AbstractList類(lèi)，實(shí)現(xiàn)RandomAccess接口 */ private class SubList extends AbstractList implements RandomAccess { private final AbstractList parent; //列表 private final int parentOffset;
private final int offset; int size;

    //構(gòu)造函數(shù)
    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    //set方法
    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
    //get方法
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }
    //add方法
    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }
    //remove方法
    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }
}

該SubLsit是ArrayList的內(nèi)部類(lèi)，它與ArrayList一樣，都是繼承AbstractList和實(shí)現(xiàn)RandomAccess接口。同時(shí)也提供了get、set、add、remove等list常用的方法。但是它的構(gòu)造函數(shù)有點(diǎn)特殊，在該構(gòu)造函數(shù)中有兩個(gè)地方需要注意：

1、this.parent = parent;而parent就是在前面?zhèn)鬟f過(guò)來(lái)的list，也就是說(shuō)this.parent就是原始list的引用。

2、this.offset = offset + fromIndex;this.parentOffset = fromIndex;。同時(shí)在構(gòu)造函數(shù)中它甚至將modCount（fail-fast機(jī)制）傳遞過(guò)來(lái)了。

我們?cè)倏磄et方法，在get方法中return ArrayList.this.elementData(offset + index);

這段代碼可以清晰表明get所返回就是原列表offset + index位置的元素。同樣的道理還有add方法里面的：

parent.add(parentOffset + index, e); this.modCount = parent.modCount; remove方法里面的

E result = parent.remove(parentOffset + index); this.modCount = parent.modCount;

誠(chéng)然，到了這里我們可以判斷subList返回的SubList同樣也是AbstractList的子類(lèi)，同時(shí)它的方法如get、set、add、remove等都是在原列表上面做操作，它并沒(méi)有像subString一樣生成一個(gè)新的對(duì)象。

所以subList返回的只是原列表的一個(gè)視圖，它所有的操作最終都會(huì)作用在原列表上。

那么從這里的分析我們可以得出上面的結(jié)果應(yīng)該恰恰與我們上面的答案相反：

list1 == list2：false list1 == list3：true

subList生成子列表后，不要試圖去操作原列表

從上面我們知道subList生成的子列表只是原列表的一個(gè)視圖而已，如果我們操作子列表它產(chǎn)生的作用都會(huì)在原列表上面表現(xiàn)，但是如果我們操作原列表會(huì)產(chǎn)生什么情況呢？

public static void main(String[] args) { List list1 = new ArrayList(); list1.add(1); list1.add(2);

    //通過(guò)subList生成一個(gè)與list1一樣的列表 list3
    List<Integer> list3 = list1.subList(0, list1.size());
    //修改list1
    list1.add(3);
    
    System.out.println("list1'size：" + list1.size());
    System.out.println("list3'size：" + list3.size());
}

該實(shí)例如果不產(chǎn)生意外，那么他們兩個(gè)list的大小都應(yīng)該都是3，但是偏偏事與愿違，事實(shí)上我們得到的結(jié)果是這樣的：

list1'size：3
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$SubList.checkForComodification(Unknown Source)
    at java.util.ArrayList$SubList.size(Unknown Source)
    at com.chenssy.test.arrayList.SubListTest.main(SubListTest.java:17)

list1正常輸出，但是list3就拋出ConcurrentModificationException異常，看過(guò)我另一篇博客的同仁肯定對(duì)這個(gè)異常非常，fail-fast？不錯(cuò)就是fail-fast機(jī)制，在fail-fast機(jī)制中，LZ花了很多力氣來(lái)講述這個(gè)異常，所以這里L(fēng)Z就不對(duì)這個(gè)異常多講了。我們?cè)倏磗ize方法：

public int size() {
            checkForComodification();
            return this.size;
        }

size方法首先會(huì)通過(guò)checkForComodification驗(yàn)證，然后再返回this.size。

private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }

該方法表明當(dāng)原列表的modCount與this.modCount不相等時(shí)就會(huì)拋出ConcurrentModificationException。

同時(shí)我們知道m(xù)odCount 在new的過(guò)程中 "繼承"了原列表modCount，只有在修改該列表（子列表）時(shí)才會(huì)修改該值（先表現(xiàn)在原列表后作用于子列表）。

而在該實(shí)例中我們是操作原列表，原列表的modCount當(dāng)然不會(huì)反應(yīng)在子列表的modCount上啦，所以才會(huì)拋出該異常。

對(duì)于子列表視圖，它是動(dòng)態(tài)生成的，生成之后就不要操作原列表了，否則必然都導(dǎo)致視圖的不穩(wěn)定而拋出異常。最好的辦法就是將原列表設(shè)置為只讀狀態(tài)，要操作就操作子列表：

//通過(guò)subList生成一個(gè)與list1一樣的列表 list3

List<Integer> list3 = list1.subList(0, list1.size());

//對(duì)list1設(shè)置為只讀狀態(tài)

list1 = Collections.unmodifiableList(list1);

推薦使用subList處理局部列表

在開(kāi)發(fā)過(guò)程中我們一定會(huì)遇到這樣一個(gè)問(wèn)題：獲取一堆數(shù)據(jù)后，需要?jiǎng)h除某段數(shù)據(jù)。例如，有一個(gè)列表存在1000條記錄，我們需要?jiǎng)h除100-200位置處的數(shù)據(jù)，可能我們會(huì)這樣處理：

for(int i = 0 ; i < list1.size() ; i++){
   if(i >= 100 && i <= 200){
       list1.remove(i);
       /*
        * 當(dāng)然這段代碼存在問(wèn)題，list remove之后后面的元素會(huì)填充上來(lái)，
         * 所以需要對(duì)i進(jìn)行簡(jiǎn)單的處理，當(dāng)然這個(gè)不是這里討論的問(wèn)題。
         */
   }
}

這個(gè)應(yīng)該是我們大部分人的處理方式吧，其實(shí)還有更好的方法，利用subList。在前面LZ已經(jīng)講過(guò)，子列表的操作都會(huì)反映在原列表上。所以下面一行代碼全部搞定：

list1.subList(100, 200).clear();

簡(jiǎn)單而不失華麗?。。。?！

保持compareTo和equals同步

在Java中我們常使用Comparable接口來(lái)實(shí)現(xiàn)排序，其中compareTo是實(shí)現(xiàn)該接口方法。我們知道compareTo返回0表示兩個(gè)對(duì)象相等，返回正數(shù)表示大于，返回負(fù)數(shù)表示小于。同時(shí)我們也知道equals也可以判斷兩個(gè)對(duì)象是否相等，那么他們兩者之間是否存在關(guān)聯(lián)關(guān)系呢？

public class Student implements Comparable<Student>{
    private String id;
    private String name;
    private int age;
    
    public Student(String id,String name,int age){
        this.id = id;
        this.name = name;
        this.age = age;
    }
    public boolean equals(Object obj){
        if(obj == null){
            return false;
        }
        
        if(this == obj){
            return true;
        }
        
        if(obj.getClass() != this.getClass()){
            return false;
        }
        
        Student student = (Student)obj;
        if(!student.getName().equals(getName())){
            return false;
        }
        
        return true;
    }
    
    public int compareTo(Student student) {
        return this.age - student.age;
    }
    /** 省略getter、setter方法 */
}

Student類(lèi)實(shí)現(xiàn)Comparable接口和實(shí)現(xiàn)equals方法，其中compareTo是根據(jù)age來(lái)比對(duì)的，equals是根據(jù)name來(lái)比對(duì)的。

public static void main(String[] args){
        List<Student> list = new ArrayList<>();
        list.add(new Student("1", "chenssy1", 24));
        list.add(new Student("2", "chenssy1", 26));
        
        Collections.sort(list);   //排序
        
        Student student = new Student("2", "chenssy1", 26);
        
        //檢索student在list中的位置
        int index1 = list.indexOf(student);
        int index2 = Collections.binarySearch(list, student);
        
        System.out.println("index1 = " + index1);
        System.out.println("index2 = " + index2);
    }

按照常規(guī)思路來(lái)說(shuō)應(yīng)該兩者index是一致的，因?yàn)樗麄儥z索的是同一個(gè)對(duì)象，但是非常遺憾，其運(yùn)行結(jié)果：

index1 = 0 index2 = 1

為什么會(huì)產(chǎn)生這樣不同的結(jié)果呢？這是因?yàn)閕ndexOf和binarySearch的實(shí)現(xiàn)機(jī)制不同。

indexOf是基于equals來(lái)實(shí)現(xiàn)的只要equals返回TRUE就認(rèn)為已經(jīng)找到了相同的元素。

而binarySearch是基于compareTo方法的，當(dāng)compareTo返回0 時(shí)就認(rèn)為已經(jīng)找到了該元素。

在我們實(shí)現(xiàn)的Student類(lèi)中我們覆寫(xiě)了compareTo和equals方法，但是我們的compareTo、equals的比較依據(jù)不同，一個(gè)是基于age、一個(gè)是基于name。

比較依據(jù)不同那么得到的結(jié)果很有可能會(huì)不同。所以知道了原因，我們就好修改了：將兩者之間的比較依據(jù)保持一致即可。

對(duì)于compareTo和equals兩個(gè)方法我們可以總結(jié)為：compareTo是判斷元素在排序中的位置是否相等，equals是判斷元素是否相等，既然一個(gè)決定排序位置，一個(gè)決定相等，所以我們非常有必要確保當(dāng)排序位置相同時(shí)，其equals也應(yīng)該相等。

使其相等的方式就是兩者應(yīng)該依附于相同的條件。當(dāng)compareto相等時(shí)equals也應(yīng)該相等，而compareto不相等時(shí)equals不應(yīng)該相等，并且compareto依據(jù)某些屬性來(lái)決定排序。

今天我們來(lái)探索一下HashSet，TreeSet與LinkedHashSet的基本原理與源碼實(shí)現(xiàn)，由于這三個(gè)set都是基于之前文章的三個(gè)map進(jìn)行實(shí)現(xiàn)的，所以推薦大家先看一下前面有關(guān)map的文章，結(jié)合使用味道更佳。

具體代碼在我的GitHub中可以找到

https://github.com/h3pl/MyTech

文章首發(fā)于我的個(gè)人博客：

https://h3pl.github.io/2018/05/12/collection7

更多關(guān)于Java后端學(xué)習(xí)的內(nèi)容請(qǐng)到我的CSDN博客上查看：

https://blog.csdn.net/a724888

我的個(gè)人博客主要發(fā)原創(chuàng)文章，也歡迎瀏覽  https://h3pl.github.io/

本文參考  http://cmsblogs.com/?p=599

HashSet

定義 public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable

HashSet繼承AbstractSet類(lèi)，實(shí)現(xiàn)Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干實(shí)現(xiàn)，從而最大限度地減少了實(shí)現(xiàn)此接口所需的工作。 ==Set接口是一種不包括重復(fù)元素的Collection，它維持它自己的內(nèi)部排序，所以隨機(jī)訪問(wèn)沒(méi)有任何意義。==

本文基于1.8jdk進(jìn)行源碼分析。

基本屬性

基于HashMap實(shí)現(xiàn)，底層使用HashMap保存所有元素 private transient HashMap<E,Object> map;

//定義一個(gè)Object對(duì)象作為HashMap的value private static final Object PRESENT = new Object();

構(gòu)造函數(shù) /** * 默認(rèn)構(gòu)造函數(shù) * 初始化一個(gè)空的HashMap，并使用默認(rèn)初始容量為16和加載因子0.75。 */ public HashSet() { map = new HashMap<>(); }

/**
 * 構(gòu)造一個(gè)包含指定 collection 中的元素的新 set。
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
/**
 * 構(gòu)造一個(gè)新的空 set，其底層 HashMap 實(shí)例具有指定的初始容量和指定的加載因子
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
/**
 * 構(gòu)造一個(gè)新的空 set，其底層 HashMap 實(shí)例具有指定的初始容量和默認(rèn)的加載因子（0.75）。
 */
public HashSet(int initialCapacity) {
   map = new HashMap<>(initialCapacity);
}
/**
 * 在API中我沒(méi)有看到這個(gè)構(gòu)造函數(shù)，今天看源碼才發(fā)現(xiàn)（原來(lái)訪問(wèn)權(quán)限為包權(quán)限，不對(duì)外公開(kāi)的）
 * 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合。
 * dummy 為標(biāo)識(shí) 該構(gòu)造函數(shù)主要作用是對(duì)LinkedHashSet起到一個(gè)支持作用
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
   map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

從構(gòu)造函數(shù)中可以看出HashSet所有的構(gòu)造都是構(gòu)造出一個(gè)新的HashMap，其中最后一個(gè)構(gòu)造函數(shù)，為包訪問(wèn)權(quán)限是不對(duì)外公開(kāi)，僅僅只在使用LinkedHashSet時(shí)才會(huì)發(fā)生作用。

方法

既然HashSet是基于HashMap，那么對(duì)于HashSet而言，其方法的實(shí)現(xiàn)過(guò)程是非常簡(jiǎn)單的。 public Iterator iterator() { return map.keySet().iterator(); }

iterator()方法返回對(duì)此 set 中元素進(jìn)行迭代的迭代器。返回元素的順序并不是特定的。

底層調(diào)用HashMap的keySet返回所有的key，這點(diǎn)反應(yīng)了HashSet中的所有元素都是保存在HashMap的key中，value則是使用的PRESENT對(duì)象，該對(duì)象為static final。 public int size() { return map.size(); } size()返回此 set 中的元素的數(shù)量（set 的容量）。底層調(diào)用HashMap的size方法，返回HashMap容器的大小。

public boolean isEmpty() { return map.isEmpty(); } isEmpty()，判斷HashSet()集合是否為空，為空返回 true，否則返回false。

public boolean contains(Object o) { return map.containsKey(o); }

public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }

//最終調(diào)用該方法進(jìn)行節(jié)點(diǎn)查找 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //先檢查桶的頭結(jié)點(diǎn)是否存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //不是頭結(jié)點(diǎn)，則遍歷鏈表，如果是樹(shù)節(jié)點(diǎn)則使用樹(shù)節(jié)點(diǎn)的方法遍歷，直到找到，或者為null if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

contains()，判斷某個(gè)元素是否存在于HashSet()中，存在返回true，否則返回false。更加確切的講應(yīng)該是要滿(mǎn)足這種關(guān)系才能返回true：(o==null ? e==null : o.equals(e))。底層調(diào)用containsKey判斷HashMap的key值是否為空。 public boolean add(E e) { return map.put(e, PRESENT)==null; }

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

map的put方法： final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i;

//確認(rèn)初始化
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    
//如果桶為空，直接插入新元素，也就是entry
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node<K,V> e; K k;
    //如果沖突，分為三種情況
    //key相等時(shí)讓舊entry等于新entry即可
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    //紅黑樹(shù)情況
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        //如果key不相等，則連成鏈表
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

}

這里注意一點(diǎn)，hashset只是不允許重復(fù)的元素加入，而不是不允許元素連成鏈表，因?yàn)橹灰猭ey的equals方法判斷為true時(shí)它們是相等的，此時(shí)會(huì)發(fā)生value的替換，因?yàn)樗衑ntry的value一樣，所以和沒(méi)有插入時(shí)一樣的。

而當(dāng)兩個(gè)hashcode相同但key不相等的entry插入時(shí)，仍然會(huì)連成一個(gè)鏈表，長(zhǎng)度超過(guò)8時(shí)依然會(huì)和hashmap一樣擴(kuò)展成紅黑樹(shù)，看完源碼之后筆者才明白自己之前理解錯(cuò)了。所以看源碼還是蠻有好處的。hashset基本上就是使用hashmap的方法再次實(shí)現(xiàn)了一遍而已，只不過(guò)value全都是同一個(gè)object，讓你以為相同元素沒(méi)有插入，事實(shí)上只是value替換成和原來(lái)相同的值而已。

當(dāng)add方法發(fā)生沖突時(shí)，如果key相同，則替換value，如果key不同，則連成鏈表。

add()如果此 set 中尚未包含指定元素，則添加指定元素。如果此Set沒(méi)有包含滿(mǎn)足(e==null ? e2==null : e.equals(e2)) 的e2時(shí)，則將e2添加到Set中，否則不添加且返回false。

由于底層使用HashMap的put方法將key = e，value=PRESENT構(gòu)建成key-value鍵值對(duì)，當(dāng)此e存在于HashMap的key中，則value將會(huì)覆蓋原有value，但是key保持不變，所以如果將一個(gè)已經(jīng)存在的e元素添加中HashSet中，新添加的元素是不會(huì)保存到HashMap中，所以這就滿(mǎn)足了HashSet中元素不會(huì)重復(fù)的特性。 public boolean remove(Object o) { return map.remove(o)==PRESENT; }

remove如果指定元素存在于此 set 中，則將其移除。底層使用HashMap的remove方法刪除指定的Entry。 public void clear() { map.clear(); }

clear從此 set 中移除所有元素。底層調(diào)用HashMap的clear方法清除所有的Entry。 public Object clone() { try { HashSet newSet = (HashSet) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(); } }

clone返回此 HashSet 實(shí)例的淺表副本：并沒(méi)有復(fù)制這些元素本身。

后記：

由于HashSet底層使用了HashMap實(shí)現(xiàn)，使其的實(shí)現(xiàn)過(guò)程變得非常簡(jiǎn)單，如果你對(duì)HashMap比較了解，那么HashSet簡(jiǎn)直是小菜一碟。有兩個(gè)方法對(duì)HashMap和HashSet而言是非常重要的，下篇將詳細(xì)講解hashcode和equals。

TreeSet

與HashSet是基于HashMap實(shí)現(xiàn)一樣，TreeSet同樣是基于TreeMap實(shí)現(xiàn)的。在《Java提高篇（二七）-----TreeMap》中LZ詳細(xì)講解了TreeMap實(shí)現(xiàn)機(jī)制，如果客官詳情看了這篇博文或者多TreeMap有比較詳細(xì)的了解，那么TreeSet的實(shí)現(xiàn)對(duì)您是喝口水那么簡(jiǎn)單。

TreeSet定義

我們知道TreeMap是一個(gè)有序的二叉樹(shù)，那么同理TreeSet同樣也是一個(gè)有序的，它的作用是提供有序的Set集合。通過(guò)源碼我們知道TreeSet基礎(chǔ)AbstractSet，實(shí)現(xiàn)NavigableSet、Cloneable、Serializable接口。

其中AbstractSet提供 Set 接口的骨干實(shí)現(xiàn)，從而最大限度地減少了實(shí)現(xiàn)此接口所需的工作。

NavigableSet是擴(kuò)展的 SortedSet，具有了為給定搜索目標(biāo)報(bào)告最接近匹配項(xiàng)的導(dǎo)航方法，這就意味著它支持一系列的導(dǎo)航方法。比如查找與指定目標(biāo)最匹配項(xiàng)。Cloneable支持克隆，Serializable支持序列化。 public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable

同時(shí)在TreeSet中定義了如下幾個(gè)變量。 private transient NavigableMap<E,Object> m;

//PRESENT會(huì)被當(dāng)做Map的value與key構(gòu)建成鍵值對(duì) private static final Object PRESENT = new Object();

其構(gòu)造方法： //默認(rèn)構(gòu)造方法，根據(jù)其元素的自然順序進(jìn)行排序

public TreeSet() { this(new TreeMap<E,Object>()); }

//構(gòu)造一個(gè)包含指定 collection 元素的新 TreeSet，它按照其元素的自然順序進(jìn)行排序。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); }

//構(gòu)造一個(gè)新的空 TreeSet，它根據(jù)指定比較器進(jìn)行排序。 public TreeSet(Collection<? extends E> c) { this(); addAll(c); }

//構(gòu)造一個(gè)與指定有序 set 具有相同映射關(guān)系和相同排序的新 TreeSet。 public TreeSet(SortedSet s) { this(s.comparator()); addAll(s); }

TreeSet(NavigableMap<E,Object> m) { this.m = m; }

二、TreeSet主要方法

1、add：將指定的元素添加到此 set（如果該元素尚未存在于 set 中）。 public boolean add(E e) { return m.put(e, PRESENT)==null; }

public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { //空樹(shù)時(shí)，判斷節(jié)點(diǎn)是否為空 compare(key, key); // type (and possibly null) check

    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
    return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//非空樹(shù)，根據(jù)傳入比較器進(jìn)行節(jié)點(diǎn)的插入位置查找
if (cpr != null) {
    do {
        parent = t;
        //節(jié)點(diǎn)比根節(jié)點(diǎn)小，則找左子樹(shù)，否則找右子樹(shù)
        cmp = cpr.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
            //如果key的比較返回值相等，直接更新值（一般compareto相等時(shí)equals方法也相等）
        else
            return t.setValue(value);
    } while (t != null);
}
else {
//如果沒(méi)有傳入比較器，則按照自然排序
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);
    } while (t != null);
}
//查找的節(jié)點(diǎn)為空，直接插入，默認(rèn)為紅節(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
    parent.left = e;
else
    parent.right = e;
    //插入后進(jìn)行紅黑樹(shù)調(diào)整
fixAfterInsertion(e);
size++;
modCount++;
return null;

}

2、get：獲取元素 public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }

該方法與put的流程類(lèi)似，只不過(guò)是把插入換成了查找

3、ceiling：返回此 set 中大于等于給定元素的最小元素；如果不存在這樣的元素，則返回 null。 public E ceiling(E e) { return m.ceilingKey(e); }

4、clear：移除此 set 中的所有元素。 public void clear() { m.clear(); }

5、clone：返回 TreeSet 實(shí)例的淺表副本。屬于淺拷貝。 public Object clone() { TreeSet clone = null; try { clone = (TreeSet) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); }

    clone.m = new TreeMap<>(m);
    return clone;
}

6、comparator：返回對(duì)此 set 中的元素進(jìn)行排序的比較器；如果此 set 使用其元素的自然順序，則返回 null。 public Comparator<? super E> comparator() { return m.comparator(); }

7、contains：如果此 set 包含指定的元素，則返回 true。 public boolean contains(Object o) { return m.containsKey(o); }

8、descendingIterator：返回在此 set 元素上按降序進(jìn)行迭代的迭代器。 public Iterator descendingIterator() { return m.descendingKeySet().iterator(); }

9、descendingSet：返回此 set 中所包含元素的逆序視圖。 public NavigableSet descendingSet() { return new TreeSet<>(m.descendingMap()); }

10、first：返回此 set 中當(dāng)前第一個(gè)（最低）元素。 public E first() { return m.firstKey(); }

11、floor：返回此 set 中小于等于給定元素的最大元素；如果不存在這樣的元素，則返回 null。 public E floor(E e) { return m.floorKey(e); }

12、headSet：返回此 set 的部分視圖，其元素嚴(yán)格小于 toElement。 public SortedSet headSet(E toElement) { return headSet(toElement, false); }

13、higher：返回此 set 中嚴(yán)格大于給定元素的最小元素；如果不存在這樣的元素，則返回 null。 public E higher(E e) { return m.higherKey(e); }

14、isEmpty：如果此 set 不包含任何元素，則返回 true。 public boolean isEmpty() { return m.isEmpty(); }

15、iterator：返回在此 set 中的元素上按升序進(jìn)行迭代的迭代器。 public Iterator iterator() { return m.navigableKeySet().iterator(); }

16、last：返回此 set 中當(dāng)前最后一個(gè)（最高）元素。 public E last() { return m.lastKey(); }

17、lower：返回此 set 中嚴(yán)格小于給定元素的最大元素；如果不存在這樣的元素，則返回 null。 public E lower(E e) { return m.lowerKey(e); }

18、pollFirst：獲取并移除第一個(gè)（最低）元素；如果此 set 為空，則返回 null。 public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); }

19、pollLast：獲取并移除最后一個(gè)（最高）元素；如果此 set 為空，則返回 null。 public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); }

20、remove：將指定的元素從 set 中移除（如果該元素存在于此 set 中）。 public boolean remove(Object o) { return m.remove(o)==PRESENT; }

該方法與put類(lèi)似，只不過(guò)把插入換成了刪除，并且要進(jìn)行刪除后調(diào)整

21、size：返回 set 中的元素?cái)?shù)（set 的容量）。 public int size() { return m.size(); }

22、subSet：返回此 set 的部分視圖 /** * 返回此 set 的部分視圖，其元素范圍從 fromElement 到 toElement。 */ public NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); }

 /**
  * 返回此 set 的部分視圖，其元素從 fromElement（包括）到 toElement（不包括）。
  */
 public SortedSet<E> subSet(E fromElement, E toElement) {
     return subSet(fromElement, true, toElement, false);
 }

23、tailSet：返回此 set 的部分視圖 /** * 返回此 set 的部分視圖，其元素大于（或等于，如果 inclusive 為 true）fromElement。 */ public NavigableSet tailSet(E fromElement, boolean inclusive) { return new TreeSet<>(m.tailMap(fromElement, inclusive)); }

/**
 * 返回此 set 的部分視圖，其元素大于等于 fromElement。
 */
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}

最后

由于TreeSet是基于TreeMap實(shí)現(xiàn)的，所以如果我們對(duì)treeMap有了一定的了解，對(duì)TreeSet那是小菜一碟，我們從TreeSet中的源碼可以看出，其實(shí)現(xiàn)過(guò)程非常簡(jiǎn)單，幾乎所有的方法實(shí)現(xiàn)全部都是基于TreeMap的。

LinkedHashSet

LinkedHashSet內(nèi)部是如何工作的

LinkedHashSet是HashSet的一個(gè)“擴(kuò)展版本”，HashSet并不管什么順序，不同的是LinkedHashSet會(huì)維護(hù)“插入順序”。HashSet內(nèi)部使用HashMap對(duì)象來(lái)存儲(chǔ)它的元素，而LinkedHashSet內(nèi)部使用LinkedHashMap對(duì)象來(lái)存儲(chǔ)和處理它的元素。這篇文章，我們將會(huì)看到LinkedHashSet內(nèi)部是如何運(yùn)作的及如何維護(hù)插入順序的。

我們首先著眼LinkedHashSet的構(gòu)造函數(shù)。在LinkedHashSet類(lèi)中一共有4個(gè)構(gòu)造函數(shù)。這些構(gòu)造函數(shù)都只是簡(jiǎn)單地調(diào)用父類(lèi)構(gòu)造函數(shù)（如HashSet類(lèi)的構(gòu)造函數(shù)）。 下面看看LinkedHashSet的構(gòu)造函數(shù)是如何定義的。 //Constructor - 1

public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); //Calling super class constructor }

//Constructor - 2

public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); //Calling super class constructor }

//Constructor - 3

public LinkedHashSet() { super(16, .75f, true); //Calling super class constructor }

//Constructor - 4

public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); //Calling super class constructor addAll(c); }

在上面的代碼片段中，你可能注意到4個(gè)構(gòu)造函數(shù)調(diào)用的是同一個(gè)父類(lèi)的構(gòu)造函數(shù)。這個(gè)構(gòu)造函數(shù)（父類(lèi)的，譯者注）是一個(gè)包內(nèi)私有構(gòu)造函數(shù)（見(jiàn)下面的代碼，HashSet的構(gòu)造函數(shù)沒(méi)有使用public公開(kāi)，譯者注），它只能被LinkedHashSet使用。

這個(gè)構(gòu)造函數(shù)需要初始容量，負(fù)載因子和一個(gè)boolean類(lèi)型的啞值（沒(méi)有什么用處的參數(shù)，作為標(biāo)記，譯者注）等參數(shù)。這個(gè)啞參數(shù)只是用來(lái)區(qū)別這個(gè)構(gòu)造函數(shù)與HashSet的其他擁有初始容量和負(fù)載因子參數(shù)的構(gòu)造函數(shù)，下面是這個(gè)構(gòu)造函數(shù)的定義， HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }

顯然，這個(gè)構(gòu)造函數(shù)內(nèi)部初始化了一個(gè)LinkedHashMap對(duì)象，這個(gè)對(duì)象恰好被LinkedHashSet用來(lái)存儲(chǔ)它的元素。

LinkedHashSet并沒(méi)有自己的方法，所有的方法都繼承自它的父類(lèi)HashSet，因此，對(duì)LinkedHashSet的所有操作方式就好像對(duì)HashSet操作一樣。

唯一的不同是內(nèi)部使用不同的對(duì)象去存儲(chǔ)元素。在HashSet中，插入的元素是被當(dāng)做HashMap的鍵來(lái)保存的，而在LinkedHashSet中被看作是LinkedHashMap的鍵。

這些鍵對(duì)應(yīng)的值都是常量PRESENT（PRESENT是HashSet的靜態(tài)成員變量，譯者注）。

LinkedHashSet是如何維護(hù)插入順序的

LinkedHashSet使用LinkedHashMap對(duì)象來(lái)存儲(chǔ)它的元素，插入到LinkedHashSet中的元素實(shí)際上是被當(dāng)作LinkedHashMap的鍵保存起來(lái)的。

LinkedHashMap的每一個(gè)鍵值對(duì)都是通過(guò)內(nèi)部的靜態(tài)類(lèi)Entry<K, V>實(shí)例化的。這個(gè) Entry<K, V>類(lèi)繼承了HashMap.Entry類(lèi)。

這個(gè)靜態(tài)類(lèi)增加了兩個(gè)成員變量，before和after來(lái)維護(hù)LinkedHasMap元素的插入順序。這兩個(gè)成員變量分別指向前一個(gè)和后一個(gè)元素，這讓LinkedHashMap也有類(lèi)似雙向鏈表的表現(xiàn)。 private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after;

    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }

}

從上面代碼看到的LinkedHashMap內(nèi)部類(lèi)的前面兩個(gè)成員變量——before和after負(fù)責(zé)維護(hù)LinkedHashSet的插入順序。LinkedHashMap定義的成員變量header保存的是 這個(gè)雙向鏈表的頭節(jié)點(diǎn)。header的定義就像下面這樣，

接下來(lái)看一個(gè)例子就知道LinkedHashSet內(nèi)部是如何工作的了。 public class LinkedHashSetExample { public static void main(String[] args) { //Creating LinkedHashSet

    LinkedHashSet<String> set = new LinkedHashSet<String>();
    //Adding elements to LinkedHashSet
    set.add("BLUE");
    set.add("RED");
    set.add("GREEN");    
    set.add("BLACK");
}

}

感謝各位的閱讀，以上就是“Java集合類(lèi)怎么使用”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Java集合類(lèi)怎么使用這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！