共计 12970 个字符，预计需要花费 33 分钟才能阅读完成。
一、汇合与数组的比拟
二、汇合构造继承图
汇合分为两大类：
一类是单个形式存储元素，超级父接口是 java.util.Collection;
一类是以键值对的形式存储元素，超级父接口是 java.util.Map。
Collection 和 Map，是汇合框架的根接口。
汇合构造的继承须要熟练掌握。留神分清哪些是接口，哪些是实现类。
有序：指的是存进去的元素是这个程序，取出来还是这个程序；无序：示意存进去是这个程序，取出来就不肯定是这个程序。并且没有下标。可反复：容许寄存反复的元素；不可反复：不容许寄存反复的元素。即存进去 1，就不能再存储 1。三、Collection 接口
Collection 接口是 List 接口和 Set 接口的父接口。Collection 接口中定义了对汇合进行增、删、改、查的办法，List 接口和 Set 接口继承了这些办法。
四、List 接口及其实现类
List 是有序可反复的 Collection，应用此接口可能准确的管制每个元素插入的地位。用户可能应用索引（元素在 List 中的地位，相似于数组下标）来拜访 List 中的元素。实现 List 接口的罕用类有 LinkedList，ArrayList，Vector。
List 中特有的办法：
1.ArrayList 类
底层是 Object 数组，所以 ArrayList 汇合查问效率高，增删效率低。
（问：为什么数组检索效率高，增删效率低？
答：检索效率高是因为第一：Java 的数组中存储的每个元素类型统一，也就是说每个元素占用的空间大小雷同；第二：Java 的数组中存储的每个元素的内存地址是间断状态的；第三：首元素的内存地址作为整个数组对象的内存地址，可见咱们是晓得首元素内存地址的；第四：数组中的元素是有下标的，有下标就能够计算出被查找的元素和首元素的偏移量。
增删效率低是因为往数组里某个下标地位减少元素须要把这个下标往后的元素后移一位，删除也同理。）
ArrayList 主动扩容机制：初始容量为 10，扩容后为原容量的 1.5 倍。
ArrayList 类有三个构造方法：
Arraylist 汇合测试：
public static void main(String[] args) {
// 创立 ArrayList 实例
ArrayList<String> list = new ArrayList<>();
// 给 list 增加元素
for (int i=97; i<105; i++) {list.add(String.valueOf((char)i));
}
System.out.println("list 数组的内容是" + list);
System.out.println("list 数组中元素个数为：" + list.size());
list.set(0,"haha");
System.out.println("list 数组批改后的内容是：" + list);
System.out.println("list 数组中是否蕴含“a”：" + list.contains("a"));
System.out.println("list 数组下标为 2 的元素是：" + list.get(2));
list.remove("c");
System.out.println("list 数组移除“c”后的内容是：" + list);
// 遍历 list 汇合
for (String s : list) {System.out.printf("%s\t",s);
}
}
后果：
list 数组的内容是[a, b, c, d, e, f, g, h]
list 数组中元素个数为：8
list 数组批改后的内容是：[haha, b, c, d, e, f, g, h]
list 数组中是否蕴含“a”：false
list 数组下标为 2 的元素是：c
list 数组移除“c”后的内容是：[haha, b, d, e, f, g, h]
haha b d e f g h
2、LinkedList 类
底层采纳双向链表构造，劣势在于高效地插入和删除其中的元素，但随机拜访元素的速度较慢，个性与 ArrayList 刚好相同。如果程序须要重复对汇合做插入和删除操作，应抉择 LinkedList 类。
LinkedList 类有两个构造方法：
LinkedList 类还实现了 Deque 和 Queue 接口，实现了这两个接口中的指定的办法，用于解决首部和尾部的元素。能够利用 LinkedList 实现栈 (stack)、队列(queue)、双向队列(double-ended queue)。它具备办法 addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast() 等。
LinkedList 汇合测试：
public static void main(String[] args) {
// 创立 ArrayList 实例
ArrayList<String> list = new ArrayList<>();
// 给 list 增加元素
for (int i=97; i<105; i++) {list.add(String.valueOf((char)i));
}
System.out.println("list 数组的内容是" + list);
// 创立 LinkedList 实例
LinkedList<String> link = new LinkedList<>(list);
System.out.println("link 的内容是" + link);
link.addFirst("first");
link.addLast("last");
System.out.println("link 的内容是" + link);
System.out.println("link 的第一个元素内容是：" + link.getFirst());
}
后果：
list 数组的内容是[a, b, c, d, e, f, g, h]
link 的内容是[a, b, c, d, e, f, g, h]
link 的内容是[first, a, b, c, d, e, f, g, h, last]
link 的第一个元素内容是：first
3、Vector 类
: 底层数据结构是数组，查问快，增删慢，线程平安，效率低，能够存储反复元素，不倡议应用。
五、Iterator 接口（迭代器）
Iterator 接口是对 Collection 进行迭代的迭代器。利用这个接口，能够对 Collection 中的元素进行拜访，实现对汇合元素的遍历。
Iterator 接口有三个办法：
迭代器一开始指向第一个对象，应用 Next()后指向下一个对象。在迭代汇合元素过程中，如果应用了出 remove()办法之外的形式扭转了汇合构造，迭代器必须从新获取。且 remove()只有在调用 Next()办法后才能够应用，每次执行 Next()之后最多调用一次。
迭代器测试：
public static void main(String[] args) {
// 创立 ArrayList 实例
ArrayList<Integer> list = new ArrayList<>();
// 给 list 增加元素
for (int i=1; i<9; i++) {list.add(i);
}
// 返回 Iterator 迭代器
Iterator<Integer> it = list.iterator();
// 迭代器遍历汇合
while (it.hasNext()) { // 判断是否有元素
int x = it.next(); // 获取元素
System.out.println(x);
if (x == 5) // 元素为 5 时移除元素
it.remove();}
// 转换为对象数组
Object[] a = list.toArray();
System.out.printf("删除之后的内容是：");
for (int i=0; i<a.length; i++) {System.out.printf("%s\t",a[i]);
}
}
后果：
1
2
3
4
5
6
7
8
删除之后的内容是：1 2 3 4 6 7 8
六、Set 接口及其实现类
无序汇合，不容许寄存反复的元素；容许应用 null 元素。对 add()、equals() 和 hashCode() 办法进行更为严格的限度。
（因为 HashSet 和 TreeSet 汇合底层都是 Map，HashSet 底层是 HashMap，TreeSet 底层是 TreeMap。所以把 Map 学会，Set 汇合就很好了解了，所以这里先简略介绍一下 Set 接口及其实现类，能够先去学习第七节 Map 接口。）
1、HashSet 类
HashSet 底层数据结构采纳哈希表实现，元素无序且惟一，线程不平安，效率高，能够存储 null 元素，元素的唯一性是靠所存储元素类型是否重写 hashCode()和 equals()办法来保障的，如果没有重写这两个办法，则无奈保障元素的唯一性。
具体实现唯一性的比拟过程：存储元素首先会应用 hash()算法函数生成一个 int 类型 hashCode 散列值，而后曾经的所存储的元素的 hashCode 值比拟，如果 hashCode 不相等，则所存储的两个对象肯定不相等，此时存储以后的新的 hashCode 值处的元素对象；如果 hashCode 相等，存储元素的对象还是不肯定相等，此时会调用 equals()办法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比拟的内容不相等，那么就是不同的对象，就该存储了，此时就要采纳哈希的解决地址抵触算法，在以后 hashCode 值处相似一个新的链表，在同一个 hashCode 值的前面存储存储不同的对象，这样就保障了元素的唯一性。
HashSet 类测试：
public static void main(String[] args) {Set<String> strs = new HashSet<>();
strs.add("aa");
strs.add("bb");
strs.add("cc");
strs.add("dd");
strs.add("aa");
Iterator<String> it = strs.iterator();
while (it.hasNext()) {String s = it.next();
System.out.println(s);
}
}
后果：
aa
bb
cc
dd
2、TreeSet 类
汇合底层是 TreeMAp，TreeMap 底层是二叉树构造。与 HashSet 类不同，TreeSet 类不是散列的，而是有序的。
元素惟一且曾经排好序；唯一性同样须要重写 hashCode 和 equals()办法，二叉树构造保障了元素的有序性。依据构造方法不同，分为天然排序（无参结构）和比拟器排序（有参结构），天然排序要求元素必须实现 Compareable 接口，并重写外面的 compareTo()办法，元素通过比拟返回的 int 值来判断排序序列，返回 0 阐明两个对象雷同，不须要存储；比拟器排须要在 TreeSet 初始化是时候传入一个实现 Comparator 接口的比拟器对象，或者采纳匿名外部类的形式 new 一个 Comparator 对象，重写外面的 compare()办法。
七、Map 接口
1、Map 汇合和 Colltection 汇合没有继承关系。
2、Map 汇合以 Key 和 Value 的 <mark style=”box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;”> 键值对 </mark> 形式存储元素。
3、Key 和 Value 都是存储 java 对象的内存地址。Key 起到主导地位，Value 是 Key 的附属品。
4、无序不可反复。
Map 中罕用办法：
Map 罕用办法测试：
public static void main(String[] args) {
// 创立 Map 汇合对象
Map<Integer,String> map = new HashMap<>();
// 向汇合增加键值对
map.put(1,"中国");
map.put(2,"美国");
map.put(3,"俄罗斯");
map.put(4,"英国");
// 通过 key 获取 value
System.out.println(map.get(1));
// 判断是否蕴含某个 key
System.out.println("是否蕴含 key“4”：" + map.containsKey(4));
// 判断是否蕴含某个 key
System.out.println("是否蕴含 value“中国”：" + map.containsValue("中国"));
// map 汇合是否为空
System.out.println("汇合是否为空：" + map.isEmpty());
// 通过 key 删除键值对
map.remove(2);
// 汇合元素个数
System.out.println("汇合元素个数：" + map.size());
// 将 map 汇合转换为 Set 汇合
Set<Map.Entry<Integer,String>> set = map.entrySet();
System.out.println("======================================================");
// 遍历汇合
for (Map.Entry<Integer,String>entry : set) {System.out.println("key:" + entry.getKey() + "value:" + entry.getValue());
}
}
后果：
中国
是否蕴含 key“4”：true
是否蕴含 value“中国”：true
汇合是否为空：false
汇合元素个数：3
======================================================
key: 1 value: 中国
key: 3 value: 俄罗斯
key: 4 value: 英国
1、遍历 Map 汇合的四种办法
public static void main(String[] args) {Map<String, String> map= new HashMap<>();
map.put("关羽", "云长");
map.put("张飞", "益德");
map.put("赵云", "子龙");
map.put("马超", "孟起");
map.put("黄忠", "汉升");
// 第一种遍历 map 的办法，通过增强 for 循环 map.keySet()，而后通过键 key 获取到 value 值
for(String s:map.keySet()){System.out.println("key :"+s+"value :"+map.get(s));
}
System.out.println("====================================");
// 第二种只遍历键或者值，通过增强 for 循环
for(String s1:map.keySet()){// 遍历 map 的键
System.out.println("键 key："+s1);
}
for(String s2:map.values()){// 遍历 map 的值
System.out.println("值 value："+s2);
}
System.out.println("====================================");
// 第三种形式 Map.Entry<String, String> 的增强 for 循环遍历输入键 key 和值 value
Set<Map.Entry<String,String>> set = map.entrySet();
for(Map.Entry<String, String> entry : set){System.out.println("键 key："+entry.getKey()+"值 value："+entry.getValue());
}
System.out.println("====================================");
// 第四种 Iterator 遍历获取，而后获取到 Map.Entry<String, String>，再失去 getKey()和 getValue()
Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
while(it.hasNext()){Map.Entry<String, String> entry=it.next();
System.out.println("键 key："+entry.getKey()+"value："+entry.getValue());
}
System.out.println("====================================");
}
2、HashMap 哈希表 (散列表) 数据结构
要把握 HashMap 汇合，就要相熟哈希表的数据结构。因为 HashMap 汇合底层是哈希表 / 散列表的数据结构。
哈希表是一个数组与单向链表的结合体。 所以哈希表在查问和增删数据方面效率都很高。
HashMap 底层实际上是一个一维数组，数组外面存的是一个 Node（HashMap.Node 节点，这个节点外面存储了哈希值，键值对，下一个节点的内存地址）。哈希值是 key 的 hashCode()办法的后果，hash 值再通过哈希函数，能够转换为 <mark style=”box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;”> 数组的下标 </mark>。
map.put(k,v)实现原理：
①先将键值对 k，v 封装到 Node 对象中；
②底层会调用 k 的 hashCode()办法得出 hash 值；
③通过哈希函数，将 hash 值转换为数组的下标。
④进行比拟：下标地位如果没有任何元素，就把 Node 增加到这个地位上；如果下标地位上有链表，此时会拿着 k 和链表上的每一个节点的 k 用 equals()办法进行比拟（因为 Map 是不可反复的），如果没有反复的新节点就会加到链表开端，否则则会笼罩有雷同 k 值的节点。
map.get(k)实现原理：
①调用 k 的 hashCode()办法得出 hash 值；
②进行比拟：下标地位如果没有任何元素，返回 null，如果下标地位上有链表，此时会拿着 k 和链表上的每一个节点的 k 用 equals()办法进行比拟，如果后果都是 false，则返回 null；如果有一个节点用了 equals 办法后后果为 true，则返回这个节点的 value 值。
问：为什么哈希表随机增删、查问效率都高？
答：增删是在链表上实现的，查问也不须要都扫描，只须要局部扫描。
这里重点来了，上述调用了的 hashCode()和 equals()办法，都须要 <mark style=”box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;”> 重写 </mark>！
equals()重写起因：equals 默认比拟的是两个对象的内存地址，但咱们须要比拟的是 k 中的内容。
hashCode
论断：放在 HashMap()汇合 key 局部的元素，，以及放在 HashSet 汇合中的元素，须要同时重写 hashCode 和 equals 办法。
重写 equals()和 hashCode()办法测试：
在重写前和重写后代码运行的后果是不同的，各位能够用这段代码测试一下，把之前的和正文局部勾销正文后比照一下。
public class HashMapTest01 {public static void main(String[] args) {Student s1 = new Student("Jake");
Student s2 = new Student("Jake");
System.out.println(s1.equals(s2));
System.out.println(s1.hashCode() == s2.hashCode());
Set<Student> students = new HashSet<>();
students.add(s1);
students.add(s2);
System.out.println(students.size());
}
}
class Student {
//@Override
//public boolean equals(Object o) {// if (this == o) return true;
// if (o == null || getClass() != o.getClass()) return false;
// Student student = (Student) o;
// return Objects.equals(name, student.name);
//}
//
//@Override
//public int hashCode() {// return Objects.hash(name);
//}
private String name;
public Student(String name) {this.name = name;}
public String getName() {return name;}
public void setName(String name) {this.name = name;}
}
3、TreeMap 类
TreeMap 类是 Map 接口的具体实现，底层是二叉树数据结构，反对元素的 <mark style=”box-sizing: border-box; outline: 0px; background-color: rgb(248, 248, 64); color: rgb(0, 0, 0); overflow-wrap: break-word;”> 有序 </mark> 存储，能够依照元素的大小程序主动排序。TreeMap 类中所有元素都必须实现 Comparable 接口，与 TreeSet 类类似（TreeSet 类底层是 TreeMap, 放在 TreeSet 汇合中的元素，等同于放在 TreeMap 汇合中的 key 局部）。
TreeSet 类主动排序测试：
public static void main(String[] args) {TreeSet<String> ts = new TreeSet<>();
ts.add("ss");
ts.add("abf");
ts.add("g");
ts.add("f");
ts.add("abcd");
ts.add("abc");
Iterator<String> it = ts.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}
后果（依照字典程序升序）：
abc
abcd
abf
f
h
ss
对于 自定义 的类型，TreeMap 是无奈主动排序的。须要指定自定义对象之间的比拟规定。如果没有指定（谁大谁小没有阐明），TreeMap 类不知如何给元素排序，就会报错，比方以下这段代码：
public class TreeSetTest02 {public static void main(String[] args) {Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
TreeSet<Student> students = new TreeSet<>();
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}
}
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
后果会报以下异样：
java.lang.ClassCastException: class test.Student cannot be cast to class java.lang.Comparable
这时咱们就须要对自定义类型 实现 Comparable 接口，并重写 compareTo()办法 ，须要在这个办法中编写比拟的逻辑（比拟规定）。
compareTo 办法返回的是 int 值：
返回 0 示意雷同，value 会笼罩；
返回 >0，会在右子树上找；
返回 <0，会在左子树上找。（此处不理解请去学习二叉树数据结构）
比拟规定是本人设定的，首先比拟年龄的大小，如果年龄一样，则比拟字符串的大小。
public class TreeSetTest02 {public static void main(String[] args) {Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
TreeSet<Student> students = new TreeSet<>();
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}
}
class Student implements Comparable<Student>{
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
// compareTO 办法返回的是 int 值；// 比拟规定是本人设定的，首先比拟年龄的大小，如果年龄一样，则比拟字符串的大小；public int compareTo(Student o) {if (this.age != o.age)
return this.age - o.age;
else // 年龄一样
return this.name.compareTo(o.name); // 此处调用的不是这个类中的 compareTo 办法，而是调用了字符串的 compareTo 办法
}
}
后果：
Student{name='Ana', age=18}
Student{name='Lip', age=18}
Student{name='Stark', age=21}
Student{name='Bob', age=25}
TreeSet 汇合中元素可排序的第二种形式：应用比拟器形式。 独自写一个比拟器，这个比拟器实现 java.util.Comparator 接口。并在创立 TreeSet 汇合时，传入这个比拟器。
public class TreeSetTest02 {public static void main(String[] args) {Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
// 创立 TreeSet 汇合时，须要传入这个比拟器
TreeSet<Student> students = new TreeSet<>(new StudentComparator());
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}
}
class Student {
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
// 独自写一个比拟器
// 比拟器实现 java.util.Comparator 接口
class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {if (o1.age != o2.age)
return o1.age - o2.age;
else
return o1.name.compareTo(o2.name);
}
}
当然也能够应用 匿名外部类 的形式。
public class TreeSetTest02 {public static void main(String[] args) {Student s1 = new Student("Ana",18);
Student s2 = new Student("Bob",25);
Student s3 = new Student("Stark",21);
Student s4 = new Student("Lip",18);
// 创立 TreeSet 汇合时，须要传入比拟器（应用匿名外部类）TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {if (o1.age != o2.age)
return o1.age - o2.age;
else
return o1.name.compareTo(o2.name);
}
});
students.add(s1);
students.add(s2);
students.add(s3);
students.add(s4);
Iterator<Student> it = students.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}
}
class Student {
public String name;
public int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
论断： 放到 TreeSet 或者 TreeMap 汇合 key 局部的元素要想做到排序，包含两种形式:
第一种: 放在汇合中的元素实现 java. lang. Comparable 接口。（比拟规定固定的时候应用这种）
第二种: 在结构 TreeSet 或者 TreeMap 汇合的时候给它传一个比拟器对象。（比拟规定常常变动的时候应用这种）
