编程技术是改变世界的力量。
本站
当前位置:网站首页 > 后端语言 > 正文

JAVA集合 java集合转为数组

gowuye 2024-04-04 11:55 11 浏览 0 评论

JAVA集合

1. 接口集成关系和实现

集合类存放于Java.util 包中,主要有3 种:set(集)、list(列表包含Queue)和map(映射)。

1. Collection:Collection 是集合List、Set、Queue 的最基本的接口。

2. Iterator:迭代器,可以通过迭代器遍历集合中的数据

3. Map:是映射表的基础接口

2. 常见的集合数据

我们常见的集合数据有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点:

2.1数组结构: 存储区间连续、内存占用严重、空间复杂度大

优点:随机读取和修改效率高,原因是数组是连续的(随机访问性强,查找速度快)

缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定不易动态扩展。

2.2链表结构:存储区间离散、占用内存宽松、空间复杂度小

优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活

缺点:不能随机查找,每次都是从第一个开始遍历(查询和修改效率低)

2.3哈希表结构:结合数组结构和链表结构的优点,从而实现了查询和修改效率高,插入和删除效率也高的一种数据结构。而我们常见的HashMap就是这样的一种数据结构。后面会详细的总结hashmap的知识。

3. List相关知识

Java 的List 是非常常用的数据类型。List 是有序的Collection。Java List 一共三个实现类:分别是ArrayList、Vector 和LinkedList。

ArrayList 是最常用的List 实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要将已经有数组的数据复制到新的存储空间中。当从ArrayList 的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。

Vector 与ArrayList 一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList 慢。

LinkedList 是用链表结构存储数据的,很适合数据的动态插入和删除,随机访问和遍历速度比较慢。另外,他还提供了List 接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。

4. set相关知识

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素,值不能重复。对象的相等性本质是对象hashCode 值(java 是依据对象的内存地址计算出的此序号)判断的,如果想要让两个不同的对象视为相等的,就必须覆盖Object 的hashCode 方法和equals 方法。

3.1HashSet

哈希表存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序(和List 显然不同) 而是按照哈希值来存的,所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值,如果哈希值一样,接着会比较equals 方法 如果 equls 结果为true ,HashSet 就视为同一个元素。如果equals 为false 就不是同一个元素。哈希值相同equals 为false 的元素是怎么存储呢,就是在同样的哈希值下顺延(可以认为哈希值相同的元素放在一个哈希桶中)。也就是哈希一样的存一列。如图1 表示hashCode 值不相同的情况;图2 表示hashCode 值相同,但equals 不相同的情况。

HashSet 通过hashCode 值来确定元素在内存中的位置。一个hashCode 位置上可以存放多个元素。

3.2 TreeSet()

1. TreeSet()是使用二叉树的原理对新add()的对象按照指定的顺序排序(升序、降序),每增加一个对象都会进行排序,将对象插入的二叉树指定的位置。

2. Integer 和String 对象都可以进行默认的TreeSet 排序,而自定义类的对象是不可以的,自己定义的类必须实现Comparable 接口,并且覆写相应的compareTo()函数,才可以正常使用。

3.在覆写compare()函数时,要返回相应的值才能使TreeSet 按照一定的规则来排序

4.比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。

3.3 LinkedHashSet ()

对于LinkedHashSet 而言, 它继承与HashSet 、又基于LinkedHashMap 来实现的。

LinkedHashSet 底层使用LinkedHashMap 来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet 相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap 来实现,在相关操作上与父类HashSet 的操作相同,直接调用父类HashSet 的方法即可。

5. Map相关知识

HashMap 根据键的hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为null,允许多条记录的值为null。HashMap 非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections 的synchronizedMap 方法使HashMap 具有线程安全的能力,或者使用ConcurrentHashMap。

5.1在new HashMap时指定数组长度为13,此时数组的长度是13吗?

明显这是一个坑,因为HashMap的数组长度只能是2的n次幂的数。而且当我们把指定容量以new HashMap(13)的方式传进构造方法之后,构造方法会调用tableSizeFor方法进行处理,把处理之后的结果再赋给threshold属性.。
tableSizeFor方法生成的值是指定容量的值往上找最近的2次幂的数:比如13 -> 16;17 -> 32;通过threshold()上的注释也可以看出,返回的是一个2的次幂的数。

注意: 数组是在put操作的时候才创建,而不是new HashMap的时候。


5.2为什么数组的大小必须是2的次幂?

在put操作的源码中可以看到下标是(数组长度 -1) & hash值按位与生成的。


由上图可知,左半部的计算的结果是hash值的后几位,右半部个别的二进制位经过计算后发生了改变。因为不是2的次幂的数减一之后对应的二进制数里肯定有为0的二进制位,这样不管hashcode对应的二进制位是1还是0,计算后的结果肯定为0,这样就导致元素分布的不够散列,使得Nodes[] tab数组上有些位置一直都为null,链表就会变得较长,增大了hash碰撞的概率,就会出现性能问题。

