文档章节

【38】java的集合框架(容器框架)

fengsehng
 fengsehng
发布于 2016/11/09 09:15
字数 4410
阅读 3
收藏 0

Collection接口

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个 Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。
 

Collection vs Collections:

首先,Collection 和 Collections 是两个不同的概念。之所以放在一起,是为了更好的比较。Collection是容器层次结构中根接口。而Collections是一个提供一些处理容器类静态方法的类。

所有容器的实现类(如ArrayList实现了List接口,HashSet实现了Set接口)提供了两个‘标准’的构造函数来实现:1、一个无参的构造方法(void)2、一个带有Collection类型单参数构造方法,用于创建一个具有其参数相同元素新的Collection及其实现类等。实际上:因为所有通用的容器类遵从Collection接口,用第二种构造方法是允许容器之间相互的复制。
这里写图片描述

Collection的类层次结构

这里写图片描述

set介绍

一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合。Set不包含满足 a.equals(b) 的元素对a和b,并且最多有一个null。实现Set的接口有:EnumSet、HashSet、TreeSet等。

HashSet,TreeSet 和 LinkedHashSet比较

一个不包括重复元素(包括可变对象)的Collection,是一种无序的集合。Set不包含满 a.equals(b) 的元素对a和b,并且最多有一个null。
泥瓦匠的记忆宫殿:
1、不允许包含相同元素

2、判断对象是否相同,根据equals方法

HashSet

一个按着Hash算法来存储集合中的元素,其元素值可以是NULL。它不能保证元素的排列顺序。同样,HashSet是不同步的,如果需要多线程访问它的话,可以用 Collections.synchronizedSet 方法来包装它:

Set s = Collections.synchronizedSet(new HashSet(...));

同上一节一样,用迭代器的时候,也要注意 并发修改异常ConcurrentModificationException。

要注意的地方是,HashSet集合判断两个元素相等不单单是equals方法,并且必须hashCode()方法返回值也要相等。

LinkedHashSet

HashSet的子类,也同样有HashCode值来决定元素位置。但是它使用链表维护元素的次序。记住两个字:有序。

有序的妙用,复制。比如泥瓦匠实现一个HashSet无序添加,然后复制一个一样次序的HashSet来。代码如下:

