Java 容器(集合)
2021-08-25 15:59:33 0 举报
AI智能生成
登录查看完整内容
为你推荐
查看更多
Java集合
作者其他创作
大纲/内容
List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。
另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。
Set和List对比
Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变
问题:List与Set之间的区别
长度区别:集合长度可别,数组长度不可变
内容不同:集合可以存储不同类型的元素,数组存储的是同一类型的元素
数据类型:集合只能存储引用类型,数组可以存储引用类型,也可以存储基本数据类型。
问题:集合和数组之间的区别
问题:ArrayList与LinkedList和Vector之间的区别
问题:ArrayList特点与扩容问题
ArrayList是动态数组的数据结构实现
LinkedList是双向链表的数据结构实现
数据结构实现
结论:ArrayList比LinkedList在随机数访问的效率高
因为LinkedList需要移动指针从前往后依次查找
随机数访问效率
结论:在非首尾的增加和删除操作,LinkedList要比ArrayList效率更高
因为ArrayList增删操作要影响数组内的其他数据的下标。
增加和删除效率
结论:LinkedList比ArrayList更占内存
因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素
内存空间占用
ArrayList和LinkedList都是不同步的,也就是不保证线程安全
线程安全
问题:ArrayList 和 LinkedList 的区别是什么?
这是一个并发修改异常问题,它使用迭代器iterator来获取元素,同时使用ArrayList自身的remove方法移除元素
使用增强for循环去遍历元素亦会如此,增强for循环底层用的也是迭代器,enhanced for loop is nothing but a syntactic sugar over Iterator in Java
问题引入
cursor本指向的是当前元素索引的下一位,但remove后数据将整体向前窜一位,从而导致cursor指向的索引位置对应的数据发生了偏差
问题描述
通过list自身的get方法获取元素的同时通过自身的remove方法移除元素
分支主题
解决方法
问题:ArrayList在遍历时remove元素所发生的并发修改异常的原因及解决方法
ArrayList线程不安全 | 不同步,相对效率较高
Vector 线程安全 | 同步
同步问题
ArrayList 每次扩容原容量的1.5倍。更有利于节约内存
Vector每次扩容原容量的2倍
扩容问题
问题:Vecotor和ArrayList之间的区别
数组转List:使用Arrays.asList(array)进行转换
List转数组:使用List自带的toArray()方法
问题:如何实现数组和 List 之间的转换?
1. for循环遍历
2. 迭代器遍历(ListIterator正向/反向)
3. foreach循环遍历(增强for循环)
问题:遍历一个 List 有哪些不同的方式?
Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。
Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。
Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
问题:Array 和 ArrayList 有何区别?
数组
当你把对象加入 HashSet 时,HashSet 会先计算对象的 hashcode 值来判断对象加入的位置,同时也会与其他已经加入的对象的 hashcode 值作比较,如果没有相符的hashcode,HashSet会假设对象没有重复出现。
但是如果发现有相同 hashcode 值的对象,这时会调用 equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让其加入操作成功。
如果不同的话,就会重新散列到其他位置。这样我们就大大减少了 equals 的次数,相应就大大提高了执行速度。
问题:为什么要有 hashCode?
Set
comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序
问题:comparable 和 comparator的区别?
java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式,其直接继承接口有List与Set。
Collections则是集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。
问题:Collection与Colections之间的区别
相同点:都是返回第一个元素,并在队列中删除返回的对象。
不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。
问题:在 Queue 中 poll()和 remove()有什么区别?
1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
3.==指引用是否相同 equals()指的是值是否相同
问题:==与equals的区别
TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。
问题:TreeMap 和 TreeSet 在排序时如何比较元素?
Iterator 可以遍历 Set 和 List 集合,而 ListIterator 只能遍历 List。
Iterator 只能单向遍历,而 ListIterator 可以双向遍历(向前/后遍历)。
ListIterator 实现 Iterator 接口,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置
问题:Iterator 和 ListIterator 有什么区别?
工具类
如何处理HashMap的线程不安全问题
HashMap的扩容机制
HashMap线程安全问题
安全机制
变参版本的函数需要额外分配一个数组,这个数组被封装于列表中。使用变参版本的方法,你就要负担分配数组、初始化以及最后对它进行垃圾回收的开销。使用定长(最多为10个)元素版本的函数,就没有这部分开销。注意,如果使用List.of创建超过10个元素的列表,这种情况下实际调用的还是变参类型的函数。
问题:Java API为什么不提供一个使用可变参数的方法,像下面这样接受任意数目的元素
常见问题
重写equals方法,hashCode方法,按需重写toString方法
哈希表中存储自定义引用数据类型,数据的去重前提:
equals相等,hashCode一定相等
hashCode相等equals一定相等
哈希表中hashCode与equals之间的关系(前提是重写hashCode与equals都是根据成员变量计算的)
实现 Comparable 接口,重写CompareTo方法
缺点:比较局限,不够灵活,硬编码,不便于后期维护
内部比较器 | 内部比较规则 | 自然排序
实现Cpmparator接口(函数式接口),重写 int compare(T o1, T o2)方法。
外部比较器 | 外部比较规则 | 定制排序
TreeSet存储不同类型的数据前提是:重写内部比较器 | 外部比较器
使用集合的注意事项:
集合表示一组对象,其中存放的内容称为元素。
数组是引用数据类型
数组长度固定,长度一旦确定不可改变
存储相同数据类型
有序,根据索引操作数组中的数据
数组的特点:
数组固定
集合可变
长度区别
数组可以是基本数据类型,也可以是引用数据类型
集合只能是引用数据类型
内容区别
数组只能存储同一种类型
集合可以存储不同类型(其实集合一般存储的也是同一种类型)
元素内容
集合和数组的区别
集合概念
类 java.util.Collections 提供了对 Set、List、Map操作的工具方法
void shuffle(List) //对List容器内的元素进行随机排列
void reverse(List) //对List容器内的元素进行逆续排列
Collections工具类
一张图
ArrayList<String> ls = new ArrayList<>();
泛型就是在创建对象的时候可以确定它的类型
概念
创建对象时不指定,默认Object
创建时指定,即泛型类型就是指定类型
泛型类
泛型接口定义之后如果要编写对应的实现类对象需要注意在实现类的声明位置
class UserServiceImpl<T> implements UserService<T>
泛型接口
如果要使用泛型,可以自己指定声明类型
类中没有声明泛型类型
改泛型在静态方法中无法使用(静态先于对象存在)
类中已声明泛型类
泛型方法
泛型+可变参数 按道理而言可以接受任意类型的实际参数(虽然这样做没啥意义)
泛型属性
定义
一个类中声明泛型之后,方法或者时属性是可以直接使用当前该类型的
注意
实例
泛型
当前类需要实现 java.lang.Compareable接口
重写compareTo方法
A: 内部比较器:对象自己比
需要实现 java.util.Comparetor接口 重写compare方法
B: 外部比较器:别人帮着比
比较器
3个知识点
无序,可重复
是集合框架中的顶级父接口 (存储单一元素)
存储特点
底层是数组:查询速度快,增删速度慢
ArrayList数组
底层是链表:查询速度慢,增删速度快
LinkedList链表
List:有序可重复
离散事件模型
Queue:队列
重写hashCode方法
重写equals方法
Hashset 哈希表
对象必须要是Comparable接口的子类型
TreeSet 红黑树
set:无序不可重复
分类
Iterator 迭代器
add(Obj); addAll(Coll);
增
删除
size(); contains(obj);isEmpty();
toArray()返回包含此集合中所有元素的数组
查看
常见方法
ListIterator如果要逆向迭代需要先正向迭代一次
注意并发修改问题
for:不行
for-each: 可以
iterator: 可以
迭代方式
Collection
存放的顺序与内部真实存储的顺序相同
存放的数据为整数时,默认以索引优先。
有序可重复
允许添加null元素
作业:为什么List接口重定义了大量的of重载方法,而且of中存在一个可变参数还有10个对应参数列表的方法。
ArrayList
LinkedList
特点
可变数组,与ArrayList很像
底层结构
Vecotor和ArrayList之间的区别
Vector (向量)
除了Collection中之外增加了对于索引的操作
addFirst(E e):在此列表的开头插入指定的元素
offerFirst(E e):在此列表的前面插入指定的元素
头
addLast(E e):将指定的元素追加到此列表的末尾
offerLast(E e) 在此列表的末尾插入指定的元素
尾
增加
remove() 检索并删除此列表的头部(第一个元素)
poll() 检索并删除此列表的头部(第一个元素)。
removeLast() 从此列表中删除并返回最后一个元素。
pollLast() 检索并删除此列表的最后一个元素,如果此列表为空,则返回 null 。
修改
getFirst() 返回此列表中的第一个元素。
getLast() 返回此列表中的最后一个元素。
get(index) subList()
for:可以
List
无序,不可重复
和Collection一样
key:唯一的,无序的-->key的集合相当于Set的集合
value:无序的可重复的-->value的集合相当于Collection(可重复的)
键值对为一个映射关系: key-->映射--->value。
一个key可以实现对应一个集合作为value,集合中可以存放多个值
V remove(Object key) 如果存在,则从该映射中移除键的映射(可选操作)。
删
改
boolean containsKey(Object key) 如果此映射包含指定键的映射,则返回 true
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值,则返回 true
V get(Object key) 返回指定键映射到的值,如果此映射不包含键的映射,则返回 null 。
keySet() -> Set集合 + get(k)
entrySet() -> Set集合 =>
getKey + getValue()
迭代方法
Map
6个接口
随机获取速度快,但是添加删除效率满
和List一样
get(int index)返回此列表中指定位置的元素
int indexOf(Object o) 返回此列表中第一次出现的指定元素的索引,如果此列表不 包含该元素,则返回-1。
static <E> List<E> of(E... elements) 返回包含任意数量元素的不可修改列 表。
新增方法:
ListIterator列表迭代器
链表:以节点为单位(双向链表)
数组:一段连续的存储空间
随机获取效率低,添加删除效率高
和List一样,多了一些针对于表头和表尾的操作
哈希表(数组+链表+红黑树) -> 是由HashMap维护
查询,增删效率都较高
无序
缺点
实现不存储相同数据,查询,增删效率较高的时候使用HashSet
应用场景
HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。
Hashset
底层由TreeMap维护 | 红黑树(平衡二叉树)
比HashSet略低,可以比大小
和Set一样,多了一些比较的方法
E floor(E e) 返回此set中小于或等于给定元素的最大元素,如果没有这样的元素,则 null 。
E first() 返回此集合中当前的第一个(最低)元素。
E last() 返回此集合中当前的最后一个(最高)元素。
E ceiling(E e) 返回此set中大于或等于给定元素的 null元素,如果没有这样的元素,则 null 。
新增方法
如果添加自定义对象的时候需要保证可以进行比较
注意事项
TreeSet
实现类
for:不可以
存放数据的顺序与内部真实存储的顺序可能不一致
注意:
哈希表,所有操作都是以key为主
哈希表:数组+链表+红黑树
和Map一样
如果添加自定义对象作为key的时候需要重写hashcode和equals方法
键的类必须重写hashCode和equals方法
不同版本计算hash值的算法可能不同,为了尽量把数据散列分布在位桶中,减少哈希碰撞
1. 根据key调用hashcode()方法得到int类型的整数
2. 通过hash算法计算位桶的索引hash
判断Node[hash],是否已经存在首节点,不存在直接构建新节点对象存储进去,作为首节点存在
如果已经存在首节点,遍历原链表,判断当前要存储键值对的key值与原链表中的每一个节点的key是否相等,相等覆盖value值,如果都不想等存储在原链表的最后
3. 确定当前数据存储在节点数组的哪一个位桶中
流程
jdk1.8后,当链表长度>8,数组总长度>64的时候,会把链表换位红黑树,否则扩容
条件
initialCapacity 初始容量:16
loadFactor 加载因子| 装载因子:0.75
组成
实际数据的个数 = 容量 * 加载因子 12
扩容临界值
扩容
HashMap
键必须是Comparable接口的子类型
红黑树
比HashMap略低,可以比大小
根据key对数据做升序排序
根据key做去重
和Map一样,多了一些可以比较的方法
TreeMap
keySet() -> Set集合 foreach 和迭代器
迭代key
values() 获取集合中所有的value
values() -> Collection foreach 和迭代器
迭代value
keySet() -> Set集合 + get(k)
entrySet() -> Set集合 =>
getKey() + getValue()
迭代k-v
9个常用类
自由主题
链表添加数据流程
ArrayList数组(索引操作)
LinkedList (首尾操作)
List 数组(有序,可重复)
实例化对象需要重写hashCode和equals方法
去重,重写
HashSet
默认升序
实现一个java.lang.Comparable接口,重写compareTo方法,在compareTo方法内部指定比较规则
内部比较器|自然排序(默认)
定义在javabean类的外部,单独指定某种数据的某种比较规则
外部比较器|定制排序
Set 链表(无序,唯一)
Collection无序可重复
集合框架
HashSet与HashMap的区别
有索引
无索引
考虑 是是否需要索引
有序
考虑 有序还是无序?
HashSet
考虑 排序去重?
需要快速访问元素
需要快速添加删除元素
集合使用环境考虑
Java 容器(集合)
0 条评论
回复 删除
下一页