標簽（空格分隔）： java

上一篇文章我們簡單的對java集合框架有了一個簡單的認識掘鄙，本次军拟，我們來具體的探討一下集合框架中的一些接口的繼承和實現(xiàn)。我不計劃使用簡單的陳述性的語言來描述，而是大家一起探討性的學(xué)習。

首先瘦真，我們從最常用最清楚的ArrayList類入手，我并不打算一開始就從上至下的分析其源碼是如何實現(xiàn)的黍瞧，為什么呢诸尽？這個類這么多方法，這么多的功能印颤，為什么會有這個方法您机？，這樣分析我們很迷茫啊年局，
首先我們來一個宏觀的認識類的繼承結(jié)構(gòu)：

ArrayList類繼承結(jié)構(gòu).png

當我們看到這個圖的時候际看，我們的第一個感覺就是這么多繼承關(guān)系，是嗎矢否？

哈哈仿村，扯淡的，java中哪有多繼承兴喂，準確的說應(yīng)該是繼承和實現(xiàn)關(guān)系，只有和AbstractList類是繼承關(guān)系，其他的都是實現(xiàn)衣迷，也就是說其他的都是接口勒畏鼓。既然是接口也就是說功能上具有獨立性，也就是說他們只是對ArrayList進行各種方面的擴展壶谒，我們這里只討論主要的功能云矫，就是集合的功能，哪些東西是集合的功能呢汗菜？

這個我們一眼就看的出來让禀，Collection,其他的是什么鬼，我也不知道陨界，目前為止巡揍，我就知道Collection具有集合的功能，Iterable是操作集合的迭代器菌瘪，但是腮敌，從實現(xiàn)和繼承的關(guān)系，我們可以知道俏扩，AbstractCollection和List都和Collection有關(guān)系糜工，而且，從圖上可以看出來录淡，他們一個是實現(xiàn)捌木，一個是繼承，這里我聲明一下嫉戚，這個圖不是我畫的刨裆，是idea工具自動生成的。彼水。崔拥。也就是說List是一個接口，AbstractCollection是一個實現(xiàn)類凤覆，好了先看看我們的認識是不是正確的链瓦？

打開AbstractCollection和List源碼，看看

AbstractCollection.png

List.png

哈哈盯桦，還真是的慈俯，但是我們還有一個意外的發(fā)現(xiàn)，AbstractCollection是一個抽象實現(xiàn)類拥峦，臥槽贴膘，怪不得它的類名是這樣的。既然是抽象的就說明實現(xiàn)了部分東西略号，要不然這貨為啥實現(xiàn)呢刑峡？好我們看看她實現(xiàn)了什么洋闽？

AbstractCollection實現(xiàn)類結(jié)構(gòu)圖.png

//沒有實現(xiàn)，反正就是返回一個迭代器就行了皇帮，
  public abstract Iterator<E> iterator();
//沒實現(xiàn)卷哩，功能嗎都知道就是計算這個集合的大小的，至于如何計算玲献。殉疼。。我也不知道捌年。
public abstract int size();

行了瓢娜，我們來看一個實現(xiàn)的東西：我們看到isEmpty（）實現(xiàn)了，這個看看

 public boolean isEmpty() {
        return size() == 0;
    }

額礼预。眠砾。。好吧托酸，這個實現(xiàn)我服褒颈，哈哈哈，以后我也可以這樣來個Collection的實現(xiàn)類了励堡。so easy在看一個
就看boolean contains(Object o)這個方法吧谷丸。

我們自己先分析一下，如果是我們自己的話如何實現(xiàn)呢?
我的話刨疼，會這樣，首先我們要便利這個集合揩慕，從第一個開始，從集合中取出元素迎卤，然后和這個對象進行對比，對比是什么呢?上一篇就劇透過玷坠，是按地址對比的蜗搔，為什么呢？因為作為框架碍扔，我們并不知道要不對的對象中的類的結(jié)構(gòu)內(nèi)容是什么，作為一般性的框架結(jié)構(gòu)不同，我們要普遍化，好了又扯多了溶耘，如果地址相等二拐，我們就認為你是存在這個集合中的凳兵，返回true就行了，如果便利了所有還沒有相等的庐扫，就認為是沒有,則返回false
至于如何便利，這個我不用多說了吧形庭，for循環(huán)，或者是迭代器+while嘛?我們常用的就是這兩種嘛斟珊。

