Java之集合

桃扇骨 2022-01-10 02:45 237阅读 0赞

**集合**

**概念**

数据结构：存储数据的某种结构

（1）底层的物理结构

①数组：开辟连续的存储空间，每一个元素使用\[下标\]进行区别

②链式：不需要开辟连续的存储空间，但是需要“结点”来包装要存储的数据，结点包含两部分内容：

A、数据

B、记录其他结点的地址，例如：next，pre，left，right，parent等

（2）表现出来的逻辑结构：动态数组、单向链表、双向链表、队列、栈、二叉树、哈希表、图等

**Collection**

因为集合的类型很多，那么我们把它们称为集合框架。

集合框架分为两个家族：Collection（一组对象）和Map（一组映射关系、一组键值对）

**Collection**

Collection是代表一种对象的集合。它是Collection系列的根接口。

它们虽然：有些可能是有序的，有些可能是无序的，有些可能可以重复的，有些不能重复的，但是它们有共同的操作规范，因此这些操作的规范就抽象为了Collection接口。

常用方法：

（1）boolean add(Object obj)：添加一个

（2）boolean addAll（Collection c）：添加多个

（3）boolean remove(Object obj)：删除一个

（4）boolean removeAll(Collection c )： 删除多个

（5）boolean contains(Object c)：是否包含某个

（6）boolean containsAll(Collection c)： 是否包含所有

（7）boolean isEmpty()：是否为空

（8）int size()：获取元素个数

（9）void clear()：清空集合

（10）Object\[\] toArray()：获取所有元素

（11）Iterator iterator()： 获取遍历当前集合的迭代器对象

（12）retainAll(Collection c)：求当前集合与c集合的交集

**Collection****系列的集合的遍历**

1、明确使用Iterator迭代器

Collection c = ....;  
  
Iterator iter = c.iterator();  
while(iter.hashNext())\{  
Object obj = iter.next();  
//...  
\}

Iterator 接口的方法：

（1）boolean hasNext()

（2）Object next()

（3）void remove()

2、foreach

Collection c = ....;  
  
for(Object obj : c)\{  
//...  
\}

Iterator也是一个接口，它的实现类，通常在集合（容器）类中用内部类实现。并在iterator()的方法中创建它的对象。

public class MyArrayList implements Iterable\{   
private Object\[\] data;  
private int total;  
  
//其他代码省略....  
  
@Override  
public Iterator iterator() \{   
return new MyItr();  
\}  
  
private class MyItr implements Iterator\{   
private int cursor;//游标  
  
@Override  
public boolean hasNext() \{   
return cursor!=total;  
\}  
  
@Override  
public Object next() \{   
return data\[cursor\++\];  
\}  
\}  
\}

**List**

**List****概述**

List：是Collection的子接口。

List系列的集合：有序的、可重复的

List系列的常用集合：ArrayList、Vector、LinkedList、Stack

**List****的****API**

常用方法：

（1）boolean add(Object obj)：添加一个

（2）boolean addAll（Collection c）：添加多个

（3）void add(int index, Object obj)：添加一个，指定位置添加

