JAVA 持有對象——容器初探（持續(xù)補充）

aikin 發(fā)布于2019-08-14 12:21 / 1734人閱讀

摘要：類庫中提供了一套相當完整的容器類來解決這個問題，其中基本類型有，，，，這些對象類型被稱為集合類。但是，類庫中使用了來指代集合類中的子集，，，所以集合類也被稱為容器。五類型是能夠?qū)ο笥成涞狡渌麑ο蟮囊环N容器，有區(qū)別于的方法。

引言

如果一個程序只包含固定數(shù)量的且其生命周期都是已知對象，那么這是一個非常簡單的程序——《think in java》

了解容器前，先提出一個問題，ArrayList和LinkedList誰的處理速度更快呢？

一持有對象的方式

在Java中，我們可以使用數(shù)組來保存一組對象。但是，數(shù)組是固定大小的，在一般情況下，我們寫程序時并不知道將需要多少個對象，因此數(shù)組固定大小對于編程有些受限。

java類庫中提供了一套相當完整的容器類來解決這個問題，其中基本類型有List，Queue，Set，Map，這些對象類型被稱為集合類。但是，Java類庫中使用了Collection來指代集合類中的子集{List，Queue，Set}，所以集合類也被稱為容器。容器提供了完善的方法來保存對象。

二類型安全的容器

java采用泛型保證我們不會向容器中插入不正確的類型，但是java的泛型只存在于程序源碼中，在經(jīng)過編譯器編譯就會將類型擦除。舉一個例子：

//經(jīng)過編譯前
List list = new ArrayList<>();
list.add("ok");
System.out.println(list.get(0));
 
//經(jīng)過編譯后
List list = new ArrayList();
list.add("ok");
System.out.println((String)list.get(0));

這樣做的好處是:在編寫程序的時候，不會將其他非導出類型的對象添加到容器中。

三 List

數(shù)組存儲多個對象的原因是它提前聲明了能存儲多少對象。那容器又是如何實現(xiàn)存儲不定多對象的呢？

//ArrayList部分源碼
 
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
 
private transient Object[] elementData;
private int size;
 
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
 
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
 
    ensureExplicitCapacity(minCapacity);
}
 
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
 
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

我們可以看到，在ArrayList類中有一個elementData數(shù)組。當使用無參構(gòu)造函數(shù)時數(shù)組長度默認為空，當向ArrayList加入對象時，會調(diào)用一個方法來判斷數(shù)組是否能放下這個對象。當數(shù)組為空時設(shè)置數(shù)組長度為10并申請相應(yīng)大小空間，當數(shù)組已滿時，最少重新申請原數(shù)組大小1.5倍的空間（除非達到int類型最大值-8）。而在LinkedList中卻沒有采用這種方式，而是采用鏈表方式。

//LinkedList add方法
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

在LinkedList中，他的add方法調(diào)用了linkLast方法，直接在鏈表后邊加入一個新的節(jié)點。

四 Set

Set類型不保存重復的元素。判斷對象元素是否相等采用的是equals方法，所以在存入自定義的對象時，如果重寫equals方法依賴于可變屬性，將會導致一些問題。

五 Map

Map類型是能夠?qū)ο笥成涞狡渌麑ο蟮囊环N容器，有區(qū)別于List的get方法。HashSet類中包含了一個HashMap對象，HashSet的實現(xiàn)依靠HashMap。

HashMap的實現(xiàn)采用了數(shù)組鏈表的方式，即數(shù)組的每一個位置都存放的是鏈表頭。查找會先通過key的hash找到對應(yīng)數(shù)組下標，再在該數(shù)組下標所對應(yīng)的鏈表中找到是否有對應(yīng)對象，查找方式為equals方法。
HashMap如果存儲的鍵值對大于設(shè)定值，會自動進行擴容并且對已經(jīng)存入的鍵值對進行重排序，一次擴容的大小是當前數(shù)組長度的兩倍。

//HashMap擴容
public V put(K key, V value) {
    //other...
    addEntry(hash, key, value, i);
    return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
   //other...
}

六 Queue

隊列是一種典型的先進先出的容器，LinkedList實現(xiàn)了Queue接口。PriorityQueue實現(xiàn)了優(yōu)先級隊列。ArrayDeque是一個用數(shù)組實現(xiàn)雙端隊列的類，我們來看一下ArrayDeque類中的一些方法。

//ArrayDeque構(gòu)造方法
    public ArrayDeque() {
        elements = (E[]) new Object[16];
    }
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

上邊的代碼是ArrayDeque的構(gòu)造方法，可以看到，當沒有定義大小時，ArrayDeque默認數(shù)組大小為16，而定義大小后，會調(diào)用allocateElements方法，這個方法的作用是：當給定長度小于最小長度8時，使用最小長度。若大于等于最小長度，則找到比給定長度大的最小的2的冪數(shù)。為什么要是2的冪數(shù)呢？原因有以下兩點：

