21天学会Java之(Java SE第十篇):容器(集合框架)、容器中的泛型

矫情吗；* 2023-02-10 13:29 163阅读 0赞

> 在日常开发中，我们时刻需要和数据打交道，而如何处理这些数据就成为编程中的重要内容了。在Java中我们可以使用“容器”来容纳和管理数据。顾名思义，生活中我们有锅碗瓢盆等容器来容纳物体，而程序中的“容器”也有类似的功能，我们可以使用它来容纳和处理数据。

在之前第八篇中讲了数组，但是数组并不能满足人们对于“管理和组织数据的需求”。所以引入容器这一概念，也称作集合。容器很好的解决了数组不灵活，不可以随时扩容的问题。下图为容器接口层次结构图，转自谷歌图片：

![容器接口层次图][format_png]

# 泛型 #

## 泛型的概念 ##

为了更好的使用理解容器，首先需要了解下泛型的概念。

泛型是JDK1.5之后增加的，用于建立类型安全的集合。在使用了泛型的集合中，遍历时不必进行强制类型转换。

泛型的本质就是“数据类型的参数化”。可以把“泛型”理解为数据类型的一个占位符，即告诉编译器，再调用泛型时必须传入实际类型。

将容器比作垃圾桶，平常我们使用的垃圾桶中可以随便装任意的垃圾，而在使用泛型之后，我们就有了垃圾分类的功能，相同的类型才会放在同一种的垃圾桶中。

## 泛型的使用 ##

在类的声明处可以增加泛型列表，如<T,E,V>`可以使用任意的字符表示泛型，但是通常采用这3个字母`。

声明泛型：

public class MyCollection<E>{
          //E:表示泛型
        Object[] objs=new Object[5];
        public E get(int index) {
          //E:表示泛型
            return (E) objs[index];
        }
        public void set(E e,int index){
          //E:表示泛型
            objs[index] = e;
        }
    }

泛型E像一个占位符一样表示*未知的某个数据类型*，在真正调用的时候将传入这个*数据类型*。

泛型的应用：

public class TestGenerics{
        
        public static void main(String[] args){
        
            //这里的“String”就是实际传入的数据类型
            MyCollection<String> mc=new MyCollection<String>();
            mc.set("123",0);
            mc.set("456",1);
            String str=mc.get(1);  //加了泛型，直接返回String类型，无需强制转换
            System.out.println(str);
        }
    }

## 容器中的泛型 ##

容器的相关类都定义了泛型，在开发工作中，使用容器类时都要使用泛型。这样，在容器中存储和读取数据时避免了大量的类型判断，更加便捷。

容器中使用泛型的例子：

public class Test {
        
        public static void main(String[] args){
        
            List<String> list=new ArrayList<String>();
            Set<Student> students=new HashSet<Student>();
            Map<Integer,String> map=new HashMap<Integer,String>();
            Iterator<Student> iterator=students.iterator();
        }
    }

# Collection接口 #

Collection表示一组对象，它是集中或收集的意思。Collection接口的两个子接口分别是List和Set。

下表示API中Collection接口中定义的方法：

<table> 
 <thead> 
  <tr> 
   <th align="left">方法()</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">boolean add(Object element)</td> 
   <td align="left">增加元素到容器中</td> 
  </tr> 
  <tr> 
   <td align="left">boolean remove(Object element)</td> 
   <td align="left">从容器中移除元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean contains(Object element)</td> 
   <td align="left">容器中是否包含该元素</td> 
  </tr> 
  <tr> 
   <td align="left">int size()</td> 
   <td align="left">容器中元素的数量</td> 
  </tr> 
  <tr> 
   <td align="left">boolean isEmpty()</td> 
   <td align="left">容器是否为空</td> 
  </tr> 
  <tr> 
   <td align="left">void clear()</td> 
   <td align="left">清空容器中的所有元素</td> 
  </tr> 
  <tr> 
   <td align="left">Iterator iterator()</td> 
   <td align="left">获得迭代器，用于遍历所有元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean containsAll(Collection c)</td> 
   <td align="left">本容器是否包含c容器中的所有元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean addAll(Collection c)</td> 
   <td align="left">将容器c中的所有元素增加到本容器</td> 
  </tr> 
  <tr> 
   <td align="left">boolean removeAll(Collection c)</td> 
   <td align="left">移除本容器和容器c中都包含的元素</td> 
  </tr> 
  <tr> 
   <td align="left">boolean retainAll(Collection c)</td> 
   <td align="left">保留本容器和容器c中都包含的元素，移除非交集元素</td> 
  </tr> 
  <tr> 
   <td align="left">Object[] toArray()</td> 
   <td align="left">转化成Object数组</td> 
  </tr> 
 </tbody> 
