Java总结之容器家族--Collection

零、前言

Collection是[收集品]的意思,这里称[容器],是java中的一个接口,位于java.util包下 Collection下有三大接口:List(列表)Set(集合)Queue(队列)

Collection.png

容器接口子类及方法.png


第一节:List接口

List:列表,顾名思义是一种表结构,核心方法: 按索引插入元素 void add(int var1, E var2) 按索引删除元素 E remove(int var1); 按索引修改元素 E set(int var1, E var2) 按索引查询元素 E get(int var1)

特点:  
1.增删改查操作都可以按照索引进行精确的控制,所以是元素的有序排列  
2.允许相同元素

List子类.png

List是java中使用频率非常高的一个接口,最要的子类:ArrayList、Vector、LinkedList 1.其中ArrayList、Vector是AbstractList-->AbstractCollection-->Collection 路线 2.LinkedList不止实现了List,还实现了Deque,就像得到两个师傅的真传,招式(方法)更多一些 Queue接口是队列(先进先出),Deque接口(双端队列)是Queue的弟子,两头都能随意进出 所以根据需求即可当栈也可当队列,LinkedList得到了Deque的真传,所以也可以

关于抽象类:

抽象类一般是先实现接口,或者拓展一些子类公用方法,总之就是把能做的先做了。 有种天下父母心的感觉,就像AbstractList对ArrayList说:我能帮你做的尽量都做了,接下来就看你的了

public abstract class AbstractCollection<E> implements Collection<E>
public abstract class AbstractSequentialList<E> extends AbstractList<E> 
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

1.ArrayList:数组列表

ArrayList.png

2.Vector:载体

Vector.png

3.LinkedList:链式列表

LinkedList.png

4.Vector、ArrayList与 LinkedList的比较

可以说Vector、ArrayList是亲兄弟,LinkedList算个堂兄

项目

线程安全?

实现

扩容

定点添加/删除

尾添加/删除

查询

修改

ArrayList

数组

50%

O(n)

O(1)

O(1)

O(1)

Vector

数组

100%

O(n)

O(1)

O(1)

O(1)

LinkedList

双链表

--

O(n)

O(1)

O(n)

O(n)

尾添加测试[add(E)]

----

复杂度

1000

10000

10W

100W

1000W

ArrayList

O(1)

0.0004秒

0.0016秒

0.0063秒

0.0297秒

0.6704秒

LinkedList

O(1)

0.0004秒

0.0017秒

0.0098秒

0.2384秒

2.4285秒

操作数opCount=1000W:插入的位置与耗时比较

----

1/9

3/9

5/9

7/9

8/9

ArrayList

0.1496秒

0.1136秒

0.0821秒

0.0297秒

0.0012秒

LinkedList

0.0150秒

0.0251秒

0.0386秒

0.0176秒

0.0102秒

可见ArrayList越往后插入越快,因为要变动的元素越少 LinkedList从两头到中间速度变慢,取决于链表的查询机制,总的来说, 随机添加LinkedList比较有优势些,只是末尾添加ArrayList较好

数组和双链表两种数据结构:
数组:定点添加,后面元素都要往后挪个位,O(n)-------双链表:耗时在找到那个定点,添加很快,综合O(n)
数组:定点删除,后面元素都要往前挪个位,O(n)-------双链表:耗时在找到那个定点,删除很快,综合O(n)
数组:定点查询,数组自带索引光环,O(1)      -------双链表:一个一个挨着找 O(n)
数组:定点修改,数组自带索引光环,O(1)      -------双链表:耗时在找到那个定点,修改很快,综合O(n)
综上所属:
随机访问、修改性能:Vector、ArrayList>LinkedList  
考虑到Vector、ArrayList添加或删除时:    
1.可能伴随扩容/缩容,  
2.当元素个数巨大时,可能造成大量空闲空间  
3.数组连续开辟空间,会造成储存空间的碎片化  
的这些问题,在大量添加或删除操作使用LinkedList是更好的选择

因为双链表:
1.双链表的添加/删除耗时在查找工作,而双链表查询时会查看索引在前半还是后半
来决定从头查询或从尾查询,从而最差情况只需size/2,而数组最差情况为size
2.链表不需要开辟连续空间,从而避免储存空间的碎片化  

