java面向对象——集合：list、queue、set、map

末蓝、 2022-05-09 15:04 263阅读 0赞

#### 数组 ####

- 本质上就是一段连续的内存空间，用于记录多个类型相同的数据。
       - 数组一旦定义则内存空间固定，若太大或太小都会造成麻烦。
       - 插入和删除元素时可能会移动大量元素，因此效率比较低。   
       - 使用下标访问元素非常便利，支持随机访问。
       - 数组中的元素可以是基本数据类型，也可以是引用数据类型。

#### 集合 ####

- 内存空间可以连续也可以不连续，元素类型可以相同也可以不同。
       - 集合一旦定义内存空间不固定，而且可以动态调整。
       - 插入和删除元素时可以不移动大量的元素。
       - 部分集合支持下标访问，部分集合不支持。
       - 集合中的元素必须是引用数据类型，借助包装类。

无论是数组还是集合本质上都是一种容器，集合类指描述容器的类和接口。

#### 基本分类 ####

集合框架主要分为两大类：java.util.Collection集合/接口 和 java.util.Map集合/接口。  
其中Collection集合的元素基本单位是：单个元素。  
其中Map集合的元素基本单位是：单对元素。

在以后的开发中很少直接使用Collection集合，通常使用该集合的子接口：List接口、Queue接口以及Set接口等。

**Collection集合的常用方法**

boolean isEmpty() - 用于判断当前集合中是否为空/是否有元素。
    int size() - 用于返回当前集合中元素的个数。
    
    boolean add(E e) - 用于将参数指定的元素放入当前集合，是否成功用返回值表示。
    boolean addAll(Collection<? extends E> c) - 用于将参数指定集合的所有元素放入当前集合中。
    boolean remove(Object o) - 用于删除当前集合中参数指定的单个元素。
    boolean removeAll(Collection<?> c) - 用于将参数指定集合中的所有元素从当前集合中删除。
    void clear() - 用于清空当前集合。 
    
    boolean contains(Object o) - 用于判断参数指定的元素是否存在当前集合中。
    boolean containsAll(Collection<?> c) - 用于判断参数指定的集合中所有元素是否包含在当前集合中。
    boolean retainAll(Collection<?> c) - 用于计算当前集合和参数集合的交集并保留
           - 若当前集合由于调用而发生更改则返回true，否则返回false。
    Iterator<E> iterator() - 用于获取当前集合的迭代器。

#### List接口 ####

java.util.List接口是Collection接口的子接口，该集合中元素有先后次序，允许重复该接口的主要实现类有：ArrayList类、LinkedList类、Stack类、Vector类（笔试）。

1.  ArrayList类的底层是采用动态数组实现的，访问方便，增删不方便
2.  LinkedList类的底层是采用链表实现的，访问不方便，增删方便
3.  Stack类（栈）的底层是采用动态数组实现的，但该集合具有后进先出的特性
4.  Vector类的底层是采用动态数组实现的，但该类与ArrayList类相比是属于线程安全的类，效率比较低，因此推荐使用ArrayList类。

**常用的方法**

void add(int index,E element)	将element放在index位置上 index的范围：0~size()
    boolean addAll(int index,Collection<?extends E>c) 	将指定集合中所有元素增加到当前集合的index的位置
    E remove(int index)		用于删除指定位置的元素，并返回该元素
    E set(int index,E element)		用于将当前集合中index位置的元素element赋值
    E get(int index)		用于返回当前集合中下标为index位置的元素
    List<E> subList(int fromIndex,int toIndex)		
    	用于获取当前集合中从fromIndex(包含)到toIndex(不包含)之间的部分的视图
    	内存空间还是同一份，一改都改。

#### 泛型机制 ####

目前集合中虽然可以存放不同类型的数据，其原因是将所有数据都看做Object类型放入的，但从集合中取出元素并表达真实类型时，需要进行强制类型转换，该转换可能引发类型转换异常。为了避免上述错误的发生，从jdk1.5开始加入泛型的机制，也就是在集合名称的后面使用<数据类型>的方法明确该集合中元素的类型，若放入其他类型则编译报错。

如：List<String> l1 = new LinkedList<String>();

泛型的本质就是参数化数据类型也就是将数据类型作为实参传递给形参E,从而在接口/类体中的E都变成了实参类型。

#### Queue接口 ####

栈（Stack）是一种具有后进先出特性的数据结构，简称为LIFO（last in first out）.

队列（Queue）是一种具有先进先出特性的数据结构，简称为FIFO（first in first out）

