您的位置: 首页  >  文章  >  java.util包中的Collection和Map接口及其常用子类的总结

java.util包中的Collection和Map接口及其常用子类的总结

分类: 文章 • 2022-10-12 10:14:48

java中比较重要必须要了解的包首先就是lang包、util包和io包了。
今天总结一下java.util包中比较常用的一些知识。Java集合类框架实际上就是java针对于数据结构的一种实现。
类集：实际上就是动态数组。
在Java的类集里面(java.util包)提供了两个最为核心的接口:Collection、Map接口。
用一张图大概的总结一下大框架，然后分块总结知识点。

这些都是比较常用的类，也是要重点掌握原理的类，需要大量阅读源码，明白其底层实现，知道它的优缺点、适用性等。
java.util包中的Collection和Map接口及其常用子类的总结

小结

先大概总结一下它们的特点，有一个大概的认知。阅读了几篇博文，总结若有偏差，欢迎评论赐教。

1.List关注事物的索引列表

2.Set关注事物的唯一性

3.Queue关注事物的被处理时间

4.Map关注事物的映射和键值的唯一性

  • ArrayList:可以理解为一个可增长的数组，提供快速迭代和随机访问的能力。
  • LinkedList：可以理解为一个双链表，提供快速插入删除的能力。
  • Vector：是线程安全版本的ArrayList，但是性能低。
  • HashSet：集合没有重复值，不关心元素顺序。
  • LinkedHashSet：集合中没有重复值，关心元素插入顺序。
  • TreeSet：集合中没有重复值，关心元素排序。
  • Queue：用于保存将要执行的任务列表。
  • LinkedList：实现先进先出队列。
  • PriorityQueue：创建自然排序的优先级队列。
  • HahsMap：键值对，不关心顺序。
  • Hashtable：是线程安全版的HashMap，效率较低
  • LinkedHashMap：键值对，关心插入顺序。
  • TreeMap：键值对，关心元素自然排序。

Collection集合保存的数据是为了输出（Iterator）
Map集合保存的数据为了根据Key查找

1. Collection接口

Collection是单个集合保存的最大父接口。
每一次进行数据操作的时候只能够对单个对象进行处理。

public interface Collection<E> extends Iterable<E>
  • Iterable是一个迭代器接口。
    接口Iterable，该接口包含一个能够产生Iterator接口的iterator()方法，并且Iterable对象被foreach用来在序列中移动，因此创建的任何实现了Iterable接口的类都可以将它用于foreach。
    java.util包中的Collection和Map接口及其常用子类的总结
    java.util包中的Collection和Map接口及其常用子类的总结

1.1Collection接口中的核心方法

****add(T t) //向类集中添加元素
****iterator() //取得类集迭代器
addAll()
clear()
contains()
remove()
size()
toArray()

---------简写，并不全是无参。加星号的表示比较重要。

collection只定义了存储数据的标准，但是无法区分存储类型。
实际中更多的是使用两个子接口：1. List（允许重复） 2. Set（不允许重复）

1.2List接口

在进行单个集合处理时，优先考虑List接口，是允许数据重复的。

List接口若想保存自定义类的对象，该类必须覆写equals()才能使用contains()、remove()。
所以使用List接口一定得覆写equals（）方法。

List接口除了实现Collection接口的方法，还有自己独有的方法。

public E get(int index) //根据索引获取数据
public E set(int index,E element) //根据索引更新数据，返回原来数据

List中有三个常用的子类，值得去深究它们之间的区别和底层实现。
1.ArrayList 2.Vector 3.LinkedList 都继承抽象类 AbstractList< E>抽象类

重点重点重点重点

  • 问题1：ArrayList和Vector区别

共同点：底层都是用数组实现存储对象
区别：

  1. 版本
    ArrayList JDK1.2。Vector JDK1.0:在类集出现之前，都是直接继承这个类。
  2. 初始化策略
    Vector在无参构造执行后将对象数组大小初始化为10.
    ArrayList在构造阶段并不初始化对象数组，在第一次添加元素时才初始化数组。-懒加载策略
    创建大小minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    DEFAULT_CAPACITY大小为10
  3. 扩容策略：
    Vector：2倍（根据操作系统不同而不同）
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    ArrayList：1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
  4. 线程处理：
    Vector： 方法上加锁，线程安全，效率较低。 synchronized
    ArrayList： 异步处理，线程不安全，效率较高。
    （即便要用线程安全的List，也不用Vector）
  5. 遍历：
    Vector： 支持较老的迭代器Enumeration
    ArrayList：不支持
  • 问题2：ArrayList和LinkedList区别

