Java梳理之理解集合（二）

Collection集合

查看上面的结构图可以发现，Collection接口继承了Iterable接口，在Iterable接口中就拥有iterator()方法，可以和上面的Iterator接口联系起来；往下看又存在Queue子接口、Set子接口、List子接口，同时还有集合抽象基础类AbstractCollection，其余的抽象基础类AbstractList、AbstractSet、AbstractQueue都继承集合抽象基础类，同时又实现自己内部的接口List、Set、Queue。故而理解这些抽象基础类之后可以更容易的分析之后的具体类。

List
SubList类

在java.util包下，可以找到几个List类，如ArrayList、LinkedList和SubList。而这些类都是继承于AbstractList类，其中有个方法subList()很有趣，如下所示：

/**
**AbstractList类中subList方法源码
**/
public List subList(int i, int j) {
        return ((List) ((this instanceof RandomAccess) ? new RandomAccessSubList(this, i, j)
                : new SubList(this, i, j)));
}

其中RandomAccess仅仅只是个标记接口，内部不存在任何的方法。在上面的方法运行后会返回一个SubList对象，很重要的一点：在new这个对象的时候，传入的是当前的this，点开SubList类的源码可知，其拥有字段如下：

/**
**SubList类源码  字段
**/
private AbstractList l; 
private int offset;
private int size;
private int expectedModCount;

其中拥有的构造器如下：

/**
**SubList类源码 构造器
**/
SubList(AbstractList abstractlist, int i, int j) {
        if (i < 0)
            throw new IndexOutOfBoundsException((new StringBuilder()).append("fromIndex = ").append(i).toString());
        if (j > abstractlist.size())
            throw new IndexOutOfBoundsException((new StringBuilder()).append("toIndex = ").append(j).toString());
        if (i > j) {
            throw new IllegalArgumentException((new StringBuilder()).append("fromIndex(").append(i)
                    .append(") > toIndex(").append(j).append(")").toString());
        } else {
        **  l = abstractlist;**
        **  offset = i;**
        **  size = j - i;**
        **  expectedModCount = l.modCount;**
            return;
        }
    }

如上所示，这里是直接把当前类this传给了SubList，而不是重新创建一个对象。故而AbstractList类的subList方法返回的仅仅是一个视图，对它的返回对象做的任何操作都会反映到原来的List中，其中size=j-i，表明它获取的长度并不包括原数组下标j的数据。当然并不是说不好，它还是有个很好的用法的，如下所示：

/**
**subList的应用
**/
public static void main(String[] arg0){
        ArrayList<String> list = new ArrayList<String>();
        list.add("test1");
        list.add("test2");
        list.add("test3");
        list.add("test4");
        list.add("test5");
        list.add("test6");
        list.subList(1, 4).clear();
        for(String s:list){
            System.out.println(s);
        }
    }
输出：
test1
test5
test6

可以看到，这样可以很方便的对list中间的部分数据进行处理，SubList还提供了一些常用的方法，用来操作这个视图的数据，相应的可以自行去了解。

ArrayList类

这个类继承AbstractList类，同时实现List、RandomAccess、Cloneable、Serializable等四个接口。打开源码可以看到，这个类有如下几个字段：

/**
**ArrayList源码 字段
**/
private transient Object elementData[];  //容器数组
private int size; //List长度
protected transient int modCount; //父类继承而来，修改的次数

如上所示，这三个字段中，功能字段只有前两个elementData[]和size。从这里也可以看出，ArrayList的底层是使用数组elementData来实现的，这个数组存的对象为Object。同时，它提供了三个构造器，如下所示：

/**
*ArrayList源码 构造器
**/
public ArrayList(int i) {
        if (i < 0) {
            throw new IllegalArgumentException((new StringBuilder()).append("Illegal Capacity: ").append(i).toString());
        } else {
            elementData = new Object[i];
            return;
        }
    }
public ArrayList() {
        this(10);
    }
