為什么會(huì)出現(xiàn)集合類(lèi)？

我們都知道數(shù)組的弊端是長(zhǎng)度固定。這樣一來(lái)，數(shù)組就不能滿(mǎn)足變化的要求。所以，Java就提供了集合供我們使用。

集合特點(diǎn)

• 集合長(zhǎng)度是可變的
• 只能存儲(chǔ)對(duì)象（在JDK1.5自動(dòng)裝箱拆箱特性后可以存儲(chǔ)基本數(shù)據(jù)類(lèi)型）
• 可以存儲(chǔ)多種類(lèi)型對(duì)象（JDK1.5泛型，一般存儲(chǔ)是一種）

集合和數(shù)組的區(qū)別

長(zhǎng)度問(wèn)題：

• 數(shù)組固定
• 集合可變

存儲(chǔ)元素問(wèn)題：

• 數(shù)組可以是基本數(shù)據(jù)類(lèi)型，也可以是引用類(lèi)型
• 集合在JDK1.5之前只能是引用類(lèi)型

同一類(lèi)型問(wèn)題：

• 數(shù)組中元素類(lèi)型必須是一樣的
• 集合中元素可以是不一樣的

功能問(wèn)題：

• 數(shù)組只能對(duì)數(shù)據(jù)進(jìn)行存取操作。
• 集合可以對(duì)數(shù)據(jù)進(jìn)行增刪存取操作。

元素?cái)?shù)量判斷問(wèn)題：

• 數(shù)組無(wú)法判斷其中實(shí)際存有多少元素，length只告訴了數(shù)組的容量；
• 而集合的size()可以確切知道元素的個(gè)數(shù) 。

集合體系的由來(lái)

集合是存儲(chǔ)多個(gè)元素的容器，但是，由于數(shù)據(jù)結(jié)構(gòu)不同，Java就提供了多種集合類(lèi)。

為什么會(huì)出現(xiàn)這么多的容器呢？
因?yàn)槊糠N容器對(duì)數(shù)據(jù)的存儲(chǔ)方式都有不同，這個(gè)存儲(chǔ)方式稱(chēng)之為：數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)存儲(chǔ)的方式。

而這多種集合類(lèi)有共性的功能，所以通過(guò)不斷的向上抽取，最終形成集合體系結(jié)構(gòu)（集合框架）。

集合類(lèi)繼承關(guān)系結(jié)構(gòu)圖

java collection集合體系圖

集合類(lèi)的共性方法

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(Collection<?> c);

    boolean removeAll(Collection<?> c);

    void clear();

}

集合類(lèi)的迭代器

理解迭代器

什么是迭代器？集合取出元素的方式（動(dòng)作）。
由于每個(gè)容器的底層數(shù)據(jù)結(jié)構(gòu)都不一樣，它們對(duì)數(shù)據(jù)的存儲(chǔ)操作實(shí)現(xiàn)也不一樣。

集合都有取的操作，而取的操作不足以用一個(gè)方法來(lái)描述，比如說(shuō)取之前判斷是否有元素，此時(shí)就涉及到多個(gè)功能。那么此時(shí)我們把取出的操作封裝成一個(gè)對(duì)象。此對(duì)象封裝在集合的內(nèi)部作為內(nèi)部類(lèi)，這樣可以方便直接獲取元素。而每一個(gè)容器的數(shù)據(jù)結(jié)構(gòu)不同，所以取出的動(dòng)作細(xì)節(jié)也不一樣，但是都有共性?xún)?nèi)容 判斷和取出，那么可以將寫(xiě)共性抽取形成一個(gè)接口Iterator。

那么這些內(nèi)部類(lèi)都符合一個(gè)規(guī)則，該規(guī)則是Iterator。如何獲取集合的取出對(duì)象（iterator的子類(lèi)對(duì)象）呢？
通過(guò)一個(gè)對(duì)外提供的方法iterator()。iterator()作用，獲取容器中的內(nèi)部類(lèi)對(duì)象。

什么是Iterator？
定義了對(duì)集合元素操作的接口方法

Iterator主要方法：

public interface Iterator<E> {
    
    boolean hasNext();

    E next();

}

迭代器的使用

代碼示例：

public class CollectionDemo {
    public static void main(String[] args) {
        Collection collection = new ArrayList();
        collection.add(1);
        collection.add(2);
        collection.add(1);
        
        /*
         * 迭代器使用方式1
         */
        Iterator iterator = collection.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
        /*
         * 迭代器使用方式2
         */
        for(Iterator i = collection.iterator();i.hasNext();){
            System.out.println(i.next());
        }
        /*
         * 兩種方式特點(diǎn)：
         *  第二種方式 更加節(jié)省內(nèi)存。因?yàn)閕terator對(duì)象在for循環(huán)執(zhí)行完后就會(huì)被回收。
         *  第一種 會(huì)一直停留在內(nèi)存當(dāng)中。
         */
    }
}