共同点：都没有加锁操作，异步处理。
区别：

  1. 底层实现：
    ArrayList：使用数组
    LinkedList：使用链表

1.3 Set接口

不允许数据重复！！

没有扩充方法，直接覆写collection的抽象方法。

  • 有两个很重要的子类：
  1. HashSet ||无序存储
    实际上就是HashMap 的Key值+一个静态的null对象
    底层使用哈希表+红黑树
    允许存放null
  2. TreeSet ||有序存储
    底层使用红黑树
    不允许存放null
    ：因为是有序存储，所以自定义类要想保存到TreeSet中
    必须①实现Comparable接口
    或者②向TreeSet中传入比较器（Compartor接口）
    实现比较标准，才能实现TreeSet中部分方法。
  • 问题1：说到了Comparable和Compartor接口，那就简单比较区分一下：

它们的目的和作用都是一样的，在Java中实现自定义类的比较。
多用于TreeSet和TreeMap。

但是使用方法上和功能实现上都是完全不一样的。

实现java.lang.Comparable（1.2）接口，就说明该类支持排序。
存放该类的collection或者数组可以通过collections.sort（）进行排序。可以直接存放在TreeSet中。
接口内就一个int ComparTo（T o）方法，覆写这个方法，就是告诉怎么去比较。在类内实现排序。
称之为 类内比较器。

第三方实现java.util.Comparator （1.5）接口，是需要比较的类本身不支持排序，就可以外部建立一个该类的"比较器"来进行排序。这个外部比较器实现Compartor接口即可。
接口中有个compare（T t，E e）方法。创建一个类在类外实现排序。必须实现equals
称之为 外部比较器。
-策略模式，更加灵活，可以轻松改变策略进行第三方排序。

  • 问题2：既然知道了TreeXXX自定义类的比较方法，那么同样在意顺序的HashXXX怎么比较对象顺序呢？

这就得引出一个HashCode概念，这是通过哈希算法散列得来的。哈希表中的概念。
要判断大小就得同时覆写HashCode（）和equals（）两个方法。
必须hashCode和equals都返回ture才是相等。
equals比较的是元素的内容，HashCode比较的是元素存储的经过hash转化的地址。

equals相同，hashcode一定保证相同
hashcode相同，equals不一定相同

这里又引入了一个问题，问题3：哈希碰撞，~~~
把任意长度的字符串变成固定长度的字符串，所以必有一个输出串对应无穷多个输入串，碰撞是必然存在的。
解决方法在这里就简单一提，
1.开放定址法，也就是一直为冲突的元素找新地址
2.再哈希法，就是同时构造多个hash函数，冲突就换函数
3.链地址法，把冲突的元素放进一个链表中
4.建立公共溢出区，将冲突的元素统一放入另一个区域

  • 问题4：那为什么非要在乎比较对象大小这个概念？

因为Set是不可重复的，那既然不可重复就得规定一个标准，让计算机知道怎么样才能算相等，就像定义了一个学生信息表，你就得规定姓名和学号完全一样才算相等。
还有就是TreeXXX在意的是对象的自然排序，所以必须要定义这个比较"准则"。

2.Map接口集合

保存二元偶对象（键值对）的最顶层接口。

public interface Map<K,V>

所有的元素都存放形式是entry对象，entry是Map接口的内部接口。

核心方法

put()				//加入数据
get()				//根据Key获取value
Set<K> KeySet()		//返回所有key值，用Set接收,不可重复
collection<V> values()	//获取所有value值，可以重复
Set<Map.Entry<K,V>> entrySet()	//将Map集合变为Set集合
V remove()			//移除某个key对应的value

常用子类
1.HashMap -使用最多
2.TreeMap
3.ConcurrentHashMap

2.1ConcurrentHashMap

juc包下，为了让集合变成线程安全的集合。推荐使用。

  1. 早期实现基于分段锁，Segment，将内部进行分段，HashEntry数组。
  2. JDK8之后，发生了很大改变。内部存储变得和HashMap十分相似，同样是桶数组，内部也是链表结构。
    内部仍有segment定义，仅仅是为了保证序列化兼容。
    初始化简化，改为lazy-load形式。
    使用volatile保证可见性。
    使用CAS操作，进行无锁并发操作。
    使用Unsafe、LongAdder等底层手段，进行优化。

