【数据结构 八】---集合类

时间:2022-10-11 17:00:22
严格意义来说,集合类不能算作一种数据结构,但在统一归纳上,依据其底层实现,便于理解,就当成数据结构来统筹在刷题的时候发现有很多关于集合类的问题,是时候总结一波了。

集合类概述

为什么使用集合类

数组是很常用的一种的数据结构,我们用它可以满足很多的功能,但有时我们会遇到如下这样的问题:
1、我们需要该容器的长度是不确定的
2、我们需要它能自动排序
3、我们需要存储以键值对方式存在的数据。
与数组类似的数据结构——集合类,集合类在Java中有很重要的意义,保存临时数据,管理对象,泛型,Web框架等,很多都大量用到了集合类。
以下是一张集合类图:
【数据结构 八】---集合类
Collection接口是集合类的根接口,Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口,就是Set和List。Set中不能包含重复的元素。List是一个有序的集合,可以包含重复的元素,提供了按索引访问的方式。

Map是Java.util包中的另一个接口,它和Collection接口没有关系,是相互独立的,但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key,但是可以包含相同的value。

Iterator,所有的集合类,都实现了Iterator接口,这是一个用于遍历集合中元素的接口,主要包含以下三种方法:
1.hasNext()是否还有下一个元素。
2.next()返回下一个元素。
3.remove()删除当前元素。

【数据结构 八】---集合类

常见的集合类

实现Collection接口:Set(无序、不能重复)、List(有序、可重复)

【数据结构 八】---集合类

Set接口和List接口的异同
相同点:都实现了Collection接口
不同点:Set接口不保证维护元素的顺序,且元素不能重复。List接口维护元素的顺序,且元素可以重复。

【数据结构 八】---集合类

====================ArrayList和其他两兄弟的比较=======================
ArrayList和Vector
1,vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用arraylist效率比较高。
2,如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据,用vector有一定的优势。
3,如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,如果频繁的访问数据,这个时候使用vector和arraylist都可以。而如果移动一个指定位置会导致后面的元素都发生移动,这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据时其它元素不移动。
ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要涉及到数组元素移动等内存操作,所以索引数据快,插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快。

ArrayList和LinkList
相同点:都实现了Collection接口
不同点:ArrayList基于数组,具有较高的查询速度,而LinkedList基于双向循环链表,具有较快的添加或者删除的速度,二者的区别,其实就是数组和列表的区别。上文有详细的分析。

====================HashSet和其他两兄弟的比较=========================
HashSet和TreeSet
TreeSet: 提供排序功能的Set,底层为树结构 。相比较HashSet其查询速度低,如果只是进行元素的查询,我们一般使用HashSet。

HashSet和LinkedHashSet
HashSet,为快速查找而设计的Set。存入HashSet的对象必须实现hashCode()和equals()。
LinkedHashSet,具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序),于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

实现Map接口(键值对、键唯一、值不唯一):

以HashMap及其实现类为主
我们常用的有Map及其实现类HashMap(LinkedHashMap),HashTable,TreeMap
【数据结构 八】---集合类
最常用的就是HashMap:Map集合中存储的是键值对,键不能重复,值可以重复。根据键得到值,对map集合遍历时先得到键的set集合,对set集合进行遍历,得到相应的值。
【数据结构 八】---集合类
在插入值的过程中:HashMap可以插入null的key或value,插入的时候,检查是否已经存在相同的key,如果不存在,则直接插入,如果存在,则用新的value替换旧的value

=======HashMap和其他三兄弟的比较=======================

HashMap和HashTable
相同点:二者都实现了Map接口,因此具有一系列Map接口提供的方法。
不同点:

1,继承不同
public class Hashtable extends Dictionary implements Map
public class HashMap extends AbstractMap implements Map

2,Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下,可以直接使用Hashtable,但是要使用HashMap的话就要自己增加同步处理了。

3,Hashtable中,key和value都不允许出现null值。在HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。

4,两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式 。

5,哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值。而且用与代替求模:
int hash = hash(k);
int i = indexFor(hash, table.length);

6 , Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。

7,Hashtable有contains方法而HashMap没有contains方法

//以下是Hashtable的方法
public synchronized boolean contains(Object value)
public synchronized boolean containsKey(Object key)
public boolean containsValue(Object value)
//以下是HashMap中的方法,注意,没有contains方法,所以,D错误
public boolean containsKey(Object key)
public boolean containsValue(Object value)

这些就是一些比较突出的不同点,实际上他们在实现的过程中会有很多的不同,如初始化的大小、计算hash值的方式等等。毕竟这两个类包含了很多方法,有很重要的功能,所以其他不同点,请感兴趣的读者自己去看源码,去研究。笔者推荐使用HashMap,因为她提供了比HashTable更多的方法,以及较高的效率,如果大家需要在多线程环境中使用,那么用Collections类来做一下同步即可。
HashMap和TreeMap
HashMap具有较高的速度(查询),TreeMap则提供了按照键进行排序的功能。

HashMap和LinkedHashMap
具有LinkedHashMap的查询速度,且内部使用链表维护元素的顺序(插入的次序),于是在使用迭代器遍历Map时,结果会按元素插入的次序显示。

集合类的使用

Arraylist的基本功能

基本操作和遍历

package com.xtfggef.list.test; 

import java.util.ArrayList;

