单列集合与泛型

Collection集合

最近刚学Java,随便记点学习笔记

(资料图)

Collection下的两个大类:List(含ArrayList,LinkedLisk,Vector)和Set(含HashSet,LinkedHashSet,TreeSet)

List系列集合:添加的元素是有序(存和取的顺序是一样的),可重复,有索引Set系列集合:添加的元素是无序,不重复,无索引

Collection是单列集合的祖宗接口,它的功能是全部单列集合都可以继承使用的

注意:Collection是一个接口,我们不能直接创建他的对象.为了学习Collection接口里的方法这里按如下方式创建:

Collection的遍历方式

迭代器遍历

迭代器在Java中的类是Iterator,迭代器是集合专用的遍历方式,迭代器在遍历集合的时候是不依赖索引的

Collection集合获取迭代器:

方法名说明Iterator iterator()返回迭代器对象,默认指向当前集合的0索引

Iterator中常用方法

细节注意点:

遍历结束后再访问报错NoSuchElementExcpetion

迭代器遍历完毕,指针不会复位.要再次遍历需要重新创建迭代器对象

迭代器遍历时不能用集合的方法进行增加或删除,而用迭代器中的remove方法删除,如果要添加暂时没有办法

增强for遍历

底层就是迭代器,为了简化迭代器的代码书写的

它是JDK5之后出现的,内部原理就是一个Iterator迭代器

所有的单列集合和数组才能用增强for遍历

Lambda表达式遍历

得益于JDK8开始的新技术Lambda表达式提供了一种更简单,更直接的遍历集合的方式

List集合

Collection的方法List都继承了

List集合因为有索引,所以多了很多索引操作的方法

List集合系列删除元素的方法

直接删除元素

通过索引进行删除

注意上面会优先认为待删除的1是index在调用方法的时候,如果方法出现了重载现象,优先调用实参和形参一致的那个方法,如果要删除元素1,可以手动装箱:

List集合的遍历方式

迭代器遍历

列表迭代器遍历

增强for遍历

Lambda表达式遍历

普通for循环(因为List集合存在索引)

五种遍历方式对比:

数据结构

栈

后进先出,先进后出

队列

先进先出,后进后出

数组

查询快,增删慢

链表

链表中的结点时独立的对象,在内存中是不连续的,每个结点包含数据值和下一个结点的地址

查询慢,无论查询哪个数据都要从头开始找

红黑树

一种自平衡的二叉查找树,1972年出现,当时被称为平衡二叉B树,1978年被修改为如今的"红黑树"

是一种特殊的二叉查找树,红黑树的每一个结点上都有存储位表示结点的颜色

每一个结点可以使红或者黑,红黑树不是高度平衡的,它的平衡是通过"红黑规则"实现的

红黑规则

每一个结点或是红色的,或是黑色的

根节点必须是黑色

如果一个结点没有子节点或父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的

如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色结点相连的情况)

对每一个结点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色结点

默认颜色:红色(效率高)

ArrayList集合底层原理

利用空参创建的集合,在底层创建一个默认长度为0的数组

添加第一个元素时,底层会创建一个新的长度为10的数组

存满时,会扩容1.5倍

如果一次添加多个元素,1.5倍还放不下,则新创建数组的长度以实际为准

源码分析见P190

LinkedList集合

底层数据结构是双链表,查询慢,增删快,如果操作的是首尾元素,速度也是极快的

LinkedList本身多了很多直接操作首尾元素的特有API

并发修改异常底层原理集合底层有modCount变量记录集合变化的次数,每add一次或remove一次,这个变量都会自增,当我们创建迭代器对象的时候,就会把这个次数告诉迭代器调用next方法时会检测当前集合中最新的变化次数和一开始记录的次数是否相同,如果相同,证明当前集合没有发生改变,如果不一样,证明在迭代器遍历集合的过程中,使用了集合中的方法添加/删除了元素

如何避免并发修改异常:在使用迭代器或者是增强for遍历集合的过程中,不要使用集合的方法添加或删除元素

泛型

泛型是JDK5中引入的特性,可以在编译阶段约束操作的数据类型,并进行检查格式:<数据类型>注意:泛型只能支持引用数据类型

在JDK5前没有泛型的时候,集合如何存储数据?

结论:如果没有给集合指定类型,默认认为所有的数据类型都是Object类型,此时可以往集合中添加任意的数据类型,带来一个坏处:我们在获取数据的时候,无法使用他的特有行为

此时推出了泛型:可以在添加数据的时候就把类型进行统一,而且我们在获取数据的时候也省的强转了,非常的方便

泛型的好处:

统一数据类型

把运行时期的问题提前到了编译期间,避免了强制类型转换可能出现的异常,因为在编译阶段类型就能确定下来

Java中的泛型是伪泛型

在编译的时候,会检查集合中的元素是否与泛型匹配,但是生成的class文件并没有泛型,此过程成为泛型的擦除

泛型的细节

泛型中不能写基本数据类型,而要写包装类

指定泛型的具体类型后,传递数据时,可以传入该类型或者其子类类型

如果不写泛型,类型默认是Object

泛型类

使用场景:当一个类中,某个变量的数据类型不确定时,就可以定义带有泛型的类

泛型方法

方法中形参类型不确定时

方案1:可以使用类名后面定义的泛型(所有方法都能用)