List類(lèi)

List類(lèi)共性方法

List：
特有方法。凡是可以操作角標(biāo)的方法都是該體系特有的方法。

增
add(index,element);
addAll(index,Collection);

刪
remove(index);

改
set(index,element);
查
get(index):
subList(from,to);
listIterator();
int indexOf(obj):獲取指定元素的位置。
ListIterator listIterator();

ListIterator---列表迭代器

public class ListDemo {
    
    public static void main(String[] args) {
        ArrayList al = new ArrayList();
        al.add("java01");
        al.add("java02");
        al.add("java03");
        
        sop(al);
        
        //在迭代過(guò)程中，準(zhǔn)備添加或者刪除元素
        Iterator it = al.iterator();
        while(it.hasNext()){
            Object obj = it.next();
            
            if(obj.equals("java02")){
                al.add("java08");
                //it.remove();//將"java02"的引用從集合中刪除了
            }
            sop(obj);
        }
        
        sop(al);
    }
    
    public static void sop(Object object){
        System.out.println(object);
    }
    
}

以上代碼會(huì)產(chǎn)生以下異常：

Paste_Image.png

原因分析：
在迭代時(shí)，不可以通過(guò)集合對(duì)象的方法操作集合中的元素
解決方案：
使用List類(lèi)提供的列表迭代器ListIterator。

引入列表迭代器ListIterator的原因是：
1.避免上方的異常
2.為迭代器添加更多的操作元素的方法，例如在迭代過(guò)程中添加元素，修改元素等新功能

總之一句話(huà)，ListIterator可以在迭代的過(guò)程中，集合中的元素進(jìn)行增刪改查。

代碼體現(xiàn)：

public class ListIteratorDemo {
    
    public static void main(String[] args) {
        ArrayList al = new ArrayList();
        al.add("java01");
        al.add("java02");
        al.add("java03");
        
        sop(al);
        
        
        ListIterator it = al.listIterator();
        while(it.hasNext()){
            Object obj = it.next();
            
            if(obj.equals("java02")){
                it.add("java08");
            }
        }
        sop(al);

        //反向迭代
        while(it.hasPrevious()){
            Object obj = it.previous();
            if(obj.equals("java03")){
                sop(obj);
                it.set("javaee");
            }
        }
        sop(al);
    }
    public static void sop(Object object){
        System.out.println(object);
    }
}

List的子類(lèi)介紹

List:元素是有序的，可以重復(fù)。

• Vector:
  • 底層是數(shù)組數(shù)據(jù)結(jié)構(gòu)。
  • 線(xiàn)程同步。
  • 因?yàn)樾实?，被ArrayList替代了。
  • 它還可以通過(guò)枚舉來(lái)取出元素。

    LinkedList在內(nèi)存中是以鏈表形式組織的，鏈表中的數(shù)據(jù)在內(nèi)存中是松散的，每一個(gè)節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，這樣查找起來(lái)就比較慢了。而插入刪除的時(shí)候就是斷開(kāi)一個(gè)節(jié)點(diǎn)，然后插入刪除之后再接起來(lái)。

ArrayList類(lèi)

• ArrayList:
  • 底層的數(shù)據(jù)結(jié)構(gòu)使用的是動(dòng)態(tài)數(shù)組結(jié)構(gòu)；
  • 特點(diǎn)：查詢(xún)速度很快，但是增刪稍慢；
  • 線(xiàn)程不同步。

可變長(zhǎng)度數(shù)組(動(dòng)態(tài)數(shù)組)其實(shí)就是當(dāng)數(shù)組不夠時(shí)，創(chuàng)建一個(gè)新的長(zhǎng)度更長(zhǎng)的數(shù)組，然后把舊的數(shù)組內(nèi)容復(fù)制到新的數(shù)組中。

• 數(shù)組的特點(diǎn)是其中的元素在內(nèi)存中的地址是連續(xù)的，所以ArrayList的優(yōu)點(diǎn)在于get、set的效率高，時(shí)間復(fù)雜度為常數(shù)。
• ArrayList中插入和刪除效率較低，由于每插入/刪除一項(xiàng)，都需要移動(dòng)后續(xù)所有項(xiàng)的位置，時(shí)間復(fù)雜度為O(N)。

List集合判斷元素是否相同，依據(jù)是元素的equals方法。

contains、indexOf等方法在執(zhí)行其核心邏輯時(shí)，都要對(duì)集合中元素進(jìn)行判斷是否有此元素，判斷的原理都是equals()。
如果不重寫(xiě)equals方法，則默認(rèn)比較地址，這會(huì)導(dǎo)致contains將永遠(yuǎn)返回false，indexOf、將永遠(yuǎn)返回-1。所以，我們需要重寫(xiě)equals方法來(lái)自己判斷，例如可以通過(guò)比較對(duì)象中一個(gè)特征字段的值來(lái)比較兩個(gè)對(duì)象是否相等。

