【面试小知识】Collection（接口）集合

青旅半醒 2022-11-28 00:46 206阅读 0赞

> 乾坤未定，你我皆是黑马~

# 1. 简介 #

近期，在牛客网看到关于collection接口集合的问题，一时间自己没想起来，于是自己整理了一下。

# 2. Collection（接口）集合架构图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 3.集合分析 #

我们可以看到，关于Collection主要分为常见的**Set、list、queue**

## 3.1 Set（接口、无序、无索引、不重复性） ##

对于set集合，一般我们在用的时候，主要利用其不重复性，比如我们在筛选数据时，放进去，提出来，Set集合自动帮我们去除掉重复的数据

*  HashSet：底层数据结构是哈希表（无序，唯一）。保证元素唯一性依赖于两个方法：hashCode()和equals()
 *  LinkedHashSet：底层数据结构是链表和哈希表。（先入先出，有序，唯一）。通过链表保证有序性， 通过哈希表保证唯一性。
 *  TreeSet：底层数据结构是红黑树。（唯一，有序）

这里主要谈一下关于Set数组去重的问题，在Set源码中，`boolean add(E e);`我们看到关于其添加的操作是一个boolean的判断值，也就是我们在添加数据时，需要判断当前Set中有没有该数据。  
在HashSet中，利用HashCode()和equals()进行比较：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]  
补充：关于HashCode：**通过对象的内部地址(也就是物理地址)转换成一个整数，然后该整数通过hash函数的算法就得到了hashcode**  
详情参考：[HashCode][]  
这也是为什么我们在重写时，HashCode和equals要一起重写的原因  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 2]

看上图，我们重写了equals()函数，只要传入的对象的w/q一样就返回true，但是，我们看上述流程图会发现，他们会先进行HashCode的比较，所以，在HashCode这一关过不去，就更不用谈equals()了。

## 3.2 list（有序，可重复。） ##

*  ArrayList：底层实现的数据结构是数组，查询快，增删慢。线程不安全，效率高
 *  LinkedList：底层实现的数据结构是链表，查询慢，增删块。线程不安全，效率高
 *  Vector：底层实现的数据结构是数组，查绚块，增删慢。线程安全，效率低。

关于ArrayList和LinkedList的区别以及ArrayList的扩容机制：[ArrayList和LinkedList][ArrayList_LinkedList]

## 3.3 queue（队列） ##

*  queue：先进先出
 *  Dueue:双向队列，可以两端对数据进行操作
 *  priorityqueue(优先队列)：按照给定的优先级，进行出队列，用于迪杰斯特拉算法，用于计算最短路径。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/4efed90704a54b22ba4fcad0c7bf99dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/57ada25e4c154ac48ca08743bcf94c51.png
[HashCode]: https://www.cnblogs.com/whgk/p/6071617.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/82fad1b7e80e4116bc56c946d75de3f2.png
[ArrayList_LinkedList]: https://editor.csdn.net/md/?articleId=107949241