一、汇合与数组的比拟
二、汇合构造继承图
汇合分为两大类：
一类是单个形式存储元素，超级父接口是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汇合的时候给它传一个比拟器对象。（比拟规定常常变动的时候应用这种）
发表回复