5.3那为什么不一开始就用红黑树,反而要经历一个转换的过程呢?

红黑树是一个特殊的平衡二叉树,查找的时间复杂度是 O(logn) ;而链表查找元素的时间复杂度为 O(n),远远大于红黑树的 O(logn),尤其是在节点越来越多的情况下,O(logn) 体现出的优势会更加明显;简而言之就是为了提升查询的效率。

其实在 JDK 的源码注释中已经对这个问题作了解释:单个 TreeNode 需要占用的空间大约是普通 Node 的两倍,所以只有当包含足够多的 Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值(默认值8)决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式,以便节省空间,这个阈值是 UNTREEIFY_THRESHOLD(默认值6)。

5.4为什么链表的长度要大于8才转为红黑树?转换阈值8是怎么来的?

如果 hashCode 分布良好,也就是 hash 计算的结果离散好的话,那么红黑树这种形式是很少会被用到的,因为各个值都均匀分布,很少出现链表很长的情况。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从链表向红黑树的转换。

事实上,链表长度超过 8 就转为红黑树的设计,更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长,从而导致查询效率低,而此时转为红黑树更多的是一种保底策略,用来保证极端情况下查询的效率。

5.5链表长度大于8就一定会转红黑树吗?

其实链表长度大于8时不一定会转红黑树。原因我们可以看putVal的源码中找到答案:


通过上面代码可以发现,不一定会立马红黑树,如果数组长度小于64,先尝试扩容,解决链表过长的问题。所以只有链表长度大于8,数组长度大于等于64的时候才会立马转成红黑树。

5.5 HashMap在什么情况下会扩容,怎么扩容?

当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。执行put方法时,如果当前的数组里的元素个数大于阈值(阈值=数组长度 x 负荷因子),就会执行resize()方法扩容。扩容的方法也很简单,创建一个比原来数组容量大两倍的新数组,遍历原来的数组,把原来数组上的元素重新按位与运算,放到新数组上。

6. 聊聊 ConcurrentHashMap 这个类

众所周知,在 Java 中,HashMap 是非线程安全的,如果想在多线程下安全的操作 map,主要有以下解决方法:

第一种方法,使用Hashtable线程安全类;

第二种方法,使用Collections.synchronizedMap方法,对方法进行加同步锁;

第三种方法,使用并发包中的ConcurrentHashMap类;

Hashtable 是遗留类,很多映射的常用功能与HashMap 类似,不同的是它承自Dictionary 类,Hashtable 是一个线程安全的类,Hashtable 几乎所有的添加、删除、查询方法都加了synchronized同步锁!相当于给整个哈希表加了一把大锁,多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞等待需要的锁被释放,在竞争激烈的多线程场景中性能就会非常差,所以 Hashtable 不推荐使用!

再来看看第二种方法,使用Collections.synchronizedMap方法,我们打开JDK源码,可以很清晰的看到,如果传入的是 HashMap 对象,其实也是对 HashMap 做的方法做了一层包装,里面使用对象锁来保证多线程场景下,操作安全,本质也是对 HashMap 进行全表锁!使用Collections.synchronizedMap方法,在竞争激烈的多线程环境下性能依然也非常差,所以不推荐使用!

再来看看第三种方法,使用并发包中的ConcurrentHashMap类!JDK1.7版本ConcurrentHashMap 类所采用的正是分段锁的思想,将 HashMap 进行切割,把 HashMap 中的哈希数组切分成小数组,每个小数组有 n 个 HashEntry 组成,其中小数组继承自ReentrantLock(可重入锁),这个小数组名叫Segment, 如下图:


JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁,采用 CAS + synchronized 来保证并发安全,数据结构 jdk1.8 中 HashMap 结构类似,都是数组 + 链表(当链表长度大于8时,链表结构转为红黑二叉树)结构。ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点,只要节点 hash 不冲突,就不会产生并发,相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍!

从源码1.7上可以看出,ConcurrentHashMap 初始化方法有三个参数,initialCapacity(初始化容量)为16、loadFactor(负载因子)为0.75、concurrentLevel(并发等级)为16,如果不指定则会使用默认值。其中,值得注意的是 concurrentLevel 这个参数,虽然 Segment 数组大小 ssize 是由 concurrentLevel 来决定的,但是却不一定等于 concurrentLevel,ssize 通过位移动运算,一定是大于或者等于 concurrentLevel 的最小的 2 的次幂!通过计算可以看出,按默认的 initialCapacity 初始容量为16,concurrentLevel 并发等级为16,理论上就允许 16 个线程并发执行,并且每一个线程独占一把锁访问 Segment,不影响其它的 Segment 操作!

详细的介绍请参看https://www.cnblogs.com/dxflqm/p/12118038.html

