当前位置:首页 > Java技术 > Java集合(一)

Java集合(一)

2022年08月04日 17:27:25Java技术2

一、简介

1.1 集合是什么?

        集合的本质是用于存储对象的数据结构。

1.2 java集合

Java集合要从两大接口说起,一为Collection接口,二为Map接口。

Collection接口框架图:        Java集合(一) _ JavaClub全栈架构师技术笔记Map接口框架图:Java集合(一) _ JavaClub全栈架构师技术笔记

1.3 集合类型

1.3.1 Collection

List

        Java 的 List 是非常常用的数据类型。 List 是有序的 Collection Java List 一共三个实现类 : 分别是 ArrayList、 Vector LinkedList
ArrayList( 数组 )
        ArrayList 是最常用的 List 实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。
Vector( 数组实现、线程同步 )
        Vector 与 ArrayList 一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写 Vector ,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比 访问 ArrayList 慢。
LinkList( 链表 )
        LinkedList 是用链表结构存储数据的,很适合数据的动态插入和删除,随机访问和遍历速度比较慢。另外,他还提供了 List 接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆 栈、队列和 双向队列使用。

Set

        Set 注重独一无二的性质 , 该体系集合用于存储无序 ( 存入和取出的顺序不一定相同 ) 元素,值不能重复。
        对象的相等性本质是对象 hashCode (java 是依据对象的内存地址计算出的此序号 ) 判断 的,如果想要让两个不同的对象视为相等的,就必须覆盖 Object hashCode 方法和 equals 方 法。
HashSet(Hash )
        哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序 ( List 显然不 同 ) 而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashcode 方法来获取 的, HashSet 首先判断两个元素的哈希值,如果哈希值一样,接着会比较 equals 方法 如果 equls 结果 为 true HashSet 就视为同一个元素。如果 equals false 就不是同一个元素。
        哈希值相同 equals 为 false 的元素是怎么存储呢 , 就是在同样的哈希值下顺延 ( 可以认为哈希值相 同的元 素放在一个哈希桶中) 。也就是哈希一样的存一列。如图 1 表示 hashCode 值不相同的情 况 ; 2 表示 hashCode 值相同,但 equals 不相同的情况。 HashSet 通过 hashCode 值来确定元素在内存中的位置。一个 hashCode 位置上可以存放多个元素。
TreeSet( 二叉树 )
        1. TreeSet()是使用二叉树的原理对新 add() 的对象按照指定的顺序排序 ( 升序、降序 ) ,每增 加一个对象都会进行排序,将对象插入的二叉树指定的位置。
        2. Integer 和 String 对象都可以进行默认的 TreeSet 排序,而自定义类的对象是不可以的,自己定义的类必须实现 Comparable 接口,并且覆写相应的 compareTo() 函数,才可以正常使用。
        3. 在覆写 compare() 函数时,要返回相应的值才能使 TreeSet 按照一定的规则来排序
        4. 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整
数、零或正整数。
LinkHashSet(HashSet+LinkedHashMap)
        对于 LinkedHashSet 而言,它继承与 HashSet 、又基于 LinkedHashMap 来实现的。
        LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素,它继承与 HashSet ,其所有的方法操作上又与 HashSet 相同,因此 LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数, 调用父类的构造器,底层构造一个 LinkedHashMap 来实现,在相关操作上与父类 HashSet 的操作相 同,直接调用父类 HashSet 的方法即可。

1.3.2 Map

HashMap(数组+链表+红黑树)

        HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快 的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ,允许多条记 录的值为 null HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap ,可能会导 致数据的不一致。如果需要满足线程安全,可以用 Collections synchronizedMap 方法使
HashMap 具有线程安全的能力,或者使用 ConcurrentHashMap 。我们用下面这张图来介绍 HashMap 的结构。
JAVA7 实现
        大方向上,HashMap 里面是一个数组,然后数组中每个元素是一个单向链表。上图中,每个绿色 的实体是嵌套类 Entry 的实例, Entry 包含四个属性: key, value, hash 值和用于单向链表的 next