/**
*
* 关于ArrayList的基本操作
* 其它操作感兴趣的读者可以自己结合源码实现一下
* * @author erqing
*
*/

public class ListTest {

public static void main(String[] args) {

/* 新建一个ArrayList */
ArrayList<String> list = new ArrayList<String>();
System.out.println("初始化大小:" + list.size());

/* 添加元素 */
list.add("zzz");
list.add("egg");
list.add("hell");
list.add("child");
System.out.println("当前容量:" + list.size());

/* 将ArrayList的大小和实际所含元素的大小设置一致 */
list.trimToSize();

/* 遍历 */
for (String string : list) {
System.out.println(string);
}

/* 在指定位置插入元素 */
list.add(2, "zhu");

for (String string : list) {
System.out.println(string);
}

System.out.println("--------------");

/* 清空list */
list.clear();

/* 遍历 */
for (String string : list) {
System.out.println(string);
}
System.out.println("--------------");
}
}

运行结果

初始化大小:0
当前容量:4
zzz
egg
hell
child
zzz
egg
zhu
hell
child
--------------

--------------

查找替换

fill——使用指定元素替换指定列表中的所有元素。
frequency——返回指定 collection 中等于指定对象的元素数。
indexOfSubList—— 返回指定源列表中第一次出现指定目标列表的起始位置,如果没有出现这样的列表,则返回 -1。
lastIndexOfSubList——返回指定源列表中最后一次出现指定目标列表的起始位置,如果没有出现这样的列表,则返回-1。
max—— 根据元素的自然顺序,返回给定 collection 的最大元素。
min——根据元素的自然顺序 返回给定 collection 的最小元素。
replaceAll——使用另一个值替换列表中出现的所有某一指定值。

public static void main(String[] args) {  

java.util.List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);

for (Integer integer : list) {
System.out.println(integer);
}
/*找出最大值*/
int max = Collections.max(list);
System.out.println("最大的为:"+max);

/*替换指定元素*/
Collections.replaceAll(list, 3, 6);
System.out.println("替换后:");
for (Integer integer : list) {
System.out.println(integer);
}
/*用指定元素替换指定list中的元素*/
Collections.fill(list, 6);
System.out.println("替换后:");
for (Integer integer : list) {
System.out.println(integer);
}

/*找出某个list里某个元素的个数*/
int count = Collections.frequency(list, 6);
System.out.println("里面有6的个数:"+count);
}

运行结果

1
2
3
最大的为:3
替换后:
1
2
6
替换后:
6
6
6
里面有6的个数:3

排序

reverse——对List中的元素进行转置
shuffle——对List中的元素随即排列
sort——对List中的元素排序
swap——交换List中某两个指定下标位元素在集合中的位置。
rotate——循环移动

public static void main(String[] args) {  

List<Integer> list = new ArrayList<Integer>();
list.add(5);
list.add(2);
list.add(1);
list.add(9);
list.add(0);

System.out.println("排序前:");
for (Integer integer : list) {
System.out.print(integer+" ");
}
System.out.println();

/*排序*/
Collections.sort(list);

System.out.println("排序后");
for (Integer integer : list) {
System.out.print(integer+" ");
}
}

运行结果

输出:
排序前:
5 2 1 9 0
排序后
0 1 2 5 9

HashSet的基本功能

Hashmap的基本功能

基本操作和遍历

第一种方式:KeySet()

将Map中所有的键存入到set集合中。因为set具备迭代器。所有可以迭代方式取出所有的键,再根据get方法。获取每一个键对应的值。 keySet():迭代后只能通过get()取key 。取到的结果会乱序,是因为取得数据行主键的时候,使用了HashMap.keySet()方法,而这个方法返回的Set结果,里面的数据是乱序排放的。

Map map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");
//先获取map集合的所有键的set集合,keyset()
=======================================================================
Iterator it = map.keySet().iterator();
//获取迭代器
while(it.hasNext()){
Object key = it.next();
System.out.println(map.get(key));
}
lisi1
lisi2
lisi3
lisi4

第二种:entrySet()(常用)

返回此映射中包含的映射关系的 Set 视图。(一个关系就是一个键-值对),就是把(key-value)作为一个整体一对一对地存放到Set集合当中的。Map.Entry表示映射关系。entrySet():迭代后可以e.getKey(),e.getValue()两种方法来取key和value。返回的是Entry接口。

Map map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");
=====================================================================
//将map集合中的映射关系取出,存入到set集合
Iterator it = map.entrySet().iterator();
while(it.hasNext()){
Entry e =(Entry) it.next();
System.out.println("键"+e.getKey () + "的值为" + e.getValue());
}

持续更新中………

面试中的集合类(错题本)

Collection和Collections的区别

java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化,就像一个工具类,服务于Java的Collection框架。

HashSet子类依靠什么方法区分重复元素

HashSet内部使用Map保存数据,即将HashSet的数据作为Map的key值保存,这也是HashSet中元素不能重复的原因。而Map中保存key值前,会去判断当前Map中是否含有该key对象,内部是先通过key的hashCode,确定有相同的hashCode之后,再通过equals方法判断是否相同。

Arraylist的初始容量

ArrayList的构造函数总共有三个:
(1)ArrayList()构造一个初始容量为 10 的空列表。
(2)ArrayList(Collection