7. 聊聊LinkedHashMap

LinkedHashMap继承于HashMap,首先使用super调用了父类HashMap的构造方法,其实就是根据初始容量、负载因子去初始化Entry[] table,然后把accessOrder设置为false,这就跟存储的顺序有关了,LinkedHashMap存储数据是有序的,而且分为两种:插入顺序和访问顺序。这里accessOrder设置为false,表示不是访问顺序而是插入顺序存储的,这也是默认值,表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap其实就是可以看成HashMap的基础上,多了一个双向链表来维持顺序。



相关推荐

爱上开源之golang入门至实战第四章-切片(Slice)

前言Go数组的长度不可改变,在特定场景中这样的集合就不太适用,Go中提供了一种灵活,功能强悍的内置类型切片("动态数组"),与数组相比切片的长度是不固定的,可以追加元素,在追加时可...

Go语言入门必知教程-切片

切片是一种灵活的和可扩展的数据结构,用于实现和管理数据集。切片由多个元素组成,所有元素都是相同类型的。切片是动态数组的一部分,可以根据需要进行增长和收缩。与数组一样,切片也可以索引。切片具有容量和长度...

Go语言基础-切片

切片是什么?切片是Go语言的一种数据结构。和数组相似,不过切片可以在它的结尾增加更多的元素。这样可变长度在实际编程中更为有用。声明切片切片的声明和数组也很相似,只是声明切片时不需要指定大小。例:va...

5分钟掌握GO中切片的基本使用方法

最近Golang越来越火,不少小伙伴都纷纷开始学习Golang,但对于原先为C++或者JAVA的同学,用习惯了数据、list、vector等,会对Go的切片slice不习惯,下面整理出go中slice...

揭秘 Go 切片(Slice)的秘密

当向切片添加新参数时,底层数组会发生什么变化?它会扩展以容纳更多元素吗?在这篇文章中,我们将深入探讨切片的内部工作原理,以及如何利用这些知识来进行更好的内存管理和性能优化。具体而言,我们将探索Go...

【Go语言slice详解】深入掌握Go语言中的slice类型及常用操作!

Go语言中的slice(切片)是一种非常方便的数据结构,可以动态地增加或减少其元素数量,且可以访问底层数组的任意一个子序列。本文将对Go语言中的slice进行详细的讲解。Slice的定义在Go语言中,...

掌握GO中的Slice,这就够了

最近Golang越来越火,不少小伙伴都纷纷开始学习Golang,但对于原先为C++或者JAVA的同学,用习惯了数据、list、vector等,会对Go的切片slice不习惯,下面整理出go中slice...

golang2021面向对象(26)Go语言类型内嵌和结构体内嵌

结构体可以包含一个或多个匿名(或内嵌)字段,即这些字段没有显式的名字,只有字段的类型是必须的,此时类型也就是字段的名字。匿名字段本身可以是一个结构体类型,即结构体可以包含内嵌结构体。?可以粗略地将这个...

2022-11-13:以下go语言代码中,如何获取结构体列表以及结构体内

2022-11-13:以下go语言代码中,如何获取结构体列表以及结构体内的指针方法列表?以下代码应该返回{"S1":["M1","M2"],"S...

Go语言文件和目录操作

文件和目录操作概述一、文件和目录操作概述在计算机中,文件和目录是存储数据的重要方式。在Go语言中,我们可以使用os和io/ioutil包提供的函数和结构体来进行文件和目录操作。本文将详细介绍Go语言中...

跟我一起学习go语言(五)golang中结构体的初始化方法

1、自定义一个结构体typeVertexstruct{X,Yfloat64}2、初始化方法-指针:rect1:=new(Vertex)rect2:=&Vertex...

Go复合数据类型:结构体

一种通用的、对实体对象进行聚合抽象的能力,在Go中,提供这种聚合抽象能力的类型是结构体类型,也就是struct。自定义一个新类型在Go中,我们自定义一个新类型一般有两种方法。第一种是类型定义...

Go语言基础:方法

导读在阅读本文章前,假定你具备如下能力:?已掌握结构体1.方法1.1方法的概念在理解程序中方法的概念时,我们先看看现实中的一些情况,这样相对比较好理解一些。在农村的朋友可能会知道,在医疗落后的情况...

为什么 Go 语言 struct 要使用 tags

在Go语言中,struct是一种常见的数据类型,它可以用来表示复杂的数据结构。在struct中,我们可以定义多个字段,每个字段可以有不同的类型和名称。除了这些基本信息之外,Go还提供了s...

一文带你掌握掌握 Golang结构体与方法

1.Golang结构体的概念及定义结构体是Golang中一种复合类型,它是由一组具有相同或不同类型的数据字段组成的数据结构。结构体是一种用户自定义类型,它可以被用来封装多个字段,从而实现数据的...

取消回复欢迎 发表评论: