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

Java集合

2022年09月16日 21:37:02Java技术9

1.集合

Java集合 _ JavaClub全栈架构师技术笔记
image.png

1. List:有序、可重复。可以通过索引快速查找,但进行增删操作时后续的数据需要移动,所以增删速度慢。

2. Set:无序、不可重复。

3. Map:键值对、键唯一、值不唯一。Map 集合中存储的是键值对,键不能重复,值可以重复。根据键得到值,对 map 集合遍历时先得到键的 set 集合,对 set 集合进行遍历,得到相应的值。

4. ArrayList: ArrayList 实现于 List、RandomAccess 接口,具有list的特性,有序,可以重复,并且可以插入空数据,也支持随机访问。ArrayList相当于动态数据(动态数组),其中最重要的两个属性分别是: elementData 数组,以及 size 大小,ArrayList 的主要消耗是数组扩容来在指定位置添加数据。增删是数组复制的过程,效率比较慢,但查询比较快。

5. Vector: Vector 也是实现于 List 接口,底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据,但是开销较大,所以 Vector 是一个同步容器并不是一个并发容器。

6. LinkedList: LinkedList 底层是基于双向链表实现的,也是实现了 List 接口,所以也拥有 List 的一些特点, 可见每次插入都是移动指针,和 ArrayList 的拷贝数组来说效率要高上不少。

  • LinkedList 插入,删除都是移动指针效率很高。
  • 查找需要进行遍历查询,效率较低。

7. HashSet: HashSet 实现了list接口,具有list的一些特点,是一个不允许存储重复元素的集合,它的实现比较简单,只要理解了 HashMap,HashSet 就水到渠成了。比较关键的就是这个 add() 方法。 可以看出它是将存放的对象当做了 HashMap 的健,value 都是相同的 。由于 HashMap 的 key 是不能重复的,所以每当有重复的值写入到 HashSet 时,value 会被覆盖,但 key 不会受到影响,这样就保证了 HashSet 中只能存放不重复的元素。
HashSet 的原理比较简单,几乎全部借助于 HashMap 来实现的。
所以 HashMap 会出现的问题 HashSet 依然不能避免。

8. HashMap: HashMap 底层是基于数组和链表实现的

Java集合 _ JavaClub全栈架构师技术笔记
image.png

每个绿色的实体是嵌套类 Entry 的实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的 next。

根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。

为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

Java集合 _ JavaClub全栈架构师技术笔记
image.png

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点,Java8 中使用 Node,基本没有区别,都是 key,value,hash 和 next 这四个属性,不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。
其中有两个重要的参数

  • 容量
  • 负载因子

容量的默认大小是 16,负载因子是 0.75,当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。
由于数组的长度有限,所以难免会出现不同的 Key 通过运算得到的 index 相同,这种情况可以利用链表来解决,
在并发环境下使用 HashMap 容易出现死循环。
并发场景发生扩容,调用 resize() 方法里的 rehash() 时,容易出现环形链表。这样当获取一个不存在的 key时,计算出的 index 正好是环形链表的下标时就会出现死循环。 所以 HashMap 只能在单线程中使用,并且尽量的预设容量,尽可能的减少扩容。

9. LinkedHashMap:它的底层是继承于 HashMap 实现的,由一个双向链表所构成。

LinkedHashMap 的排序方式有两种:

  • 根据写入顺序排序。

  • 根据访问顺序排序。

其中根据访问顺序排序时,每次 get 都会将访问的值移动到链表末尾,这样重复操作就能得到一个按照访问顺序排序的链表。总的来说 LinkedHashMap 其实就是对 HashMap 进行了拓展,使用了双向链表来保证了顺序性。

因为是继承与 HashMap 的,所以一些 HashMap 存在的问题 LinkedHashMap 也会存在,比如不支持并发等。

10. ConcurrentHashMap(线程安全的并发容器):

Java集合 _ JavaClub全栈架构师技术笔记
image.png

是由 Segment 数组、HashEntry 数组组成,和 HashMap 一样,仍然是数组加链表组成。ConcurrentHashMap 采用了分段锁技术,其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment。

Java集合 _ JavaClub全栈架构师技术笔记
image.png

1.8 中的 ConcurrentHashMap 数据结构和实现与 1.7 还是有着明显的差异。其中抛弃了原有的 Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。