java.util.Queue接口是Collection接口的子接口，主要实现类：LinkedList类

**常用方法**

boolean offer(E e) 	用于将参数指定的元素插入到当前队列的尾部，插入成功返回true，否则返回false
    E poll()	用于将队列中队首元素进行出队操作，若队列为空则返回null.
    E peek()	用于获取队列中的队首元素并返回，若队列为空则返回null。

#### Set接口 ####

java.util.Set接口是Collection接口的子接口，元素没有先后次序，不能重复

该接口的主要实现类：

HashSet类：底层是采用一张哈希表实现的

TreeSet类：底层是采用一颗二叉树实现的

方法与Collection集合中的方法完全一致。

Iterator 为接口
    Iterator<E>iterator()	- 用于获取当前集合中的迭代器，用于遍历集合中所有元素

迭代器的使用

boolean hasNext() 	- 判断当前迭代器指向的集合中是否有元素可以遍历/访问
    E next()	- 获取可以访问到的元素，并指向下一个元素，返回获取到的元素值
    void remove()	- 删除上一次获取到的元素值

注意：当使用迭代器遍历集合中的元素时，若需要删除元素这必须使用迭代器自己的remove()方法。不能使用集合的remove()方法，否则会引发并发修改异常。

总结：对于Set集合来说的遍历方式有三种：toString()、迭代器、for-each结构

对于List集合来说的遍历方式除了上述三种之外，还多了一种get()方法。

**元素放入HashSet集合的过程**

1.  使用元素调用hashCode()方法，得到该元素的哈希码值
2.  将哈希码值交给哈希算法，算出该元素在哈希表中的索引位置
3.  若该索引位置没有元素，则直接将新元素插入该位置
4.  若该索引位置有元素，则判断新元素与已经存在的元素是否相等
5.  若相等，则放弃新元素的插入，保留旧元素
6.  若不相等，使用新元素与后续元素继续比较，若都不相等，则插入到最后

#### TreeSet类 ####

二叉树：指每个节点最多只有两个子节点的树形结构

【有序二叉树】：

1.  要求左子树中任意节点的元素值都小于根节点元素值
2.  要求右子树中任意节点的元素值都大于根节点元素值
3.  左右子树的内部也依然满足上述规则

【元素放入TreeSet类时需要制定比较大小的规则】：

1.  使用元素的自然排序来指定，实现java.lang.Comparable接口，重写compareTo方法
2.  使用比较器来指定，实现java.util.Comparator接口，重写compare方法  
    该比较器由创建Set集合时的构造方法传入
3.  比较器指定大小规则的优先级高于自然排序，若没有比较器则默认采用自然排序。自然排序的规则比较单一，而比较器排序的规则可以通过匿名内部类多元化处理

**常用的工具类**

java.util.Arrays 类是有关数组操作的工具类，里面提供大量操作数组元素的方法。

java.util.Collections类是有关集合操作的工具类，里面提供大量操作集合的方法。

**四种遍历方式**

//自定义List集合放入4个整数，要求使用四中方式进行遍历
    		List<Integer> l2 = new ArrayList<Integer>();
    		l2.add(111);
    		l2.add(222);
    		l2.add(333);
    		l2.add(444);
    		System.out.println(l2);				//1
    		System.out.println("------------------------------------");
    		for(int i = 0;i<l2.size();i++)		//2
    			System.out.print(l2.get(i)+" ");
    		System.out.println("\n------------------------------------");
    		for(int i : l2)						//3
    			System.out.print(i+" ");
    		System.out.println("\n------------------------------------");
    		Iterator it2 = l2.iterator();		//4
    		while(it2.hasNext())
    			System.out.print(it2.next()+" ");

**TreeSet排序**

