集合_集合面试题 - CSDN
集合 订阅
集合,简称集,是数学中一个基本概念,也是集合论的主要研究对象。集合论的基本理论创立于19世纪,关于集合的最简单的说法就是在朴素集合论(最原始的集合论)中的定义,即集合是“确定的一堆东西”,集合里的“东西”则称为元素。现代的集合一般被定义为:由一个或多个确定的元素所构成的整体 [1]  。 展开全文
集合,简称集,是数学中一个基本概念,也是集合论的主要研究对象。集合论的基本理论创立于19世纪,关于集合的最简单的说法就是在朴素集合论(最原始的集合论)中的定义,即集合是“确定的一堆东西”,集合里的“东西”则称为元素。现代的集合一般被定义为:由一个或多个确定的元素所构成的整体 [1]  。
信息
提出者
康托尔
简    称
定    义
一个或多个确定元素所构成的整体
中文名
集合
创立时间
19世纪
外文名
aggregate
集合定义
集合是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。其中,构成集合的这些对象则称为该集合的元素 [1-2]  [3]  。例如,全中国人的集合,它的元素就是每一个中国人。通常用大写字母如A,B,S,T,...表示集合,而用小写字母如a,b,x,y,...表示集合的元素。若x是集合S的元素,则称x属于S,记为x∈S。若y不是集合S的元素,则称y不属于S,记为y∉S [2]  。集合中元素的数目称为集合的基数,集合A的基数记作card(A)。当其为有限大时,集合A称为有限集,反之则为无限集 [4]  。一般的,把含有有限个元素的集合叫做有限集,含无限个元素的集合叫做无限集 [4]  。假设有实数x < y:①[x,y] :方括号表示包括边界,即表示x到y之间的数以及x和y;②(x,y):小括号是不包括边界,即表示大于x、小于y的数 [4]  。
收起全文
精华内容
参与话题
  • Java集合框架精讲

    千人学习 2019-05-17 09:44:51
    该课程内容包括:Collection集合的继承体系、Map集合集合体系、部分数据结构知识点、List、Set、ArrayList、Vector、LinkedList、Iterator(迭代器)、TreeSet、HashSet、LinkedHashSet、TreeSet、Map、TreeMap、...
  • java集合超详解

    万次阅读 多人点赞 2018-08-03 21:28:15
    一、集合大纲 1.集合和数组的区别: 2.Collection集合的方法: 3.常用集合的分类: Collection 接口的接口 对象的集合(单列集合) ├——-List 接口:元素按进入先后有序保存,可重复 │——...

    一、集合大纲

    常用集合大纲
    这里写图片描述
    Collection集合大纲

    1.集合和数组的区别:

    这里写图片描述

    2.Collection集合的方法:

    这里写图片描述

    3.常用集合的分类:

    Collection 接口的接口 对象的集合(单列集合)
    ├——-List 接口:元素按进入先后有序保存,可重复
    │—————-├ LinkedList 接口实现类, 链表, 插入删除, 没有同步, 线程不安全
    │—————-├ ArrayList 接口实现类, 数组, 随机访问, 没有同步, 线程不安全
    │—————-└ Vector 接口实现类 数组, 同步, 线程安全
    │ ———————-└ Stack 是Vector类的实现类
    └——-Set 接口: 仅接收一次,不可重复,并做内部排序
    ├—————-└HashSet 使用hash表(数组)存储元素
    │————————└ LinkedHashSet 链表维护元素的插入次序
    └ —————-TreeSet 底层实现为二叉树,元素排好序

    Map 接口 键值对的集合 (双列集合)
    ├———Hashtable 接口实现类, 同步, 线程安全
    ├———HashMap 接口实现类 ,没有同步, 线程不安全-
    │—————–├ LinkedHashMap 双向链表和哈希表实现
    │—————–└ WeakHashMap
    ├ ——–TreeMap 红黑树对所有的key进行排序
    └———IdentifyHashMap

    二、List和Set集合详解:

    1.list和set的区别:

    这里写图片描述

    2.List:

    (1)ArrayList:底层数据结构是数组,查询快,增删慢,线程不安全,效率高,可以存储重复元素
    (2)LinkedList 底层数据结构是链表,查询慢,增删快,线程不安全,效率高,可以存储重复元素
    (3)Vector:底层数据结构是数组,查询快,增删慢,线程安全,效率低,可以存储重复元素
    这里写图片描述
    (4小结:

    3.Set:

    (1)HashSet底层数据结构采用哈希表实现,元素无序且唯一,线程不安全,效率高,可以存储null元素,元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的,如果没有重写这两个方法,则无法保证元素的唯一性。
    具体实现唯一性的比较过程:存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值,然后已经的所存储的元素的hashCode值比较,如果hashCode不相等,则所存储的两个对象一定不相等,此时存储当前的新的hashCode值处的元素对象;如果hashCode相等,存储元素的对象还是不一定相等,此时会调用equals()方法判断两个对象的内容是否相等,如果内容相等,那么就是同一个对象,无需存储;如果比较的内容不相等,那么就是不同的对象,就该存储了,此时就要采用哈希的解决地址冲突算法,在当前hashCode值处类似一个新的链表, 在同一个hashCode值的后面存储存储不同的对象,这样就保证了元素的唯一性。
    Set的实现类的集合对象中不能够有重复元素,HashSet也一样他是使用了一种标识来确定元素的不重复,HashSet用一种算法来保证HashSet中的元素是不重复的, HashSet采用哈希算法,底层用数组存储数据。默认初始化容量16,加载因子0.75。
    Object类中的hashCode()的方法是所有子类都会继承这个方法,这个方法会用Hash算法算出一个Hash(哈希)码值返回,HashSet会用Hash码值去和数组长度取模, 模(这个模就是对象要存放在数组中的位置)相同时才会判断数组中的元素和要加入的对象的内容是否相同,如果不同才会添加进去。
    Hash算法是一种散列算法。
    Set hs=new HashSet();

    hs.add(o);
    |
    o.hashCode();
    |
    o%当前总容量 (0–15)
    |
    | 不发生冲突
    是否发生冲突—————–直接存放
    |
    | 发生冲突
    | 假(不相等)
    o1.equals(o2)——————-找一个空位添加
    |
    | 是(相等)
    不添加
    覆盖hashCode()方法的原则:
    1、一定要让那些我们认为相同的对象返回相同的hashCode值
    2、尽量让那些我们认为不同的对象返回不同的hashCode值,否则,就会增加冲突的概率。
    3、尽量的让hashCode值散列开(两值用异或运算可使结果的范围更广)
    HashSet 的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成,我们应该为保存到HashSet中的对象覆盖hashCode()和equals(),因为再将对象加入到HashSet中时,会首先调用hashCode方法计算出对象的hash值,接着根据此hash值调用HashMap中的hash方法,得到的值& (length-1)得到该对象在hashMap的transient Entry[] table中的保存位置的索引,接着找到数组中该索引位置保存的对象,并调用equals方法比较这两个对象是否相等,如果相等则不添加,注意:所以要存入HashSet的集合对象中的自定义类必须覆盖hashCode(),equals()两个方法,才能保证集合中元素不重复。在覆盖equals()和hashCode()方法时, 要使相同对象的hashCode()方法返回相同值,覆盖equals()方法再判断其内容。为了保证效率,所以在覆盖hashCode()方法时, 也要尽量使不同对象尽量返回不同的Hash码值。

    如果数组中的元素和要加入的对象的hashCode()返回了相同的Hash值(相同对象),才会用equals()方法来判断两个对象的内容是否相同。

    (2)LinkedHashSet底层数据结构采用链表和哈希表共同实现,链表保证了元素的顺序与存储顺序一致,哈希表保证了元素的唯一性。线程不安全,效率高。
    (3)TreeSet底层数据结构采用二叉树来实现,元素唯一且已经排好序;唯一性同样需要重写hashCode和equals()方法,二叉树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储;比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;
    (4)小结:Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只 是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set不保存重复的元素。
    Set 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

    4.List和Set总结:

    (1)、List,Set都是继承自Collection接口,Map则不是
    (2)、List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉,(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set 的Object必须定义equals()方法 ,另外list支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。)
    (3).Set和List对比:
    Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
    List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。
    (4)、ArrayList与LinkedList的区别和适用场景
    Arraylist:
    优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
    缺点:因为地址连续, ArrayList要移动数据,所以插入和删除操作效率比较低。

    LinkedList:
    优点:LinkedList基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址,对于新增和删除操作add和remove,LinedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景
    缺点:因为LinkedList要移动指针,所以查询操作性能比较低。
    适用场景分析
    当需要对数据进行对此访问的情况下选用ArrayList,当需要对数据进行多次增加删除修改时采用LinkedList。

    ArrayList与Vector的区别和适用场景
    ArrayList有三个构造方法:

    public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。    
    public ArrayList()      //默认构造一个初始容量为10的空列表。    
    public ArrayList(Collection<? extends E> c)//构造一个包含指定 collection 的元素的列表

    Vector有四个构造方法:

    public Vector()//使用指定的初始容量和等于0的容量增量构造一个空向量。    
    public Vector(int initialCapacity)//构造一个空向量,使其内部数据数组的大小,其标准容量增量为零。    
    public Vector(Collection<? extends E> c)//构造一个包含指定 collection 中的元素的向量    
    public Vector(int initialCapacity,int capacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量    

    ArrayList和Vector都是用数组实现的,主要有这么三个区别:
    (1).Vector是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果。而ArrayList不是,这个可以从源码中看出,Vector类中的方法很多有synchronized进行修饰,这样就导致了Vector在效率上无法与ArrayList相比;
    (2)两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。
    *(3)*Vector可以设置增长因子,而ArrayList不可以。
    *(4)*Vector是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。
    适用场景分析
    1.Vector是线程同步的,所以它也是线程安全的,而ArrayList是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用ArrayList效率比较高。
    2.如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用Vector有一定的优势。

    .TreeSet 是二差树(红黑树的树据结构)实现的,Treeset中的数据是自动排好序的,不允许放入null值
    2.HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,就如数据库中唯一约束
    3.HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

    适用场景分析:HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。
    (5)何时使用:
    这里写图片描述

    三、Map详解:

    Map用于保存具有映射关系的数据,Map里保存着两组数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value。

    (1)、请注意!!!, Map 没有继承 Collection 接口, Map 提供 key 到 value 的映射,你可以通过“键”查找“值”。一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图, Map 的内容可以被当作一组 key 集合,一组 value 集合,或者一组 key-value 映射。
    (2)Map:
    这里写图片描述
    (3)HashMap和HashTable的比较:
    这里写图片描述
    (4)TreeMap:
    这里写图片描述
    (5)Map的其它类:
    IdentityHashMapHashMap的具体区别,IdentityHashMap使用 == 判断两个key是否相等,而HashMap使用的是equals方法比较key值。有什么区别呢?
    对于==,如果作用于基本数据类型的变量,则直接比较其存储的 “值”是否相等; 如果作用于引用类型的变量,则比较的是所指向的对象的地址。
    对于equals方法,注意:equals方法不能作用于基本数据类型的变量
    如果没有对equals方法进行重写,则比较的是引用类型的变量所指向的对象的地址;
    诸如String、Date等类对equals方法进行了重写的话,比较的是所指向的对象的内容。
    这里写图片描述
    (6)小结:
    HashMap 非线程安全
    HashMap:基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()],为了优化HashMap空间的使用,您可以调优初始容量和负载因子。

    TreeMap:非线程安全基于红黑树实现。TreeMap没有调优选项,因为该树总处于平衡状态。

    适用场景分析:
    HashMap和HashTable:HashMap去掉了HashTable的contains方法,但是加上了containsValue()和containsKey()方法。HashTable同步的,而HashMap是非同步的,效率上比HashTable要高。HashMap允许空键值,而HashTable不允许。

    HashMap:适用于Map中插入、删除和定位元素。
    Treemap:适用于按自然顺序或自定义顺序遍历键(key)。

    5.线程安全集合类与非线程安全集合类
    LinkedList、ArrayList、HashSet是非线程安全的,Vector是线程安全的;
    HashMap是非线程安全的,HashTable是线程安全的;
    StringBuilder是非线程安全的,StringBuffer是线程安全的。

    数据结构
    ArrayXxx:底层数据结构是数组,查询快,增删慢
    LinkedXxx:底层数据结构是链表,查询慢,增删快
    HashXxx:底层数据结构是哈希表。依赖两个方法:hashCode()和equals()
    TreeXxx:底层数据结构是二叉树。两种方式排序:自然排序和比较器排序

    各种集合对比
    List和Set对比总结

    展开全文
  • Java集合容器面试题(2020最新版)

    万次阅读 多人点赞 2020-05-06 14:11:36
    文章目录集合容器概述什么是集合集合的特点集合和数组的区别使用集合框架的好处常用的集合类有哪些?List,Set,Map三者的区别?List、Set、Map 是否继承自 Collection 接口?List、Map、Set 三个接口存取元素时,各...

    文章目录

    Java面试总结汇总,整理了包括Java基础知识,集合容器,并发编程,JVM,常用开源框架Spring,MyBatis,数据库,中间件等,包含了作为一个Java工程师在面试中需要用到或者可能用到的绝大部分知识。欢迎大家阅读,本人见识有限,写的博客难免有错误或者疏忽的地方,还望各位大佬指点,在此表示感激不尽。文章持续更新中…

    序号 内容 链接地址
    1 Java基础知识面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104390612
    2 Java集合容器面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104588551
    3 Java异常面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104390689
    4 并发编程面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104863992
    5 JVM面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104390752
    6 Spring面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397516
    7 Spring MVC面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397427
    8 Spring Boot面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397299
    9 Spring Cloud面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397367
    10 MyBatis面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/101292950
    11 Redis面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/103522351
    12 MySQL数据库面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104778621
    13 消息中间件MQ与RabbitMQ面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104588612
    14 Dubbo面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104390006
    15 Linux面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104588679
    16 Tomcat面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397665
    17 ZooKeeper面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104397719
    18 Netty面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/104391081
    19 架构设计&分布式&数据结构与算法面试题(2020最新版) https://thinkwon.blog.csdn.net/article/details/105870730

    集合容器概述

    什么是集合

    集合框架:用于存储数据的容器。

    集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。
    任何集合框架都包含三大块内容:对外的接口、接口的实现和对集合运算的算法。

    接口:表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现,从而达到“多态”。在面向对象编程语言中,接口通常用来形成规范。

    实现:集合接口的具体实现,是重用性很高的数据结构。

    算法:在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法,例如查找、排序等。这些算法通常是多态的,因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上,算法是可复用的函数。
    它减少了程序设计的辛劳。

    集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上,而不是为了让程序能正常运转而将注意力于低层设计上。
    通过这些在无关API之间的简易的互用性,使你免除了为改编对象或转换代码以便联合这些API而去写大量的代码。 它提高了程序速度和质量。

    集合的特点

    集合的特点主要有如下两点:

    • 对象封装数据,对象多了也需要存储。集合用于存储对象。

    • 对象的个数确定可以使用数组,对象的个数不确定的可以用集合。因为集合是可变长度的。

    集合和数组的区别

    • 数组是固定长度的;集合可变长度的。

    • 数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型。

    • 数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。

    数据结构:就是容器中存储数据的方式。

    对于集合容器,有很多种。因为每一个容器的自身特点不同,其实原理在于每个容器的内部数据结构不同。

    集合容器在不断向上抽取过程中,出现了集合体系。在使用一个体系的原则:参阅顶层内容。建立底层对象。

    使用集合框架的好处

    1. 容量自增长;
    2. 提供了高性能的数据结构和算法,使编码更轻松,提高了程序速度和质量;
    3. 允许不同 API 之间的互操作,API之间可以来回传递集合;
    4. 可以方便地扩展或改写集合,提高代码复用性和可操作性。
    5. 通过使用JDK自带的集合类,可以降低代码维护和学习新API成本。

    常用的集合类有哪些?

    Map接口和Collection接口是所有集合框架的父接口:

    1. Collection接口的子接口包括:Set接口和List接口
    2. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
    3. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等
    4. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

    List,Set,Map三者的区别?List、Set、Map 是否继承自 Collection 接口?List、Map、Set 三个接口存取元素时,各有什么特点?

    img

    Java 容器分为 Collection 和 Map 两大类,Collection集合的子接口有Set、List、Queue三种子接口。我们比较常用的是Set、List,Map接口不是collection的子接口。

    Collection集合主要有List和Set两大接口

    • List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
    • Set:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

    Map是一个键值对集合,存储键、值和之间的映射。 Key无序,唯一;value 不要求有序,允许重复。Map没有继承于Collection接口,从Map集合中检索元素时,只要给出键对象,就会返回对应的值对象。

    Map 的常用实现类:HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

    集合框架底层数据结构

    Collection

    1. List
    • Arraylist: Object数组
    • Vector: Object数组
    • LinkedList: 双向循环链表
    1. Set
    • HashSet(无序,唯一):基于 HashMap 实现的,底层采用 HashMap 来保存元素
    • LinkedHashSet: LinkedHashSet 继承与 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样,不过还是有一点点区别的。
    • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。)

    Map

    • HashMap: JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间
    • LinkedHashMap:LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。
    • HashTable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
    • TreeMap: 红黑树(自平衡的排序二叉树)

    哪些集合类是线程安全的?

    • vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。
    • statck:堆栈类,先进后出。
    • hashtable:就比hashmap多了个线程安全。
    • enumeration:枚举,相当于迭代器。

    Java集合的快速失败机制 “fail-fast”?

    是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。

    例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。

    原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

    解决办法:

    1. 在遍历过程中,所有涉及到改变modCount值得地方全部加上synchronized。

    2. 使用CopyOnWriteArrayList来替换ArrayList

    怎么确保一个集合不能被修改?

    可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合,这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

    示例代码如下:

    List<String> list = new ArrayList<>();
    list. add("x");
    Collection<String> clist = Collections. unmodifiableCollection(list);
    clist. add("y"); // 运行时此行报错
    System. out. println(list. size());
    

    Collection接口

    List接口

    迭代器 Iterator 是什么?

    Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration,迭代器允许调用者在迭代过程中移除元素。

    Iterator 怎么使用?有什么特点?

    Iterator 使用代码如下:

    List<String> list = new ArrayList<>();
    Iterator<String> it = list. iterator();
    while(it. hasNext()){
      String obj = it. next();
      System. out. println(obj);
    }
    

    Iterator 的特点是只能单向遍历,但是更加安全,因为它可以确保,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常。

    如何边遍历边移除 Collection 中的元素?

    边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法,如下:

    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
       *// do something*
       it.remove();
    }
    

    一种最常见的错误代码如下:

    for(Integer i : list){
       list.remove(i)
    }
    

    运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时,会自动生成一个iterator 来遍历该 list,但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

    Iterator 和 ListIterator 有什么区别?

    • Iterator 可以遍历 Set 和 List 集合,而 ListIterator 只能遍历 List。
    • Iterator 只能单向遍历,而 ListIterator 可以双向遍历(向前/后遍历)。
    • ListIterator 实现 Iterator 接口,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

    遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么?

    遍历方式有以下几种:

    1. for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。

    2. 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。

    3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。

    最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。

    • 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。
    • 如果没有实现该接口,表示不支持 Random Access,如LinkedList。

    推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。

    说一下 ArrayList 的优缺点

    ArrayList的优点如下:

    • ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。
    • ArrayList 在顺序添加一个元素的时候非常方便。

    ArrayList 的缺点如下:

    • 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。
    • 插入元素的时候,也需要做一次元素复制操作,缺点同上。

    ArrayList 比较适合顺序添加、随机访问的场景。

    如何实现数组和 List 之间的转换?

    • 数组转 List:使用 Arrays. asList(array) 进行转换。
    • List 转数组:使用 List 自带的 toArray() 方法。

    代码示例:

    // list to array
    List<String> list = new ArrayList<String>();
    list.add("123");
    list.add("456");
    list.toArray();
    
    // array to list
    String[] array = new String[]{"123","456"};
    Arrays.asList(array);
    

    ArrayList 和 LinkedList 的区别是什么?

    • 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。
    • 随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。
    • 增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。
    • 内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
    • 线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;

    综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。

    补充:数据结构基础之双向链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

    ArrayList 和 Vector 的区别是什么?

    这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合

    • 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。
    • 性能:ArrayList 在性能方面要优于 Vector。
    • 扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。

    Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

    Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。

    插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性?

    ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。

    Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差

    LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快

    多线程场景下如何使用 ArrayList?

    ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样:

    List<String> synchronizedList = Collections.synchronizedList(list);
    synchronizedList.add("aaa");
    synchronizedList.add("bbb");
    
    for (int i = 0; i < synchronizedList.size(); i++) {
        System.out.println(synchronizedList.get(i));
    }
    

    为什么 ArrayList 的 elementData 加上 transient 修饰?

    ArrayList 中的数组定义如下:

    private transient Object[] elementData;
    

    再看一下 ArrayList 的定义:

    public class ArrayList<E> extends AbstractList<E>
         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    

    可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现:

    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
        *// Write out element count, and any hidden stuff*
            int expectedModCount = modCount;
        s.defaultWriteObject();
        *// Write out array length*
            s.writeInt(elementData.length);
        *// Write out all elements in the proper order.*
            for (int i=0; i<size; i++)
                s.writeObject(elementData[i]);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
    }
    

    每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。

    List 和 Set 的区别

    List , Set 都是继承自Collection 接口

    List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

    Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

    另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。

    Set和List对比

    Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
    List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变

    Set接口

    说一下 HashSet 的实现原理?

    HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。

    HashSet如何检查重复?HashSet是如何保证数据不可重复的?

    向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。
    HashSet 中的add ()方法会使用HashMap 的put()方法。

    HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。

    以下是HashSet 部分源码:

    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        // 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
    	return map.put(e, PRESENT)==null;
    }
    

    hashCode()与equals()的相关规定

    1. 如果两个对象相等,则hashcode一定也是相同的
    2. 两个对象相等,对两个equals方法返回true
    3. 两个对象有相同的hashcode值,它们也不一定是相等的
    4. 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
    5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

    ==与equals的区别

    1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
    2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同

    HashSet与HashMap的区别

    HashMap HashSet
    实现了Map接口 实现Set接口
    存储键值对 仅存储对象
    调用put()向map中添加元素 调用add()方法向Set中添加元素
    HashMap使用键(Key)计算Hashcode HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
    HashMap相对于HashSet较快,因为它是使用唯一的键获取对象 HashSet较HashMap来说比较慢

    Queue

    BlockingQueue是什么?

    Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

    在 Queue 中 poll()和 remove()有什么区别?

    • 相同点:都是返回第一个元素,并在队列中删除返回的对象。
    • 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。

    代码示例:

    Queue<String> queue = new LinkedList<String>();
    queue. offer("string"); // add
    System. out. println(queue. poll());
    System. out. println(queue. remove());
    System. out. println(queue. size());
    

    Map接口

    说一下 HashMap 的实现原理?

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

    HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

    HashMap 基于 Hash 算法实现的

    1. 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
    2. 存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中
    3. 获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。
    4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。

    需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

    HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现

    在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。

    JDK1.8之前

    JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

    jdk1.7中HashMap数据结构

    JDK1.8之后

    相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。

    jdk1.8中HashMap数据结构

    JDK1.7 VS JDK1.8 比较

    JDK1.8主要解决或优化了一下问题:

    1. resize 扩容优化
    2. 引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考
    3. 解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。
    不同 JDK 1.7 JDK 1.8
    存储结构 数组 + 链表 数组 + 链表 + 红黑树
    初始化方式 单独函数:inflateTable() 直接集成到了扩容函数resize()
    hash值计算方式 扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算 扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算
    存放数据的规则 无冲突时,存放数组;冲突时,存放链表 无冲突时,存放数组;冲突 & 链表长度 < 8:存放单链表;冲突 & 链表长度 > 8:树化并存放红黑树
    插入数据方式 头插法(先讲原位置的数据移到后1位,再插入数据到该位置) 尾插法(直接插入到链表尾部/红黑树)
    扩容后存储位置的计算方式 全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1)) 按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量)

    HashMap的put方法的具体流程?

    当我们put的时候,首先计算 keyhash值,这里调用了 hash方法,hash方法实际是让key.hashCode()key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。

    putVal方法执行流程图

    putVal方法执行流程图

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    //实现Map.put和相关方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 步骤①:tab为空则创建 
        // table未初始化或者长度为0,进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步骤②:计算index,并对null做处理  
        // (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 桶中已经存在元素
        else {
            Node<K,V> e; K k;
            // 步骤③:节点key存在,直接覆盖value 
            // 比较桶中第一个元素(数组中的结点)的hash值相等,key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                    // 将第一个元素赋值给e,用e来记录
                    e = p;
            // 步骤④:判断该链为红黑树 
            // hash值不相等,即key不相等;为红黑树结点
            // 如果当前元素类型为TreeNode,表示为红黑树,putTreeVal返回待存放的node, e可能为null
            else if (p instanceof TreeNode)
                // 放入树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 步骤⑤:该链为链表 
            // 为链表结点
            else {
                // 在链表最末插入结点
                for (int binCount = 0; ; ++binCount) {
                    // 到达链表的尾部
                    
                    //判断该链表尾部指针是不是空的
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        //判断链表的长度是否达到转化红黑树的临界值,临界值为8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //链表结构转树形结构
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等,跳出循环
                        break;
                    // 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表
                    p = e;
                }
            }
            //判断当前的key已经存在的情况下,再来一个相同的hash值、key值时,返回新来的value这个值
            if (e != null) { 
                // 记录e的value
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值替换旧值
                    e.value = value;
                // 访问后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 结构性修改
        ++modCount;
        // 步骤⑥:超过最大容量就扩容 
        // 实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    }
    

    ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

    ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

    ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

    ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

    ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

    ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

    HashMap的扩容操作是怎么实现的?

    ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容;

    ②.每次扩展的时候,都是扩展2倍;

    ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。

    在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {//如果oldCap不为空的话,就是hash桶数组不为空
            if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了,就赋值为整数最大的阀值
                threshold = Integer.MAX_VALUE;
                return oldTab;//返回
            }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
        }
        // 旧的容量为0,但threshold大于零,代表有参构造有cap传入,threshold已经被初始化成最小2的n次幂
        // 直接将该值赋给新的容量
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 无参构造创建的map,给出默认容量和threshold 16, 16*0.75
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 新的threshold = 新的cap * 0.75
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        // 计算出新的数组长度后赋给当前成员变量table
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
        table = newTab;//将新数组的值复制给旧的hash桶数组
        // 如果原先的数组没有初始化,那么resize的初始化工作到此结束,否则进入扩容元素重排逻辑,使其均匀的分散
        if (oldTab != null) {
            // 遍历新数组的所有桶下标
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 旧数组的桶下标赋给临时变量e,并且解除旧数组中的引用,否则就数组无法被GC回收
                    oldTab[j] = null;
                    // 如果e.next==null,代表桶中就一个元素,不存在链表或者红黑树
                    if (e.next == null)
                        // 用同样的hash映射算法把该元素加入新的数组
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果e是TreeNode并且e.next!=null,那么处理树中元素的重排
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // e是链表的头并且e.next!=null,那么处理链表中元素重排
                    else { // preserve order
                        // loHead,loTail 代表扩容后不用变换下标,见注1
                        Node<K,V> loHead = null, loTail = null;
                        // hiHead,hiTail 代表扩容后变换下标,见注1
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 遍历链表
                        do {             
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    // 初始化head指向链表当前元素e,e不一定是链表的第一个元素,初始化后loHead
                                    // 代表下标保持不变的链表的头元素
                                    loHead = e;
                                else                                
                                    // loTail.next指向当前e
                                    loTail.next = e;
                                // loTail指向当前的元素e
                                // 初始化后,loTail和loHead指向相同的内存,所以当loTail.next指向下一个元素时,
                                // 底层数组中的元素的next引用也相应发生变化,造成lowHead.next.next.....
                                // 跟随loTail同步,使得lowHead可以链接到所有属于该链表的元素。
                                loTail = e;                           
                            }
                            else {
                                if (hiTail == null)
                                    // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 遍历结束, 将tail指向null,并把链表头放入新数组的相应下标,形成新的映射。
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    

    HashMap是怎么解决哈希冲突的?

    答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行;

    什么是哈希?

    Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

    所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。

    什么是哈希冲突?

    当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)

    HashMap的数据结构

    在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突:

    img

    这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化

    hash()函数

    上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或)
    }
    

    这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动)

    JDK1.8新增红黑树

    img

    通过上面的链地址法(使用散列表)扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn);

    总结

    简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的:

    1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据;
    2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;
    3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;

    能否使用任何类作为 Map 的 key?

    可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点:

    • 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。

    • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

    • 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。

    • 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。

    为什么HashMap中String、Integer这样的包装类适合作为K?

    答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率

    1. 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况
    2. 内部已重写了equals()hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况;

    如果使用Object作为HashMap的Key,应该怎么办呢?

    答:重写hashCode()equals()方法

    1. 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞;
    2. 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性

    HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?

    答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;

    那怎么解决呢?

    1. HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均;
    2. 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题;

    HashMap 的长度为什么是2的幂次方

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

    这个算法应该如何设计呢?

    我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。

    那为什么是两次扰动呢?

    答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;

    HashMap 与 HashTable 有什么区别?

    1. 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
    2. 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
    3. 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。
    4. **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
    5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
    6. 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。

    如何决定使用 HashMap 还是 TreeMap?

    对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。

    HashMap 和 ConcurrentHashMap 的区别

    1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。)
    2. HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。

    ConcurrentHashMap 和 Hashtable 的区别?

    ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

    • 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
    • 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

    两者的对比图

    HashTable:

    img

    JDK1.7的ConcurrentHashMap:

    img

    JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点):

    img

    答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

    ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?

    JDK1.7

    首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

    在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下:

    一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。

    img

    1. 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;
    2. Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。

    JDK1.8

    JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。

    结构如下:

    img

    附加源码,有需要的可以看看

    插入元素过程(建议去看看源码):

    如果相应位置的Node还没有初始化,则调用CAS插入相应的数据;

    else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
            break;                   // no lock when adding to empty bin
    }
    

    如果相应位置的Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁,如果该节点的hash不小于0,则遍历链表更新节点或插入新节点;

    if (fh >= 0) {
        binCount = 1;
        for (Node<K,V> e = f;; ++binCount) {
            K ek;
            if (e.hash == hash &&
                ((ek = e.key) == key ||
                 (ek != null && key.equals(ek)))) {
                oldVal = e.val;
                if (!onlyIfAbsent)
                    e.val = value;
                break;
            }
            Node<K,V> pred = e;
            if ((e = e.next) == null) {
                pred.next = new Node<K,V>(hash, key, value, null);
                break;
            }
        }
    }
    
    1. 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;
    2. 如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount;

    辅助工具类

    Array 和 ArrayList 有何区别?

    • Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。
    • Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。
    • Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。

    对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。

    如何实现 Array 和 List 之间的转换?

    • Array 转 List: Arrays. asList(array) ;
    • List 转 Array:List 的 toArray() 方法。

    comparable 和 comparator的区别?

    • comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序
    • comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序

    一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort().

    Collection 和 Collections 有什么区别?

    • java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式,其直接继承接口有List与Set。
    • Collections则是集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。

    TreeMap 和 TreeSet 在排序时如何比较元素?Collections 工具类中的 sort()方法如何比较元素?

    TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。

    Collections 工具类的 sort 方法有两种重载的形式,

    第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较;

    第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。

    展开全文
  • Java集合中List,Set以及Map等集合体系详解(史上最全)

    万次阅读 多人点赞 2019-07-16 12:40:01
    概述: List Set Map都是接口,前两个继承至Collection接口,Map为独立接口 Set下有HashSet,LinkedHashSet,TreeSet List下有ArrayList,Vector,LinkedList ...Map下有Hashtable,LinkedHashMap,HashMap,...

    转载请注明出处:Java集合中List,Set以及Map等集合体系详解(史上最全)

    概述:

    • List , Set, Map都是接口,前两个继承至Collection接口,Map为独立接口
    • Set下有HashSet,LinkedHashSet,TreeSet
    • List下有ArrayList,Vector,LinkedList
    • Map下有Hashtable,LinkedHashMap,HashMap,TreeMap
    • Collection接口下还有个Queue接口,有PriorityQueue类

    这里写图片描述

    注意:

    • Queue接口与List、Set同一级别,都是继承了Collection接口。
      看图你会发现,LinkedList既可以实现Queue接口,也可以实现List接口.只不过呢, LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法 了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用。

    • SortedSet是个接口,它里面的(只有TreeSet这一个实现可用)中的元素一定是有序的。

    总结:

    Connection接口:

    List 有序,可重复

    • ArrayList
      优点: 底层数据结构是数组,查询快,增删慢。
      缺点: 线程不安全,效率高
    • Vector
      优点: 底层数据结构是数组,查询快,增删慢。
      缺点: 线程安全,效率低
    • LinkedList
      优点: 底层数据结构是链表,查询慢,增删快。
      缺点: 线程不安全,效率高

    Set 无序,唯一

    • HashSet
      底层数据结构是哈希表。(无序,唯一)
      如何来保证元素唯一性?
      1.依赖两个方法:hashCode()和equals()

    • LinkedHashSet
      底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
      1.由链表保证元素有序
      2.由哈希表保证元素唯一

    • TreeSet
      底层数据结构是红黑树。(唯一,有序)
      1. 如何保证元素排序的呢?
      自然排序
      比较器排序
      2.如何保证元素唯一性的呢?
      根据比较的返回值是否是0来决定

    针对Collection集合我们到底使用谁呢?(掌握)

    唯一吗?

    是:Set

    排序吗?

    是:TreeSet或LinkedHashSet
    否:HashSet
    如果你知道是Set,但是不知道是哪个Set,就用HashSet。

    否:List

    要安全吗?

    是:Vector
    否:ArrayList或者LinkedList

    查询多:ArrayList
    增删多:LinkedList
    如果你知道是List,但是不知道是哪个List,就用ArrayList。

    如果你知道是Collection集合,但是不知道使用谁,就用ArrayList。
    如果你知道用集合,就用ArrayList。

    说完了Collection,来简单说一下Map.

    Map接口:

    上图:
    这里写图片描述

    Map接口有三个比较重要的实现类,分别是HashMap、TreeMap和HashTable。

    • TreeMap是有序的,HashMap和HashTable是无序的。
    • Hashtable的方法是同步的,HashMap的方法不是同步的。这是两者最主要的区别。

    这就意味着:

    • Hashtable是线程安全的,HashMap不是线程安全的。
    • HashMap效率较高,Hashtable效率较低。
      如果对同步性或与遗留代码的兼容性没有任何要求,建议使用HashMap。 查看Hashtable的源代码就可以发现,除构造函数外,Hashtable的所有 public 方法声明中都有 synchronized关键字,而HashMap的源码中则没有。
    • Hashtable不允许null值,HashMap允许null值(key和value都允许)
    • 父类不同:Hashtable的父类是Dictionary,HashMap的父类是AbstractMap

    重点问题重点分析:

    (一).TreeSet, LinkedHashSet and HashSet 的区别

    1. 介绍

    • TreeSet, LinkedHashSet and HashSet 在java中都是实现Set的数据结构
    • TreeSet的主要功能用于排序
    • LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
    • HashSet只是通用的存储数据的集合

    2. 相同点

    • Duplicates elements: 因为三者都实现Set interface,所以三者都不包含duplicate elements
    • Thread safety: 三者都不是线程安全的,如果要使用线程安全可以Collections.synchronizedSet()

    3. 不同点

    • Performance and Speed: HashSet插入数据最快,其次LinkHashSet,最慢的是TreeSet因为内部实现排序
    • Ordering: HashSet不保证有序,LinkHashSet保证FIFO即按插入顺序排序,TreeSet安装内部实现排序,也可以自定义排序规则
    • null:HashSet和LinkHashSet允许存在null数据,但是TreeSet中插入null数据时会报NullPointerException

    4. 代码比较

      public static void main(String args[]) {
            HashSet<String> hashSet = new HashSet<>();
            LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
            TreeSet<String> treeSet = new TreeSet<>();
    
            for (String data : Arrays.asList("B", "E", "D", "C", "A")) {
                hashSet.add(data);
                linkedHashSet.add(data);
                treeSet.add(data);
            }
    
            //不保证有序
            System.out.println("Ordering in HashSet :" + hashSet);
    
            //FIFO保证安装插入顺序排序
            System.out.println("Order of element in LinkedHashSet :" + linkedHashSet);
    
            //内部实现排序
            System.out.println("Order of objects in TreeSet :" + treeSet);
    
    
        }
    

    运行结果:
    Ordering in HashSet :[A, B, C, D, E] (无顺序)
    Order of element in LinkedHashSet :[B, E, D, C, A] (FIFO插入有序)
    Order of objects in TreeSet :[A, B, C, D, E] (排序)

    (二).TreeSet的两种排序方式比较

    1.排序的引入(以基本数据类型的排序为例)

    由于TreeSet可以实现对元素按照某种规则进行排序,例如下面的例子

    public class MyClass {
    
        public static void main(String[] args) {
            // 创建集合对象
            // 自然顺序进行排序
            TreeSet<Integer> ts = new TreeSet<Integer>();
    
            // 创建元素并添加
            // 20,18,23,22,17,24,19,18,24
            ts.add(20);
            ts.add(18);
            ts.add(23);
            ts.add(22);
            ts.add(17);
            ts.add(24);
            ts.add(19);
            ts.add(18);
            ts.add(24);
    
            // 遍历
            for (Integer i : ts) {
                System.out.println(i);
            }
        }
    }
    
    

    运行结果:
    17
    18
    19
    20
    22
    23
    24

    2.如果是引用数据类型呢,比如自定义对象,又该如何排序呢?

    测试类:

    public class MyClass {
        public static void main(String[] args) {
            TreeSet<Student> ts=new TreeSet<Student>();
            //创建元素对象
            Student s1=new Student("zhangsan",20);
            Student s2=new Student("lis",22);
            Student s3=new Student("wangwu",24);
            Student s4=new Student("chenliu",26);
            Student s5=new Student("zhangsan",22);
            Student s6=new Student("qianqi",24);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
        }
    }
    

    Student.java:

    public class Student {
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    }
    
    

    结果报错:

    这里写图片描述
    原因分析:
    由于不知道该安照那一中排序方式排序,所以会报错。
    解决方法:
    1.自然排序
    2.比较器排序

    (1).自然排序

    自然排序要进行一下操作:
    1.Student类中实现 Comparable接口
    2.重写Comparable接口中的Compareto方法

    compareTo(T o)  比较此对象与指定对象的顺序。
    
    public class Student implements Comparable<Student>{
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public int compareTo(Student s) {
            //return -1; //-1表示放在红黑树的左边,即逆序输出
            //return 1;  //1表示放在红黑树的右边,即顺序输出
            //return o;  //表示元素相同,仅存放第一个元素
            //主要条件 姓名的长度,如果姓名长度小的就放在左子树,否则放在右子树
            int num=this.name.length()-s.name.length();
            //姓名的长度相同,不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前,则比较结果为一个负整数。
            //如果按字典顺序此 String 对象位于参数字符串之后,则比较结果为一个正整数。
            //如果这两个字符串相等,则结果为 0
            int num1=num==0?this.name.compareTo(s.name):num;
            //姓名的长度和内容相同,不代表年龄相同,所以还要判断年龄
            int num2=num1==0?this.age-s.age:num1;
            return num2;
        }
    }
    
    

    运行结果:

    lis-----------22
    qianqi-----------24
    wangwu-----------24
    chenliu-----------26
    zhangsan-----------20
    zhangsan-----------22

    (2).比较器排序

    比较器排序步骤:
    1.单独创建一个比较类,这里以MyComparator为例,并且要让其继承Comparator接口
    2.重写Comparator接口中的Compare方法

    compare(T o1,T o2)      比较用来排序的两个参数。
    

    3.在主类中使用下面的 构造方法

    TreeSet(Comparator<? superE> comparator)
              构造一个新的空 TreeSet,它根据指定比较器进行排序。
    

    测试类:

    public class MyClass {
    
        public static void main(String[] args) {
            //创建集合对象
            //TreeSet(Comparator<? super E> comparator) 构造一个新的空 TreeSet,它根据指定比较器进行排序。
            TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());
    
            //创建元素对象
            Student s1=new Student("zhangsan",20);
            Student s2=new Student("lis",22);
            Student s3=new Student("wangwu",24);
            Student s4=new Student("chenliu",26);
            Student s5=new Student("zhangsan",22);
            Student s6=new Student("qianqi",24);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
        }
    }
    
    

    Student.java:

    public class Student {
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
    }
    
    

    MyComparator类:

    public class MyComparator implements Comparator<Student> {
    
        @Override
        public int compare(Student s1,Student s2) {
            // 姓名长度
            int num = s1.getName().length() - s2.getName().length();
            // 姓名内容
            int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
            // 年龄
            int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
            return num3;
        }
    
    }
    

    运行结果:

    lis-----------22
    qianqi-----------24
    wangwu-----------24
    chenliu-----------26
    zhangsan-----------20
    zhangsan-----------22

    (三). 性能测试

    对象类:

    class Dog implements Comparable<Dog> {
        int size;
        public Dog(int s) {
            size = s;
        }
        public String toString() {
            return size + "";
        }
        @Override
        public int compareTo(Dog o) {
           //数值大小比较
            return size - o.size;
        }
    }
    

    主类:

    public class MyClass {
    
        public static void main(String[] args) {
    
            Random r = new Random();
            HashSet<Dog> hashSet = new HashSet<Dog>();
            TreeSet<Dog> treeSet = new TreeSet<Dog>();
            LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
    
            // start time
            long startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                hashSet.add(new Dog(x));
            }
    
            // end time
            long endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("HashSet: " + duration);
    
            // start time
            startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                treeSet.add(new Dog(x));
            }
            // end time
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("TreeSet: " + duration);
    
            // start time
            startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                linkedSet.add(new Dog(x));
            }
    
            // end time
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("LinkedHashSet: " + duration);
        }
    
    }
    
    

    运行结果:

    HashSet: 1544313
    TreeSet: 2066049
    LinkedHashSet: 629826
    虽然测试不够准确,但能反映得出,TreeSet要慢得多,因为它是有序的。

    嘿嘿

    好了,至此完结.小伙伴有问题的话,请留言

    参考文章:
    HashSet、TreeSet和LinkedHashSet的使用区别
    Collection集合总结
    HashMap、TreeMap和HashTable的区别

    展开全文
  • 集合

    千次阅读 多人点赞 2019-10-02 07:47:28
    集合集合是java中提供的一种容器,可以用来存储多个数据。集合和数组既然都是容器,它们有啥区别呢? 数组的长度是固定的。集合的长度是可变的。 数组中存储的是同一类型的元素,可以存储基本数据...

    0  Collection接口和Map接口

    1 Collection集合

    1.1 集合概述

    • 集合:集合是java中提供的一种容器,可以用来存储多个数据。集合和数组既然都是容器,它们有啥区别呢?

    • 数组的长度是固定的。集合的长度是可变的。

    • 数组中存储的是同一类型的元素,可以存储基本数据类型值。集合存储的都是对象。而且对象的类型可以不一致。在开发中一般当对象多的时候,使用集合进行存储。

    1.2 集合框架

    • Collection:单列集合类的根接口,用于存储一系列符合某种规则的元素,它有两个重要的子接口,分别是java.util.Listjava.util.Set

    • List的特点是元素有序、元素可重复。Set的特点是元素无序,而且不可重复。List接口的主要实现类有java.util.ArrayListjava.util.LinkedList

    • Set接口的主要实现类有java.util.HashSetjava.util.TreeSet

    1.3 Collection 常用功能

      Collection是所有单列集合的父接口,因此在Collection中定义了单列集合(List和Set)通用的一些方法,这些方法可用于操作所有的单列集合。方法如下:

    • public boolean add(E e): 把给定的对象添加到当前集合中 。

    • public void clear() :清空集合中所有的元素。

    • public boolean remove(E e): 把给定的对象在当前集合中删除。

    • public boolean contains(E e): 判断当前集合中是否包含给定的对象。

    • public boolean isEmpty(): 判断当前集合是否为空。

    • public int size(): 返回集合中元素的个数。

    • public Object[] toArray(): 把集合中的元素,存储到数组中。

    import java.util.ArrayList;
    import java.util.Collection;
    ​
    public class Demo1Collection {
        public static void main(String[] args) {
            // 创建集合对象 
            // 使用多态形式
            Collection<String> coll = new ArrayList<String>();
            // 使用方法
            // 添加功能  boolean  add(String s)
            coll.add("小李广");
            coll.add("扫地僧");
            coll.add("石破天");
            System.out.println(coll);
    ​
            // boolean contains(E e) 判断o是否在集合中存在
            System.out.println("判断  扫地僧 是否在集合中"+coll.contains("扫地僧"));
    ​
            //boolean remove(E e) 删除在集合中的o元素
            System.out.println("删除石破天:"+coll.remove("石破天"));
            System.out.println("操作之后集合中元素:"+coll);
            
            // size() 集合中有几个元素
            System.out.println("集合中有"+coll.size()+"个元素");
    ​
            // Object[] toArray()转换成一个Object数组
            Object[] objects = coll.toArray();
            // 遍历数组
            for (int i = 0; i < objects.length; i++) {
                System.out.println(objects[i]);
            }
    ​
            // void  clear() 清空集合
            coll.clear();
            System.out.println("集合中内容为:"+coll);
            // boolean  isEmpty()  判断是否为空
            System.out.println(coll.isEmpty());     
        }
    }
    方法示例

    2 Iterator迭代器

    2.1 Iterator接口

      JDK专门提供了一个接口java.util.Iterator,遍历集合中的所有元素。

      Iterator接口也是Java集合中的一员,但它与CollectionMap接口有所不同,

      Collection接口与Map接口主要用于存储元素,而Iterator主要用于迭代访问(即遍历)Collection中的元素,因此Iterator对象也被称为迭代器。

      想要遍历Collection集合,那么就要获取该集合迭代器完成迭代操作,获取迭代器的方法:

    • public Iterator iterator(): 获取集合对应的迭代器,用来遍历集合中的元素的。

      Iterator接口的常用方法如下:

    • public E next():返回迭代的下一个元素。

    • public boolean hasNext():如果仍有元素可以迭代,则返回 true。

    接下来我们通过案例学习如何使用Iterator迭代集合中元素:

    public class IteratorDemo {
        public static void main(String[] args) {
            // 使用多态方式 创建对象
            Collection<String> coll = new ArrayList<String>();
    ​
            // 添加元素到集合
            coll.add("串串星人");
            coll.add("吐槽星人");
            coll.add("汪星人");
            //遍历
            //使用迭代器 遍历   每个集合对象都有自己的迭代器
            Iterator<String> it = coll.iterator();
            //  泛型指的是 迭代出 元素的数据类型
            while(it.hasNext()){ //判断是否有迭代元素
                String s = it.next();//获取迭代出的元素
                System.out.println(s);
            }
        }
    }
    方法示例

    注意::在进行集合元素取出时,如果集合中已经没有元素了,还继续使用迭代器的next方法,将会发生java.util.NoSuchElementException没有集合元素的错误。

    2.2 迭代器的实现原理

      当遍历集合时,首先通过调用t集合的iterator()方法获得迭代器对象,然后使用hashNext()方法判断集合中是否存在下一个元素,如果存在,则调用next()方法将元素取出,否则说明已到达了集合末尾,停止遍历元素。

      Iterator迭代器对象在遍历集合时,内部采用指针的方式来跟踪集合中的元素代元素的过程。

      在调用Iterator的next方法之前,迭代器的索引位于第一个元素之前,不指向任何元素,当第一次调用迭代器的next方法后,迭代器的索引会向后移动一位,指向第一个元素并将该元素返回,当再次调用next方法时,迭代器的索引会指向第二个元素并将该元素返回,依此类推,直到hasNext方法返回false,表示到达了集合的末尾,终止对元素的遍历。

    2.3 增强for

      增强for循环(也称for each循环)是JDK1.5以后出来的一个高级for循环,专门用来遍历数组和集合的。它的内部原理其实是个Iterator迭代器,所以在遍历的过程中,不能对集合中的元素进行增删操作。

      格式:

    for(元素的数据类型  变量 : Collection集合or数组){ 
        //写操作代码
    }

      它用于遍历Collection和数组。通常只进行遍历元素,不要在遍历的过程中对集合元素进行增删操作。

    //练习1:遍历数组
    public class NBForDemo1 {
        public static void main(String[] args) {
            int[] arr = {3,5,6,87};
            //使用增强for遍历数组
            for(int a : arr){//a代表数组中的每个元素
                System.out.println(a);
            }
        }
    }
    // 练习2:遍历集合
    public class NBFor {
        public static void main(String[] args) {        
            Collection<String> coll = new ArrayList<String>();
            coll.add("小河神");
            coll.add("老河神");
            coll.add("神婆");
            //使用增强for遍历
            for(String s :coll){//接收变量s代表 代表被遍历到的集合元素
                System.out.println(s);
            }
        }
    }
    方法练习

    tips: 新for循环必须有被遍历的目标。目标只能是Collection或者是数组。新式for仅仅作为遍历操作出现。

    3 泛型

    3.1 泛型概述

      集合中是可以存放任意对象的,只要把对象存储集合后,那么这时他们都会被提升成Object类型。当我们在取出每一个对象,并且进行相应的操作,这时必须采用类型转换。

      泛型:可以在类或方法中预支地使用未知的类型。一般在创建对象时,将未知的类型确定具体的类型。当没有指定泛型时,默认类型为Object类型。

    public class GenericDemo {
        public static void main(String[] args) {
            Collection coll = new ArrayList();
            coll.add("abc");
            coll.add("itcast");
            coll.add(5);//由于集合没有做任何限定,任何类型都可以给其中存放
            Iterator it = coll.iterator();
            while(it.hasNext()){
                //需要打印每个字符串的长度,就要把迭代出来的对象转成String类型
                String str = (String) it.next();
                System.out.println(str.length());
            }
        }
    }

      程序在运行时发生了问题java.lang.ClassCastException。 为什么会发生类型转换异常呢?

      由于集合中什么类型的元素都可以存储。导致取出时强转引发运行时 ClassCastException。 怎么来解决这个问题呢? Collection虽然可以存储各种对象,但实际上通常Collection只存储同一类型对象。例如都是存储字符串对象。

      在JDK5之后,新增了泛型(Generic)语法,在设计API时可以指定类或方法支持泛型,这样在使用API的时候也变得更为简洁,并得到了编译时期的语法检查。

    3.2 使用泛型的好处

    • 将运行时期的ClassCastException,转移到了编译时期变成了编译失败。

    • 避免了类型强转的麻烦。

    public class GenericDemo2 {
        public static void main(String[] args) {
            Collection<String> list = new ArrayList<String>();
            list.add("abc");
            list.add("itcast");
            // list.add(5);//当集合明确类型后,存放类型不一致就会编译报错
            // 集合已经明确具体存放的元素类型,那么在使用迭代器的时候,迭代器也同样会知道具体遍历元素类型
            Iterator<String> it = list.iterator();
            while(it.hasNext()){
                String str = it.next();
                //当使用Iterator<String>控制元素类型后,就不需要强转了。获取到的元素直接就是String类型
                System.out.println(str.length());
            }
        }
    }
    初体验

    tips:泛型是数据类型的一部分,我们将类名与泛型合并一起看做数据类型。

    3.3 泛型的定义与使用

      泛型,用来灵活地将数据类型应用到不同的类、方法、接口当中。将数据类型作为参数进行传递。

    (1)在创建对象的时候确定泛型

      例如,ArrayList<String> list = new ArrayList<String>();

      此时,变量E的值就是String类型,那么我们的类型就可以理解为:

    class ArrayList<String>{ 
         public boolean add(String e){ }
    ​
         public String get(int index){  }
         ...
    }

    (2)含有泛型的方法

      定义格式:

      修饰符 <代表泛型的变量> 返回值类型 方法名(参数){  }
    public class MyGenericMethod {    
        public <MVP> void show(MVP mvp) {
            System.out.println(mvp.getClass());
        }
        
        public <MVP> MVP show2(MVP mvp) {   
            return mvp;
        }
    }

      使用格式:调用方法时,确定泛型的类型

    public class GenericMethodDemo {
        public static void main(String[] args) {
            // 创建对象
            MyGenericMethod mm = new MyGenericMethod();
            // 演示看方法提示
            mm.show("aaa");
            mm.show(123);
            mm.show(12.45);
        }
    }

    (3)含有泛型的接口

      定义格式:

      修饰符 interface接口名<代表泛型的变量> {  }
    public interface MyGenericInterface<E>{
        public abstract void add(E e);
        
        public abstract E getE();  
    }

    3.4 泛型通配符

      当使用泛型类或者接口时,传递的数据中,泛型类型不确定,可以通过通配符<?>表示。但是一旦使用泛型的通配符后,只能使用Object类中的共性方法,集合中元素自身方法无法使用。

      通配符基本使用:不知道使用什么类型来接收的时候,此时可以使用?,?表示未知通配符。

      此时只能接受数据,不能往该集合中存储数据。

    public static void main(String[] args) {
        Collection<Intger> list1 = new ArrayList<Integer>();
        getElement(list1);
        Collection<String> list2 = new ArrayList<String>();
        getElement(list2);
    }
    public static void getElement(Collection<?> coll){}
    //?代表可以接收任意类型

    tips:泛型不存在继承关系 Collection<Object> list = new ArrayList<String>();这种是错误的。

      通配符高级使用----受限泛型

      在JAVA的泛型中可以指定一个泛型的上限下限

      <1> 泛型的上限

    • 格式类型名称 <? extends 类 > 对象名称

    • 意义只能接收该类型及其子类

      <2> 泛型的下限

    • 格式类型名称 <? super 类 > 对象名称

    • 意义只能接收该类型及其父类型

      比如:现已知Object类,String 类,Number类,Integer类,其中Number是Integer的父类

    public static void main(String[] args) {
        Collection<Integer> list1 = new ArrayList<Integer>();
        Collection<String> list2 = new ArrayList<String>();
        Collection<Number> list3 = new ArrayList<Number>();
        Collection<Object> list4 = new ArrayList<Object>();
        
        getElement(list1);
        getElement(list2);//报错
        getElement(list3);
        getElement(list4);//报错
      
        getElement2(list1);//报错
        getElement2(list2);//报错
        getElement2(list3);
        getElement2(list4);
      
    }
    // 泛型的上限:此时的泛型?,必须是Number类型或者Number类型的子类
    public static void getElement1(Collection<? extends Number> coll){}
    // 泛型的下限:此时的泛型?,必须是Number类型或者Number类型的父类
    public static void getElement2(Collection<? super Number> coll){}

    4  集合综合案例

    4.1 案例介绍

      按照斗地主的规则,完成洗牌发牌的动作。 具体规则:

      使用54张牌打乱顺序,三个玩家参与游戏,三人交替摸牌,每人17张牌,最后三张留作底牌。

    4.2 案例分析

    • 准备牌:

      牌可以设计为一个ArrayList<String>,每个字符串为一张牌。 每张牌由花色数字两部分组成,我们可以使用花色集合与数字集合嵌套迭代完成每张牌的组装。 牌由Collections类的shuffle方法进行随机排序。

    • 发牌

      将每个人以及底牌设计为ArrayList<String>,将最后3张牌直接存放于底牌,剩余牌通过对3取模依次发牌。

    • 看牌

      直接打印每个集合。

    import java.util.ArrayList;
    import java.util.Collections;
    ​
    public class Poker {
        public static void main(String[] args) {
            /*
            * 1: 准备牌操作
            */
            //1.1 创建牌盒 将来存储牌面的 
            ArrayList<String> pokerBox = new ArrayList<String>();
            //1.2 创建花色集合
            ArrayList<String> colors = new ArrayList<String>();
    ​
            //1.3 创建数字集合
            ArrayList<String> numbers = new ArrayList<String>();
    ​
            //1.4 分别给花色 以及 数字集合添加元素
            colors.add("♥");
            colors.add("♦");
            colors.add("♠");
            colors.add("♣");
    ​
            for(int i = 2;i<=10;i++){
                numbers.add(i+"");
            }
            numbers.add("J");
            numbers.add("Q");
            numbers.add("K");
            numbers.add("A");
            //1.5 创造牌  拼接牌操作
            // 拿出每一个花色  然后跟每一个数字 进行结合  存储到牌盒中
            for (String color : colors) {
                //color每一个花色 
                //遍历数字集合
                for(String number : numbers){
                    //结合
                    String card = color+number;
                    //存储到牌盒中
                    pokerBox.add(card);
                }
            }
            //1.6大王小王
            pokerBox.add("小☺");
            pokerBox.add("大☠");   
            // System.out.println(pokerBox);
            //洗牌 是不是就是将  牌盒中 牌的索引打乱 
            // Collections类  工具类  都是 静态方法
            // shuffer方法   
            /*
             * static void shuffle(List<?> list) 
             *     使用默认随机源对指定列表进行置换。 
             */
            //2:洗牌
            Collections.shuffle(pokerBox);
            //3 发牌
            //3.1 创建 三个 玩家集合  创建一个底牌集合
            ArrayList<String> player1 = new ArrayList<String>();
            ArrayList<String> player2 = new ArrayList<String>();
            ArrayList<String> player3 = new ArrayList<String>();
            ArrayList<String> dipai = new ArrayList<String>();    
    ​
            //遍历 牌盒  必须知道索引   
            for(int i = 0;i<pokerBox.size();i++){
                //获取 牌面
                String card = pokerBox.get(i);
                //留出三张底牌 存到 底牌集合中
                if(i>=51){//存到底牌集合中
                    dipai.add(card);
                } else {
                    //玩家1   %3  ==0
                    if(i%3==0){
                        player1.add(card);
                    }else if(i%3==1){//玩家2
                        player2.add(card);
                    }else{//玩家3
                        player3.add(card);
                    }
                }
            }
            //看看
            System.out.println("令狐冲:"+player1);
            System.out.println("田伯光:"+player2);
            System.out.println("绿竹翁:"+player3);
            System.out.println("底牌:"+dipai);  
        }
    }
    代码实现

    5 List集合

    5.1  List接口中常用方法

    List作为Collection集合的子接口,不但继承了Collection接口中的全部方法,而且还增加了一些根据元素索引来操作集合的特有方法,如下:

    • public void add(int index, E element): 将指定的元素,添加到该集合中的指定位置上。

    • public E get(int index):返回集合中指定位置的元素。

    • public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。

    • public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

    5.2 List的子类

    (1) ArrayList集合

      java.util.ArrayList集合数据存储的结构是数组结构。

      元素增删慢,查找快,由于日常开发中使用最多的功能为查询数据、遍历数据,所以ArrayList是最常用的集合。

    (2) LinkedList集合

      java.util.LinkedList集合数据存储的结构是链表结构。方便元素添加、删除的集合。

      在开发时,LinkedList集合也可以作为堆栈,队列的结构使用。

      实际开发中对一个集合元素的添加与删除经常涉及到首尾操作,而LinkedList提供了大量首尾操作的方法。了解即可:

    • public void addFirst(E e):将指定元素插入此列表的开头。

    • public void addLast(E e):将指定元素添加到此列表的结尾。

    • public E getFirst():返回此列表的第一个元素。

    • public E getLast():返回此列表的最后一个元素。

    • public E removeFirst():移除并返回此列表的第一个元素。

    • public E removeLast():移除并返回此列表的最后一个元素。

    • public E pop():从此列表所表示的堆栈处弹出一个元素。

    • public void push(E e):将元素推入此列表所表示的堆栈。

    • public boolean isEmpty():如果列表不包含元素,则返回true。

    6 Set接口

      Set集合有多个子类,主要使用java.util.HashSetjava.util.LinkedHashSet这两个集合。

    // Set集合取出元素的方式可以采用:迭代器、增强for。
    
    // 不能用普通的for循环,因为是无序的,没有U索引/下标。

    6.1 HashSet集合介绍

      java.util.HashSetSet接口的一个实现类,它所存储的元素是不可重复的,并且元素都是无序的(即存取顺序不一致)。

      java.util.HashSet底层的实现其实是一个java.util.HashMap支持。

      HashSet是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于:hashCodeequals方法

    6.1.1 HashSet集合存储数据的结构(哈希表)

      在JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。

      而JDK1.8中,哈希表存 储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

    6.1.2 存储流程图

           往集合中存放自定义的对象,那么保证其唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。

    6.2  LinkedHashSet

      HashSet保证元素唯一,可是元素存放进去是没有顺序的,那么我们要保证有序,怎么办呢?

      在HashSet下面有一个子类java.util.LinkedHashSet,它是链表和哈希表组合的一个数据存储结构。

      【链表的作用】:记录元素存储时的顺序

    public class LinkedHashSetDemo {
        public static void main(String[] args) {
            Set<String> set = new LinkedHashSet<String>();
            set.add("bbb");
            set.add("aaa");
            set.add("abc");
            set.add("bbc");
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
        }
    }
    结果:
      bbb
      aaa
      abc
      bbc

    6.3 可变参数

      修饰符 返回值类型 方法名(参数类型... 形参名){  }    <=>    修饰符 返回值类型 方法名(参数类型[] 形参名){  }

    注意:如果在方法书写时,这个方法拥有多参数,参数中包含可变参数,可变参数一定要写在参数列表的末尾位置。

    public class ChangeArgs {
        public static void main(String[] args) {
            int[] arr = { 1, 4, 62, 431, 2 };
            int sum = getSum(arr);
            System.out.println(sum);
            //  6  7  2 12 2121
            // 求 这几个元素和 6  7  2 12 2121
            int sum2 = getSum(6, 7, 2, 12, 2121);
            System.out.println(sum2);
        }
    
        /*
         * 完成数组  所有元素的求和 原始写法
         
          public static int getSum(int[] arr){
            int sum = 0;
            for(int a : arr){
                sum += a;
            }
            
            return sum;
          }
        */
        //可变参数写法
        public static int getSum(int... arr) {
            int sum = 0;
            for (int a : arr) {
                sum += a;
            }
            return sum;
        }
    }
    可变参数练习

    7 Collections

    7.1 常用功能

    • java.utils.Collections是集合工具类,用来对集合进行操作。部分方法如下:

    • public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素。

    • public static void shuffle(List<?> list) 打乱顺序:打乱集合顺序。

    • public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。

    • public static <T> void sort(List<T> list,Comparator<? super T> ):将集合中元素按照指定规则排序。

    public class CollectionsDemo {
        public static void main(String[] args) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            //原来写法
            //list.add(12);
            //list.add(14);
            //list.add(15);
            //list.add(1000);
            //采用工具类 完成 往集合中添加元素  
            Collections.addAll(list, 5, 222, 1,2);
            System.out.println(list);
            //排序方法 
            Collections.sort(list);
            System.out.println(list);
        }
    }
    结果:
    [5, 222, 1, 2]
    [1, 2, 5, 222]
    方法演示

      由方法运行结果发现,集合按照顺序进行了排列,可是这样的顺序是采用默认的顺序,如果想要指定顺序该怎么办呢?

      ——>   public static <T> void sort(List<T> list,Comparator<? super T> ):将集合中元素按照指定规则排序。

    7.2 Comparator接口实现

      采用的public static <T> void sort(List<T> list)这个方法完成的排序,实际上要求了被排序的类型需要实现Comparable接口完成比较的功能。

      实现类需要重写compare方法:

      public int compare(String o1, String o2):比较其两个参数的顺序。

    两个对象比较的结果有三种:大于,等于,小于。

    如果要按照升序排序:

    则o1 小于o2,返回(负数);相等返回0;01大于02返回(正数)

    如果要按照降序排序:

    则o1 小于o2返回(正数);相等返回0;01大于02返回(负数)

    public class CollectionsDemo3 {
        public static void main(String[] args) {
            ArrayList<String> list = new ArrayList<String>();
            list.add("cba");
            list.add("aba");
            list.add("sba");
            list.add("nba");
            //排序方法  按照第一个单词的降序
            Collections.sort(list, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o2.charAt(0) - o1.charAt(0);
                }
            });
            System.out.println(list);
        }
    }
    
    //运行结果:
    [sba, nba, cba, aba]
    示例

    7.3 Comparable接口实现

    案例:如果要对两个对象进行比较,则需要在对象bean中实现Comparable接口,重写compare方法

    //Student 初始类
    
    public class Student{
        private String name;
        private int age;
    
        public Student() {
        }
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Student{" +
                   "name='" + name + '\'' +
                   ", age=" + age +
                   '}';
        }
    }
    Student初始类
    public class Demo {
    
        public static void main(String[] args) {
            // 创建四个学生对象 存储到集合中
            ArrayList<Student> list = new ArrayList<Student>();
    
            list.add(new Student("rose",18));
            list.add(new Student("jack",16));
            list.add(new Student("abc",16));
            list.add(new Student("ace",17));
            list.add(new Student("mark",16));
    
    
            /*
              让学生 按照年龄排序 升序
             */
    //        Collections.sort(list);//要求 该list中元素类型  必须实现比较器Comparable接口
    
    
            for (Student student : list) {
                System.out.println(student);
            }
    
    
        }
    }
    测试类

      发现,当我们调用Collections.sort()方法的时候 程序报错了。

      原因:如果想要对list集合中的元素(Student对象)完成排序,那么必须要实现比较器Comparable接口。

    public class Student implements Comparable<Student>{
        ....
        @Override
        public int compareTo(Student o) {
            return this.age-o.age;//升序
        }
    }

      再次测试,代码就OK 了效果如下:

    Student{name='jack', age=16}
    Student{name='abc', age=16}
    Student{name='mark', age=16}
    Student{name='ace', age=17}
    Student{name='rose', age=18}

    8 Map集合

    8.1 概述

      现实生活中,我们常会看到这样的一种集合:IP地址与主机名,身份证号与个人,系统用户名与系统用户对象等,这种一一对应的关系,就叫做映射。Java提供了专门的集合类用来存放这种对象关系的对象,即java.util.Map接口。

    • Collection中的集合,元素是孤立存在的(理解为单身),向集合中存储元素采用一个个元素的方式存储。

    • Map中的集合,元素是成对存在的(理解为夫妻)。每个元素由键与值两部分组成,通过键可以找对所对应的值。

    • Collection中的集合称为单列集合,Map中的集合称为双列集合。

    • 需要注意的是,Map中的集合不能包含重复的键,值可以重复;每个键只能对应一个值。

    8.2 Map常用子类

      常用HashMap集合、LinkedHashMap集合。

    • HashMap<K,V>:存储数据采用的哈希表结构,元素的存取顺序不能保证一致。由于要保证键的唯一、不重复,需要重写键的hashCode()方法、equals()方法

    • LinkedHashMap<K,V>:HashMap下有个子类LinkedHashMap,存储数据采用的哈希表结构+链表结构。通过链表结构可以保证元素的存取顺序一致;通过哈希表结构可以保证的键的唯一、不重复,需要重写键的hashCode()方法、equals()方法。

    tips:Map接口中的集合都有两个泛型变量<K,V>,在使用时,要为两个泛型变量赋予数据类型。两个泛型变量<K,V>的数据类型可以相同,也可以不同。

    8.3 Map接口中的常用方法

      Map接口中定义了很多方法,常用的如下:

    • public V put(K key, V value): 把指定的键与指定的值添加到Map集合中。

    • public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除,返回被删除元素的值。

    • public V get(Object key) 根据指定的键,在Map集合中获取对应的值。

    • boolean containsKey(Object key) 判断集合中是否包含指定的键。

    • public Set<K> keySet(): 获取Map集合中所有的键,存储到Set集合中。

    • public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。

    public class MapDemo {
        public static void main(String[] args) {
            //创建 map对象
            HashMap<String, String>  map = new HashMap<String, String>();
    
            //添加元素到集合
            map.put("黄晓明", "杨颖");
            map.put("文章", "马伊琍");
            map.put("邓超", "孙俪");
            System.out.println(map);
    
            //String remove(String key)
            System.out.println(map.remove("邓超"));
            System.out.println(map);
    
            // 想要查看 黄晓明的媳妇 是谁
            System.out.println(map.get("黄晓明"));
            System.out.println(map.get("邓超"));    
        }
    }
    方法演示

    8.4 Map集合遍历键找值方式:keyset()

      键找值方式:即通过元素中的键,获取键所对应的值

      分析步骤:

    1. 获取Map中所有的键,由于键是唯一的,所以返回一个Set集合存储所有的键。方法提示:keyset()

    2. 遍历键的Set集合,得到每一个键。

    3. 根据键,获取键所对应的值。方法提示:get(K key)

    public class MapDemo01 {
        public static void main(String[] args) {
            //创建Map集合对象 
            HashMap<String, String> map = new HashMap<String,String>();
            //添加元素到集合 
            map.put("胡歌", "霍建华");
            map.put("郭德纲", "于谦");
            map.put("薛之谦", "大张伟");
    
            //获取所有的键  获取键集
            Set<String> keys = map.keySet();
            // 遍历键集 得到 每一个键
            for (String key : keys) {
                  //key  就是键
                //获取对应值
                String value = map.get(key);
                System.out.println(key+"的CP是:"+value);
            }  
        }
    }
    keyset

    8.5 Map集合遍历键值对方式

      Map中存放的是两种对象,一种称为key(键),一种称为value(值),它们在在Map中是一一对应关系,这一对对象又称做Map中的一个Entry(项)

      Entry将键值对的对应关系封装成了对象。即键值对对象,这样我们在遍历Map集合时,就可以从每一个键值对(Entry)对象中获取对应的键与对应的值。

      既然Entry表示了一对键和值,那么也同样提供了获取对应键和对应值得方法:

    • public K getKey():获取Entry对象中的键。

    • public V getValue():获取Entry对象中的值。

      在Map集合中也提供了获取所有Entry对象的方法:

    • public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。

      键值对方式:即通过集合中每个键值对(Entry)对象,获取键值对(Entry)对象中的键与值。

      操作步骤与图解:

      1.   获取Map集合中,所有的键值对(Entry)对象,以Set集合形式返回。方法提示:entrySet()

      2.   遍历包含键值对(Entry)对象的Set集合,得到每一个键值对(Entry)对象。

      3.   通过键值对(Entry)对象,获取Entry对象中的键与值。 方法提示:getkey() getValue()

    public class MapDemo02 {
        public static void main(String[] args) {
            // 创建Map集合对象 
            HashMap<String, String> map = new HashMap<String,String>();
            // 添加元素到集合 
            map.put("胡歌", "霍建华");
            map.put("郭德纲", "于谦");
            map.put("薛之谦", "大张伟");
    
            // 获取 所有的 entry对象  entrySet
            Set<Entry<String,String>> entrySet = map.entrySet();
    
            // 遍历得到每一个entry对象
            for (Entry<String, String> entry : entrySet) {
                   // 解析 
                String key = entry.getKey();
                String value = entry.getValue();  
                System.out.println(key+"的CP是:"+value);
            }
        }
    }
    EntrySet

    8.6 HashMap存储自定义类型键值

      练习:每位学生(姓名,年龄)都有自己的家庭住址。那么,既然有对应关系,则将学生对象和家庭住址存储到map集合中。学生作为键, 家庭住址作为值。

    public class Student {
        private String name;
        private int age;
    
        public Student() {
        }
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Student student = (Student) o;
            return age == student.age && Objects.equals(name, student.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
    }
    学生类
    public class HashMapTest {
        public static void main(String[] args) {
            //1,创建Hashmap集合对象。
            Map<Student,String>map = new HashMap<Student,String>();
            //2,添加元素。
            map.put(newStudent("lisi",28), "上海");
            map.put(newStudent("wangwu",22), "北京");
            map.put(newStudent("zhaoliu",24), "成都");
            map.put(newStudent("zhouqi",25), "广州");
            map.put(newStudent("wangwu",22), "南京");
            
            //3,取出元素。键找值方式
            Set<Student>keySet = map.keySet();
            for(Student key: keySet){
                Stringvalue = map.get(key);
                System.out.println(key.toString()+"....."+value);
            }
        }
    }
    测试类
    • 当给HashMap中存放自定义对象时,如果自定义对象作为key存在,这时要保证对象唯一,必须复写对象的hashCode和equals方法(如果忘记,请回顾HashSet存放自定义对象)。

    • 如果要保证map中存放的key和取出的顺序一致,可以使用java.util.LinkedHashMap集合来存放。

    8.7 LinkedHashMap

      在HashMap下面有一个子类LinkedHashMap,它是链表和哈希表组合的一个数据存储结构。

    public class LinkedHashMapDemo {
        public static void main(String[] args) {
            LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
            map.put("邓超", "孙俪");
            map.put("李晨", "范冰冰");
            map.put("刘德华", "朱丽倩");
            Set<Entry<String, String>> entrySet = map.entrySet();
            for (Entry<String, String> entry : entrySet) {
                System.out.println(entry.getKey() + "  " + entry.getValue());
            }
        }
    }

    8.8 Map集合练习

      需求:

      计算一个字符串中每个字符出现次数。

      分析:

    1. 获取一个字符串对象

    2. 创建一个Map集合,键代表字符,值代表次数。

    3. 遍历字符串得到每个字符。

    4. 判断Map中是否有该键。

    5. 如果没有,第一次出现,存储次数为1;如果有,则说明已经出现过,获取到对应的值进行++,再次存储。

    6. 打印最终结果

    public class MapTest {
    public static void main(String[] args) {
            //友情提示
            System.out.println("请录入一个字符串:");
            String line = new Scanner(System.in).nextLine();
            // 定义 每个字符出现次数的方法
            findChar(line);
        }
        private static void findChar(String line) {
            //1:创建一个集合 存储  字符 以及其出现的次数
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            //2:遍历字符串
            for (int i = 0; i < line.length(); i++) {
                char c = line.charAt(i);
                //判断 该字符 是否在键集中
                if (!map.containsKey(c)) {//说明这个字符没有出现过
                    //那就是第一次
                    map.put(c, 1);
                } else {
                    //先获取之前的次数
                    Integer count = map.get(c);
                    //count++;
                    //再次存入  更新
                    map.put(c, ++count);
                }
            }
            System.out.println(map);
        }
    }
    示例

    8.9 HashMap排序

    public class SortMap
    {
        public static void main(String[] args)
        {
            Map<String, Integer> map = new HashMap<String, Integer>();
            map.put("1d", 4);
            map.put("2b", 3);
            map.put("3a", 1);
            map.put("4c", 2);
            System.out.println("原始数据:");
            // 排序前
            for(String s:map.keySet())
            {
                System.out.println(s+":"+map.get(s));
            }
            List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
            
            // 根据key值排序
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2)
                {
                    return o1.getKey().toString().compareTo(o2.toString());
                }
            });
            System.out.println("根据key值排序:");
            // 根据key值排序后
            for (Entry<String, Integer> entry : list)
            {
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
            // 根据value排序
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2)
                {
                    return o1.getValue()-o2.getValue();
                }
            });
            System.out.println("根据value值排序:");
            // 根据value值排序后
            for (Entry<String, Integer> entry : list)
            {
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
    }

     

    9 JDK9对集合添加的优化

      (1)通常,我们在代码中创建一个集合(例如,List 或 Set ),并直接用一些元素填充它。 实例化集合,几个 add方法 调用,使得代码重复。

    public class Demo01 {
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("abc");
            list.add("def");
            list.add("ghi");
            System.out.println(list);
        }
    }

      (2)Java 9,添加了几种集合工厂方法,更方便创建少量元素的集合、map实例。新的List、Set、Map的静态工厂方法可以更方便地创建集合的不可变实例。

      需要注意以下两点:

    1:of()方法只是Map,List,Set这三个接口的静态方法,其父类接口和子类实现并没有这类方法,比如 HashSet,ArrayList等待;

    2:返回的集合是不可变的;

    public class HelloJDK9 {  
        public static void main(String[] args) {  
            Set<String> str1=Set.of("a","b","c");  
            //str1.add("c");这里编译的时候不会错,但是执行的时候会报错,因为是不可变的集合  
            System.out.println(str1);  
            Map<String,Integer> str2=Map.of("a",1,"b",2);  
            System.out.println(str2);  
            List<String> str3=List.of("a","b");  
            System.out.println(str3);  
        }  
    } 

     

     

    转载于:https://www.cnblogs.com/timetellu/p/11614033.html

    展开全文
  • java各种集合的线程安全

    万次阅读 多人点赞 2015-03-31 20:52:18
    java集合的线程安全
  • Java线程安全的集合详解

    万次阅读 多人点赞 2018-03-25 18:52:32
    一、早期线程安全的集合我们先从早期的线程安全的集合说起,它们是Vector和HashTable1.VectorVector和ArrayList类似,是长度可变的数组,与ArrayList不同的是,Vector是线程安全的,它给几乎所有的public方法都加上...
  • 集合&线程

    2019-11-27 09:22:39
    目录 1 回顾:类集 2 线程 3 练习:实现链表 4 练习:多线程-打印操作 1 回顾 类集:...集合输出:https://blog.csdn.net/qq_43711904/article/details/97489552 2 线程 https://blog...
  • ArrayList:底层基于数组实现,有序可重复集合,是线程不安全的,查改快。因为可以使用数组索引直接定位到数据,所以查询和修改效率快;而数组的长度一旦确定不能更改,每次添加数据的时候都需要对数组容量进行判断...
  • 1.共享式获取锁 1.1 不响应线程中断 // 步骤1:尝试获取锁 // 步骤2:排队获取锁 public final void acquireShared(int arg) { if (tryAcquireShared(arg) < 0) doAcquireShared(arg); ...
  • 首先知道java中为什么要用集合这个概念2.java中的集合族的基本介绍3.java中的单列结合3.1 单列各个集合底层数据结构和基本性质4.java的双列集合二、java中的集合的使用1.如何正确的使用集合了?2.集合的遍历方法:三...
  • 交集,并集,差集,补集,对称差集
  • 集合类-六种常见的集合

    千次阅读 2009-04-29 02:09:00
    一、先来说说数组的不足(也可以说集合与数组的区别)1.数组是固定大小的,不能伸缩。虽然System.Array.Resize这个泛型方法可以重置数组大小,但是该方法是重新创建新设置大小的数组,用的是旧数组的元素初始化。...
  • 实现集合List中的元素进行排序

    万次阅读 多人点赞 2020-06-02 22:23:24
    Collections对List集合中的数据进行排序 有时候需要对集合中的元素按照一定的规则进行排序,这就需要用到 Java中提供的对集合进行操作的工具类Collections,其中的sort方法 先看一个简单的例子: public static ...
  • java集合详解和集合面试题目

    万次阅读 多人点赞 2019-09-22 22:04:59
    一、集合与数组 数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下使用。 集合(只能存储对象,对象类型可以不一样)的长度可变,可在多数情况下使用。 ...
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Java集合面试题 Java 集合框架的基础接口有哪些? Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合...
  • Redis底层详解(四) 整数集合

    万次阅读 2018-12-03 07:42:57
    一、集合概述  对于集合,STL 的 set 相信大家都不陌生,它的底层实现是红黑树。无论插入、删除、查找都是 O(log n) 的时间复杂度。当然,如果用哈希表来实现集合,插入、删除、查找都可以达到 O(1)。那么为什么...
  • 人工智能,零基础入门!... 有一个场景,就是一个有list,list里面放的是Card对象,Card对象有多个属性值,包括卡用户信息、卡最近使用时间opTime,这个list是查询用户卡包得到的卡列表。 现在有一个需求,就是查询卡...
  • Java集合类详解

    万次阅读 多人点赞 2017-10-23 14:06:12
    Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ... Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Element
  • 快速入门Scala(六):数组与集合

    万次阅读 2019-04-20 15:08:22
    除此之外,Scala还提供了一套很好的集合( Collection)实现,提供了一些集合类型的抽象。 数组 数组声明的语法格式: var z:Array[String] = new ArrayString 或 var z = new ArrayString...
1 2 3 4 5 ... 20
收藏数 2,380,592
精华内容 952,236
关键字:

集合