红黑树
R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。
红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意:
(01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
(02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

Java集合 _ JavaClub全栈架构师技术笔记
image.jpeg

红黑树的时间复杂度为: O(lgn)

2. ArrayList 和 LinkedList 有何区别?

ArrayList 是基于动态数组的数据结构,LinkedList 是基于链表的数据结构;对于随机访问 get 和 set,ArrayList 较优, 是基于索引 (index) 的数据结构,它使用索引在数组中搜索和读取数据是很快的。 Array 获取数据的时间复杂度是 O(1), 但是要删除数据却是开销很大的,因为这需要重排数组中的所有数据,因为 LinkedList 要移动指针。;对于新增和删除操作 add 和 remove,LinedList 较优,只需要改变指针即可,因为ArrayList 要移动数据

3. HashMap 和 Hashtable 的区别?

HashMap 允许空键值,Hashtable 不允许;
HashMap 继承自 AbstractMap,Hashtable 继承自 Dictionary 类,两者都实现了 Map 接口; HashMap 的方法不是同步的,Hashtable 的方法是同步的(效率较差,不建议使用)。
HashMap和Hashtable都实现了Map接口
HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。

  1. HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
  2. 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
  3. 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
  4. HashMap不能保证随着时间的推移Map中的元素次序是不变的。

4. Iterater 和 ListIterator 之间有什么区别?

Iterator 用来遍历 Set 和 List 集合,而 ListIterator 只能遍历 List; Iterator 只可以向前遍历,而 LIstIterator 可以双向遍历;ListIterator 从 Iterator 接口继承,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置

5. Arraylist和vector区别

数据增长:Vector增长原来的一倍,ArrayList增加原来的0.5倍。
同步性:Vector是线程安全的 Arraylist是不安全的。

6. HashMap和TreeMap区别

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

HashMap:数组方式存储key/value,线程非安全,允许null作为key和value,key不可以重复,value允许重复,不保证元素迭代顺序是按照插入时的顺序,key的hash值是先计算key的hashcode值,然后再进行计算,每次容量扩容会重新计算所以key的hash值,会消耗资源,要求key必须重写equals和hashcode方法

默认初始容量16,加载因子0.75,扩容为旧容量乘2,查找元素快,如果key一样则比较value,如果value不一样,则按照链表结构存储value,就是一个key后面有多个value;

TreeMap:基于红黑二叉树的NavigableMap的实现,线程非安全,不允许null,key不可以重复,value允许重复,存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口,会按照排序后的顺序迭代元素,两个相比较的key不得抛出classCastException。主要用于存入元素的时候对元素进行自动排序,迭代输出的时候就按排序顺序输出

ArrayList的扩容方式和扩容时机

引用:https://blog.csdn.net/zhou920786312/article/details/83750032

初始化

ArrayList的底层是一个动态数组,ArrayList首先会对传进来的初始化参数initalCapacity进行判断

  • 如果参数等于0,则将数组初始化为一个空数组,
  • 如果不等于0,将数组初始化为一个容量为10的数组。

扩容时机

当数组的大小大于初始容量的时候(比如初始为10,当添加第11个元素的时候),就会进行扩容,新的容量为旧的容量的1.5倍。

扩容方式

扩容的时候,会以新的容量建一个原数组的拷贝,修改原数组,指向这个新数组,原数组被抛弃,会被GC回收。

ArraList初始化容量判断
//ArraList初始化容量判断
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0 : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

//添加元素的方法
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

//判断是否需要扩容
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//扩容的机制
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

作者:π。
来源链接:https://www.cnblogs.com/wuhen8866/p/11861821.html

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

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


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

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

“Java集合” 的相关文章

Java 并发核心机制

Java 并发核心机制

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

java中将英尺换算为身高

java中将英尺换算为身高

直接上代码 如图所示便是身高的换算,你学到了吗?、 int foot; double inch; Scanner in=new Scanner(System.in); foot=in.nextInt(); inch=in.nextDouble...

Java开发手册精华总结

Java开发手册精华总结

阿里 Java 开发手册的思考总结 一个优秀的工程师和一个普通的工程师的区别,不是满天飞的架构图,他的功底体现在所写的每一行代码上。 -- 毕玄 1. 命名风格 【书摘】类名用 UpperCamelCase 风格,比如 DO/BO/VO...

Java Web 工作技巧总结 16.8

Java Web 工作技巧总结 16.8

摘要: 原创出处:www.bysocket.com 泥瓦匠BYSocket 希望转载,保留摘要,谢谢! 四时不谢之兰,百节长青之竹,万古不败之石,千秋不变之人。 1. AOP – LOG 项目中,一个请求过来,一个响应回去。...

JAVA UUID 生成唯一标识

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket Reprint it anywhere u want 需求     项目在设计表的时候,要处理并发多...

编写高质量代码改善java程序的151个建议——[52

编写高质量代码改善java程序的151个建议——[52

原创地址:   http://www.cnblogs.com/Alandre/  (泥沙砖瓦浆木匠),需要转载的,保留下! Thanks Although the world is full of...

java总结文章

java总结文章

java总结文章 原创地址: http://www.cnblogs.com/Alandre/ (泥沙砖瓦浆木匠),需要转载的,保留下! Thanks Talk is cheap. Show me the...

[Java 泥水匠] Java Components 之二:算法篇之项目实践中的位运算符(有你不懂的哦)

[Java 泥水匠] Java Components 之二:算法篇之项目实践中的位运算符(有你不懂的哦)

作者:泥沙砖瓦浆木匠 网站:http://blog.csdn.net/jeffli1993 个人签名:打算起手不凡写出鸿篇巨作的人,往往坚持不了完成第一章节。 交流QQ群:【编程之美 365234583】http://qm.qq.com/cgi-bin/qm/qr?k=...

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

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

Java实现ModbusTCP通信

Java实现ModbusTCP通信

使用ModbusTCP实现和硬件设备通信 有问题可以私信和评论,看到会回复。 一个项目,需要用Java实现使用ModbusTCP和硬件设备通信 视频地址:https://www.bilibili.com/video/BV1cz4y1R7cg...

发表评论

访客

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