</table>

因为List、Set是Collection的子接口，所以List、Set的实现类都有上面的方法。

## List接口 ##

### List接口的概念 ###

List是指有序、可重复的容器\*\*。List接抠中包含了Collection接口中的所有方法，并且List接口增加了和索引相关的方法。

*  有序：List中的每个元素都有索引标记，可以根据元素的索引标记(在List中的位置)来访问元素，从而精确控制这些元素。
 *  可重复：List允许加入重复的元素。即List允许e1.equals(e2)的元素重复的加入容器。

## List接口中定义的方法 ##

除了Collection接口中的方法，List还增加了跟顺序相关的方法，如下表：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>void add(int index,Object element)</td> 
   <td>在指定位置插入元素，以前元素全部后移一位</td> 
  </tr> 
  <tr> 
   <td>Object set(int index,Object element)</td> 
   <td>修改指定位置的元素</td> 
  </tr> 
  <tr> 
   <td>Object get(int index)</td> 
   <td>返回指定位置的元素</td> 
  </tr> 
  <tr> 
   <td>Object remove(int index)</td> 
   <td>删除指定位置的元素，后面元素全部前移一位</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个匹配元素的索引，如果没有该元素，返回-1</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个匹配元素的索引，如果没有该元素，返回-1</td> 
  </tr> 
 </tbody> 
</table>

## ArrayList和LinkedList的特点和底层实现 ##

### ArrayList ###

*  特点：查询效率高，增删效率低，线程不安全。
 *  底层实现：ArrayList底层使用Object数组来存储元素数据，所有的方法都是围绕这个核心的Object数组来开展的。

数组的长度是有限的，而ArrayList可以存放任意数量的对象，长度不受限制。

本质上，ArrayList是通过定义新的更大数组，并将旧数组中的内容复制到新数组来实现扩容的。ArrayList的Object数组默认初始化长度为10，如果存储满了这个数组，需要存储第11个对象时就会定义一个长度更大的新数组，并将原数组中的内容和新元素一起加入到新数组中。

### LinkedList ###

*  特点：查询效率低，增删效率高，线程不安全
 *  底层实现：LinkedList底层使用双向链表来实现存储，双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。

双链表的包含的三部分内容：

class Node{
        
        Node previous;
        Object element;
        Node next;
    }

## Vector向量 ##

Vector底层是一个长度可以动态增长的对象数组，它的相关方法都进行了线程同步，所以**线程安全，效率低**。

## List接口下选用哪个实现类？ ##

1.  需要线程安全时，用Vector。
2.  不存在线程安全问题，并且查找较多时，用ArrayList(一般使用它)。
3.  不存在线程安全问题，但增加或删除元素较多时，用LinkedList。

# Map接口 #

Map接口存储了键(key)-值(value)对信息。Map类中存储的“键值对”通过键来标识，所以“键对象”不能重复。

Map接口的实现类有HashMap、TreeMap、HashTable和Properties等。