LinkedList類(lèi)

LinkedList特有方法

addFirst();
addLast();

getFirst();
getLast();
獲取元素，但不刪除元素。如果集合中沒(méi)有元素，會(huì)出現(xiàn)NoSuchElementException

removeFirst();
removeLast();
獲取元素，但是元素被刪除。如果集合中沒(méi)有元素，會(huì)出現(xiàn)NoSuchElementException

在JDK1.6出現(xiàn)了替代方法。

offerFirst();
offerLast();

peekFirst();
peekLast();
獲取元素，但不刪除元素。如果集合中沒(méi)有元素，會(huì)返回null。

pollFirst();
pollLast();
獲取元素，但是元素被刪除。如果集合中沒(méi)有元素，會(huì)返回null。

• LinkedList
  • 底層使用的雙向鏈表結(jié)構(gòu)。
  • 特點(diǎn)：增刪速度很快，查詢(xún)稍慢。
  • 線(xiàn)程不同步。

雙向鏈表的特點(diǎn)，元素（結(jié)點(diǎn)）之間的地址不連續(xù)，通過(guò)引用找到當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)，即插入和刪除效率較高，只需要常數(shù)時(shí)間，而get和set則較為低效，需要O(n)的時(shí)間。

LinkedList與ArrayList比較

LinkedList的方法和使用和ArrayList大致相同，由于LinkedList是鏈表實(shí)現(xiàn)的，所以額外提供了在頭部和尾部添加/刪除元素的方法，并且沒(méi)有ArrayList擴(kuò)容的問(wèn)題了。另外，ArrayList和LinkedList都可以實(shí)現(xiàn)棧、隊(duì)列等數(shù)據(jù)結(jié)構(gòu)，但LinkedList本身實(shí)現(xiàn)了隊(duì)列的接口，所以更推薦用LinkedList來(lái)實(shí)現(xiàn)隊(duì)列和棧。

一種數(shù)據(jù)結(jié)構(gòu)可能會(huì)基于另一種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，比如說(shuō)隊(duì)列基于鏈表。

Vector類(lèi)

通過(guò)以下代碼介紹

/*
枚舉就是Vector特有的取出方式。
發(fā)現(xiàn)枚舉和迭代器很像。
其實(shí)枚舉和迭代是一樣的。

因?yàn)槊杜e的名稱(chēng)以及方法的名稱(chēng)都過(guò)長(zhǎng)。
所以被迭代器取代了。
枚舉郁郁而終了。

*/
class VectorDemo 
{
    public static void main(String[] args) 
    {
        Vector v = new Vector();

        v.add("java01");
        v.add("java02");
        v.add("java03");
        v.add("java04");

        Enumeration en = v.elements();

        while(en.hasMoreElements())
        {
            System.out.println(en.nextElement());
        }
    }
}

Vector類(lèi)與ArrayList類(lèi)比較

• Vector和ArrayList的底層數(shù)據(jù)結(jié)構(gòu)都是數(shù)組，在使用上相似。
• Vector的方法都是同步的(Synchronized),是線(xiàn)程安全的，而ArrayList的方法不是，由于線(xiàn)程的同步必然要影響性能，因此，ArrayList的性能比Vector好。（建議使用ArrayList，因?yàn)楦咝?，就算是多線(xiàn)程可以自己加鎖）
• 當(dāng)容器空間不足時(shí)，Vector會(huì)將它的容量翻倍，而ArrayList只增加50%的大小，這樣，ArrayList就有利于節(jié)約內(nèi)存空間。

總結(jié)

在不同的應(yīng)用場(chǎng)景下，選擇合適的集合。比如說(shuō)在需要頻繁讀取集合中的元素時(shí)，使用ArrayList效率較高，而在插入和刪除操作較多時(shí)，使用LinkedList效率較高。

Set類(lèi)

Set體系的類(lèi)特點(diǎn)：

• 不保證放入元素的順序(存入和取出的順序不一定一致)
• 元素不可以重復(fù)。

HashSet類(lèi)

HashSet底層數(shù)據(jù)結(jié)構(gòu)是哈希表，線(xiàn)程不同步。

下面是HashSet的構(gòu)造函數(shù)以及主要方法的代碼：

public HashSet() {
        map = new HashMap<>();
}

public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
}

public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
 }

private transient HashMap<E,Object> map;

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

public int size() {
    return map.size();
}

從以上代碼可以知道：

• HashSet基于HashMap實(shí)現(xiàn)，底層使用HashMap保存數(shù)據(jù)。
• 其實(shí)HashSet就是操作了HashMap的key，并且同時(shí)具有Set接口的特點(diǎn)。