package com.sedion.bysocket.collection;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashListTest
{
    public static void main(String[] args)
    {
        /* 复制HashSet */
        Set h1 = new HashSet<String>();
        h1.add("List");
        h1.add("Queue");
        h1.add("Set");
        h1.add("Map");

        System.out.println("HashSet Elements:");
        System.out.print("\t" + h1 + "\n");

        Set h2 = copy(h1);
        System.out.println("HashSet Elements After Copy:");
        System.out.print("\t" + h2 + "\n");
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static Set copy(Set set)
    {
        Set setCopy = new LinkedHashSet(set);
        return setCopy;
    }

}

输出:

HashSet Elements:
    [Map, Queue, Set, List] HashSet Elements After Copy: [Map, Queue, Set, List] 

TreeSet

TreeSet使用树结构实现(红黑树),集合中的元素进行排序,但是添加、删除和包含的算法复杂度为O(log(n))。

总结:

HashSet:equlas hashcode

LinkedHashSet:链式结构

TreeSet:比较,Comparable接口,性能较差

List:

一个有序的Collection(也称序列),元素可以重复。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素。实现List的有:ArrayList、LinkedList、Vector、Stack等。

ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2,并且如果列表本身允许 null 元素的话,通常它们允许多个 null 元素。实现List的有:ArrayList、LinkedList、Vector、Stack等。值得一提的是,Vector在JDK1.1的时候就有了,而List在JDK1.2的时候出现,待会我们会聊到ArrayList和Vector的区别。

ArrayList vs. Vector

ArrayList是一个可调整大小的数组实现的序列。随着元素增加,其大小会动态的增加。此类在Iterator或ListIterator迭代中,调用容器自身的remove和add方法进行修改,会抛出ConcurrentModificationException并发修改异常。

注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须 保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:

 List list = Collections.synchronizedList(new ArrayList(...));

特别注意:

@SuppressWarnings({ “unchecked”, “rawtypes” })
public static void iteratorTest()
{
List a1 = new ArrayList<String>();

a1.add(“List01″);
a1.add(“List02″);
a1.add(“List04″);
a1.add(“List05″);

Iterator i1 = a1.iterator();
while (i1.hasNext())
{
Object obj = i1.next();
if (obj.equals(“List02″))
a1.add(“List03″);
}

System.out.print(“集合:\n\t”+a1+”\n”);
}

运行出错:
问题描述很清楚,在创建迭代器之后,除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException。

改为:

@SuppressWarnings({ "unchecked", "rawtypes" })
    public static void listIterator()
    {

        List a1 = new ArrayList<String>();

        a1.add("List01");
        a1.add("List");
        a1.add("List03");
        a1.add("List04");

        ListIterator l1 = a1.listIterator();
        while (l1.hasNext())
        {
            Object obj = l1.next();
            if (obj.equals("List"))
            {
                l1.remove();
                l1.add("List02");
            }
        }
        System.out.print("集合:\n\t"+a1+"\n");
    }

Vector非常类似ArrayList。早在JDK1.1的时候就出现了,以前没有所谓的List接口,现在此类被改进为实现List接口。但与新的Collection不同的是,Vector是同步的。Vector在像查询的性能上会比ArrayList开销大。
从方法上看几乎没差别,同样注意的是:此接口的功能与 Iterator 接口的功能是重复的。此外,Iterator 接口添加了一个可选的移除操作,并使用较短的方法名。新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。

LinkedList及其与ArrayList性能比

LinkedList与ArrayList一样实现List接口,LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作,并允许所有的元素包括null。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

LinkedList和ArrayList的方法时间复杂度总结如下图所示。
这里写图片描述

LinkedList介绍:

LinkedList相对ArrayList添加了更多的方法,这些方法也很好的为使用LinkedList实现队列、双向队列、栈等提供了很好的支持。

LinkedList底层使用双向链表实现,一个节点持有前一个节点的引用、需要保存的元素的引用和后一节点的引用。空的LinkedList中first和last都为null,只有一个元素(节点)的LinkedList中first->next==last、last.prev==first。

所有操作的底层就是对链表的操作,对链表实现了各种增删改查的方法,然后对外提供了更多操作行为,如队列的操作,栈的操作和普通List的操作,这些操作可能实际的实现是相同的,但是对外提供不同的接口以展示更多的行为。

LinkedList是一个很强大的工具。

虽然LinkedList提供了很多操作,诸如栈和队列的,但有时候我们任然希望一个功能更专一的栈或队列,下面就演示以代理模式通过LinkedList实现的栈和队列:
//LinkedList的使用
public class TestUse {
    public static void main(String[] args) {
        //栈
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=0;i<10;i++)
            stack.push(i);
        System.out.println(stack.peek());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        Iterator<Integer> iterator = stack.iterator();
        while(iterator.hasNext())
            System.out.print(iterator.next());
        System.out.println();
        //队列
        Queue<Integer> queue = new Queue<Integer>();
        for(int i=0;i<10;i++)
            queue.enqueue(i);
        System.out.println(queue.peek());
        System.out.println(queue.peek());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        iterator = queue.iterator();
        while(iterator.hasNext())
            System.out.print(iterator.next());
    }
}
//很使用使用代理模式利用LinkedList实现一个栈
class Stack<T> implements Iterable<T>{
    private LinkedList<T> stack = new LinkedList<T>();
    public T pop(){//出栈,会删除栈顶元素
        return stack.poll();
    }
    public T peek(){//出栈,但不删除栈顶元素
        return stack.peek();
    }
    public void push(T t){//入栈
        stack.push(t);
    }
    @Override
    public Iterator<T> iterator() {
        return stack.iterator();
    }
}
//很使用使用代理模式利用LinkedList实现一个队列
class Queue<T> implements Iterable<T>{
    private LinkedList<T> queue = new LinkedList<T>();
    public void enqueue(T t){
        queue.offer(t);
    }
    public T dequeue(){
        return queue.poll();
    }
    public T peek(){
        return queue.peek();
    }
    @Override
    public Iterator<T> iterator() {
        return queue.iterator();
    }
}

关于List的总结:

首先LinkedList是双向链表,ArrayList和vertor是数组
Vector和ArrayList

1、vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。

2、记住并发修改异常 java.util.ConcurrentModificationException ,优先考虑ArrayList,除非你在使用多线程所需。

Aarraylist和Linkedlist
1、对于随机访问get和set,ArrayList觉得优于LinkedList,LinkedList要移动指针。
2、于新增和删除操作add和remove,LinedList比较占优势,ArrayList要移动数据。
3、
单条数据插入或删除,ArrayList的速度反而优于LinkedList.原因是:LinkedList的数据结构是三个对象,组大小恰当就会比链表快,直接赋值就完了,不用再设置前后指针的值。
若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