下表为Map接口中常用的方法：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Object put(Object key,Object value)</td> 
   <td>存放键值对</td> 
  </tr> 
  <tr> 
   <td>Object get(Object key)</td> 
   <td>通过键对象查找得到值对象</td> 
  </tr> 
  <tr> 
   <td>Object remove(Object key)</td> 
   <td>删除键对象对应的键值对</td> 
  </tr> 
  <tr> 
   <td>boolean containsKey(Object key)</td> 
   <td>Map容器中是否包含键对象对应的键值对</td> 
  </tr> 
  <tr> 
   <td>boolean containsValue(Object value)</td> 
   <td>Map容器中是否包含值对象对应的键值对</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>包含键值对的数量</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>Map是否为空</td> 
  </tr> 
  <tr> 
   <td>void putAll(Map t)</td> 
   <td>将t的所有键值对存放到本Map对象</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空本Map对象的所有键值对</td> 
  </tr> 
 </tbody> 
</table>

## HashMap和HashTable ##

HashMap采用散列算法来实现，它是Map接口最常用的实现类。由于底层采用哈希表来存储数据，因此要求键不能重复，如果发生重复，新的键值对会替换旧的键值对。HashMap在查找、删除、修改方面的效率都非常高。

HashTable和HashMap用法几乎一样，底层实现也几乎一样，知识HashTable的方法添加了synchronized关键字以确保线程同步检查，效率较低，总结就是如下：

*  **HashMap：** 线程不安全，效率高。允许key或value为null。
 *  **HashTable：** 线程安全，效率低。不允许key或value为null。

## HashMap的底层实现 ##

HashMap底层实现采用了哈希表。数据结构中由数组和链表来实现对数据的存储，它们的特点如下：

*  数组：占用空间连续；寻址容易，查询速度快。但是，增加和删除效率非常低。
 *  链表：占用空间不连续；寻址困难，查询速度慢。但是，增加和删除效率非常高。

而哈希表的本质就是“数组+链表”，所以它就吸取了两者的优点，查询快，效率又高。

### 1.HashMap基本结构 ###

哈希表的基本结构就是“数组+链表”。在HashMap中我们可以找到两个核心内容。

其一就是Entry\[\] table是HashMap的核心数组结构，被称为“位桶数组”。在源码中我们可以发现一个Entry对象存储了如下四部分内容：

*  hash：键对象的hash值
 *  key：键对象
 *  value：值对象
 *  next：下一个节点

显而易见，每一个Entry对象是一个单向链表结构，Entry对象结构，如图所示：

![format_png 1][]

Entry\[\]数组的结构(也是HashMap的结构)，如图所示：

![format_png 2][]

### 2.存储数据的过程put(key,value) ###

*  （1）首先应该获得key对象的hashcode：调用key对象的hashcode()方法`继承与Object的方法`，获得hashcode。
 *  （2）根据hashcode计算出hash值，该hash值应在\[0,数组长度-1\]区间中。
    
    hashcode是一个整数，根据既定的算法将转化后的hash值尽量的均匀地分布在\[0,数组长度-1\]区间中，以减少hash冲突，如下两种算法：
    
     *  hash值=hashcode/hashcode
        
        采用这个算法后，hash值就一直为1，这时候，键值对对象全部存储到数组索引位置为1的位置，每一个存储的对象都会发生hash冲突，HashMap就由此退化成了一个“单向链表”。
     *  hash值=hashcode%数组长度
        
        这种算法可以让hash值均匀分布在\[0,数组长度-1\]区间中。早期的HashTable就是采用这种算法。由于这种算法采用了除法，所以效率低下。JDK在后续更新中改进了算法，首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：**hash值=hashcode&(数组长度-1)**。
 *  （3）生成Entry对象：如上所述，一个Entry对象包含了四部分，我们现在已经有了hash值、key对象、value对象，还有最后一部分指向下一个Entry对象。下一个Entry对象next所对应的值就为null。
 *  （4）将Entry对象放到table数组中：如果本Entry对象对应的数组索引位置还没有Entry对象，则直接将该Entry对象存储进数组索引位置的第一位；如果对应索引位置已有Entry对象，则将已有Entry对象的next指向该Entry对象，形成单向链表。

