Java 集合框架学习笔记(基础)
由于篇幅原因,它们因实现许多接口而多出来的方法我并没写,因为它们太多了,以后再补充吧!
目录
集合主要分为三大常用(Set、List、Map)、二大体系(Collection、Map)
TreeSet 自定义排序的两种方法(其实现了 SortedSet 接口,支持元素比较)
Java为一组对象的处理提供了一套完整的、从接口到抽象类、再到实现类的体系结构,通常称作集合框架
好多集合底层都是依赖数组的,但是为什么要有集合呢?这不得不提一嘴数组了,我们知道数组一旦初始化后其长度就确定了,所以数组存储数据对象就不能达到动态扩展,次之数组不便于对其存储元素进行添加、删除、修改操作(增删改),而且数组允许存储重复元素,这时集合就应运而生了!
数组 | 集合 | |
---|---|---|
长度区别 | 固定 | 可变 |
内容区别 | 基本类型或引用类型 | 只能存储引用类型 |
元素类别 | 只能存储同一种类型的数据 | 可以存储不同类型的数据 |
集合主要分为三大常用(Set、List、Map)、二大体系(Collection、Map)
Set(集) | List(列表) | Map(映射/键值对) | |
---|---|---|---|
元素组织方式 | 一般不按特定方式排列 | 可以按照索引位置排序 | 每一个元素都包含着一对键对象和值对象(key-value) |
是否允许重复对象 | 不允许 | 允许 | 不允许有重复的键对象(key),而值对象(value)可以重复 |
补充 | - | 允许按照对象在 List 中的索引位来检索对象,(数组的升级版) | - |
Java 集合框架用?接口 为我们提供了处理一组对象(集合)的标准方式,而 Collection 根接口和 Map 根接口形成了两大体系。
(图例:实线表示继承,虚线表示实现接口。此图片是网上的,如有侵权,请联系我删除)
Java 集合类主要由两个根接口(集合框架中最上层的接口)Collection 和 Map 派生出来的,所以称其为二大体系。
Collection 根接口(第一体系)
因为是接口,所以我们主要考虑它的方法是如何被其实现类实现的。(以下是 Collection 接口里定义的方法)
格式 | 描述 |
---|---|
public boolean add(Object o) public boolean addAll(Collection c) | 从集合中添加元素 |
public boolean remove(Object o) public boolean removeAll(Collection c) | 从集合中删除元素 |
public boolean isEmpty() public boolean contains(Oject o) public boolean contains(Collection c) | 判断集合中的元素 |
public Iterator iterator() public Object toArray() | 与其它类型的对象进行转换 |
public int size() public boolean equals(Object o) public int hashCode() | 比较通用的方法 |
而Collection接口有三种子类型集合:Set、List 和 Queue
子接口 Set (不保留元素的插入顺序、唯一)单列集合
????????Set 继承于 Collection 接口,是一个不允许出现重复元素并且本无序的集合(即添加顺序和输出/遍历顺序不一致),它主要有 HashSet 和 TreeSet 两大实现类。
Set 通过 hashCode() 和 equals() 方法来保证元素唯一性,而其实现类需要重写、利用它们来防止插入重复对象/key
????????HashSet “key”
特点:
- 不保留其元素的插入顺序,其元素顺序随时可能发生变化(元素插入顺序和输出顺序不一致)
- 不是同步的,如果多个线程同时访问一个 HashSet,而其中至少一个线程对此 HashSet 进行了修改,那么它必须保持外部同步
- 元素值可以是 null
- 底层数据结构采用哈希表,主要利用 HashMap 的 key 来存储元素,元素地址基于 hashCode
- 底层基于HashMap实现
哈希表依赖两个方法:hashCode() 和 equals() 来保证 HashSet 里的元素唯一,具体执行如下:
首先传入的新元素和原有元素进行比较 hashCode()(哈希码值)是否相同:如果不相同则一定是不同的元素就添加;倘若相同则继续用 equals() 方法进行比较返回值(元素内容)是否一样,如果一样则代表元素重复就放弃添加,如果不一样则代表是新元素就要添加!
哈希的解决地址冲突(哈希码值冲突)算法:当元素的哈希码值一样但其内容又不同(实际属于不同的元素)时,就会在此哈希值地址上建立一个链表,让同一个哈希值后面可以存储不同的元素,这样就保证了元素的唯一性。
Hash算法是一种散列算法,由数组、链表/红黑树组成(JDK1.8后是这样的)
格式 | 效能 |
---|---|
?public HashSet() | 创建初始化大小为16、加载因子为0.75的默认实例 |
public HashSet(Collection c) | 以已经存在的集合对象中的元素为基础来创建新的实例 |
public HashSet(int initalCapacity) | 根据指定的初始化空间大小来创建实例 |
public HashSet(int initalCapacity, float loadFactor) | 根据指定的初始化空间大小和指定的加载因子来创建实例 |
????????
??????? TreeSet “树”
特点:
- 元素唯一且需要排序(默认使用自然排序(按键值的升序排序),但也可以自定义排序)
- 不是同步的,但可以使用 Collections.synchronizedSet()包装器进行外部同步
- 元素值不能是 null
- 底层数据结构采用红黑树(一种平衡的二叉树)
- 基于TreeMap实现
红黑树是一种平衡二叉查找树,它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点,并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
TreeSet 自定义排序的两种方法(其实现了 SortedSet 接口,支持元素比较)
- 其存储元素的类必须实现 Comparable 接口,并重写了 compareTo(Object obj) 方法(向 TreeSet 中添加元素时,只有第一个元素自己和自己比较,后面添加的所有元素都会调用 compareTo() 方法进行比较)
- 单独写一个比较器类 Comparator 当参数传入 TreeSet,其实现 Comparato 接口,重写 compare() 方法
格式 | 效能 |
---|---|
TreeSet() | 创建一个默认实例 |
TreeSet(Collection c) | 创建一个集合元素为c的实例 |
TreeSet(Comparator comparator) | 创建一个带比较器的实例 |
TreeSet(SortedSet s) | 创建一个带 SortedMap 的实例 |
子接口 List (有序可变、可重复)有序集合
????????List 就像数组的升级版,保留元素插入顺序并且允许元素重复,可以通过索引来访问 List 中的元素
格式 | 描述 |
---|---|
public void add(int index, Object o) public boolean addAll(int index, Collection c) | 在指定索引插入元素(从0开始,如果不指定位置则默认添加到末端) |
public Object remove(int index) public List subList(int fromIndex, int toIndex) | 获取某个/些元素 [ fromIndex ~ toIndex ) |
public int indexOf(Object o) public int lastIndexOf(Object o) | 查找某个元素(若返回 -1 标志符,则代表没找到此元素) |
public Object set(int index, Object o) | 修改元素 |
public ListIterator listIterator() public ListIterator listIterator(int index) | 转换成有序的迭代器 |
??????? ArrayList “数组”
特点:
- 元素像数组那样排序,是一个动态数组
- 不是同步的
- 允许元素值null
- 查询、修改效率高
- 底层数据结构是数组
ArrayList 是动态数组的数据结构,因为存储地址连续,所以一旦数据存储好了后其查询、修改效率比较高,但又因为此它的插入及删除操作的效率比较低
格式 | 效能 |
---|---|
public ArrayList(int initialCapacity) | 构造一个具有指定初始容量的空列表 |
public ArrayList() | 默认构造一个初始容量为10的空列表 |
public ArrayList(Collection c) | 构造一个包含指定 Collection 的元素的列表 |
??????? LinkedList “火车”
特点:
- 有头有尾的顺序
- 不是同步的
- 允许元素值null
- 增加、删除效率高
- 底层数据结构是双向链表,可以当栈/队列
LinkedList 是链表的数据结构,故地址是任意的,所以在开辟内存空间时不需要等一片连续的地址,即对于增加和删除操作LinkedList是占优势的,但因为LinkedList需要移动指针,所以查询操作性能较低
构造方法类似ArrayList
??????? Vector “安全”
特点:
- 可以设置增长因子
- 是同步的
- 运行效率低
- 允许元素值null
- 底层数据结构是数组(动态数组)
Vector类中的许多方法被synchronized进行修饰了,这样就导致了Vector在效率上无法与ArrayList相比。如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用Vector有一定的优势
格式 | 效能 |
---|---|
public Vector() | 使用指定的初始容量和等于0的容量增量构造一个空向量 |
public Vector(int initialCapacity) | 构造一个空向量,使其内部数据数组的大小,其标准容量增量为零 |
public Vector(Collection c) | 构造一个包含指定 Collection 中的元素的向量 |
public Vector(int initialCapacity, int capacityIncrement) | 使用指定的初始容量和容量增量构造一个空的向量 |
子接口 Queue (排队,先入先出)
暂先不写
Map 根接口(第二体系)
Map 就是用于保存具有映射关系的数据(地图指向),Map里保存着两组数据:key和value,它们都可以是任何引用类型的数据,但key是唯一的(value可重复)。所以通过指定的key就可以取出对应的value。
格式 | 描述 |
---|---|
public Object put(Object key, Object value) public void putAll(Map m) | 添加元素 |
public void get(Object key) | 获取元素 |
public Object remove(Object key) | 删除元素 |
public Set entrySet() public Set keySet() public Collection values() | 与键集合、值集合及映射集合相关的操作 |
public boolean containsValue(Object value) public boolean containsKey(Object key) | 判断是否存在指定键和值 |
??????
????????HashTable “安全”
特点:
- 是同步的
- 无序
- 运行效率低
- 不允许键值对为null(key、value都不能为null)
- 底层数据结构是哈希表(数组+链表)
构造方法以后补充
??????? HashMap “指向”
特点:
- 不是同步的
- 无序
- 访问速度快
- 最多允许一个key为null,允许多个value为null
- 底层数据结构是数组+链表+红黑树
构造方法以后补充
实现类们之间的比较
HashSet VS HashMap
????????首先HashSet是基于HashMap实现的
HashSet | HashMap | |
---|---|---|
实现接口 | 实现Set接口 | 实现Map接口 |
存储形式 | 存储对象,即单列 | 存储键值对,即双列 |
重复值 | 不允许元素重复 | 不允许键重复,但允许值重复 |
区别就在于HashMap的元素是键值对(key-value),而在HashSet中的元素是一个键(key)。(HashSet的value被设置为常量present,即弃用它)
TreeSet VS TreeMap
????????TreeSet的大部分方法都是基于TreeMap的,区别主要在于前者是单列集合,后者是双列集合
TreeSet | TreeMap | |
---|---|---|
不同点 | 实现Set接口 | 实现Map接口 |
只存储一个对象(key) | 存储一对对象(key-value)但只有key对象有序 | |
不支持重复对象 | 支持重复对象 | |
相同点 | 都是需要排序的集合 | |
都是非同步的集合 | ||
运行速度都比Hash集合慢 |
HashMap VS TreeMap
??????? 它们都是键值对形式(key-value)的集合
HashMap | TreeMap | |
---|---|---|
底层 | 基于Hash表 | 树 |
是否有调优选项 | 可以设置初始容量和负载因子来调优,优化HashMap空间的使用 | 没有调优选项,因为该树总处于平衡状态 |
性能 | HashMap??? >?? TreeMap |
HashSet VS TreeSet
????????首先它们都属于 Set 单列集合体系里的!
HashSet | TreeSet | |
---|---|---|
底层数据结构 | 哈希表 | 二叉树 |
元素排序 | 无序 | 有序,默认为key的升序 |
性能 | HashSet??? >??? TreeSet | |
重复值 | 都不允许有重复 | |
是否线程安全 | 都需要同步,都是非线程安全的 |
HashMap VS HashTable
HashMap | HashTable | |
---|---|---|
线程是否安全 | 非同步,非线程安全 | 是同步,是线程安全 |
null问题 | 允许将null作为key或value | 不允许键值对为null |
来自于 | Java 1.2引入的Map接口的实现类 | 基于老的Dictionary类 |
分类一览
依照实现接口分类 | |
---|---|
实现Map接口的有: | EnumMap、IdentityHashMap、HashMap、LinkedHashMap、WeakHashMap、TreeMap |
实现List接口的有: | ArrayList、LinkedList |
实现Set接口的有: | HashSet、LinkedHashSet、TreeSet |
实现Queue接口的有: | PriorityQueue、LinkedList、ArrayQueue |
依据底层实现的数据结构分类 | |
底层以数组的形式实现: | EnumMap、ArrayList、ArrayQueue |
底层以链表的形式实现: | LinkedHashSet、LinkedList、LinkedHashMap |
底层以hash table的形式实现: | HashMap、HashSet、LinkedHashMap、LinkedHashSet、WeakHashMap、IdentityHashMap |
底层以红黑树的形式实现: | TreeMap、TreeSet |
底层以二叉堆的形式实现: | PriorityQueue |
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!