当前位置:首页 > Java技术 > JAVA集合分析

JAVA集合分析

2022年11月07日 17:31:11Java技术24

说明:本文是我对自己学习知识的一个简单总结,可能存在许多不足,我希望通过此方式来回顾知识,加强理解,也希望大家能指出文中的错误与不足,互相学习,谢谢。

1.集合Collection分析

在开始说集合之前我们先看一下什么是变量,变量是由变量类型+变量名称组成,变量是用来保存信息的载体。那再看看集合,集合是由集合存储的类型+集合名称组成,简单来说就是存储一类数据的容器,在java中集合的父类是Collection(还有Map集合),集合属于数据结构的一种,在计算机中怎样存储数据考虑的就是通过怎样的数据结构更合理的将数据存储在计算机中。所以集合有不同的子类,通过不同的数据结构来存储数据。
下面是我总结的集合粗略体系图。

JAVA集合分析 _ JavaClub全栈架构师技术笔记

我们先对比查看一下Collection接口。

JAVA集合分析 _ JavaClub全栈架构师技术笔记

如上图所示,在jdk1.8版本中比jdk1.7版本多了几个方法,我们以一种一个方法为例说明。

 default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }

2.List集合分析

之前的接口中,定义的是方法,而具体的实现则由子类完成,但是我们可以看到的是在这个Collection接口里面竟然有方法体实现,这是jdk1.8出来的新特性,在接口中可以由default(或者static)开头定义方法和方法体,那为什么有这样的特性呢?那是因为这样可以扩展接口的方法【这里扩展了Stream的功能】而不会破坏原有的继承体系,如果没有这个特性,那么只要是实现了Collection这个接口的子类也必须重写这些扩展的方法。在面向对象的编程中,我们需要遵守的法则是开闭原则,对修改封闭,对扩展放开。
现在我们查看一下集合中重要的两个子类,LinkList、 ArrayList,下面是他们的类图。

JAVA集合分析 _ JavaClub全栈架构师技术笔记

从类图中可以看出,集合的顶层接口是Collection,接下来是实现Collection接口的AbstractCollection和AbstractList,这两个类实现了Collection中的大部分方法,并定义了一些模板,子类只需要实现实现模板中的方法即可完成集合中的大部分操作了。

这里引出了设计模式-模板方法模式(定义了一套算法流程,里面实现了大部分方法,子类实现其中的小部分方法就可以实现整个流程)。

  • Collection代表的子类有ArrayList LinkList, ArrayList底层是通过数组方式实现,它的初始容量大小为10,以0.5的增装因子扩容,扩容时通过调用native方法复制数据(native方法是用来访问C语言代码的桥梁,Java是通过JVM访问内存的,C语言直接访问内存,所以为了解决JAVA的一些操作慢的问题,引入了Native方法),为了保障效率,一般给它一定的大小(根据数据量来计算)避免底层复制,由于底层是数组,存储的内存空间连续,对于查找操作,时间复制度为O(1)而删除和新增节点比较耗时。
  • LinkList通过链表形式存储数据,地址空间不连续,每一个节点为一个Node,数据通过Node连接,相比于ArrayList删除和新增操作效率更高,查找效率低。

补充:由上图可知LinkList实现了Deque(双端队列),即可以从头或从尾添加节点。分别为linkFirst(E e)方法与linkLast(E e)方法。

3.Set集合分析

从源码中定义可知,Set是一个没有包含重复元素的集合。它可以存入为null的元素,元素的类型可以不一样。但是不能保证顺序。

JAVA集合分析 _ JavaClub全栈架构师技术笔记

  • 这里简单分析下HashSet,从HashSet源码中可以知道它间接实现了Collection接口,所有具有添加、删除、得到集合大小等基本方法。HashSet它不能保证插入的顺序和遍历时一样,因为它是基于Hash值来存放元素的(HashSet构造方法中其实调用的是HashMap实例,HashMap是可以运行键值都为null,线程不安全),同时多线程访问时会有线程安全问题,要注意。
  • TreeSet相比于HashSet最大的不同是它可以保证添加元素的顺序,TreeSet的构造方法中创建了TreeMap实例(TreeMap是一个基于红黑树的实现)。
  • 注意点:在集合中进行遍历时候操作,如果操作不当会抛出异常。
//这段代码在遍历时候删除元素没有问题
ArrayList<Integer> list = ArrayList();
list.add();
list.add();
list.add();
list.add();
(i=0; i<list.size(); i++){
    list.remove(i);
    //下面这种输出remove移除的元素,但这里却只输出1 3。因为第一个元素移除后,第二个元素跑到第一个元素位置上,
    //后面元素依次前移,所以只输出1 3。
    //System.out.println(list.remove(i)); 
}
================华丽的分割线===================
//这段代码在遍历时候删除元素会报错(ConcurrentModificationException),这里涉及到一个名词,快速失败。
(Integer integer:list){
    list.remove(integer);
}

上面使用迭代器方式遍历删除元素时候,不允许对集合中元素增加或者删除。具体实现可以查看集合源码,这里就不做扩展了。

