1 容器

1.1 容器简介

开发和学习中需要时刻和数据打交道，如何组织这些数据是我们编程中重要的内容。我们一般通过“容器”来容纳和管理数据。事实上，我们前面所学的数组就是一种容器，可以在其中放置对象或基本类型数据。
数组的优势：是一种简单的线性序列，可以快速地访问数组元素，效率高。如果从效率和类型检查的角度讲，数组是最好的。
数组的劣势：不灵活。容量需要事先定义好，不能随着需求的变化而扩容。

2 容器的结构

2.1 结构图

2.1.1 单例集合

单例集合：将数据一个一个的进行存储。

2.1.2 双例集合

双例集合：基于 Key 与 Value 的结构存储数据。

3 单例集合的使用

3.1 Collection接口

由于 List、Set 是 Collection 的子接口，意味着所有 List、Set 的实现类都有Collection接口中定义的方法。

3.2 List接口

有序：有序(元素存入集合的顺序和取出的顺序一致)。List 中每个元素都有索引标记。可以根据元素的索引标记（在 List 中的位置）访问元素，从而精确控制这些元素。
可重复：List 允许加入重复的元素。更确切地讲，List 通常允许满足 e1.equals(e2) 的元素重复加入容器。

3.3 ArrayList容器类

ArrayList 是 List 接口的实现类。是 List 存储特征的具体实现。
ArrayList 底层是用数组实现的存储，延迟初始化，1.5倍扩容。特点：查询效率高，增删效率低，线程不安全。

3.4 Vector 容器类

Vector 底层是用数组实现的，立即初始化，2倍扩容。相关的方法都加了同步检查，因此“线程安全,效率低”。

3.4.1 Stack容器

Stack 栈容器，是 Vector 的一个子类，它实现了一个标准的后进先出。

3.5LinkedList 容器类

LinkedList 底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。

3.6 Set 接口介绍

Set 接口继承自 Collection，Set 接口中没有新增方法，方法和 Collection 保持完全一致。

3.6.1 Set接口特点

Set 特点：无序、不可重复。无序指 Set 中的元素没有索引，我们只能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新元素如果和 Set 中某个元素通过 equals()方法对比为 true，则只能保留一个。

3.6.2 HashSet 容器类

HashSet 是一个没有重复元素的集合，不保证元素的顺序。而且 HashSet 允许有 null 元素。HashSet 是采用哈希算法实现，底层实际是用 HashMap 实现的（HashSet 本质就是一个简化版的 HashMap），因此，查询效率和增删效率都比较高。
Hash 算法原理：Hash 算法也称之为散列算法。

HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程不安全的。HashSet允许有 null 元素。
无序：在 HashSet 中底层是使用 HashMap 存储元素的。HashMap 底层使用的是数组与链表实现元素的存储。元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。
不重复：当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的 equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素。
利用HashSet存储自定义数据类型时，应重写equals()和hashCode()方法。

3.6.3 TreeSet容器类

TreeSet 是一个可以对元素进行排序的容器。底层实际是用 TreeMap 实现的，内部维持了一个简化版的 TreeMap，通过 key 来存储 Set 的元素。 TreeSet 内部需要对存储的元素进行排序，因此，我们需要给定排序规则。
排序规则实现方式：

• 通过元素自身实现比较规则。
  在元素自身实现比较规则时，需要实现 Comparable 接口中的 compareTo 方法，该方法中用来定义比较规则。TreeSet 通过调用该方法来完成对元素的排序处理。

public class Users implements Comparable<Users>{
	private String username;
	private int userage;
	public Users(String username, int userage) {
		this.username = username;
		this.userage = userage;
	}
	public Users() {
	}
	@Override
	public boolean equals(Object o) {
		System.out.println("equals...");
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;
		Users users = (Users) o;
		if (userage != users.userage) return false;
		return username != null ? username.equals(users.username) :
		users.username == null;
	}
	@Override
	public int hashCode() {
		int result = username != null ? username.hashCode() : 0;
		result = 31 * result + userage;
		return result;
	}
	public String getUsername() {
		return username;
	}
	public void setUsername(String username) {
		this.username = username;
	}
	public int getUserage() {
		return userage;
	}
	public void setUserage(int userage) {
		this.userage = userage;
	}
	@Override
	public String toString() {
		return "Users{" +
		"username='" + username + '\'' +
		", userage=" + userage +
		'}';
	}
	//定义比较规则
	//正数：大，负数：小，0：相等
	@Override
	public int compareTo(Users o) {
		if(this.userage > o.getUserage()){
			return 1;
		}
		if(this.userage == o.getUserage()){
			return this.username.compareTo(o.getUsername());
		}
		return -1;
	}
}

