标签（空格分隔）： java

上一篇文章我们简单的对java集合框架有了一个简单的认识，本次，我们来具体的探讨一下集合框架中的一些接口的继承和实现。我不计划使用简单的陈述性的语言来描述，而是大家一起探讨性的学习。

首先，我们从最常用最清楚的ArrayList类入手，我并不打算一开始就从上至下的分析其源码是如何实现的，为什么呢？这个类这么多方法，这么多的功能，为什么会有这个方法？，这样分析我们很迷茫啊，
首先我们来一个宏观的认识类的继承结构：

ArrayList类继承结构.png

当我们看到这个图的时候，我们的第一个感觉就是这么多继承关系，是吗？

哈哈，扯淡的，java中哪有多继承，准确的说应该是继承和实现关系，只有和AbstractList类是继承关系，其他的都是实现，也就是说其他的都是接口勒。既然是接口也就是说功能上具有独立性，也就是说他们只是对ArrayList进行各种方面的扩展，我们这里只讨论主要的功能，就是集合的功能，哪些东西是集合的功能呢？

这个我们一眼就看的出来，Collection,其他的是什么鬼，我也不知道，目前为止，我就知道Collection具有集合的功能，Iterable是操作集合的迭代器，但是，从实现和继承的关系，我们可以知道，AbstractCollection和List都和Collection有关系，而且，从图上可以看出来，他们一个是实现，一个是继承，这里我声明一下，这个图不是我画的，是idea工具自动生成的。。。也就是说List是一个接口，AbstractCollection是一个实现类，好了先看看我们的认识是不是正确的？

打开AbstractCollection和List源码，看看

AbstractCollection.png

List.png

哈哈，还真是的，但是我们还有一个意外的发现，AbstractCollection是一个抽象实现类，卧槽，怪不得它的类名是这样的。既然是抽象的就说明实现了部分东西，要不然这货为啥实现呢？好我们看看她实现了什么？

AbstractCollection实现类结构图.png

//没有实现，反正就是返回一个迭代器就行了，
  public abstract Iterator<E> iterator();
//没实现，功能吗都知道就是计算这个集合的大小的，至于如何计算。。。我也不知道。
public abstract int size();

行了，我们来看一个实现的东西：我们看到isEmpty（）实现了，这个看看

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

额。。。好吧，这个实现我服，哈哈哈，以后我也可以这样来个Collection的实现类了。so easy在看一个
就看boolean contains(Object o)这个方法吧。

我们自己先分析一下，如果是我们自己的话如何实现呢?
我的话，会这样，首先我们要便利这个集合，从第一个开始，从集合中取出元素，然后和这个对象进行对比，对比是什么呢?上一篇就剧透过，是按地址对比的，为什么呢？因为作为框架，我们并不知道要不对的对象中的类的结构内容是什么，作为一般性的框架结构，我们要普遍化，好了又扯多了，如果地址相等，我们就认为你是存在这个集合中的，返回true就行了，如果便利了所有还没有相等的，就认为是没有,则返回false
至于如何便利，这个我不用多说了吧，for循环，或者是迭代器+while嘛?我们常用的就是这两种嘛。

官方是如何实现的呢，人家是神级的任务，肯会有硬货哦。赶紧看看，

 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;
    }

额。。。好像和我们的差不多哦。。。哈哈哈，其实就是这样，道理和算法都很朴实，实现方式也就如此，是不是发现你和大神的距离瞬间很近了。

好嘞，我们在看一个：

 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;
    }

这个方法是干什么的？看名字就知道，就是将集合转换成数组嘛，既然是数组，我们就要搞一个数组出来嘛。于是我们就new了一个数组出来.这个数组的大小肯定是集合的大小了，就是size()。

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();
        }

在这里我们可以看出jdk的设计人员并不是遍历这个集合，而是遍历我我们预先定义好的数组，为什么是这样的呢？
我的认为是这样的：首先遍历一个集合是一个谨慎的事，为什么？因为，在多线程操作中，集合的大小可能会随时会发生改变，我们无法准确的知道在我们调用toArray()之后，集合的内容是否发生了改变，如果集合增加了，这个问题还不严重，但是如果集合减少了，就会在循环的时候发生越界访问异常，有人会说我使用迭代器访问没事啊，这里也有一个问题，就是空间的浪费问题，你会发现我们返回的数组不是满数组，jdk设计人员在综合了两者之后，使用for循环遍历定义的数组，使用迭代器遍历集合，同时返回截取后的有数据的数组。