public class Student implements Comparable<Student>{
    	private int num;
    	private String name;
    	private int age;
    	@Override
    	public int compareTo(Student o) {		//将比较的方法进行重写。大于0,放右边
    		//调用String类内部的compareTo()方法 getNum()为调用对象，o为指定对象
    		return getNum()-o.getNum();
    	}
    }
    -------------------------------------------------------------------------------------
    public class TestTreeSet {
    	public static void main(String[] args) {
    		Set<Student> s1 = new TreeSet<Student>();
    		s1.add(new Student(1,"guanyu",35));
    		s1.add(new Student(2,"zhangfei",32));
    		s1.add(new Student(5,"machao",24));
    		s1.add(new Student(3,"zhaoyun",26));
    		s1.add(new Student(4,"huangzhong",45));
    		//使用元素的自然排序指定，实现java.long.Comparable接口，重写compareTo方法
    		System.out.println(s1);
    		
    		System.out.println("-------------------------");
    		//采用匿名内部类的策略准备一个接口类型的引用
    		Comparator<Student> cp = new Comparator<Student>(){		
    			//o1对象代表新增加的元素，o2对象代表二叉树中已有的元素
    			@Override
    			public int compare(Student o1, Student o2) {
    				//大于0,o1数大，放右边
    				return o1.getAge()-o2.getAge();
    			}
    		};
    		//使用比较器来指定按照学号进行比较大小的规则,注意将(cp)作为参数传入。
    		Set<Student> s2 = new TreeSet<Student>(cp);
    		s2.add(new Student(1,"guanyu",35));
    		s2.add(new Student(2,"zhangfei",32));
    		s2.add(new Student(5,"machao",24));
    		s2.add(new Student(3,"zhaoyun",26));
    		s2.add(new Student(4,"huangzhong",45));
    		System.out.println(s2);
    	}
    }

#### Map接口（重点） ####

java.util.Map<K,V>接口用于存放键值对的集合，其中键不允许重复，一个键只能对应一个值

该结构的主要实现类有：

HashMap类：底层是采用哈希表来实现的

TreeMap类：底层是采用红黑树来实现的

Hashtable（笔试）：线程安全，基本使用HashMap

**常用的方法：**

boolean isEmpty()	- 用于将参数指定的key和value组成一队放入当前集合
    int size()	- 用于获取当前集合中的键值对个数
    V put(K key,V value)	- 用于将参数指定的key和value组成一对放入当前集合
    		若当前集合中没有key，则相当于增加的功能，返回null
    		若当前集合中有key,则相当于修改的功能，返回value
    V remove(Objcet key)	参数指定的key来删除对应键值对，返回之前value
    
    boolean containsKey(Objcet key)		判断key是否存在
    boolean containsValue(Objcet value)		判断value是否存在
    V get(Object key)	根据参数指定的key来返回对应的value
    
    Set<Map.Entry<k,v>>entrySet()	用于将集合转换成为Set视图并返回
    	K getKey()	用于获取当前元素中的key值
    	V getValue()	用于获取当前元素中的value值
    Set<K> keySet()		用于将当前集合中的key值转换为Set视图并返回

**分组**

List<Grope> l1 = new ArrayList<Grope>();
    Map<String,List<Grope>> m1 = new HashMap<String,List<Grope>>();
    l1.add(new Grope("黄蓉","120"));
    l1.add(new Grope("郭靖","119"));
    l1.add(new Grope("杨过","110"));
    m1.put("好友", l1);
    
    List<Grope> l2 = new ArrayList<Grope>();
    l2.add(new Grope("金镶玉","10010"));
    l2.add(new Grope("孙二娘","10086"));
    m1.put("闺蜜", l2);
    System.out.println(m1);

**map排序**

public class TestMap {
    	public static void main(String[] args) {
    		//创建一个Map接口类型的引用，指向HashMap对象
    		//Map接口用于存放键值对的集合，其中键值对不允许重复,一个键只允许对应一个值
    		Map<Integer,String> m1 = new HashMap<Integer,String>();
    		
    		//将指定的键值对放入集合中，若原集合中没有该Key,则返回null,有则等于修改的功能，返回修改的值
    		System.out.println(m1.put(1, "one"));
    		System.out.println(m1.put(2, "two"));
    		System.out.println(m1.put(3, "three"));
    		System.out.println(m1);
    		
    		System.out.println("----------------------------");
    		
    		//判断key是否存在，存在返回true
    		System.out.println(m1.containsKey(2));
    		System.out.println(m1.containsKey(5));
    		System.out.println(m1.containsValue("one"));
    		System.out.println(m1.containsValue("five"));
    		
    		System.out.println("----------------------------");
    		
    		//根据Key删除该键值对
    		System.out.println(m1.remove(2));
    		System.out.println(m1);
    		System.out.println(m1.remove(4));
    		System.out.println(m1);
    		
    		System.out.println("----------------------------");
    		
    		//将当前集合转换成Set视图并遍历里面的所有元素
    		Set<Map.Entry<Integer, String>> sm = m1.entrySet();
    		//使用增强版的for循环可以变脸Set集合中的每个元素
    		for(Map.Entry<Integer, String> x : sm)
    			System.out.println(x.getKey()+":"+x.getValue());
    	}
    }