• 通过比较器指定比较规则。
  通过比较器定义比较规则时，我们需要单独创建一个比较器，比较器需要实现
  Comparator 接口中的 compare 方法来定义比较规则。在实例化 TreeSet 时将比较器对象交给TreeSet 来完成元素的排序处理。此时元素自身就不需要实现比较规则了。

public class StudentComparator implements Comparator<Student> {
	//定义比较规则
	@Override
	public int compare(Student o1, Student o2) {
		if(o1.getAge() > o2.getAge()){
			return 1;
		}
		if(o1.getAge() == o2.getAge()){
			return o1.getName().compareTo(o2.getName());
		}
		return -1;
	}
}

Set<Student> set2 = new TreeSet<>(new StudentComparator());
Student s = new Student("oldlu",18);
Student s1 = new Student("admin",22);
Student s2 = new Student("sxt",22);
set2.add(s);
set2.add(s1);
set2.add(s2);
for(Student student:set2){
	System.out.println(student);
}

4 双例集合

4.1 Map接口介绍

Map 接口定义了双例集合的存储特征，它并不是 Collection 接口的子接口。双例集合的存储特征是以 key 与 value 结构为单位进行存储。
Map 与 Collecton 的区别：

• Collection 中的容器，元素是孤立存在的（理解为单身），向集合中存储元素采用一个个元素的方式存储。
• Map 中的容器，元素是成对存在的(理解为现代社会的夫妻)。每个元素由键与值两部分组成，通过键可以找对所对应的值。
• Collection 中的容器称为单列集合，Map 中的容器称为双列集合。
• Map 中的集合不能包含重复的键，值可以重复；每个键只能对应一个值。
• Map 中常用的容器为 HashMap，TreeMap 等。

4.2 HashMap容器类

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

4.2.1 获取元素

• 方式一
  通过 get 方法获取元素。

String val = map.get("a");
System.out.println(val);

• 方式二
  通过 keySet 方法获取元素

//获取 HashMap 容器中所有的元素，可以使用 keySet 方法与 get 方法一并完成。
Set<String> keys = map.keySet();
for(String key:keys){
	String v1 = map.get(key);
	System.out.println(key+" ---- "+v1);
}

• 方式三
  通过 entrySet 方法获取 Map.Entry 类型（内部接口类型）

Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
	String key = entry.getKey();
	String v = entry.getValue();
	System.out.println(key+" ---------- "+v);
}

4.2.2 HashMap底层源码分析

HashMap 底层实现采用了哈希表，这是一种非常重要的数据结构。
数据结构中由数组和链表来实现对数据的存储，他们各有特点。
(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。
(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
哈希表的本质就是“数组+链表”。


在 JDK1.8 的 HashMap 中对于数组的初始化采用的是延迟初始化方式。通过 resize 方法实现初始化处理。resize 方法既实现数组初始化，也实现数组扩容处理。
计算 Hash 值
(1) 获得 key 对象的 hashcode
首先调用 key 对象的 hashcode()方法，获得 key 的 hashcode 值。
(2) 根据 hashcode 计算出 hash 值(要求在[0, 数组长度-1]区间)
hashcode 是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的 hash 值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash 冲突”。

• 一种极端简单和低下的算法是：
  hash 值 = hashcode/hashcode;也就是说，hash 值总是 1。意味着，键值对对象都会存储到数组索引 1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap 也退化成了一个“链表”。
• 一种简单和常用的算法是（相除取余算法）：
  hash 值 =hashcode%数组长度，这种算法可以让 hash 值均匀的分布在[0,数组长度-1]的区间。但是，这种算法由于使用了“除法”，效率低下。
• JDK算法
  首先约定数组长度必须为 2 的整数幂，这样采用位运算即可实现取余的效果：hash 值 =hashcode&(数组长度-1)。

4.3 TreeMap容器类

HashMap 效率高于 TreeMap；TreeMap 是可以对键进行排序的一种容器，在需要对键排序时可选用 TreeMap。TreeMap 底层是基于红黑树实现的。
在使用 TreeMap 时需要给定排序规则：

• 元素自身实现比较规则
• 通过比较器实现比较规则

5 Iterator迭代器

Collection接口继承了Iterable接口，在该接口中包含一个名为iterator的抽象方法，所有实现了Collection接口的容器类对该方法做了具体实现。iterator方法会返回一个Iterator接口类型的迭代器对象，在该对象中包含了三个方法用于实现对单例容器的迭代处理。

• boolean hasNext(); //判断游标当前位置是否有元素，如果有返回true，否则返回false；
• Object next();//获取当前游标所在位置的元素，并将游标移动到下一个位置；
• void remove();//删除游标当前位置的元素，在执行完next后该操作只能执行
  一次；
  注：迭代器对象只能使用一次。

6 Collections 工具类

Collections 是一个工具类，它提供了对 Set、List、Map 进行排序、填充、查找元素的辅助方法。该类中所有的方法都为静态方法。