Java集合篇：集合类介绍

上面的图展示了整个集合大家族的成员以及他们之间的关系。下面就上面的各个接口、基类做一些简单的介绍(主要介绍各个集合的特点，区别)。

一、Collection接口：

Collection接口是最基本的集合接口，它不提供直接的实现，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。Collection所代表的是一种规则，它所包含的元素都必须遵循一条或者多条规则。如有些允许重复而有些则不能重复、有些必须要按照顺序插入而有些则是散列，有些支持排序但是有些则不支持。

在Java中所有实现了Collection接口的类都必须提供两套标准的构造函数，一个是无参，用于创建一个空的Collection，一个是带有Collection参数的有参构造函数，用于创建一个新的Collection，这个新的Collection与传入进来的Collection具备相同的元素。

二、List接口：

List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList：

（1）ArrayList底层是一个基于数组的非同步实现，是线程不安全的，它的操作基本上都是基于对数组的操作。

（2）允许包括null在内的所有元素，ArrayList擅长于随机访问，所以对元素的查询快，增删慢，在ArrayList的中间插入或删除一个元素，该位置后面的元素都会被移动，查询的时间复杂度为O(1)，插入和删除的时间复杂度为O(n)。

（3）初始容量为10，数组扩容时，会将旧数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种操作的代价很高。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

（4）采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

（5）remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

2.2、LinkedList：

（1）LinkedList是基于双向链表的非同步实现，所以是线程不安全的；

（2）允许包括null在内的所有元素。

（3）LinkedList不能随机访问，在查找元素的时候，需要从开头或结尾遍历列表（先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

（4）虽然LinkedList对元素的查询慢，时间复杂度为O(n)，但是对元素的增删快，插入或删除元素只需要修改元素的指针，时间复杂度为O(1)

2.3、Vector：

（1）与ArrayList相似，但是Vector是同步的，底层使用synchronized进行加锁。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

（2）初始容量是10，扩容时，Vector的容量增加capacityIncrement，如果没有指定capacityIncrement，则将容量增加为原来的两倍。

2.4、Stack：

（1）Stack继承自Vector，实现一个后进先出的堆栈。所以用法、线程安全什么的跟Vector都差不多，Stack刚创建后是空栈。

（2）Stack还提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。

三、Map接口：

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。实现map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

3.1、HashMap（JDK1.8及以上）：

（1）HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序，它是为快速查询而设计的。

（2）数据结构可以看成数组+链表+红黑树。底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。

（3）HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。

（4）HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能。

HashMap的扩容代价非常大，要生成一个新的桶数组，然后要把所有元素都重新Hash落桶一次，几乎等于重新执行了一次所有元素的put。所以如果我们对Map的大小有一个范围的话，可以在构造时给定大小，一般大小设置为：(int) ((float) expectedSize / 0.75F + 1.0F)。

（5）采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常。

3.2、Hashtable：

（1）Hashtable是基于哈希表的Map接口的同步实现，使用synchronized实现线程安全，即每次锁住整张表让线程独占。

（2）底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体，采用链表法解决哈希冲突；

（3）不允许使用null值和null键；

（4）Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

3.3、ConcurrentHashMap（JDK1.7版本）：

（1）ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同段进行的修改，每个段其实就是一个小的hashtable，它们有各自的锁。只要多个并发发生在不同的段上，它们就可以并发进行。

（2）与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)，ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁，但在HashMap中的实现中，因为允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。

（3）ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

（4）在JDK1.8之后的版本中，抛弃了Segment锁分段的概念，而是才赢CAS算法，保存并发安全性，同时底层数据结构可以看成“数组+链表+红黑树”。

3.4、TreeMap：

键以某种排序规则排序，内部以red-black（红-黑）树数据结构实现，实现了SortedMap接口。

3.5 LinkedHashMap：

（1）LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。

（2）基本操作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而构成了双向链接列表。

3.6、WeakHashMap：

WeakHashMap与HashMap的用法基本相同，区别在于：后者的key保留对象的强引用，即只要HashMap对象不被销毁，其对象所有key所引用的对象不会被垃圾回收，HashMap也不会自动删除这些key所对应的键值对对象。但WeakHashMap的key所引用的对象没有被其他强引用变量所引用，则这些key所引用的对象可能被回收。WeakHashMap中的每个key对象保存了实际对象的弱引用，当回收了该key所对应的实际对象后，WeakHashMap会自动删除该key所对应的键值对。

3.7、IdentifyHashMap：

IdentityHashMap与HashMap基本相似，只是当两个key严格相等时，即key1==key2时，它才认为两个key是相等的。IdentityHashMap也允许使用null，但不保证键值对之间的顺序。

四、Set接口：

Set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样运行null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，同时要注意任何可变对象，如果在对集合中元素进行操作时，导致e1.equals(e2)==true，则必定会产生某些问题。实现了Set接口的集合有：EnumSet、HashSet、TreeSet。

3.1、HashSet：

（1）HashSet基于HashMap实现，API也是对HashMap的行为进行了封装。

（2）HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的。它内部元素的顺序是由哈希码来决定的，所以它不保证set 的迭代顺序，特别是它不保证该顺序恒久不变，并允许使用null元素。

3.2、LinkedHashSet：

（1）对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。

（2）LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承与HashSet，其所有的方法操作上又与HashSet相同。

3.3、TreeSet：

基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现。它是使用元素的自然顺序对元素进行排序，或者根据创建Set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。

3.4、EnumSet：

是枚举的专用Set。所有的元素都是枚举类型。

五、Queue：