官方是如何實現(xiàn)的呢，人家是神級的任務(wù)囤踩，肯會有硬貨哦晓褪。趕緊看看，

 public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

額涣仿。。埃元。好像和我們的差不多哦媚狰。。崭孤。哈哈哈糊肠，其實就是這樣遗锣，道理和算法都很樸實，實現(xiàn)方式也就如此精偿，是不是發(fā)現(xiàn)你和大神的距離瞬間很近了。

好嘞搔预，我們在看一個：

 public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

這個方法是干什么的叶组？看名字就知道，就是將集合轉(zhuǎn)換成數(shù)組嘛甩十，既然是數(shù)組，我們就要搞一個數(shù)組出來嘛侣监。于是我們就new了一個數(shù)組出來.這個數(shù)組的大小肯定是集合的大小了，就是size()张弛。

Object[] r = new Object[size()];

然后怎么辦呢酪劫？然后我們是不是要遍歷這個集合。把集合里面的元素一個一個的添加到數(shù)組中覆糟，最后返回出去呢？

 Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }

在這里我們可以看出jdk的設(shè)計人員并不是遍歷這個集合滩字，而是遍歷我我們預(yù)先定義好的數(shù)組，為什么是這樣的呢漓藕？
我的認為是這樣的：首先遍歷一個集合是一個謹慎的事挟裂，為什么享钞？因為诀蓉，在多線程操作中暑脆，集合的大小可能會隨時會發(fā)生改變狐肢，我們無法準確的知道在我們調(diào)用toArray()之后，集合的內(nèi)容是否發(fā)生了改變份名，如果集合增加了，這個問題還不嚴重玄帕，但是如果集合減少了想邦，就會在循環(huán)的時候發(fā)生越界訪問異常，有人會說我使用迭代器訪問沒事啊丧没，這里也有一個問題锡移，就是空間的浪費問題，你會發(fā)現(xiàn)我們返回的數(shù)組不是滿數(shù)組淆珊，jdk設(shè)計人員在綜合了兩者之后，使用for循環(huán)遍歷定義的數(shù)組往声，使用迭代器遍歷集合，同時返回截取后的有數(shù)據(jù)的數(shù)組浩销。

這里這個我們就可以看出自己和jdk設(shè)計者的差距听哭，別人的嚴謹性，考慮問題的全面性陆盘。

有人又要問了，這個只能解決在遍歷過程中太防，集合可能發(fā)生減少的情況祟霍，那么如果發(fā)生了增加盈包，又該如何是好呢醇王？別急呢燥。寓娩。。寞埠，我們看到如果集合發(fā)生了增加焊夸，我們會發(fā)現(xiàn)，

 if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);

這段代碼不會執(zhí)行阱穗，而是進入了下面的代碼

 return it.hasNext() ? finishToArray(r, it) : r;

這句代碼是什么意思呢？就是說我將數(shù)組全部遍歷完成了昌抠，發(fā)現(xiàn)集合中沒有下一個元素了，就直接返回我們原來的數(shù)組（代碼執(zhí)行到這一步是集合沒有發(fā)生過改變炊苫，數(shù)組的大小和集合的大小是一致的）冰沙，如果還有元素沒有加入數(shù)組，這就壞事了倦淀，是不是。怎么辦呢姻成？
代碼告訴了我們是調(diào)用finishToArray(r, it)愿棋，這又是是一個什么東西呢？參數(shù)是一個是將我們放有數(shù)據(jù)的數(shù)組傳遞了進去糠雨，然后又將我們的迭代器傳遞了進去。
我們想一下琅攘，如果是我們的話，里面如何實現(xiàn)呢坞琴？會有什么功能呢？首先它既然要單獨處理寒亥，就是說要將剩余的數(shù)據(jù)還要一起加進數(shù)組荧关，那我們的數(shù)組不夠，怎么辦呢忍啤？找一個更大的數(shù)組唄，然后將數(shù)據(jù)放里面嘛胸竞，話是沒錯参萄，可是找多大的數(shù)組呢煎饼。額。吆玖。。這個懵逼了怜奖，哈哈哈翅阵，我們來看看jdk怎么做的.

 private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // overflow-conscious code
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