public ArrayList(Collection collection)
    {
        elementData = collection.toArray();
        size = elementData.length;
        if(((Object) (elementData)).getClass() != [Ljava/lang/Object;)
            elementData = Arrays.copyOf(elementData, size, [Ljava/lang/Object;);
    }

在构造器这部分可以看到，它会初始化这个数组elementData，这里支持的三种构造器前两种会给数组初始化长度i或者默认长度10，最后一种则是使用了Collection接口中的方法toArray()直接转成数组。
在这字段和构造器看完之后，根据数组结构可知，数组本身是有下标的存在，在ArrayList中也保留了数组下标的作用，故而使得操作会变的简单很多，比如添加add(int i,Object obj)、设置set(int i,Object obj)、删除remove(int i)等。除此之外，还有两个方法如下：

/**
**ArrayList 
**/
public void trimToSize() {
        modCount++;
        int i = elementData.length;
        if (size < i)
            elementData = Arrays.copyOf(elementData, size);
    }

public void ensureCapacity(int i) {
        modCount++;
        int j = elementData.length;
        if (i > j) {
            Object aobj[] = elementData;
            int k = (j * 3) / 2 + 1;
            if (k < i)
                k = i;
            elementData = Arrays.copyOf(elementData, k);
        }
    }

其中trimToSize()方法缩小数组长度，类似于String中的trim()方法，而ensureCapactity()方法用来扩容数组。至此，ArrayList内部实现大体上梳理完全，从实现方面思考自然就可以解决一些面试问题。

LinkedList类

类LinkedList不同于ArrayList，它的底层并不是使用数组来写的；查看源码可知它继承了AbstractSequentialList，同时实现了List、Deque、 Cloneable、 Serializable这四个接口，其中AbstractSequentialList类继承了AbstractList类并使用ListIterator来实现了List中一些有需要下标的操作，如add(i, E)；而比较特别的是Deque接口，在这个接口中定义了一系列双端队列的操作，即两头都可以操作，还增加了poll(),peek(),push(),pop()操作，所以LinkedList类的操作方法看起来相比ArrayList多了一些。
下面从字段开始，查看源码可知，它有两个字段如下：

/**
**LinkedList类 字段
**/
private transient Entry header;
private transient int size;

这里可以看到，字段header的类型是Entry，这是个LinkedList的内部类，源码如下：

/**
** LinkedList内部类 Entry 源码
**/
private static class Entry {

        Object element;
        Entry next;
        Entry previous;

        Entry(Object obj, Entry entry1, Entry entry2) {
            element = obj;
            next = entry1;
            previous = entry2;
        }
    }

在静态内部类Entry中存在三个字段，这里就可以看出为什么叫LinkedList了，类LinkedList内部实现并不是用数组而是保存下一个元素的地址，形成像铁链一样的结构。这里也是说明为什么说LinkedList便于插入或者删除操作。类LinkedList的构造器如下所示：

/**
**LinkedList类的构造器
**/
public LinkedList() {
        header = new Entry(null, null, null);
        size = 0;
        header.next = header.previous = header;
    }

public LinkedList(Collection collection) {
        this();
        addAll(collection);
    }

可以看到，LinkedList的size默认初始值是0，当然，这里也提供了入参是Collection的构造器，说明这个接口下的所有类都可以转化为LinkedList。在这之后，查看它的方法就知道，它的操作脱离不了Entry实例和长度size，其中Entry类的next字段和previous字段是这个类的核心操作点，根据这点，源码中方法就很清楚的展示出来了，通过常见的方法就可以完成对LinkedList的操作，如下所示：

/**
**LinedList类的 entry()方法
**/
private Entry entry(int i) {
        if (i < 0 || i >= size)
            throw new IndexOutOfBoundsException(
                    (new StringBuilder()).append("Index: ").append(i).append(", Size: ").append(size).toString());
        Entry entry1 = header;
        if (i < size >> 1) {
            for (int j = 0; j <= i; j++)
                entry1 = entry1.next;

        } else {
            for (int k = size; k > i; k--)
                entry1 = entry1.previous;

        }
        return entry1;
    }

在这个方法中通过下标i来获取LinkedList的数据，也就是普通的if或or操作。其他的方法，或调用这个方法，或进行类似的操作，具体的其他方法就不在这里放了。

当然，并不是说，List下就只有这三个类，其实这三个类只是三个并不是线程安全的类，如果要扯上线程安全的问题，那么还有类Vecter、Stack栈，只是这两个类在使用中并不常见，而且在新版本中已经对线程安全的List有了替代类，详情查看java.util.concurrent包下的各个同步集合类。

Set

在结构图中可以发现，Set下面有个子类AbstractSet，一应的Set类都继承这个抽象类。在Java.util包中可以找到的Set集合类有EnumSet、HashSet、LinkedHashSet和TreeSet。在这里就从HashSet开始：

HashSet

在上篇文章中梳理过Map之后，那么Set就很简单了。在HashSet的源码中可以看到其中有两个字段，如下所示：

/**
**HashSet源码 字段
**/
private transient HashMap map;
private static final Object PRESENT = new Object();

在这里就可以看到，HashSet的底层是使用HashMap实现的，看过HashMap源码之后，这个HashSet就非常简单了，只是HashMap的一层包装，查看Set的方法add(obj)如下：

/**
**HashSet的add方法
**/
public boolean add(Object obj) {
        return map.put(obj, PRESENT) == null;
}

在put方法内部使用map.put()方法来实现，将静态对象PRESENT置入，而我们的Set存放的对象则作为Key来存放，所以说Set是Map的一层包装。

TreeSet

类似于HashSet，TreeSet也是使用对于的Map来实现的。查看TreeMap中的源码，其字段如下所示：

/**
**TreeSet源码 字段
**/
private transient NavigableMap map;
private static final Object PRESENT = new Object();

可以看到，其中的字段NavigableMap类型的map，查看构造器如下：

/**
**TreeMap源码 构造器
**/
TreeSet(NavigableMap navigablemap) {
        m = navigablemap;
    }
public TreeSet() {
        this(((NavigableMap) (new TreeMap())));
    }

public TreeSet(Comparator comparator1) {
        this(((NavigableMap) (new TreeMap(comparator1))));
    }

public TreeSet(Collection collection) {
        this();
        addAll(collection);
    }

public TreeSet(SortedSet sortedset) {
        this(sortedset.comparator());
        addAll(sortedset);
    }

对于每个构造器而言，最后都会new一个TreeMap，并将这个TreeMap转化为NavigableMap传给被保护的构造器。这样就知道TreeSet内使用的就是TreeMap来存储TreeSet。
在TreeSet中的存储和HashSet一样，如下所示：

/**
**TreeSet的add方法
**/
public boolean add(Object obj) {
        return m.put(obj, PRESENT) == null;
}

可以看到，这里使用的也是map的put方法，并将PRESENT字段存放在val中，整个的TreeSet相当于是TreeMap包装了一层。

到此为止，Set大体上就是这样的，如果清楚了Map的内部结构，那么Set则没有什么难点。

Queue

在Java中存在队列这么一个结构，就像我们平常所知道的队列一样，它奉行的是先进先出的原则，可以看到在源码中其定义如下：

/**
**Queue接口
**/
public interface Queue extends Collection {
    public abstract boolean add(Object obj); //插入指定元素到容器中，成功返回true，失败报异常。
    public abstract boolean offer(Object obj);  //插入到容器，失败返回false。
    public abstract Object remove();  //获取元素并从容器中移除
    public abstract Object poll();  //获取元素并从容器中移除，为空则返回null
    public abstract Object element();  //获取头元素，但是不移除
    public abstract Object peek();  //获取头元素，但是不移除，为空则返回null
}

在Queue接口下，存在子类AbstractQueue，其中对几个方法拥有简单的实现，并没有什么需要特别注意的点。在AbstractQueue下还则存在一个类PriorityQueue，可以看它的实现：

PriorityQueue

在看了之前的那些之后，类PriorityQueue也能简单的分析出来，首先可以查看它的结构拥有一个内部类Itr实现了Iterator接口，就像之前看到的类似的内部类一样，它必定是用在Collection接口的Iterator()方法中。除此之外，可以查看这个类的字段：

/**
** PriorityQueue源码 字段
**/
private static final int DEFAULT_INITIAL_CAPACITY = 11; //初始化长度
private transient Object queue[]; //内部容器
private int size;  //大小
private final Comparator comparator;  //比较器
private transient int modCount;  //修改的次数

到这里的时候，这几个字段相对来说已经很熟悉了，相较于ArrayList类来说，字段方面很类似，PriorityQueue也是使用的数组来实现的。那么查看它的构造器，如下：

/**
**PriorityQueue构造器
**/
public PriorityQueue() {
        this(11, null);
    }
public PriorityQueue(int i){...}
public PriorityQueue(int i, Comparator comparator1) {
        size = 0;
        modCount = 0;
        if (i < 1) {
            throw new IllegalArgumentException();
        } else {
            queue = new Object[i];
            comparator = comparator1;
            return;
        }
}
public PriorityQueue(Collection collection){...}
public PriorityQueue(PriorityQueue priorityqueue){...}
public PriorityQueue(SortedSet sortedset){...}
//构造器内部方法
private void initFromCollection(Collection collection)
    {
        Object aobj[] = collection.toArray();
        if(((Object) (aobj)).getClass() != [Ljava/lang/Object;)
            aobj = Arrays.copyOf(aobj, aobj.length, [Ljava/lang/Object;);
        queue = aobj;
        size = aobj.length;
    }

如上所示，在第一个构造器中可知PriorityQueue内部的数组默认长度为11，它也能接受各种参数Collection参数，对于上面两种类型的参数PriorityQueue和SortedSet而言，其中的差别在于使用的比较器不同，两个都是有顺序的Collection使用的也是它自身的Comparator。
对于类PriorityQueue内部的实现而言，其实是比较简单的，如下所示offer()方法：

/**
**PriorityQueue源码 offer方法
**/
public boolean offer(Object obj) {
        if (obj == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = obj;
        else
            siftUp(i, obj);
        return true;
    }
private void siftUp(int i, Object obj) {
        if (comparator != null)
            siftUpUsingComparator(i, obj);
        else
            siftUpComparable(i, obj);
    }
private void siftUpUsingComparator(int i, Object obj) {
        do {
            if (i <= 0)
                break;
            int j = i - 1 >>> 1;
            Object obj1 = queue[j];
            if (comparator.compare(obj, obj1) >= 0)
                break;
            queue[i] = obj1;
            i = j;
        } while (true);
        queue[i] = obj;
    }

从如上方法就可以看出，它的实现，只是简单的比较，然后赋值，并没有复杂的逻辑。而另一个添加方法add则是调用的offer()方法。

至此，关于Collection这部分就简单的梳理完成，虽然并没有细致的分析到每一个方法或者类，但是做到这些集合类的实现方式都清楚；如果需要重新设计集合类，也可以根据现有的集合类或者类似的实现方式完成逻辑需要。当然，也有人说：不要局限于过去的所知有限的数据结构，设计出优秀好用的集合类就是好的。

Collections和Arrays

在工具类中，Collections负责的是集合操作，包括没有继承Collection接口的Map集合，其中主要有如下几个类型的操作：

  1. 排序
    对list列表进行排序操作，如sort(list)、sort(list,comparator)
    倒序 reverse(list)
    对List中的元素随机排列 shuffle(list)、shuffle(list,random)
    对比较器相反操作使得使用的集合倒序 reverseOrder()、reverseOrder(comparator)
  2. 查找
    二分查找 如binarySearch(list,obj)、binarySearch(list,obj,comparator)
    集合中的最大最小值min(collection)、min(collection,comparator)、max(collection)、max(collection,comparator)
    返回指定源列表中第一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1 indexOfSubList(list1, list2)
    返回指定源列表中最后一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回-1 lastIndexOfSubList()
    返回指定collection中 obj的个数 frequency(collection,obj)
    3.移位
    交换列表中指定两个元素的位置 swap(list,i,j)
    循环移动 rotate(list1,i)，例：list包含[a,b,c,d,e]。在调用Collection.rotate(list, 1)或者Collection.rotate(list, -4)后， list将为[e, a, b, c, d]
    4.替换
    使用指定元素替换列表中的所有元素 fill(list, obj)
    使用另一个值替换列表中出现的所有某一指定值replaceAll(list1,obj,obj1)
  3. 拷贝
    拷贝列表list2 copy(list,list2)
    拷贝i个对象obj成为一个数组，不可变 nCopies(i,obj)
    6.比较
    判断相等 eq(obj1,obj2)
    两个集合是否有重复元素 disjoint(collection1,collection2)
    7.转换
    Collection集合转Enumeration枚举 enumeration(collection)
    枚举Enumeration转List list(enumeration)
    Map转Set newSetFromMap(map)
    Deq转Queue ``asLifoQueue(deq)
    8.添加
    addAll(Collection,obj[])
    9.只读集合：这些集合一旦初始化以后就不能修改，任何修改这些集合的方法都会抛出UnsupportedOperationException异常
    unmodifiableCollection(collection)
    unmodifiableSet(set)
    unmodifiableSortedSet(sortedset)
    unmodifiableList(list1)
    unmodifiableMap(map)
    unmodifiableSortedMap(sortedmap)
    10.同步集合：为集合加锁，保证数据安全性
    synchronizedCollection(collection)
    synchronizedSet(set)
    synchronizedSortedSet(sortedset)
    synchronizedList(list1)
    synchronizedMap(map)
    synchronizedSortedMap(sortedmap)
    11.检查集合：在插入的同时检查是否是这个类型：
    checkedCollection(collection,class)
    checkedSet(set,class1)
    checkedSortedSet(sortedset,class1)
    checkedList(list1,class1)
    checkedMap(map,class1,class2)
    checkedSortedMap(sortedMap,class1,class2)
    12.无元素的空集合
    emptySet()
    emptyList()
    emptyMap()
    13.单一元素并且只读
    singleton(obj)
    singletonList(obj)
    singletonMap(obj)

相较于Collections来说，Arrays的方法会少很多，主要包括数组的排序sort1()、交换swap()、查找binarySearch()、比较equals()和deepEquals()、填充fill()、拷贝copyOf()和copyOfRange()、hash值hashcode()、深度hash算法deepHashCode()、toString()方法和deepToString()。其中包括基本数据类型和泛型方法，具体的使用还需要根据实际情况而定。

到此为止，集合已经大体上梳理过了，其中还有些很细节的东西需要注意，比如asList()方法返回的list并不能被操作、保持compareTo和equals同步等，其中的缘由在源码中都可以找到。 基础系列到这基本上也都写了，如果其中有疑问或不解的地方请留言，我会认真查看并修改解答，准备下一个计划吧~

参考：
java.utl.*

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

推荐阅读更多精彩内容

  • Java初级面试题
    1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语...
    子非鱼_t_阅读 31,567评论 18赞 399
  • JAVA面试题 java部分
    （一）Java部分 1、列举出JAVA中6个比较常用的包【天威诚信面试题】 【参考答案】 java.lang;ja...
    独云阅读 7,066评论 0赞 62
  • java中的集合
    Collection ├List │├LinkedList │├ArrayList │└Vector │└Stac...
    AndyZX阅读 869评论 0赞 1
  • java笔记
    java笔记第一天 == 和 equals ==比较的比较的是两个变量的值是否相等，对于引用型变量表示的是两个变量...
    jmychou阅读 1,485评论 0赞 3
  • iOS开发--打印NSRange,CGRect,CGPoint等结构体
    NSString*NSStringFromCGPoint(CGPoint point); NSString*NSS...
    李sir35阅读 1,608评论 0赞 3