队列，它主要分为两大类，一类是阻塞式队列，队列满了以后再插入元素则会抛出异常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一种队列则是双端队列，支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

六、相关问题：

6.1、Set集合是如何保证对象不重复的？

Set集合不允许有重复出现的对象，且最终的判断是根据equals()的。其实原理是这样的：HashSet的底层采用HashMap来存放数据，HashMap的put()方法是这样的：

  public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());//----------1----------
        int i = indexFor(hash, table.length);//-----------2---------
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//-----------3---------
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }//------------------4--------------------
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

当向HashMap中添加元素的时候，首先计算元素的hashcode值，然后根据1处的代码计算出Hashcode的值，再根据2处的代码计算出这个元素的存储位置，如果这个位置为空，就将元素添加进去；如果不为空，则看3-4的代码，遍历索引为i的链上的元素，如果key重复，则替换并返回oldValue值。

6.2、集合类排序问题：

一种情况是集合类本身自带排序功能，如前面说过的TreeSet、SortedSet、SortedMap等，另一种就是本身不带排序功能，我们通过为需要排序的类实现Comparable或者Comparator接口来实现。

先来看两个例子，一个是实现Comparable的，一个是实现Comparator的，为了方便，我将类都写在了一个文件中。

（1）实现Comparable的：

package com.xtfggef.list.test;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
 
@SuppressWarnings("unchecked")
public class ComparableTest {
	public static void main(String[] args) {
		// User[] users = { new User("egg", 23), new User("niuniu", 22),
		// new User("qing", 28) };
		// Arrays.sort(users);
		// for (User user : users) {
		// System.out.println(user.getName() + " " + user.getAge());
		// }
		List<User> users = new ArrayList<User>();
		users.add(new User("egg", 23));
		users.add(new User("niu", 22));
		users.add(new User("qing", 28));
 
		Collections.sort(users);
		for (User user : users) {
			System.out.println(user.getName() + " " + user.getAge());
		}
	}
}
 
@SuppressWarnings("unchecked")
class User implements Comparable {
	private String name;
	private int age;
 
	public User(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public int getAge() {
		return age;
	}
 
	public void setAge(int age) {
		this.age = age;
	}
 
	@Override
	public int compareTo(Object o) {
		return this.age - ((User) o).getAge();
	}
}

（2）下面是实现Comparator接口的：

package com.xtfggef.comparator.test;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class ComparatorTest {
 
	public static void main(String[] args) {
		List<User> users = new ArrayList<User>();
		users.add(new User("egg", 21));
		users.add(new User("niu", 22));
		users.add(new User("gg", 29));
		UserComparator comparator = new UserComparator();
		Collections.sort(users, comparator);
		for (User user : users) {
			System.out.println(user.getUsername() + " " + user.getAge());
		}
	}
 
}
class User {
	private String username;
	private int age;
 
	public User(String username, int age) {
		super();
		this.username = username;
		this.age = age;
	}
 
	public String getUsername() {
		return username;
	}
 
	public void setUsername(String username) {
		this.username = username;
	}
 
	public int getAge() {
		return age;
	}
 
	public void setAge(int age) {
		this.age = age;
	}
}
class UserComparator implements Comparator<User> {
 
	@Override
	public int compare(User user1, User user2) {
		int age1 = user1.getAge();
		int age2 = user2.getAge();
		if (age1 < age2) {
			return 1;
		}
		return 0;
	}
}

通过上面的这两个小例子，我们可以看出，Comparator和Comparable用于不同的场景，实现对对象的比较从而进行排序。

总结为：

相同点：二者都可以实现对象的排序，不论用Arrays的方法还是用Collections的sort()方法。

不同点：

（1）实现Comparable接口的类，似乎是预先知道该类将要进行排序，需要排序的类实现Comparable接口，是一种“静态绑定排序”。

（2）实现Comparator的类不需要，设计者无需事先为需要排序的类实现任何接口。

（3）Comparator接口里有两个抽象方法compare()和equals()，而Comparable接口里只有一个方法：compareTo()。

（4）Comparator接口无需改变排序类的内部，也就是说实现算法和数据分离，是一个良好的设计，是一种“动态绑定排序”。

（5）Comparator接口可以使用多种排序标准，比如升序、降序等。

6.3、使用for循环删除元素陷阱：

先来看看下面这个程序：

public class Test {
 
	public static void main(String[] args) {
		List<String> list = new LinkedList<String>();
		list.add("A");
		list.add("B");
		list.add("C");
		
		for(int i=0; i<list.size(); i++){
			list.remove(i);
		}
		
		for(String item:list){
			System.out.println(item);
		}
	}
}

读者朋友们可以先猜猜这个程序输出什么？按我们的思路，应该是输不出什么，但是执行它，输出的却是：B。这是为什么呢？我们分部分析下这个程序，当地一步remove完后，集合内还剩2个元素，此时i为1，而list.size()的值为2，从0开始的话，i为1时，正好指向第二个元素，也就是说当remove完A后，直接就跳到C，将B漏了。

public class Test {
 
	public static void main(String[] args) {
		List<String> list = new LinkedList<String>();
		list.add("A");
		list.add("B");
		list.add("C");
		
		for(int i=0; i<list.size(); i++){
			list.remove(i);
			i -= 1;//每次删除完后，i减少1
		}
		
		for(String item:list){
			System.out.println(item);
		}
	}
}

参考博客：

https://blog.csdn.net/chenssy/article/details/17732841

https://blog.csdn.net/zhangerqing/article/details/8122075

https://blog.csdn.net/qq_25868207/article/details/55259978

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/114669.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...