另外在数据非常巨大的时候:
LinkedList基于双链表,需要new 巨大数量的节点(Node),
Vector、ArrayList只是开辟空间,所以更好一些,所以根据需求酌情处理
关于 Vector
Vector类对集合的元素操作时都加了synchronized,保证线程安全。但使得效率下降:如

    public synchronized boolean add(E e) {
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }

所谓同步:即当一个Iterator被正在被使用,另一个线程对Vector添加或删除元素,这时调用Iterator的方法时将抛出异常
public synchronized void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final Object[] es = elementData;
        final int size = elementCount;
        for (int i = 0; modCount == expectedModCount && i < size; i++)
            es[i] = operator.apply(elementAt(es, i));
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        modCount++;
    }

可以看到很多关于修改的方法当:modCount != expectedModCount时都会扔一个ConcurrentModificationException异常
也就是期望的修改次数与真实的修改次数不一致时

第二节:Set接口

集合:数学上的集合性质:

确定性:给定一个集合,任给一个元素,该元素或者属于或者不属于该集合
互异性:一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次。
无序性:一个集合中,每个元素的地位都是相同的,元素之间是无序的。

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性,根本上是HashMap、LinkedHashMap、TreeMap的特性


1.HashSet

HashSet内部有一个HashMap<E,Object> map成员变量,增删实际上是使用map的方法 按照哈希的顺序:hashCode(),equals(Object obj) 底层实现:HashMap

HashSet.png

private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
2.LinkedHashSet

LinkedHashSet是HashSet的子类,源码少得可怜,基本上都是调用父类(HashSet)的构造方法 基于一个由链表实现的哈希表,保留了元素插入顺序 底层实现:LinkedHashMap

LinkedHashSet.png

LinkedHashSet中:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

HashSet中的三参构造

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
3.TreeSet---有序集合

实现NavigableSet:使用元素的compareTo对元素进行排序,也可使用Comparator自定义比较器 TreeSet多拜了一个师傅:NavigableSet-->SortedSet 使用方法也多几个 底层实现:TreeMap

    public TreeSet() {
        this(new TreeMap<>());
    }

TreeSet.png


插入元素顺序比较
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("赵");
        hashSet.add("钱");
        hashSet.add("孙");
        hashSet.add("李");

        //按照哈希的顺序:hashCode(),equals(Object obj)
        System.out.println(hashSet);//[钱, 赵, 孙, 李]

        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("赵");
        linkedHashSet.add("钱");
        linkedHashSet.add("孙");
        linkedHashSet.add("李");
        //基于链表实现了插入的顺序
        System.out.println(linkedHashSet);//[赵, 钱, 孙, 李]

        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("赵");
        treeSet.add("钱");
        treeSet.add("孙");
        treeSet.add("李");
        //按照compareTo()的排序
        System.out.println(treeSet);//[孙, 李, 赵, 钱]

项目

线程安全?

实现

add

remove

contains

HashSet

HashMap

O(1)

O(1)

O(1)

LinkedHashSet

LinkedHashMap

O(1)

O(1)

O(1)

TreeSet

TreeMap

O(log(n))

O(log(n))

O(log(n))


第三节:Queue

关于队列,是一直先进先出的线性数据结构,使用场合比较狭窄 子类常见的有PriorityQueue(优先队列)和上文提到的LinkedList。

Queue.png


PriorityQueue

PriorityQueue优先队列,是基于数组实现的二叉堆来实现的特殊队列,具有完全二叉树的性质。 每次从优先队列中取出来的元素要么是最大值或最小值(最大堆/最小堆)

Collection的简单总结就酱紫


后记、

1.声明:

1----本文由张风捷特烈原创,转载请注明 2----欢迎广大编程爱好者共同交流 3---个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 4----你的喜欢与支持将是我最大的动力

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人分享

JAVA源码走读(一) HashMap与ArrayList

HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变...

11920
来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

35860
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

13120
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11440
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(中)

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

14210
来自专栏糊一笑

Immutable日常操作之深入API

写在前面 本文只是个人在熟悉Immutable.js的一些个人笔记,因此我只根据我自己的情况来熟悉API,所以很多API并没有被列举到,比如常规的push/ma...

43590
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

42270
来自专栏数据结构笔记

数据结构(三):线性表

该序列中所含的元素个数叫做线性表的长度,用 n表示(n>=0)。当 n=0时,表示线性表是一个空表,即表中不包含任何数据元素。

20860
来自专栏mathor

线性表(一)

12320
来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

27480

扫码关注云+社区

领取腾讯云代金券