1. capacity :当前数组容量,始终保持 2^n ,可以扩容,扩容后数组大小为当前的 2 倍。
2. loadFactor :负载因子,默认为 0.75
3. threshold :扩容的阈值,等于 capacity * loadFactor
JAVA8 实现
        Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组 + 链表 + 红黑 树 组成。
        根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的 具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决 于链表的长度,为 O(n) 。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)
HashTable( 线程安全 )
        Hashtable 是遗留类,很多映射的常用功能与 HashMap 类似,不同的是它承自 Dictionary 类, 并且是线程安全的,任一时间只有一个线程能写 Hashtable ,并发性不如 ConcurrentHashMap, 因为 ConcurrentHashMap 引入了分段锁。 Hashtable 不建议在新代码中使用,不需要线程安全的场合可以用 HashMap 替换,需要线程安全的场合可以用 ConcurrentHashMap 替换。
TreeMap( 可排序 )
        TreeMap 实现 SortedMap 接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历 TreeMap 时,得到的记录是排过序的。 在使用 TreeMap 时, key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator,否则会在运行时抛出 java.lang.ClassCastException 类型的异常。
LinkHashMap( 记录插入顺序 )
        LinkedHashMap 是 HashMap 的一个子类,保存了记录的插入顺序,在用 Iterator 遍历
LinkedHashMap 时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

二、JDK8的ArrayList源码解析

2.1ArrayList初始化

 ArrayList有三种初始化方法:
        1、初始化一种指定集合大小的空ArrayList。
        2、初始化一个空的ArrayList。
        3、初始化一个含有指定元素的ArrayLsit。

Java集合(一) _ JavaClub全栈架构师技术笔记

 在第三个构造中,存在一个JDK的bug:6260652。

而see 6260652是什么呢?6260652是JDK的bug文档编号。

JDK-6260652 : (coll) Arrays.asList(x).toArray().getClass() should be Object[].class。

执行Arrays.asList(x).toArray()函数后,理论上返回的class对象是Object[].class。

Bug ID: JDK-6260652 (coll) Arrays.asList(x).toArray().getClass() should be Object[].class

在ArrayList中防止错误数组导致异常的解决方案是:

 if (elementData.getClass() != Object[].class)

                  elementData = Arrays.copyOf(elementData, size, Object[].class);

        判断该对象的class不等于Object[].class,创建一个新的Object[]数组,将原来的数组对象放入这个新的Object[]数组中。

2.2 ArrayList核心方法新增add()

        ArrayList的add方法无非就是将需要添加的数据e加到下标为size的elmentDate的数组中。

        而在添加数据前,需要确保数组长度是足够的,执行ensureCapacityInternal()进行检查。

    ensureExplicitCapacity(int minCapacity)中有行代码 modCount++;在下面fail-fast(快速失败)机制说明。

Java集合(一) _ JavaClub全栈架构师技术笔记

Java集合(一) _ JavaClub全栈架构师技术笔记

Java集合(一) _ JavaClub全栈架构师技术笔记

2.3 fail-fast(快速失败)机制

        创建迭代器对象时 将全局的modCount赋值给迭代器的局部变量expectedModCount 在迭代的过程中modCount != expectedModCount快速抛出异常.

2.3.1 多线程环境下

Java集合(一) _ JavaClub全栈架构师技术笔记

启动两个线程,分别对其中一个对list进行添加,另一个线程对list进行迭代的,结果也是抛出了java.util.ConcurrentModificationException。

Java集合(一) _ JavaClub全栈架构师技术笔记

在ArrayList中,当调用list.iterator()时。

   public Iterator<E> iterator() {
        return new Itr();
    }

 它会创建并返回Itr类的对象,而Itr类是ArrayList的内部类,并且实现了Iterator接口。创建Itr对象时会去获取modCount值并赋值到expectedModCount。

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}
    }