4.集合Map分析

  • Map集合里面提供三种集合视图,分别是键的集合,值的集合与键值对形式的集合,由源码定义可知,map集合的key值不能重复。
  • Map集合的代表子类有HashMap HashTable。这里简单介绍下这两种集合的不同之处,通过这些比较选择使用的场景。
    这两种MAP存储的数据结构都是通过数组+链表的形式(jdk1.7中),结构如下图;在jdk1.8中HashMap数据结构是数组+链表+红黑树。存储数据都是先通过hash函数计算出键在数组中的具体位置,然后存入数据,当数组同一个位置插入两个值时,如果两个值不同,将以链表形式连接起来(jdk1.7是头部插入法)。
    JAVA集合分析 _ JavaClub全栈架构师技术笔记
  • HashMap中存储的键和值可以为null,而HashTable不能。
  • HashMap中存在线程安全问题,put操作时没有加锁,当多个线程同时操作时可能导致值的丢失(比如当两个线程同时存入数据时,当它们的key的hash相同,值不同时,就有可能导致其中一个值被覆盖),jdk1.7中多线程操作还可能导致链表的死循环【可以自行查询】。HashTable线程安全,但是速度慢。
  • HashMap初始容量为16,加载因子为0.75:即当 元素个数 超过 容量长度的0.75倍 时,进行扩容,扩容为原来的两倍。HashTable初始容量为11,加载因子0.75,扩容大小为原来的两倍+1.

补充:

1.HashMap和HashTable的键均通过hash函数去映射到数组中。Hash函数在使用时候会有hash冲突,即两个不同键通过hash函数转换后地址相同,所以为了减少hash冲突,一般来说可以通过优化hash函数来减少冲突,比如HashMap、HashTable中的链地址法(数组+链表)。

2.HashMap的容量必须为2的幂,是因为为了提高计算效率,也是为了减少hash冲突。例如HashMap容量为16二进制为10000,通过这个算式tab[i = (n - 1) & hash] ,n-1后二进制为1111。这里假设hash值为1111和1110
JAVA集合分析 _ JavaClub全栈架构师技术笔记
当容量不为2的幂时,比如容量为15,二进制1111,n-1后二进制1110,假设hash值为1111和1110
JAVA集合分析 _ JavaClub全栈架构师技术笔记
由上可知,当容量不为2的幂时得出的结果均为1110,也就是发生了冲突。容量为2的幂就是因为能够减少冲突,使其分配均匀。
JAVA集合分析 _ JavaClub全栈架构师技术笔记
3.HashMap可以通过构造函数初始化容量大小,那是怎么保证容量为2的幂呢?如下代码

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

通过上面的运算即可将输入的容量大小转换为大于等于它的2的幂的数。

4.key相同,hash值一定相同,hash值相同,key不一定相同。HashMap中如果key相同,那么后面put进去的值就会覆盖原来的值,如果想实现key相同,值不覆盖,那么可以使用google提供的类Multimap,它的数据结构可以是一个key对应多个值。
JAVA集合分析 _ JavaClub全栈架构师技术笔记

作者:安安静静写bug
来源链接:https://blog.csdn.net/qq_37803406/article/details/103759379

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

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


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

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

“JAVA集合分析” 的相关文章

深入理解 Java 并发锁

深入理解 Java 并发锁

📦 本文以及示例源码已归档在 javacore 一、并发锁简介 确保线程安全最常见的做法是利用锁机制(Lock、sychronized)来对共享数据做互斥同步,这样在同一个时刻,只有一个线程可以执行某个方法或者某个代码块,那么操作必然是原子性的,线程安全的...

Java实现阶乘运算

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

Java打印车票主要学习Java的比较语句

直接上代码 public static void main(String[] args) { // TODO Auto-generated method stub //初始化 Scanner in=new Scanner(S...

Java对象的大小

基本数据的类型的大小是固定的,这里就不多说了。对于非基本类型的Java对象,其大小就值得商榷。 在Java中,一个空Object对象的大小是8byte,这个大小只是保存堆中一个没有任何属性的对象的大小。看 下面语句: Object ob = new Ob...

java泛型通配符详解

java泛型通配符详解

前言 泛型带来的好处 泛型中通配符 常用的 T,E,K,V,? ?无界通配符 上界通配符 < ? extends E> 下界通配符 < ? super E>...

java空指针异常:java.lang.NullPointException

一.什么是java空指针异常     我们都知道java是没有指针的,这里说的"java指针"指的就是java的引用,我们不在这里讨论叫指针究竟合不合适,而只是针对这个异常本身进行分析。空指针就是空引用,java空指针异常就是引用本身为空,却调用了方...

java 实现图片压缩

转载https://www.cnblogs.com/strongmore/p/14158639.html 添加依赖 <dependency> <groupId>net.coobird</groupId> <artifa...

Java并发之AQS详解

Java并发之AQS详解

java、多线程、并发、AbstractQueuedSynchronized、AQS、Lock、Mutex、ReentrantLock、Semaphore、CountDownLatch、线程同步 一、概述   谈到并发,不得不谈ReentrantLock;而谈到...

java如何防止反编译

java如何防止反编译

综述(写在前面的废话) Java从诞生以来,其基因就是开放精神,也正因此,其可以得到广泛爱好者的支持和奉献,最终很快发展壮大,以至于有今天之风光!但随着java的应用领域越来越广,特别是一些功能要发布到终端用户手中(如Android开发的app),有时候,公司为了商业技术的保密考...

JAVA面试精选【Java基础第一部分】

  这个系列面试题主要目的是帮助你拿轻松到offer,同时还能开个好价钱。只要能够搞明白这个系列的绝大多数题目,在面试过程中,你就能轻轻松松的把面试官给忽悠了。对于那些正打算找工作JAVA软件开发工作的童鞋们来说,当你看到这份题目的时候,你应该感动很幸运,因为,只要你把题目中...

发表评论

访客

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