Queue:

一种队列则是双端队列,支持在头、尾两端插入和移除元素,主要包括:ArrayDeque、LinkedBlockingDeque、LinkedList。另一种是阻塞式队列,队列满了以后再插入元素则会抛出异常,主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。虽然接口并未定义阻塞方法,但是实现类扩展了此接口。

Map:

这里写图片描述
Map:

是一个键值对的集合。也就是说,一个映射不能包含重复的键,每个键最多映射到一个值。该接口取代了Dictionary抽象类。实现map的有:HashMap、TreeMap、HashTable、Properties、EnumMap。

HashMap 和 TreeMap

Map,又称映射表,是将键映射到值的对象。有四种实现Map接口并且经常使用的Map集合为:HashMap,TreeMap,Hashtable 和 LinkedHashMap.

1、一个映射不包含重复的键。

2、每个键最多只能映射到一个值。

HashMap

HashMap是基于哈希表的Map接口的实现。其对键进行散列,散列函数只能作用于键。
HaspMap的键必须唯一,同样其同一个键不能存放两个值,如果对同一个键两次调用put方法,第二个值会取代第一个值。同样是允许使用 null 值和 null 键。
下面有三点是HashMap重要之处:

1、HashMap的构造函数

HaspMap构造函数涉及两个参数:初始容量和加载因子。初试容量是哈希表创建时的其中桶的含量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。这两个参数都是影响HashMap的性能。默认构造一个具有默认初始容量 (16) 和默认加载因子 (0.75)。默认加载因子 (.75) 在时间和空间成本上是一种折衷的考虑。

2、和上次总结的Set都差不多,这个HashMap线程是不安全不同步的。如果想防止意外发生,则设置成同步即可:

Map m = Collections.synchronizedMap(new HashMap(...));

3、不同步的话,意味着存在快速失败导致的并发修改异常。

TreeMap

reeMap使用树结构实现(红黑树),集合中的元素进行排序,但是添加、删除和包含的算法复杂度为O(log(n))。

1、TreeMap实现了SortedMap,顾名思义,其表示为有排序的集合。

2、同样其同一个键不能存放两个值,如果对同一个键两次调用put方法,第二个值会取代第一个值。

总结:

1.  HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。集合框架”提供两种常规的Map实现:HashMap和TreeMap (TreeMap实现SortedMap接口)。
2.  2.在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项,因为该树总处于平衡状态。

接口总结:

这里写图片描述

总结:

Vector和ArrayList

1,vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用arraylist效率比较高。
2,如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据,用vector有一定的优势。
3,如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度,这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。

ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!

Aarraylist和Linkedlist

1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。

HashMap与TreeMap

1、HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。HashMap中元素的排列顺序是不固定的)。

2、 HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。集合框架”提供两种常规的Map实现:HashMap和TreeMap (TreeMap实现SortedMap接口)。

3、在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项,因为该树总处于平衡状态。

hashtable与hashmap

1、历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 。

2、同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 。

3、值:只有HashMap可以让你将空值作为一个表的条目的key或value 。
参考博客:
主要参考泥瓦匠的博客还有其他的两篇博客,链接如下:
http://www.bysocket.com/?p=424
http://anxpp.com/index.php/archives/656/
http://blog.csdn.net/softwave/article/details/4166598

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin
05/25
0
0
Spring面试题(70道,史上最全)

1.什么是spring? 2.使用Spring框架的好处是什么? 3.Spring由哪些模块组成? 4.核心容器(应用上下文)模块。 5.BeanFactory–BeanFactory实现举例。 6.XMLBeanFactory 7.解释AOP模块 8.解释J...

java技术栈
2017/11/08
0
0
【JAVA集合框架二 】java集合框架容器 java框架层级 继承图结构 集合框架的抽象类 集合框架主要实现类

本文关键词: java集合框架 框架设计理念 容器 继承层级结构 继承图 集合框架中的抽象类 主要的实现类 实现类特性 集合框架分类 集合框架并发包 并发实现类 什么是容器? 由一个或多个确定的元...

noteless
07/09
0
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
08/08
0
0
8个超实用的Java测试工具和框架

Java入门 如果你才刚开始接触Java世界,那么要做的第一件事情是,安装JDK——Java Development Kit(Java开发工具包),它自带有Java Runtime Environment(JRE)和JVM(Java运行时环境)。它...

拉偶有所依
2015/06/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
32分钟前
0
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
5
2
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
1
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
1
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部