这里这个我们就可以看出自己和jdk设计者的差距，别人的严谨性，考虑问题的全面性。

有人又要问了，这个只能解决在遍历过程中，集合可能发生减少的情况，那么如果发生了增加，又该如何是好呢？别急。。。，我们看到如果集合发生了增加，我们会发现，

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

这段代码不会执行，而是进入了下面的代码

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

这句代码是什么意思呢？就是说我将数组全部遍历完成了，发现集合中没有下一个元素了，就直接返回我们原来的数组（代码执行到这一步是集合没有发生过改变，数组的大小和集合的大小是一致的），如果还有元素没有加入数组，这就坏事了，是不是。怎么办呢？
代码告诉了我们是调用finishToArray(r, it)，这又是是一个什么东西呢？参数是一个是将我们放有数据的数组传递了进去，然后又将我们的迭代器传递了进去。
我们想一下，如果是我们的话，里面如何实现呢？会有什么功能呢？首先它既然要单独处理，就是说要将剩余的数据还要一起加进数组，那我们的数组不够，怎么办呢？找一个更大的数组呗，然后将数据放里面嘛，话是没错，可是找多大的数组呢。额。。。这个懵逼了，哈哈哈，我们来看看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);
    }

首先他将我们原来的数组长度用变量i存放起来，然后在使用迭代器找元素，但是我们在while循环里又搞了一个cap这个是什么呢？不急慢慢看，它判断我们的i是否等于cap这个不是扯淡吗，这个肯定的啊，初始赋值都是数组的长度吗，怎么不相等呢？这里不是多此一举吗？是吗？带着问题，我们继续看，接下来我们又看到了一个newCap,这个家伙等于cap + (cap >> 1) + 1，啥意思，从大小上看就是这个大小就是在cap的基础上加上cap的一半还多加一个1，哦。。。我猜想这个就是扩容数组了，是不是，带着第二个问题，继续看，它又判断newCap是不是大于MAX_ARRAY_SIZE的值，这个是什么鬼？

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

这个就是分配给数组的最大值，为了避免数组无限大的问题，看值我们就知道差不多够用了，再打就不是int能够表示的了,哈哈哈，小插曲，继续，我们假设不会超过，开始执行

 r = Arrays.copyOf(r, newCap);

是不是有点懂了，将数组开始扩容了，扩容后的新的数组，从新给了r，然后开始存放，我们的第二个问题猜想解决了，是正确的

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

最后在开始循环，那第一个问题呢，我们回头看看，发现当我们再次循环的时候，cap就不等于i。因为，i每次加1，而cap是不是一次加了(cap >> 1)+1啊，这里我们就知道了，为什么又要加1了吧，因为至少要加1啊，要不没有意义是不是呢？也就是说，当i==cap的时候，就是数组扩容的时候，就是说发现数组又不够用了，对吧。

下面我们看最后一段代码，这个也是防止过度扩容的，最后保证返回的数组是一个满数组吧。

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

到这里我们还有最后一个问题没有处理，就是cap很不幸，真的很大，然后怎么办，代码中我们看到这样一句代码？

 newCap = hugeCapacity(cap + 1);

从形式上看它好像是对newCap进行了从新的定义分配，那到底是如何呢？看看代码实现。

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太小，反而是太大，我们知道计算机的数是有符号的，最高位是符号位，当一个数太大溢出了，表示的是符合为也有了数字1，这个时候这个数就是负数了，jdk直接返回内存溢出的异常，如果这个值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间的话，我们返回Integer.MAX_VALUE否则的话我们返回MAX_ARRAY_SIZE，这样我们就做了最精细的处理了。

到此我们就分析完了toArray() 这个方法的全部实现了，是不是感觉考虑的东西有点多呢？哈哈哈，要不你以为jdk设计者牛在哪呢？人家处处是细节啊，我们就是要从源码中学习，不是吗。

好了本次就分析到这里了，下次我们在继续。。。