在执行next()方法时,会去判断modCount和expectedModCount是否相等,不相等则执行fail-fast机制。

    public E next() {
            checkForComodification();//判断modCount!=expectedModCount
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

   final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

作者:不忙时都很闲
来源链接:https://blog.csdn.net/qq_47375994/article/details/125011640

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/17244.html

标签: Java集合Java
分享给朋友:

“Java集合(一)” 的相关文章

Java空指针异常解决java.lang.NullPointerException解决心得

Java空指针异常解决java.lang.NullPointerException解决心得

今天做课设的时候运行程序报出以下错误 java.lang.NullPointerException 首先要理解的是此错误并不会在 程序中报错,只会在运行的时候报错。 是由于某个参数(集合,数组等数据)可能出现一个null值而导致后面的程序不能运行时...

一分钟搞定Java环境变量配置

一分钟搞定Java环境变量配置

对于学Java的人来说,成功配置环境变量是第一步,因为后期不论 你做什么工作,会发现都需要这些,接下来介绍如何安装与配置,我按照jdk1.6来说明,其他一致。 下载官网 首先将jdk安装好后进行配置。 右击“计算机”,右键打开“属性”,...

Java实现Email发送

一、前言最近将项目的登录密码从图形验证码改为了短信验证码,同时也将忘记密码时长度进行了修改,在修改时,想到了之前在一些国外的网站上,使用过邮箱接收验证码的情况,故想到何妨不自己尝试整合一下Java程序发送邮件信息呢,所以动手整合了Email的发送实例。二、Email发送协议想要在互联网上提供电子邮件...

Java中四种访问修饰符的区别

在java中共有4种访问级别,按访问权限由高到低为:public(公有的)、protected(受保护的)、友好的(没有任何访问权限关键字修饰)和private(私有的)。 类型 类内部 同一个包其...

全面了解 Java 原子变量类

📦 本文以及示例源码已归档在 javacore 一、原子变量类简介 为何需要原子变量类 保证线程安全是 Java 并发编程必须要解决的重要问题。Java 从原子性、可见性、有序性这三大特性入手,确保多线程的数据一致性。 确保线程安全最...

Java 并发核心机制

Java 并发核心机制

📦 本文以及示例源码已归档在 javacore 一、J.U.C 简介 Java 的 java.util.concurrent 包(简称 J.U.C)中提供了大量并发工具类,是 Java 并发能力的主要体现(注意,不是全部,有部分并发能力的支持在其他包中)。...

Java 内存模型

Java 内存模型

📦 本文以及示例源码已归档在 javacore Java 内存模型(Java Memory Model),简称 JMM。 JVM 中试图定义一种 JMM 来屏蔽各种硬件和操作系统的内存访问差异,以实现让 Java 程序在各种平台下都能达到一致的内存访问效果。...

Java日志框架那些事儿

Java日志框架那些事儿

在项目开发过程中,我们可以通过 debug 查找问题。而在线上环境我们查找问题只能通过打印日志的方式查找问题。因此对于一个项目而言,日志记录是一个非常重要的问题。因此,如何选择一个合适的日志记录框架也非常重要。在Java开发中,常用的日志记录框架有JDKLog、Log4J、LogBack、SLF4J...

冒泡排序的原理,思路,以及算法分析(Java实现)

冒泡排序的原理,思路,以及算法分析(Java实现)

冒泡排序 如果遇到相等的值不进行交换,那这种排序方式是稳定的排序方式。 1.原理:比较两个相邻的元素,将值大的元素交换到右边 2.思路:依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。 (1)第一次比较:首先比较第...

Java实现阶乘运算

n!=123*…n 学习编程就是要了解从问题到程序是如何实现的 Scanner in=new Scanner(System.in); int n ; n=in.nextInt(); // int i=1; int factor=1;...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。