方案2:在方法声明上定义自己的泛型(只有本方法能用)

泛型接口

如何使用一个带泛型的接口

方式1:实现类给出具体类型

方式2:实现类延续泛型,创建对象时再确定

泛型的继承和通配符

泛型不具备继承性,但是数据具备继承性

如果想写一个方法,虽然不确定类型,但是希望只能传递Ye,Fu,Zi此时可以使用泛型的通配符:?也表示不确定的类型,可以进行类型的限定? extends E表示可以传递E或者E所有的子类类型? super E表示可以传递E或者E所有的父类类型

应用场景:

如果我们在定义类,方法,接口的时候,如果类型不确定,就可以定义泛型类,泛型方法,泛型接口

如果类型不确定,但是能指导以后只能传递某个继承体系的,就可以使用泛型的通配符

泛型的通配符:        关键点:可以限定类型的范围

泛型小结

什么是泛型?JDK5引入的特性,可以在编译阶段约束操作的数据类型,并进行检查

泛型的好处?

统一数据类型

吧运行时期的问题提前到了编译期间,避免了强制类型转换可能出现的异常,因为在编译阶段类型就能确定下来

泛型的细节?

泛型中不能写基本数据类型

指定泛型的具体类型后,传递数据时,可以传入该类型和他的子类类型

如果不写泛型,类型默认是Object

哪里定义泛型?

泛型类:在类名后面定义泛型,创建该类对象的时候,确定类型

泛型方法:在修饰符后面定义方法,调用该方法的时候确定类型

泛型接口:在接口名后面定义泛型,实现类确定类型,实现类延续泛型

泛型的继承和通配符

泛型不具备继承性,但是数据具备继承性(即<>里面的东西具备继承性)

泛型的通配符?

Set集合

无序:存取顺序不一致

不重复:可以去除重复

无索引:没有带索引的方法,所以不能使用普通for循环遍历,也不能通过索引来获取元素

实现类:

HashSet:无序,不重复,无索引

LinkedHashSet:有序,不重复,无索引

TreeSet:可排序,不重复,无索引

Set接口中的方法基本与Collection的API一致

遍历方式:

迭代器

增强for

Lambda表达式

HashSet

底层采用哈希表存储数据,哈希表是一种对于增删改查数据性能都较好的结构

哈希表组成:

JDK8以前:数组+链表

JDK8开始:数组+链表+红黑树

哈希值:对象的整数表现形式

格努hashCode方法算出来的int类型的整数

该方法定义在Object类中,所有对象都可以调用,默认使用地址值进行计算

一般情况下,会重写hashCode方法,利用对象内部的属性值计算哈希值

对象的哈希值特点:

如果没有重写hashCode方法,不同对象计算出的哈希值是不同的

如果已经重写hashCode方法,不同的对象只要属性值相同,计算出的哈希值就是一样的

在小部分情况下,不同的属性值或者不同的地址值计算出来的哈希值也有可能一样

HashSet 底层原理

创建一个默认长度16,默认加载因子为0.75的数组,数组名table

根据元素的哈希值跟数组的长度计算出应存入的位置

判断当前位置是否为null,如果是null直接存入

如果位置不为null,表示有元素,则调用equals方法比较属性值

一样:不存   不一样:存入数组,形成链表JDK8以前:新元素存入数组,老元素挂在新元素下面JDK8以后:新元素直接挂在老元素下面

加载因子的作用:当数组中存了个元素时,数组会扩容两倍当链表长度大于8而且数组长度大于64,链表会自动转换为红黑树,提示查找效率如果集合中存储的是自定义对象,必须要重写hashCode和equals方法

问题1:HashSet为什么存和取的顺序不一样?遍历时会从数组的0索引开始沿着每一条链表(红黑树)遍历的

问题2:HashSet为什么没有索引?挂着的链表(红黑树)不好定义索引

问题3:HashSet是利用什么机制保证数据去重的?HashCode方法和equals方法

LinkedHashSet

有序,不重复,无索引

这里的有序指的是保证存储和取出的元素顺序一致

原理:底层数据结构依然是哈希表,只是每个元素又额外多了一个双链表的机制记录存储的顺序

在以后如果仅仅要数据去重,默认还是使用HashSet,因为效率要比LinkedHashSet要高

TreeSet

不重复,无索引,可排序

可排序:按照元素的默认规则(由小到大)排序

TreeSet集合底层是基于红黑树的数据结构实现排序的,增删改查性能都很好

TreeSet集合默认的规则

对于数值类型:Integer,Double默认按照从小到大的顺序进行排序

对于字符,字符串类型:按照字符在ASCII码表中的数字升序进行排序

集合小结

如果想要集合中的元素可重复

用ArrayList集合,基于数组的(最常使用)

如果想要集合中的元素可重复,而且当前的增删操作明显多于查询

用LinkedList集合,基于链表的

如果想对集合中的元素去重

用HashSet集合,基于哈希表的(最常使用)

如果想对集合中的元素去重,而且保证存取顺序

用LinkedHashSet集合,基于哈希表和双链表,效率低于HashSet

如果想对集合中的元素进行排序

用TreeSet集合,基于红黑树.后序也可以用List集合实现排序

源码分析

HashSet,LinkedHashSet,TreeSet在底层都是new了一个对应的双列集合Map

往期传送门: