Java学习之路——Java集合源码分析（一）

一、集合的继承关系

Collection是继承自Iterable

二、什么是Iterable

1 . Iterable是可迭代的意思
2 . Iterable是一个接口
3 . 我们看一下官方解释：Implementing this interface allows an object to be the target of the "for-each loop" statement.
简单意思就是：实现此接口，让对象允许成为"for-each loop"的目标。
相信什么是"for-each"大家都知道

4 . 里面有三个方法：

  • 1 Iterator<T> iterator()；生成一个迭代器
Iterator<T> iterator();
  • 2 default void forEach(Consumer<? super T> action)；根据action对内部元素进行遍历
 default void forEach(Consumer<? super T> action) {
        //判断动作是否为空
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
  • 3 创建一个分割器（Spliterator），这里先不了解。
default Spliterator<T> spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
}

那么我们简单定义一下，实现此接口的类会成为一个可迭代的容器。

三、什么是Collection

1 . 通过注释我们可以知道Collection是所有集合的根接口
2 . Collection中包含了很多处理容器中各种元素的方法，比如：增加，移除，比较（两个集合），转换（数组或者其他）

那么我们可以简单定义一下，这个Collection接口就是给实现它的容器提供基本规范的方法；

四、什么是List

1 .List是List家族的顶级接口
2 .List是一个有序集合序列（在我看来线性表）
3 .从List中的各种方法看来，List就是用来规范List家族的接口
4 .List家族的成员都必须实现这个接口，实现其中的方法，成为List的一员
5 .List家族有四个成员ArrayList、LinkList、Victor、Stack

这里简单总结一下，这些接口都是用于规范的，并没有实现具体逻辑。

五、ArryList是如何实现的

接下来我们要看ArryList的源码了，但是在看源码之前我们要理清思路，我们重点看什么？

  • 1 ArryList的重要方法，添加，移除，扩张，比较等等还有与其相关的属性
  • 2 ArryList的迭代器

1 . ArryList的迭代器，ArryList中有一个内部类专门实现了迭代器接口

 private class Itr implements Iterator<E> {}

2 . 虽然List已经有了一个基本的迭代器，但是List对这个基本的迭代器的功能并不满足，所以下面有产生了一个List专门用的迭代器：

private class ListItr extends Itr implements ListIterator<E> {}

3、初此之外，ArrayList覆写了父类和List接口的方法，添加，移除，扩张，比较等等。

  • 1 ArrayList是通过数组实现
  • 2 ArrayList扩张是数组的copyOf()方法，第一次扩张数组大小变为10，后面如果要扩张的话，大小变为以前的1.5倍
  • 3 对ArrayList的中操作迭代器会改变ArrayList的成员变量，但是如果只对ArrayList操作，则没有影响迭代器
  • 4 ArrayList里面的元素是无序的（没有按大小顺序排列），他是根据插入元素的先后顺序排列的

源码分析

ArrayList的源码比较清晰，这里只讨论是如何自动扩张的。
我们知道ArrayList是基于数组的，数组有什么不好的地方呢？对了，就是一旦生成了就大小固定无法扩展了，那么ArrayList是如何自动扩张的呢？
首先看向add()方法：

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

这里有一个调用了ensureCapacityInternal()方法，翻译一下：确保容量内部，那这个方法是干什么的呢？我们跟踪查看一下。

private void ensureCapacityInternal(int minCapacity) {
        //判断当前使用的数组是否为空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //最小的容量为DEFAULT_CAPACITY和size+1的更大者
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

从第二行看起，elementData是一个全局变量，用来表示ArrayList当前正在使用的数组，当前正在使用的数组是否是空数组，如果是空数组的话，最小容量就是DEFAULT_CAPACITY（10）和size+1的更大者。
好了看看第六行，又调用了一个ensureExplicitCapacity（）方法，解释一下：确保明确的容量，我们再跟踪查看，等会儿再回来。

 private void ensureExplicitCapacity(int minCapacity) {
 //ArrayList的结构变化增加了一次
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        //一定会执行
            grow(minCapacity);
    }

modCount是什么？ ArrayList 发生结构变化的次数。
接下来看看第6行：如果最小容量大于当前正在使用的数组的容量，就执行 grow（）方法，我们继续追踪grow()方法

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新的容量是旧的容量的1.5倍
        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);
    }

重点来了，看向第13行，数组实际扩张的办法，通过Arrays的静态方法copyOf（）。我们追踪一下这个方法：

 public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

啊哈，又调用了它的三个参数的重载方法，我们继续追踪：

  public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

完成了，就是直接new一个新的数组，然后再把旧的数组的数据复制回去。

接下来我们要返回到add（）方法中完成最后的步骤了：

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

给当前正在使用的数elementData添加元素，这里有个问题，size中的是什么呢？大家可以猜猜哦。。

六、LinkList是如何实现的

我们先看一下LinkList的继承关系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

我们可以看见LinkList比ArrayList多实现了一个接口Deque<E>，那么这个接口是什么呢？我们来看看

public interface Deque<E> extends Queue<E> {}

通过注释我们可以发现这个接口是一个线性双端队列，它支持容量限制的双端队列。
在这里我们对LinkList有了一点了解。接下来我们看看LinkList的注释。

 * Doubly-linked list implementation of the {@code List} and {@code Deque}
 * interfaces.  Implements all optional list operations, and permits all
 * elements (including {@code null}).

大致意思是：LinkList是一个双链表，可以操作所有元素

1、LinkList与ArrayList不同，他是双链表
2、LinkList的扩张与删除就是结点的增加和删除
3、集合中的元素是也是无序的，他是根据插入结点的位置来排列的
4、判断是从头结点插入还是从尾结点开始插入做了优化

源码分析

为什么说LinkList是双链表呢？

 /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

LinkList定义了一个头结点和一个尾结点。Node是LinkList的内部类，我们看看他这个结点是怎么实现的：

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

首先Node是一个私有的静态泛型类，它有三个全局变量，第一个变量是结点储存的元素，后面两个变量分别是当前结点的前驱结点和后继结点，很简单。

接下来我们看看LinkList的插入结点的方法add（）

public boolean add(E e) {
//直接插入默认插入到尾部
        linkLast(e);
        return true;
    }
    
      public void add(int index, E element) {
      //检查这个索引是否超出链表的边界
        checkPositionIndex(index);

        if (index == size)
        //链表为空的时候或者想要插入到尾部的时候直接插入到尾部
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

我们可以看见 LinkList的add（）有两个重载方法。

直接插入话，默认是插入到尾部的。

如果过通过索引插入的话，我们看向第15行：
这里执行了linkBefore（）方法，插入之前的查找工作，传入了需要插入的元素和node（）这个方法的返回值
我们先看看node（）这个方法是干什么的：

 Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

这里代码很简单，如果请求插入的索引小于size的一半则从头开始遍历，反之则从尾部开始遍历。返回的也是一个节点

然后我们看看linkBefore（）方法：

 /**
     * Inserts element e before non-null Node succ.//把我们要插入的元素插入到suuc这个节点之前
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

这部分代码的意思就是把我们需要插入的节点插入到我们用node（）方法找到的节点的前一个节点那里。

好了LinkList的源码主要也是分析add（）方法。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,386评论 6赞 479
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,939评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,851评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,953评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,971评论 5赞 369
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,784评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,126评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,765评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,148评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,479评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,080评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2赞 343