HashSet是如何保證元素唯一性的呢？
是通過(guò)兩個(gè)方法，hashCode和equals來(lái)完成。
如果元素hashCode值相同，才會(huì)判斷equals是否為true。
如果元素的hashCode不同，不會(huì)調(diào)用equals方法。

注意：對(duì)于判斷元素是否存在以及刪除等操作，依賴(lài)的方法是元素的hashCode和equals方法。

/**
 * 往HashSet集合中存入自定對(duì)象 姓名和年齡相同為同一個(gè)人，重復(fù)元素。
 * 
 */
public class HashSetDemo {

    public static void print(Object obj) {
        System.out.println(obj);
    }

    public static void main(String[] args) {
        HashSet<Person> hashSet = new HashSet<>();

        hashSet.add(new Person("a1", 11));
        hashSet.add(new Person("a2", 12));
        hashSet.add(new Person("a3", 13));
        hashSet.add(new Person("a2", 12));
        // hashSet.add(new Person("a4",14));

        // print("a1:"+hashSet.contains(new Person("a2",12)));

        // hashSet.remove(new Person("a4",13));

        Iterator it = hashSet.iterator();

        while (it.hasNext()) {
            Person p = (Person) it.next();
            print(p.getName() + "::" + p.getAge());
        }
    }

}

class Person {
    private String name;
    private int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int hashCode() {
        System.out.println(this.name + "....hashCode");
        return name.hashCode() + age * 37;
    }

    public boolean equals(Object obj) {

        if (!(obj instanceof Person))
            return false;

        Person p = (Person) obj;
        System.out.println(this.name + "...equals.." + p.name);

        return this.name.equals(p.name) && this.age == p.age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

LinkedHashSet

LinkedHashSet是HashSet的子類(lèi)，它和HashSet的區(qū)別就在于LinkedHashSet的元素嚴(yán)格按照放入順序排列。LinkedHashSet內(nèi)部使用LinkedHashMap實(shí)現(xiàn)，所以它和HashSet的關(guān)系就相當(dāng)于HashMap和LinkedHashMap的關(guān)系。如果你想讓取出元素的順序和插入元素的順序完全相同，那么就使用LinkedHashSet代替HashSet。

TreeSet

上面提到HashSet是用HashMap實(shí)現(xiàn)的，其實(shí)這里的TreeSet也是用Map接口的另一個(gè)實(shí)現(xiàn)類(lèi)TreeMap實(shí)現(xiàn)的。TreeMap是一個(gè)有序的二叉樹(shù)。TreeSet實(shí)現(xiàn)了SortedSet接口，其特點(diǎn)是會(huì)對(duì)放入其中的元素進(jìn)行排序，和LinkedHashSet不同的是，LinkedHashSet是根據(jù)元素的放入順序進(jìn)行排序，而TreeSet是根據(jù)元素的自然順序進(jìn)行排序。

保證元素唯一性的依據(jù)：
compareTo方法return 0.

二叉樹(shù)原理圖

TreeSet排序的第一種方式：讓元素自身具備比較性。
元素需要實(shí)現(xiàn)Comparable接口，覆蓋compareTo方法。
這種方式也稱(chēng)為元素的自然順序，或者叫做默認(rèn)順序。

TreeSet能對(duì)Integer和String類(lèi)型的數(shù)據(jù)進(jìn)行排序，是因?yàn)镮nteger和String都實(shí)現(xiàn)Comparable接口并實(shí)現(xiàn)了compareTo方法。

TreeSet的第二種排序方式。
當(dāng)元素自身不具備比較性時(shí)，或者具備的比較性不是所需要的。
這時(shí)就需要讓集合自身具備比較性。
在集合初始化時(shí)，就有了比較方式。

實(shí)際開(kāi)發(fā)中，TreeSet的使用頻率較低，是因?yàn)門(mén)reeSet每插入一個(gè)數(shù)據(jù)，就會(huì)排一次序，導(dǎo)致性能降低，而一般我們都是放入一堆數(shù)據(jù)后再一起排序，所以用不到TreeSet。但如果剛好碰到需要進(jìn)行插入后即時(shí)排序的需求，那這時(shí)候就可以用上TreeSet了。

總結(jié)

在Set接口的實(shí)現(xiàn)類(lèi)中，HashSet是一種元素不重復(fù)且無(wú)序的存儲(chǔ)容器，可以存儲(chǔ)一個(gè)null元素，放入HashSet的對(duì)象需要重寫(xiě)equals和hashCode方法以保證存入對(duì)象唯一；LinkedHashSet是HashSet的子類(lèi)，具有HashSet的性質(zhì)，且它保存了元素放入的順序；TreeSet可以將存入的元素按照一定的規(guī)則排序，但是對(duì)象和集合其中一個(gè)必須要比較性，TreeSet中不能存在null元素。