首先他將我們原來的數(shù)組長度用變量i存放起來，然后在使用迭代器找元素滥崩，但是我們在while循環(huán)里又搞了一個cap這個是什么呢讹语？不急慢慢看，它判斷我們的i是否等于cap這個不是扯淡嗎，這個肯定的啊导匣，初始賦值都是數(shù)組的長度嗎茸时，怎么不相等呢？這里不是多此一舉嗎屹蚊？是嗎？帶著問題命斧，我們繼續(xù)看嘱兼，接下來我們又看到了一個newCap,這個家伙等于cap + (cap >> 1) + 1，啥意思芹壕，從大小上看就是這個大小就是在cap的基礎(chǔ)上加上cap的一半還多加一個1，哦通孽。睁壁。。我猜想這個就是擴容數(shù)組了潘明，是不是，帶著第二個問題厚宰，繼續(xù)看遂填，它又判斷newCap是不是大于MAX_ARRAY_SIZE的值，這個是什么鬼吓坚？

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

這個就是分配給數(shù)組的最大值，為了避免數(shù)組無限大的問題并齐，看值我們就知道差不多夠用了，再打就不是int能夠表示的了,哈哈哈撕贞，小插曲测垛，繼續(xù)，我們假設(shè)不會超過食侮，開始執(zhí)行

 r = Arrays.copyOf(r, newCap);

是不是有點懂了，將數(shù)組開始擴容了链快，擴容后的新的數(shù)組眉尸，從新給了r，然后開始存放噪猾，我們的第二個問題猜想解決了，是正確的

r[i++] = (T)it.next();

最后在開始循環(huán)丝蹭，那第一個問題呢坪蚁，我們回頭看看，發(fā)現(xiàn)當我們再次循環(huán)的時候迅细，cap就不等于i淘邻。因為，i每次加1统阿，而cap是不是一次加了(cap >> 1)+1啊筹我，這里我們就知道了，為什么又要加1了吧蔬蕊，因為至少要加1啊，要不沒有意義是不是呢麻献？也就是說，當i==cap的時候监婶，就是數(shù)組擴容的時候齿桃，就是說發(fā)現(xiàn)數(shù)組又不夠用了，對吧短纵。

下面我們看最后一段代碼，這個也是防止過度擴容的刮刑，最后保證返回的數(shù)組是一個滿數(shù)組吧养渴。

return (i == r.length) ? r : Arrays.copyOf(r, i);

到這里我們還有最后一個問題沒有處理，就是cap很不幸理卑，真的很大，然后怎么辦帆疟，代碼中我們看到這樣一句代碼宇立？

 newCap = hugeCapacity(cap + 1);

從形式上看它好像是對newCap進行了從新的定義分配，那到底是如何呢柳琢？看看代碼實現(xiàn)润脸。

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

我們看到 minCapacity < 0這個是什么呢？不是說這個minCapacity太小毙驯，反而是太大，我們知道計算機的數(shù)是有符號的垦巴，最高位是符號位，當一個數(shù)太大溢出了魂那，表示的是符合為也有了數(shù)字1，這個時候這個數(shù)就是負數(shù)了鲜结，jdk直接返回內(nèi)存溢出的異常活逆，如果這個值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之間的話，我們返回Integer.MAX_VALUE否則的話我們返回MAX_ARRAY_SIZE怒允，這樣我們就做了最精細的處理了锈遥。

到此我們就分析完了toArray() 這個方法的全部實現(xiàn)了，是不是感覺考慮的東西有點多呢所灸？哈哈哈，要不你以為jdk設(shè)計者牛在哪呢钾唬？人家處處是細節(jié)啊侠驯，我們就是要從源碼中學(xué)習，不是嗎儒士。

好了本次就分析到這里了檩坚，下次我們在繼續(xù)。效床。权谁。