集合分类
- 单列集合(Collection)。元素是一个一个的。
- 双列集合(Map)。元素是一对一的。
单列集合(Collection)
Collection集合体系
- 子接口List
。 - 实现类ArrayList
。 - 实现类LinkedList
。
- 实现类ArrayList
- 子接口Set。
- 实现类HashSet
。 - LinkedHashSet
。
- LinkedHashSet
- 实现类TreeSet
。
- 实现类HashSet
学习时要掌握的:
- 有什么特点?
- 是否有特有功能?
- 适合什么业务场景?
Collection集合特点
List系列
添加的元素有序、可重复、有索引。
- ArrayList、LinkedList有序、可重复、有索引。
Set系列
添加的元素无序、不重复、无索引。
- HashSet。无序、不重复、无索引。
- LinkedHashSet。有序、不重复、无索引。
- TreeSet。按照大小默认升序排序、不重复、无索引。
Collection常用方法
为什么要学?
- 因为Collection是单列集合的祖宗,它规定的方法(功能)是全部单列集合都会继承的。
常用方法:
- public boolean add(E e)。把给定的对象添加到当前集合中 。由于允许数据重复,所以一定返回true。
- public void clear() 。清空集合中所有的元素。
- public boolean remove(E e)。把给定的对象在当前集合中删除。如果有多个重复元素只能删除第一个。
- public boolean contains(Object obj)。判断当前集合中是否包含给定的对象。是精确匹配。
- public boolean isEmpty()。判断当前集合是否为空。
- public int size()。返回集合中元素的个数。
- public Object[] toArray()。把集合中的元素,存储到数组中。Object类型是为了兼容各种类型的数据。
- addAll(Collection<? extends String> c)。
把另一个集合中的全部数据倒入
,数据类型要一样。
Collection遍历方式
1. 迭代器
迭代器是用来遍历集合的专用方式(数组没有迭代器),在Java中迭代器的代表是Iterator。
Collection集合获取迭代器的方法:
- **Iterator
iterator()**。返回集合中的迭代器对象,该迭代器对象默认指向当前集合的第一个元素。 - 从集合对象中获取迭代器对象。
- 判断当前位置是否有元素可以获取。不判断的话可能出现NoSuchElementException异常。
- 获取当前位置的元素,然后自动指向下一个元素。
1 | Collection<String> c = new ArrayList<>(); |
Iterator迭代器中的常用方法:
- boolean hasNext()。询问当前位置是否有元素存在,存在返回true ,不存在返回false。
- E next()。获取当前位置的元素,并同时将迭代器对象指向下一个元素处。
2. 增强for
为什么用增强的?因为Collection中没有规定集合的索引,只有List集合才支持索引。
- 格式:for (元素的数据类型 变量名 : 数组或者集合) { }。变量名相当于游标。(类似于Python中的for img in imgs这种写法。)
- 可以遍历集合或者数组。
- 遍历集合本质是迭代器遍历集合的简化写法。
- 简化写法:数组或集合**.for再回车**。
3. lambda表达式
得益于JDK 8开始的新技术Lambda表达式,提供了一种更简单、更直接的方式来遍历集合。
方法:default void forEach(Consumer<? super T> action) 。结合lambda遍历集合。
举例:
1 | Collection<String> c = new ArrayList<>(); |
lambda表达式遍历Collection集合不算简洁,之后遍历Map才是简洁。
(一)List集合
ArrayList、LinkedList有序、可重复、有索引。但是底层数据结构不同(数据结构:存储、组织数据的方式),应用场景也不同。继承了Collection的功能。
创建(List是接口,所以需要指定具体的类):
1 | List<String> list = new ArrayList<>();//经典代码,多态 |
常用方法
List集合因为支持索引,所以多了很多索引相关的方法:
- void add(int index,E element)。在此集合中的指定位置插入指定的元素。不写索引的话,默认是插入到最后。
- E remove(int index)。删除指定索引处的元素,返回被删除的元素。
- E set(int index,E element)。修改指定索引处的元素,返回被修改的元素。
- E get(int index)。返回指定索引处的元素。
List集合支持的遍历方式
- 普通for循环(只因为List有索引)。集合名.fori自动完成。
- 增强for/foreach遍历。集合名.for自动完成。
- 迭代器。先创建迭代器,再判断并遍历。
- Lambda表达式。forEach方法。
1 | List<String> list = new ArrayList<>(); |
(1)ArrayList集合的底层原理
基于数组实现的。
特点(查询快、增删慢):
- 查询速度快(根据索引查询数据快)。查询数据通过地址值和索引定位,查询任意数据耗时相同。
- 删除效率低。可能需要把后面很多的数据进行前移。
- 添加效率极低。可能需要把后面很多的数据后移,再添加元素;或者也可能需要进行数组的扩容。
底层原理:
- 利用无参构造器创建的集合,会在底层创建一个默认查高难度为0的数组。
- 添加第一个元素时,底层会创建一个新的长度为10的数组。
- 存满时(添加第11个元素时),扩容1.5倍。
- 如果一次添加多个元素,1.5倍还放不下,则新创建数组的长度以实际为准。
应用场景:
- 适合:根据索引查询数据,比如根据随机索引取数据(高效),或者数据量不是很大时。
- 不适合:数据量大的同时,又要频繁地进行增删操作。
(2)LinkedList集合的底层原理
基于双链表实现的(Java中大多数情况都使用双向链表)。
什么是链表?
- 链表结构是由一个一个的节点组成,一个节点由数据值、下一个元素的地址组成。
- 链表中的结点是独立的对象,在内存中是不连续的,每个节点包含数据值和下一个节点的地址。
- 特点1:查询慢,无论查询哪个数据都要从头开始。
- 特点2:增删相对较快。但是对于首尾元素进行增删改查的速度是极快的。
LinkedList新增了一些可以针对头尾进行操作的方法:
- public void addFirst(E e)。在该列表开头插入指定的元素。
- public void addLast(E e)。将指定的元素追加到此列表的末尾。
- public E getFirst()。返回此列表中的第一个元素。
- public E getLast()。返回此列表中的最后一个元素。
- public E removeFirst()。从此列表中删除并返回第一个元素。
- public E removeLast()。从此列表中删除并返回最后一个元素。
应用场景:
- 设计队列(特点:先进先出,后进后出)。队列只是在首尾增删元素。
- 入队。addLast方法。
- 出队。removeFirst方法。
- 设计栈(特点:先进后出,后进先出)。
- 进栈(压栈)。push方法(其实就是调用的addFirst方法)。
- 出站(弹栈)。pop方法(其实就是调用的removeFirst方法)。
(二)Set集合
添加的元素无序、不重复、无索引。
- HashSet。无序、不重复、无索引。
- LinkedHashSet。有序、不重复、无索引。(是HashSet的子孙类。)
- TreeSet。按照大小默认升序排序、不重复、无索引。
创建(Set是接口,所以需要指定具体的类):
1 | //一行经典代码 |
常用方法
要用的常用方法,基本上都是其父类Collection提供的。
(1)HashSet集合
需要掌握的:
- 为什么添加的元素无序、不重复、无索引?
- 增删改查数据有什么特点,适合什么场景?
哈希值:
- 一个int类型的数值,Java中每个对象都有一个哈希值。
- Java中的所有对象,都可以调用Object类提供的hashCode方法,返回该对象自己的哈希值。
对象哈希值的特点:
- 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
- 不同的对象,哈希值一般不同,但也有可能相同(哈希碰撞)。
HashSet集合的底层原理
- 基于哈希表实现。
- 是一种增删改查性能都较好的数据结构。
- JDK8以前:哈希表 = 数组+链表
- JDK8以后:哈希表 = 数组+链表+红黑树
JDK8以前HashSet集合的底层原理:
- 创建一个默认长度为16的数组,默认加载因子为0.75,数组名table;
- 使用元素的哈希值对数组的长度求余计算出应存入的位置;
- 判断当前位置是否为null,如果是null直接存入;
- 如果不为null,表示有元素,则调用equals方法比较相等,则不存;不相等,则存入数据。
- JDK8以前,新元素存入数组,占用老元素的位置,老元素挂下面;
- JDK8以后,新元素挂在老元素下面。
往HashSet集合中存储元素时,底层调用了元素的两个方法:一个是hashCode方法获取元素的hashCode值(哈希值);另一个是调用了元素的equals方法,用来比较新添加的元素和集合中已有的元素是否相同。
- 只有新添加元素的hashCode值和集合中以后元素的hashCode值相同、新添加的元素调用equals方法和集合中已有元素比较结果为true, 才认为元素重复。
- 如果hashCode值相同,equals比较不同,则以链表的形式连接在数组的同一个索引为位置。–>导致的问题:如果数组快占满了,链表过长,导致查询性能降低。–>哈希表的扩容机制(占满加载因子0.75*长度就会扩容,扩容成原来数组的两倍)。
在JDK8以后的优化:
- 当链表的长度超过8,且数组长度超过64时,就会自动把链表转换为红黑树。
深入理解HashSet集合去重的机制
注意:HashSet集合默认不能对内容一样的两个不同对象去重复!(因为不同对象哈希值不一样,因此存储位置不同,就会被认为不是重复的。)
如何让HashSet集合能够实现对内容一样的两个不同对象也能去重复???
- 如果希望Set集合认为2个内容一样的对象是重复的,
必须重写对象的hashCode()和equals()方法。 - 在类中**右键-generate-euqals() and hashCode()**,一路next。这里euqals方法只要两个对象内容一样就返回true,hashCode方法只要两个对象内容一样,返回的哈希值就是一样的。
(2)LinkedHashSet集合
- 有序、不重复、无索引。
- 基于哈希表(数组+链表+红黑树)实现的。
- 每个元素都额外的多了一个双链表的机制记录它前后元素的位置。增删改查比较快,但是也更占内存。
(3)TreeSet集合
- 排序、不重复、无索引。
- 基于红黑树实现的排序。增删改查性能较好。
- 对于数值类型:Integer , Double,默认按照数值本身的大小进行升序排序。
- 对于字符串类型:默认按照首字符的编号升序排序。
- 对于自定义类型如Student对象,TreeSet默认是无法直接排序的。
自定义排序规则
- TreeSet集合存储自定义类型的对象时,必须指定排序规则,支持如下两种方式来指定比较规则。
排序方式1:让自定义的类(如学生类)实现Comparable接口,重写里面的compareTo方法来指定比较规则。但是要注意,如果值相等,就认为是重复的,只会保存一个对象!
1 | //第一步:先让Student类,实现Comparable接口 |
排序方式2:通过调用TreeSet集合有参数构造器,可以设置Comparator对象(比较器对象,用于指定比较规则)。TreeSet自动选择自己自带的比较器对象进行排序。
1 | //创建TreeSet集合时,传递比较器对象排序 |
总结
- 如果希望记住元素的添加顺序,需要存储重复的元素,又要频繁的根据索引查询数据?
- 用ArrayList集合(有序、可重复、有索引),底层基于数组的。(常用)
- 如果希望记住元素的添加顺序,且增删首尾数据的情况较多?
- 用LinkedList集合(有序、可重复、有索引),底层基于双链表实现的。
- 如果不在意元素顺序,也没有重复元素需要存储,只希望增删改查都快?
- 用HashSet集合(无序,不重复,无索引),底层基于哈希表实现的。 (常用)
- 如果希望记住元素的添加顺序,也没有重复元素需要存储,且希望增删改查都快?
- 用LinkedHashSet集合(有序,不重复,无索引), 底层基于哈希表和双链表。
- 如果要对元素进行排序,也没有重复元素需要存储?且希望增删改查都快?
- 用TreeSet集合,基于红黑树实现。
注意事项:集合的并发修改异常问题
集合的并发修改异常
并发:多件事正在进行。
- 使用迭代器遍历集合时,又同时在删除集合中的数据,程序就会出现并发修改异常的错误。
- 原因:其实和之前用for循环的时候差不多,索引没有减1的话会导致有些元素没被删掉,但是迭代器知道程序员有可能出现这个错误,所以报了一个善意的提醒。
- 解决方法:不能用集合对象自己去删除数据。使用迭代器的remove方法。(现在一共学了3种方法:1. 每次减1,2. 倒着遍历,3. 用迭代器去删。)
- 由于增强for循环遍历集合就是迭代器遍历集合的简化写法,因此,使用增强for循环遍历集合,又在同时删除集合中的数据时,程序也会出现并发修改异常的错误。
- 原因:增强for循环相当于迭代器简化写法,但是又拿不到迭代器。类似地,使用lambda表达式也会出现这个问题,因为其内部使用的是增强for循环。
怎么保证遍历集合同时删除数据时不出bug?
- 使用迭代器遍历集合,但用迭代器自己的删除方法删除数据即可。
- 如果能用for循环遍历时:可以倒着遍历并删除;或者从前往后遍历,但删除元素后做i–操作。
Collection集合其他知识
可变参数
就是一种特殊形参,定义在方法、构造器的形参列表里,格式是:数据类型…参数名称。
可变参数的特点和好处
- 特点:可以不传数据给它;可以传一个或者同时传多个数据给它;也可以传一个数组给它。
- 好处:常常用来灵活的接收数据。
可变参数的注意事项
- 可变参数在方法内部就是一个数组。
- 一个形参列表中可变参数只能有一个。
- 可变参数必须放在形参列表的最后面。
Collections
一个用来操作集合的工具类。
提供的静态方法
- public static
boolean addAll(Collection<? super T> c, T… elements)。给集合批量添加元素。 - public static void shuffle(List<?> list) 。打乱List集合中的元素顺序。
- public static
void sort(List list)。对List集合中的元素进行升序排序。 - public static
void sort(List list,Comparator<? super T> c)。对List集合中元素,按照比较器对象指定的规则进行排序。
后两个是排序方法,3可以直接对自定义类型的List集合排序,但自定义类型必须实现了Comlarable接口,指定了比较规则才可以。
综合案例
斗地主。