2.2 HashMap

内部实现：数组+单链表
数组被分成一个桶，通过哈希地址来寻找桶的位置，哈希值相同的键值对就存放在这个桶里的链表下。
但如果链表大小超过了最大值，也就是内部规定的阈值，一般是8.链表就会树化。

问题1：为什么树化？

因为可以大幅度缩减遍历链表查找元素的时间。

问题2：怎么树化？

如果容量<树化阈值，就只会简单的扩容，若>则树化。

HashMap和HashSet初始化方式是一样的，都是懒加载策略，

resize（）方法有两个作用：1.初始化数组（桶）2.扩容

问题3：怎么规定扩容大小？

初始化一般是默认容量16.

扩容：newThr = oldThr <<1；每次都是*2

问题4：负载因子和容量？

负载因子就相当于可用余额占全部空间的百分比，一般是0.75

容量就是真正的总空间大小

阈值（可用余额） = 负载因子*容量

初始阈值 = 负载因子（默认0.75）*默认容量（也就是初始化容量，16） = 12

newCap = oldCap<<1;每次扩容2倍

这个阈值就是桶的最大可用空间大小，一旦超过，就会扩容，但其实还有0.25的空间，就是提前预防。

问题5：那hashcode怎么和桶的i联系起来呢？

i= （length-1）&hash， （关于hash碰撞Set部分已说明）

问题6：为什么hash表的length最好是2^n?

2^n-1就相当于后面的低位都变成了1，那么&操作的结果最大程度上取决于hash地址，唯一性提高，而且位运算效率更高。

  • Map集合迭代器输出

      //1.Map->Set
  Set<Map.Entry<Integer, String>> key = map.entrySet();
  //2.取得Set迭代器
  Iterator<Map.Entry<Integer, String>> iterator = key.iterator();
  //3.迭代输出
  while (iterator.hasNext()){
      Map.Entry<Integer,String> entry = iterator.next();
      System.out.println(entry.getKey()+"="+entry.getValue());
  }

2.3 几个经典问题

问题1：HashMap与Hashtable区别？

  • 相同点：都实现了Map接口
  • 区别
    Hashtable相当于HashMap的一个线程安全版。
  1. 元素要求：
    HashMap：允许key和value为空，且key有且只有一个null，value可以有多个null。
    Hashtable：key与value都不可为空
  2. 版本、线程：
    HashMap：JDK1.2 不加锁 异步处理 效率高 线程不安全
    Hashtable：JDK1.0 方法加锁 同步处理 效率低 线程安全
  3. 底层：
    HashMap：哈希表+红黑树（JDK8以后）
    Hashtable：哈希表

问题2：HashSet和HashMap关系
先有Map再有Set的
4. Set集合实际上就是value是同一个对象并且是空的Map集合。
XXSet本质上就是XXMap，先有Map再有Set。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
private static final Object PRESENT = new Object();
5. 反过来说，Map的Key值集合就是一个Set集合。

问题3：

3. 栈与队列

3.1 栈 Stack

  • 是一个继承Vecto类的集合类
    push() //入栈
    pop() //出栈
    peek() //返回栈顶元素但不出栈

应用：撤销、浏览器的返回、树的遍历、函数栈帧

3.2 队列 Queue

  • 是一个直接实现coolection接口的接口。
    add() //入队
    poll() //出队
    peek() //返回队头，不出队

实现
Queue queue = new LinkedList<>();

4. Collections工具类

  • 常用子类
  1. 将线程不安全集合包装成线程安全集合（不推荐）
    推荐使用juc包下的并发集合类（ConcurrentHashMap、CopyOnWriteArrayList）
    eg：把ArrayList变的安全
    内部实现就是在方法内部使用 线程安全同步代码块，效率较低
    synchronizedList(list)
  2. 向集合中一次加入多个元素
    addAll()
  3. 集合反转
    reverse()
  4. 集合排序
    sort()

写到这里，Collection接口和Map接口的特点、实现以及它们的常用子类的特点、区别、适用都已经有个大概了解和区分了。
这个总结的比较精炼，就是我觉得重要的都写了，图我也是花了一下午时间，如果看不懂的话可以去源码里找答案，看源码真的蛮有意思，一步跳一步像推理小说一样。哈哈~
嗯，可以从图中看见，Collection接口还实现了一个迭代器接口，下一篇博客再总结它吧~

相关推荐