（4）void addAll(int index, Collection c）：添加多个

（5）boolean remove(Object obj)：删除一个

（6）Object remove(int index)：删除指定位置的元素，并返回刚刚删除的元素

（7）boolean removeAll(Collection c )： 删除多个

（8）boolean contains(Object c)：是否包含某个

（9）boolean containsAll(Collection c)： 是否包含所有

（10）boolean isEmpty()：是否为空

（11）int size()：获取元素个数

（12）void clear()：清空集合

（13）Object\[\] toArray()：获取所有元素

（14）Iterator iterator()： 获取遍历当前集合的迭代器对象

（15）retainAll(Collection c)：求当前集合与c集合的交集

（16）ListIterator listIterator()：获取遍历当前集合的迭代器对象，这个迭代器可以往前、往后遍历

（17）ListIterator listIterator(int index)：从\[index\]位置开始，往前或往后遍历

（18）Object get(int index)：返回index位置的元素

（19）List subList(int start, int end)：截取\[start,end)部分的子列表

**ListIterator** **接口**

Iterator 接口的方法：

（1）boolean hasNext()

（2）Object next()

（3）void remove()

ListIterator 是 Iterator子接口：增加了如下方法

（4）void add(Object obj)

（5）void set(Object obj)

（6）boolean hasPrevious()

（7）Object previous()

（8）int nextIndex()

（9）int previousIndex()

**List****的实现类们的区别**

ArrayList、Vector、LinkedList、Stack

（1）ArrayList、Vector：都是动态数组

Vector是最早版本的动态数组，线程安全的，默认扩容机制是2倍，支持旧版的迭代器Enumeration

ArrayList是后增的动态数组，线程不安全的，默认扩容机制是1.5倍

（2）动态数组与LinkedList的区别

动态数组：底层物理结构是数组

优点：根据\[下标\]访问的速度很快

缺点：需要开辟连续的存储空间，而且需要扩容，移动元素等操作

LinkedList：底层物理结构是双向链表

优点：在增加、删除元素时，不需要移动元素，只需要修改前后元素的引用关系

缺点：我们查找元素时，只能从first或last开始查找

（3）Stack：栈

是Vector的子类。比Vector多了几个方法，能够表现出“先进后出或后进先出”的特点。

①Object peek()：访问栈顶元素

②Object pop()：弹出栈顶元素

③push()：把元素压入栈顶

（4）LinkedList可以作为很多种数据结构使用

单链表：只关注next就可以

队列：先进先出，找对应的方法

双端队列(JDK1.6加入)：两头都可以进出，找对应的方法

栈：先进后出，找对应的方法

**Set**

**Set****概述**

Set系列的集合：不可重复的

Set系列的集合，有有序的也有无序的。HashSet无序的，TreeSet按照元素的大小顺序遍历，LinkedHashSet按照元素的添加顺序遍历。

**实现类的特点**

（1）HashSet：

底层是HashMap实现。添加到HashSet的元素是作为HashMap的key，value是一个Object类型的常量对象PRESENT。

依赖于元素的hashCode()和equals()保证元素的不可重复，存储位置和hashCode()值有关，根据hashCode()来算出它在底层table数组中的\[index\]

（2）TreeSet

底层是TreeMap实现。添加到TreeSet的元素是作为TreeMap的key，value是一个Object类型的常量对象PRESENT。

依赖于元素的大小，要么是java.lang.Comparable接口compareTo(Object obj)，要么是java.util.Comparator接口的compare(Object o1, Object o2)来比较元素的大小。认为大小相等的两个元素就是重复元素。

（3）LinkedHashSet

底层是LinkedHashMap。添加到LinkedHashSet的元素是作为LinkedHashMap的key，value是一个Object类型的常量对象PRESENT。

LinkedHashSet是HashSet的子类，比父类多维护了元素的添加顺序。

当且仅当，你既想要元素不可重复，又要保证元素的添加顺序时，再使用它。

**Map**

**Map****概述**

用来存储键值对，映射关系的集合。所有的Map的key都不能重复。

键值对、映射关系的类型：Entry类型

Entry接口是Map接口的内部接口。所有的Map的键值对的类型都实现了这个接口。  
HashMap中的映射关系，是有一个内部类来实现Entry的接口，JDK1.7是一个叫做Entry的内部类实现Entry接口。  
JDK1.8是一个叫做Node的内部类实现Entry接口。  
TreeMap中的映射关系，是有一个内部类Entry来实现Entry的接口

**API**

（1）put(Object key, Object value)：添加一对映射关系

（2）putAll(Map m)：添加多对映射关系

（3）clear()：清空map

（4）remove(Object key)：根据key删除一对

（5）int size()：获取有效元素的对数

（6）containsKey(Object key)：是否包含某个key

（7）containsValue(Object value)：是否包含某个value

（8）Object get(Object key)：根据key获取value

（9）遍历相关的几个方法

Collection values()：获取所有的value进行遍历

Set keySet()：获取所有key进行遍历