综上所述，HashMap对应的就是一个存储链表的数组，根据hash值找到数组的索引位置，根据链表来存储Entry对象。**JDK8中，当链表长度大于【8】时，链表就转换为红黑树，这样又大大的提高了查找的效率**。

### 3.读取数据过程get(key) ###

*  （1）获取key的hashcode，通过hash()散列算法得到hash值，进而找到数组的索引位置。
 *  （2）在链表上逐个比较key对象。调用equals()方法，将key对象的链表上所有节点的key对象进行比较，直到碰到返回true的节点对象为止。
 *  （3）返回equals()为true的节点对象的value对象。

### 4.扩容问题 ###

HashMap的位桶数组初始大小为**16**，即数组区间在\[0,15\]中。在实际使用中，其大小显然是可变的。如果位桶数组中的元素个数达到**0.75\*数组的length**时，就调整数组大小至原来的2倍。

扩容会消耗性能。扩容的本质就是定义一个更大的新数组，将原数组中的内容逐个复制到新数组中。

## TreeMap的使用和底层实现 ##

TreeMap是红黑二叉树的典型实现。观摩TreeMap的源码，我们可以发现其中有一行核心代码：

private transient Entry<K,V> root = null;

其中，root用来存储整个树的根节点，继续查看Entry(TreeMap的内部类)的代码，如下所示：

static final class Entry<K,V> implements Map.Entry<K,V>{
        
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
    }

从中可以发现，Entry中存储了key、value、左节点、右节点、父节点以及节点颜色。TreeMap的put()/remove()方法中大量的使用了红黑树的理论。限于本人水平有限，需要了解红黑树等相关概念的可以参考数据结构的相关书籍。

## TreeMap和HashMap的使用区别 ##

TreeMap和HashMap同样实现了的Map接口，因此用法对于使用者来说没有区别。HashMap效率高于TreeMap；所以除非在需要Map中Key按照自然顺序排序时才选用TreeMap，其余我们都可采用HashMap。

# Set接口 #

Set接口继承于Collection接口，Set接口中没有新增方法，所以在前面List中使用到的方法，在Set中仍然可以适用。

Set的主要特点是**无序、不可重复**。无序指的是Set中的元素没有索引，只能通过遍历的方式查找；不可重复指不允许加入重复的元素。即新元素如果和Set中的任意一个元素通过equals()方法返回true，那么它就无法加入到Set中，同理Set中仅能存在一个null元素；

Set常用的实现类有HashSet和TreeSet，一般常用HashSet。

## HashSet的底层实现 ##

HashSet底层其实是用HashMap实现的，本质上就是简化版都得HashMap，因此查询效率和增删效率都比较高。

//HashSet部分源码
    public class HashSet<E> extends AbstractSet<E> 
        implements Set<E>, Cloneable,java.io.Serializable{
        
        private transient HashMap<E,Object> map;
        private static final Object PRESENT = new Object();
        
        public HashSet() {
        
            map = new HashMap<>();
        }
        
        public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }
    }

观摩HashSet源码，其中的map属性就是HashSet的核心。在其add()方法中，可以发现增加元素其实就是在map中put一个键值对，键对象就是这个元素，值对象就是PRESENT的Object对象。在Set中加入元素，本质上就是把这个元素作为key加入到内部的map中。

由于map中的key都是不可重复的，因此Set自然具备不可重复的特性。

### TreeSet的底层实现 ###

TreeSet的底层用TreeMap实现，本质上就是一个简化版的TreeMap，通过key来存储Set的元素。TreeMap内部需要对存储的元素进行排序，因此，对应的类需要实现Comparable接口。这样才能根据compareTo()方法来比较对象的大小，并进行内部的排序。

*  **使用TreeSet使用的注意事项**

1.  由于TreeSet底层是一种二叉查找树(红黑树)，需要对元素做内部排序。如果要放入TreeSet中的类没有实现Comparable接口，则会抛出java.lang.ClassCastException的异常。
2.  TreeSet中不能放入null元素。