操作系統(tǒng)分配內(nèi)存的方法使用伙伴系統(tǒng)的話，每一塊的大小都是2的冪數(shù)，如果分配的內(nèi)存大小為2的冪數(shù)，可以減少內(nèi)存分配的時間。
伙伴系統(tǒng)在百度百科中的解釋：http://baike.baidu.com/view/4...

在ArrayDeque的addFirst方法中不固定將頭放在數(shù)組的第一位，而是循環(huán)移位。使用2的冪數(shù)能夠有效判斷頭部所在的地址。

同樣在第二點中，如果隊列滿了，數(shù)組擴充是將容量capacity值左移一位即可擴充一倍。

public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
    }

七 List的選擇

在文章開頭提出了一個問題，數(shù)組實現(xiàn)的List快還是鏈表實現(xiàn)的List快。模擬一下試試：

public static void add()
{
    long start = 0;
    long end = 0;
 
    List alist = new ArrayList<>();
    List llist = new LinkedList<>();
 
    System.out.println("ArrayList添加1000萬數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    for (int i=0; i<10000000; i++)
    {
        alist.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end-start);
 
    System.out.println("LinkedList添加1000萬數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    for (int i=0; i<10000000; i++)
    {
        llist.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println(end-start+"
");
 
    System.out.println("ArrayList從1000萬數(shù)據(jù)刪除數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    alist.remove(0);
    alist.remove(2000000);
    alist.remove(4000000);
    alist.remove(6000000);
    alist.remove(8000000);
    alist.remove(9999994);
    end = System.currentTimeMillis();
    System.out.println(end - start);
 
    System.out.println("LinkedList從1000萬數(shù)據(jù)刪除數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    llist.remove(0);
    llist.remove(2000000);
    llist.remove(4000000);
    llist.remove(6000000);
    llist.remove(8000000);
    llist.remove(9999994);
    end = System.currentTimeMillis();
    System.out.println(end - start+"
");
 
    System.out.println("ArrayList從1000萬數(shù)據(jù)查找數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    alist.contains(0);
    alist.contains(2000000);
    alist.contains(4000000);
    alist.contains(6000000);
    alist.contains(8000000);
    alist.contains(10000000);
    end = System.currentTimeMillis();
    System.out.println(end - start);
 
    System.out.println("LinkedList從1000萬數(shù)據(jù)查找數(shù)據(jù)所需毫秒數(shù)");
    start = System.currentTimeMillis();
    llist.contains(0);
    llist.contains(2000000);
    llist.contains(4000000);
    llist.contains(6000000);
    llist.contains(8000000);
    llist.contains(10000000);
    end = System.currentTimeMillis();
    System.out.println(end - start+"
");
}

可以看到，無論在何種情況下，數(shù)組實現(xiàn)的list都比鏈表快。當我在ArrayList構(gòu)造方法中設(shè)置數(shù)組初始大小1000萬時，ArrayLIst添加數(shù)據(jù)的速度慢了下來，降到5000毫秒左右，所以一般情況下不需要優(yōu)化。

總結(jié)

簡單容器類圖：

Java的容器分為兩類，一類是Collection，一類是Map。collection中包含三種集合類型：Set，List，Queue。

如果想要set中的數(shù)據(jù)有序，請使用TreeSet。

HashTable和Vector是線程安全的，但是不建議使用，請使用java.util.concurrent包下的容器。

HashMap允許key/value值為null。

發(fā)表評論

登陸后可評論

0條評論

aikin

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow

閱讀 2129·2023-04-26 00:09
Vultr，澳大利亞悉尼云服務(wù)器簡單測評

閱讀 3162·2021-09-26 10:12
程序員用什么軟件畫C語言程序流程圖

閱讀 3525·2019-08-30 15:44
一道CSS筆試題

閱讀 2887·2019-08-30 13:47
2019 年了，為什么我還在用 jQuery？

閱讀 949·2019-08-23 17:56
nodejs實現(xiàn)webservice問題總結(jié)

閱讀 3259·2019-08-23 15:31
new 命令的原理

閱讀 501·2019-08-23 13:47
瀏覽器安全機制

閱讀 2560·2019-08-23 11:56

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JAVA 持有對象——容器初探（持續(xù)補充）

相關(guān)文章

第十一章持有對象

構(gòu)建 Web 應(yīng)用之 Service Worker 初探

Java動態(tài)編程初探

Java 持有對象（11）

發(fā)表評論

0條評論

aikin

男|高級講師

TA的文章

tensorflow

Vultr，澳大利亞悉尼云服務(wù)器簡單測評

程序員用什么軟件畫C語言程序流程圖

一道CSS筆試題

2019 年了，為什么我還在用 jQuery？

nodejs實現(xiàn)webservice問題總結(jié)

new 命令的原理

瀏覽器安全機制

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JAVA 持有對象——容器初探（持續(xù)補充）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！