java容器-Collection和Map的理解

╰半夏微凉° 2022-10-23 08:29 162阅读 0赞

# 1.JAVA内部的容器类 #

**容器**：在Java当中，如果有一个类专门用来存放其它类的对象，这个类就叫做容器，或者就叫做集合，集合就是将若干性质相同或相近的类对象组合在一起而形成的一个整体  
在JAVA的util包中有两个所有集合的父接口Collection和Map,它们的父子关系：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]  
在编程的时候，有时候需要集中存放多个数据，可以用数组来保存多个数据，但是数组的长度是不可变的，一旦数组的长度确定了之后就无法再改变，如果要保存可变长度的数据的话，数组肯定是不行的。而且数组也无法保存具有一定关联的数据。为了可以保存上面的这些信息，java提供了集合类，主要是负责保存、盛装数据的。因此集合相当于一个容器类。  
集合类有两个派生类，Collection和Map.

# 2.Collection #

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口” 如List和Set（List是有序、重复的集合，set是无序、不可重复的集合）。

## 2.1 List (以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。) ##

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。  
和下面要提到的Set不同，List允许有相同的元素。  
除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

### 2.1.1 LinkedList类 ###

*  由列表实现的List，实现所有可选的列表操作，并且允许所有元素（包括 null）。对顺序访问进行了优化，向List中间插入与删除得开销不大，随机访问则相对较慢(可用ArrayList代替)。它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()，这些方法(没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。
 *  此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
 *  所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端)
 *  方便插入和删除，但是不方便与随便检索 （按插入顺序排序）
 *  注意，此实现**不是同步的**。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须保持外部同步。

### 2.1.2 ArrayList类 ###

#### [定义][Link 1] ####

*  ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
 *  每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
 *  和LinkedList一样，ArrayList也是**非同步的（unsynchronized）。**
 *  它允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList，而不是用来插入和删除元素，因为这比LinkedList开销要大很多。
 *  如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

#### 常用的方法 ####

boolean add(E e)  
将指定的元素添加到此列表的尾部。  
void add(int index, E element)  
将指定的元素插入此列表中的指定位置。  
boolean addAll(Collection<? extends E> c)  
按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。  
boolean addAll(int index, Collection<? extends E> c)  
从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。  
void clear()  
移除此列表中的所有元素。  
Object clone()  
返回此 ArrayList 实例的浅表副本。  
boolean contains(Object o)  
如果此列表中包含指定的元素，则返回 true。  
void ensureCapacity(int minCapacity)  
如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。  
E get(int index)  
返回此列表中指定位置上的元素。  
int indexOf(Object o)  
返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。  
boolean isEmpty()  
如果此列表中没有元素，则返回 true  
int lastIndexOf(Object o)  
返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。  
E remove(int index)  
移除此列表中指定位置上的元素。  
boolean remove(Object o)  
移除此列表中首次出现的指定元素（如果存在）。  
protected void removeRange(int fromIndex, int toIndex)  
移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。  
E set(int index, E element)  
用指定的元素替代此列表中指定位置上的元素。  
int size()  
返回此列表中的元素数。  
Object\[\] toArray()  
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。  
T\[\] toArray(T\[\] a)  
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。  
void trimToSize()  
将此 ArrayList 实例的容量调整为列表的当前大小。

### 2.1.3 Vector类 ###

Vector 类可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。但是，Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。  
Vector非常类似ArrayList，但是**Vector是同步的**。由Vector创建的Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

### 2.1.4 Stack类 ###

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

## 2.2 [Set][] (不能含有重复的元素) ##

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。  
很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。  
请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

#### 常用方法 ####

*  Set(interface):  
    存入Set的每个元素必须是唯一的，这也是与List不同的，因为Set不保存重复元素。加入Set的Object必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。
 *  HashSet: HashSet能快速定位一个元素，存入HashSet的对象必须定义hashCode()。
 *  TreeSet: 保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。
 *  LinkedHashSet: 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。  
    　　HashSet采用散列函数对元素进行排序，这是专门为快速查询而设计的；TreeSet采用红黑树的数据结构进行排序元素；LinkedHashSet内部使用散列以加快查询速度，同时使用链表维护元素的次序，使得看起来元素是以插入的顺序保存的。需要注意的是，生成自己的类时，Set需要维护元素的存储顺序，因此要实现Comparable接口并定义compareTo()方法。

# 3.Map #

[参考链接][Set]  
Map接口储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。最常见的Map实现类是HashMap，他的储存方式是哈希表，优点是查询指定元素效率高。  
Map接口提供了将键映射到集合的对象,一个映射不能包含重复的键。每个键最多只能映射到一个值.Map接口中同样提供了集合的常用方法,如clear()方法,isEmpty()方法,Size()方法等.。

## 3.1 HashMap ##

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。  
此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。  
HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。  
加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。  
如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。  
如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。  
注意，此实现**不是同步的**。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。

## 3.2 Hashtable ##

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。  
Hashtable **是同步的**

## 3.3 LinkedHashMap ##

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入 键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）  
此实现可以让客户避免未指定的、由 HashMap（及 Hashtable）所提供的通常为杂乱无章的排序工作，同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本，而与原映射的实现无关：Map copy = new LinkedHashMap(m);  
此类提供所有可选的 Map 操作，并且允许 null 元素。与 HashMap 一样，它可以为基本操作（add、contains 和 remove）提供稳定的性能，假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支，其性能很可能比 HashMap 稍逊一筹，不过这一点例外：LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量 成比例。  
链接的哈希映射具有两个影响其性能的参数：初始容量和加载因子。它们的定义与 HashMap 极其相似。要注意，为初始容量选择非常高的值对此类的影响比对 HashMap 要小，因为此类的迭代时间不受容量的影响。  
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。

# 4.总结 #

*  如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
 *  如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
 *  要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
 *  尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。
 *  在各种Lists中，最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList()；  
    Vector总是比ArrayList慢，所以要尽量避免使用。
 *  在各种Sets中，HashSet通常优于HashTree（插入、查找）。只有当需要产生一个经过排序的序列，才用TreeSet。  
    HashTree存在的唯一理由：能够维护其内元素的排序状态。
 *  当元素个数固定，用Array，因为Array效率是最高的。

**注意：**

1.  Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。
2.  Set和Collection拥有一模一样的接口。
3.  List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)…。(add/get) 一般使ArrayList。用LinkedList构造堆栈stack、队列queue。
4.  Map用 put(k,v) /get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。HashMap会利用对象的hashCode来快速找到key。  
    **hashing**  
    哈希码就是将对象的信息经过一些转变形成一个独一无二的int值，这个值存储在一个array中。我们都知道所有存储结构中，array查找速度是最快的。所以，可以加速查找。发生碰撞时，让array指向多个values。即，数组每个位置上又生成一个梿表。
5.  Map中元素，可以将key序列、value序列单独抽取出来。  
    使用keySet()抽取key序列，将map中的所有keys生成一个Set。  
    使用values()抽取value序列，将map中的所有values生成一个Collection。
6.  为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。

深入学习：  
参考链接：[深入理解java中的容器][java]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]: /images/20221023/4ac1772be95b4246b41e4e886ba3e98f.png
[Link 1]: https://baike.baidu.com/item/ArrayList/5529371
[Set]: https://www.jianshu.com/p/8ef342da8732
[java]: https://blog.csdn.net/a2011480169/article/details/52047600