# Iterator接口 #

Iterator接口可以让开发者实现对容器中对象的遍历

## 迭代器 ##

所有实现Collection接口的容器类都有一个Iterator方法用以返回一个实现了Iterator接口的对象。

Iterator对象称为迭代器，可用于方便地实现对容器内元素的遍历。

Iterator接口定义了如下方法：

*  boolean hasNext()：判断游标当前位置的下一个位置是否还有元素没有被遍历。
 *  Object next()：返回游标当前位置的下一个元素并将游标移动到下一个位置。
 *  void remove()：删除游标当前位置的元素，在执行完next后该操作只能执行一次。

## 迭代器遍历常用容器 ##

迭代器提供了统一的遍历容器的方式。

### 迭代器遍历List ###

public static void testIteratorList() {
        
    	List<String> list=new ArrayList<String>();
    	list.add("aa");
    	list.add("bb");
    	list.add("cc");
    	for (Iterator<String> iter=list.iterator();iter.hasNext();) {
        
    		String temp=iter.next();  //把迭代器返回,返回泛型定义的类型
    		//iter.next()方法把标示指向下一个.
    		System.out.println(temp);
    	}
    }

### 迭代器遍历Set ###

public static void testIteratorSet() {
        
    	Set<String> set=new HashSet<String>();
    	set.add("AA");
    	set.add("BB");
    	set.add("CC");
    	for(Iterator<String> iter=set.iterator();iter.hasNext();) {
        
    		String temp=iter.next();
    		System.out.println(temp);
    	}
    }

### 迭代器遍历Map ###

public static void testIteratorMap() {
        
    	Map<Integer, String> map=new HashMap<Integer, String>();
    	map.put(1, "123");
    	map.put(2, "456");
    	map.put(3, "789");
    		
    	//第一种遍历Map的方式
    	Set<Entry<Integer, String>> setEntry=map.entrySet();  
    	for (Iterator<Entry<Integer, String>> iterEntry=setEntry.iterator();iterEntry.hasNext();) {
        
    		Entry<Integer, String> temp=iterEntry.next();
    		System.out.println(temp);
    	}
    	System.out.println("#######################");
    	//第二种遍历Map的方式
    	Set<Integer> setKey=map.keySet();
    	for (Iterator<Integer> iterKey=setKey.iterator();iterKey.hasNext();) {
        
    		Integer temp=iterKey.next();
    		System.out.println(temp+"---"+map.get(temp));
    	}
    }

# Collections工具类 #

java.util.Collections类提供了对List、Set、Map进行排序、填充、查找元素的辅助方法：

*  void sort(List)：对List容器类的元素按照升序排序。
 *  void shuffle(List)：对List容器内的元素进行随机排序。
 *  void reverse(List)：对List容器内的元素进行逆序排序。
 *  void fill(List,Object)：用一个特定的对象重写整个List容器(将List全部中的对象全部替换成这个Object对象)。
 *  int binarySearch(List,Object)：对于顺序的List容器，采用折半查找法来查找特定的对象(可以先用sort()方法排序该List容器)

# 结语 #

> 对于容器的理解，限于本人水平有限仅至于此，以上的内容基本完全满足了日常开发工作所需。如果想更深入了解容器的用法可以参阅官方的JDK文档；想更深入了解容器的底层实现原理，可以观摩容器的源码。本篇内容至此结束，感谢各位阅读。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9vc2NpbWcub3NjaGluYS5uZXQvb3NjbmV0L2M5MDIyYjA0ZTk2N2I4NWFmNWFmM2JmOWJhNTE1ZWQyYjczLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy53aHouYWMuY24vUGljR08vRXhjZXB0aW9uL0VudHJ5LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy53aHouYWMuY24vUGljR08vRXhjZXB0aW9uL0VudHJ5W10lMjB0YWJsZS5wbmc?x-oss-process=image/format,png