Java- 进阶:集合框架 2,熬夜整理华为最新 Java 笔试题
三、迭代器的并发修改异常
1. 迭代器的并发修改异常
java.util.ConcurrentModificationException
就是在遍历的过程中,使用了集合方法?修改了?集合的长度
2. 出现场景:
首先,在遍历集合的过程中修改集合;其次,修改集合行为,不是迭代器对象来完成的,而是直接修改 Collection 对象
3. 原因:
在迭代过程中,使用了集合的方法对元素进行操作。导致迭代器并不知道集合中的变化,容易引发数据的不确定性。迭代器对象,是依赖与当前的数据集合产生的(换言之,迭代器依赖于数据集,它们必须对应)
四、ArrayList 、LinkedList 集合
1. ArrayList 集合
底层采用的是?数组?结构,线程不安全,查询快,增删慢
2. LinkedList 集合
底层采用?链表?结构,线程不安全,查询慢,增删快
每次查询都要从链头或链尾找起,查询相对数组较慢,但是删除直接修改元素记录的地址值即可,不要大量移动元素
LinkedList 的索引决定是从链头开始找还是从链尾开始找,如果该元素小于元素长度一半,从链头开始找起,如果大于元素长度的一半,则从链尾找起
LinkedList 提供了大量的操作开始和结尾的方法
子类的特有功能:不能多态调用:
addFirst(E) 添加到链表的开头?addLast(E) 添加到链表的结尾?E getFirst() 获取链表的开头?E getLast() 获取链表的结尾?E removeFirst() 移除并返回链表的开头?E removeLast() 移除并返回链表的结尾
3. Vector 集合(基本不用)
Vector 集合数据存储的结构是?数组?结构,为 JDK 中最早提供的集合,它是线程同步的,线程安全的
Vector 集合已被 ArrayList 替代
五、Set 接口
1. 特点
它是个?不包含重复元素?的集合,没索引
是一个不包含重复元素的?collection
无序集合,没有索引,不存储重复元素
Set 无序:存储和取出的顺序不同,
Set 集合取出元素的方式可以采用:迭代器、增强 for
代码的编写上,和?ArrayList?完全一致
Set 集合常用实现类:
HashSet 集合
LinkedHashSet 集合
六、 HashSet (哈希表)
1. 特点:
底层数据结构为?哈希表
存储、取出都比较快
线程不安全,运行速度快
不保证 set 的迭代顺序
不保证该顺序的恒久不变
2. 哈希表的数据结构:
加载因子:表中填入的记录数/哈希表的长度?例如:加载因子是 0.75 代表:数组中的 16 个位置, 其中存入 16 * 0.75 = 12 个元素。
如果在存入第十三个( > 12 )元素,导致存储链子过长,会降低哈希表的性能,那么此时会扩充哈希表(再哈希),底层会开辟一个长度为原长度 2 倍的数组,把老元素拷贝到新数组中,再把新元素添加数组中。?当?
存入元素数量 > 哈希表长度 * 加载因子
,就要扩容,因此加载因子决定扩容时机
3. 字符串对象的哈希值:
对象的哈希值,是普通的十进制整数,Object?类的方法?
public int hashCode()
?来计算,计算结果?int?整数String 类重写了
hashCode()
?方法,见源码
4. 哈希表的存储过程
存取原理:?每存入一个新的元素都要走以下三步:1. 首先调用本类的?
hashCode()
?方法算出哈希值 2. 在容器中找是否与新元素哈希值相同的老元素,如果没有直接存入,如果有转到第三步 3. 新元素会与该索引位置下的老元素利用?equals 方法
一一对比,一旦?新元素.equals(老元素)
,返回?true,停止对比,说明重复,不再存入,如果与该索引位置下的老元素都通过?equals?方法对比返回?false,说明没有重复,存入
哈希表的存储过程
5. 哈希表的存储自定义对象
自定义对象需要重写 hashCode() 和 equals(),来保证存入对象的不重复
6. LinkedHashSet 集合
LinkedHashSet
?基于链表的哈希表实现,继承自?HashSet
LinkedHashSet 自身特性:
具有顺序,存储和取出的顺序相同的,线程不安全,运行速度块
7. ArrayList,HashSet 判断对象是否重复的原因
ArrayList 的?
contains()
原理:底层依赖于equals()
ArrayList 的 contains 方法 调用时,传入的元素的调用?equals 方法?依次与集合中的旧元素所比较,从而根据返回的布尔值判断是否有重复元素。此时,当 ArrayList 存放自定义类型时,由于自定义类型在未重写 equals 方法前, 判断是否重复的依据是地址值,所以如果想根据内容判断是否为重复元素,需要重写元素的 equals 方法。
HashSet 的?
add()
?和?contains()
?底层都依赖hashCode()
与?equals()
Set 集合不能存放重复元素,其添加方法在添加时会判断是否有重复元素,有重复不添加,没重复则添加。?HashSet 集合由于是无序的,其判断唯一的依据是元素类型的 hashCode 与 equals 方法的返回结果。规则如下:
1. 先判断新元素与集合内已经有的旧元素的 HashCode 值 2. 如果不同,说明是不同元素,添加到集合。3. 如果相同,再判断 equals 比较结果。返回 true 则相同元素;返回 false 则不同元素,添加到集合。所以,使用 HashSet 存储自定义类型,如果没有重写该类的 hashCode()与 equals(),则判断重复时,使用的是地址值,如果想通过内容比较元素是否相同,需要重写该元素类的 hashcode()与 equals()。
七、TreeSet
1.概述
Set 的另外一种实现,底层由?红黑树?实现;也就是说 TreeSet 会根据元素的大小关系,将元素默认从小到大排列
特点:
元素无序(迭代或者存储顺序和插入顺序)
不能存储重复元素
没有位序
Comparator comparator();如果 TreeSet 采用了定制排序,则该方法返回定制排序所使用 Comparator;如果 TreeSet 采用了自然排序,则返回 null;
2. TreeSet 如何实现,不能存储重复元素
最后总结
搞定算法,面试字节再不怕,有需要文章中分享的这些二叉树、链表、字符串、栈和队列等等各大面试高频知识点及解析,以及算法刷题 LeetCode 中文版的小伙伴们可以点赞后点击这里即可免费获取!
最后再分享一份终极手撕架构的大礼包(学习笔记):分布式+微服务+开源框架+性能优化
评论