参考链接：

[https://blog.csdn.net/zhangqunshuai/article/details/80660974]

[(https://blog.csdn.net/zhangqunshuai/article/details/80660974)

https://blog.csdn.net/t_testview/article/details/89014863

参考书籍： Offer来了（Java面试核心知识点）王磊 电子工业出版社

1、概述

List , Set, Map都是接口，前两个继承至Collection接口，Map为独立接口

Set下有HashSet，linkedHashSet，TreeSet

List下有ArrayList，Vector，linkedList

Map下有Hashtable，linkedHashMap，HashMap，TreeMap

Collection接口下还有个Queue接口，有PriorityQueue类

Java中集合类是放在java.util中，是一个用来存放对象的容器。 1、只能存放对象，不能存放int等类型，存的是对应的是Integer等对象 2、存的是对象的引用，对象本身是放在堆内存中 3、可以存放不同类型的对象（因为实现的时候使用了泛型），不建议使用。

注意：

Queue接口与List、Set同一级别，都是继承了Collection接口。

看图你会发现,linkedList既可以实现Queue接口,也可以实现List接口.只不过呢, linkedList实现了Queue接口。Queue接口窄化了对linkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 linkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。

2、Connection接口（所有集合类的根接口）

image.png

2.1 List集合

特点： 有序,可重复

• ArrayList 优点: 底层数据结构是数组，查询快；定义时不需要定义数组大小，如果数组大小不够，会创建一个新的更大的数组将原来的元素复制过去。 缺点: 线程不安全；增删慢。（元素必须连续存储，因此如果在中间位置添加或删除元素，需要其后面所有元素进行移动，不适合随机插入和删除，更适合随机查找和遍历操作）
• Vector 优点: 底层数据结构是数组，查询快；线程安全，支持线程同步（即同一时刻只允许一个线程对Vector进行写操作，以保证多线程下数据的一致性） 缺点: 增删慢；读写效率比ArrayList低（因为需要频繁的对Vector对象进行加锁和释放锁操作）
• linkedList 优点: 底层数据结构是双向链表，增删快（链表操作，增删只需要移动对应指针）。 缺点: 线程不安全，效率高，查询慢（需要从头到尾遍历）

2.2 Queue队列

• ArrayBlockingQueue:基于数组数据结构实现的有界阻塞队列。
• linkedBlockingQueue:基于链表数据结构的有界阻塞队列。
• PriorityBlockingQueue:支持优先级排序的无界阻塞队列。
• DelayQueue:支持延迟操作的无界阻塞队列。
• SynchronousQueue:用于线程同步的阻塞队列。
• linkedTransferQueue:基于链表数据结构实现的无界阻塞队列。
• linkedBlockingQueue:基于链表数据结构实现的双向阻塞队列。

2.3 Set 集合

特点：不可重复，无序

（1）HashSet

特点：底层数据结构是哈希表。(无序,唯一)

如何来保证元素唯一性?

依赖两个方法：hashCode()和equals()

（2）linkedHashSet（HashTable实现数据存储，双向链表记录顺序 ）

特点：底层数据结构是链表和哈希表。(FIFO插入有序,唯一)

1.由链表保证元素有序

2.由哈希表保证元素唯一

（3）TreeSet

特点：底层数据结构是红黑树。基于二叉树的原理对新添加的对象按照指定的顺序排序（升序或降序），每添加一个对象都会进行排序，并将对象插入二叉树的指定位置。(唯一，有序)

1）.如何保证元素唯一性的呢?

根据比较的返回值是否是0来决定

2）. 如何保证元素排序的呢?

① 自然排序

• 需要排序的类中实现 Comparable接口
• 重写Comparable接口中的Compareto方法

代码演示：

把用户类按照名字长度排序，长度相等的按照名字的hash值，如果hash值相等则名字相等，按照年龄排序。

User类：

public class User implements Comparable<User> { private String name; private int age; public User(String name, int age) { 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 hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; User other = (User) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } @Override public int compareTo(User o) { // return -1; //-1表示放在红黑树的左边,即逆序输出 // return 1; //1表示放在红黑树的右边，即顺序输出 // return 0; //表示元素相同，仅存放第一个元素 // 主要条件 姓名的长度,如果姓名长度小的就放在左子树，否则放在右子树 int num = this.name.length() - o.name.length(); // 姓名的长度相同，不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。 // 如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。 // 如果这两个字符串相等，则结果为 0 int num1 = num == 0 ? (this.name.hashCode() - o.name.hashCode()) : num; // 姓名的长度和内容相同，不代表年龄相同，所以还要判断年龄 int num2 = num1 == 0 ? this.age - o.age : num1; return num2; } @Override public String toString() { return "User [name=" + name + ", age=" + age + "]"; } }

测试类：

import java.util.TreeSet; public class Demo { public static void main(String[] args) { User user1 = new User("zhanggengying", 18); User user2 = new User("zhoufan", 21); User user3 = new User("zhoufan", 20); TreeSet<User> ts = new TreeSet<User>(); ts.add(user1); ts.add(user2); ts.add(user3); for (User user : ts) { System.out.println(user); } } }

结果：

User [name=zhoufan, age=20] User [name=zhoufan, age=21] User [name=zhanggengying, age=18]

② 比较器排序

比较器排序步骤：

• 单独创建一个比较类，这里以MyComparator为例，并且要让其继承Comparator接口。
• 重写Comparator接口中的Compare方法。

代码案例：和上述案例相同，不过是另一种实现方式

//用户类

package com.company.project.test09; public class User { private String name; private int age; public User(String name, int age) { 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 hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; User other = (User) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } @Override public String toString() { return "User [name=" + name + ", age=" + age + "]"; } }

//自己写的比较器

package com.company.project.test09; import java.util.Comparator; public class MyComparator implements Comparator<User> { @Override public int compare(User s1, User s2) { // 姓名长度 int num = s1.getName().length() - s2.getName().length(); // 姓名内容 int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num; // 年龄 int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2; return num3; } }

//测试类

package com.company.project.test09; import java.util.TreeSet; //TreeSet的自然排序 //实现Comparable接口，重写compareTo方法 public class Demo { public static void main(String[] args) { User user1 = new User("zhanggengying", 18); User user2 = new User("zhoufan", 21); User user3 = new User("zhoufan", 20); TreeSet<User> ts = new TreeSet<User>(new MyComparator()); ts.add(user1); ts.add(user2); ts.add(user3); for (User user : ts) { System.out.println(user); } } }

（4）TreeSet, linkedHashSet and HashSet 的区别

1）介绍：

• TreeSet, linkedHashSet and HashSet 在java中都是实现Set的数据结构
• TreeSet的主要功能用于排序
• linkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
• HashSet只是通用的存储数据的集合，通过传入的数据，计算出哈希值，存入哈希表中。

2）相同点

• Duplicates elements: 因为三者都实现Set interface，所以三者都不包含duplicate elements
• Thread safety: 三者都不是线程安全的，如果要使用线程安全可以Collections.synchronizedSet()

3）不同点

• Performance and Speed: HashSet插入数据最快，其次linkHashSet，最慢的是TreeSet因为内部实现排序
• Ordering: HashSet不保证有序，linkHashSet保证FIFO即按插入顺序排序，TreeSet安装内部实现排序，也可以自定义排序规则
• null:HashSet和linkHashSet允许存在null数据，但是TreeSet中插入null数据时会报NullPointerException

代码：

package com.company.project.test07; import java.util.Arrays; import java.util.HashSet; import java.util.linkedHashSet; import java.util.TreeSet; //TreeSet, linkedHashSet and HashSet的区别 public class Demo { public static void main(String[] args) { HashSet<Integer> hashSet = new HashSet<>(); linkedHashSet<Integer> linkedHashSet = new linkedHashSet<>(); TreeSet<Integer> treeSet = new TreeSet<>(); for (Integer data: Arrays.asList(5, 4, 3, 6, 8, 9, 10, 50, 30, 90, 111)) { // hashSet.add(data); hashSet.add(data); linkedHashSet.add(data); treeSet.add(data); } // 不保证有序 System.out.println("Ordering in HashSet :" + hashSet); // FIFO保证安装插入顺序排序 System.out.println("Order of element in linkedHashSet :" + linkedHashSet); // 内部实现排序 System.out.println("Order of objects in TreeSet :" + treeSet); } }

结果：

Ordering in HashSet :[50, 3, 4, 5, 6, 8, 9, 10, 90, 30, 111] Order of element in linkedHashSet :[5, 4, 3, 6, 8, 9, 10, 50, 30, 90, 111] Order of objects in TreeSet :[3, 4, 5, 6, 8, 9, 10, 30, 50, 90, 111]

2.4 总结

针对Collection集合我们到底使用谁呢?(掌握)

image.png

3. Map接口（映射接口，存放键值对）

image.png

特点：

以键值对的形式存放对象。key-value。一般是key为String类型，value为Object的类型。

Map接口有四个比较重要的实现类，分别是HashMap、TreeMap、linkedHashMap和HashTable。

3.1 Map集合

1. HashMap（数组+链表/红黑树，线程不安全）

HashMap的数据结构，内部为数组，数组的每个元素又是一个单向链表，如果单链表的元素超过8个，HashMap又会将链式结构变为红黑树来提高查找效率。

如果想要线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全，或者使用ConcurrentHashMap。

image.png

HashMap数组+链表结构

image.png

HashMap数组+红黑树结构

2.ConcurrentHashMap(分段锁实现，线程安全)

采用分段锁的思想实现并发操作，因此线程安全。

ConcurrentHashMap由多个Segment组成（Segment的数量是锁的并发度），每个Segment都是继承ReentrantLock并单独加锁，所有每次加锁操作是锁住的都是一个Segment，这样只要保证每个Segment都是线程安全的，也就实现了全局的线程安全。

image.png

ConcurrentHashMap数组+单向链表结构

image.png

ConcurrentHashMap数组+红黑树结构

3.HashTable(线程安全，哈希表)

继承Dictionary类，同一时刻只有一个线程能写HashTable,并发性不如ConcurrentHashMap

4.TreeMap(二叉树数据结构，有序)

实现了SortedMap接口保证元素顺序存储，默认按键值升序存储，也可自定义比较器（实现Comparable接口或者自定义比较器）

5.linkedHashMap（基于HashTable数据结构，使用链表保存插入顺序）

linkedHashMap是HashMap的子类，内部使用链表保存元素的插入顺序，通过Iterator遍历linkedHashMap时，会按照元素的插入顺序访问元素。

（1）HashMap、TreeMap、linkedHashMap的区别：

image.png

（2）Hashtable和HashMap的区别：

• Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别。
• Hashtable是线程安全的，HashMap不是线程安全的。
• HashMap效率较高，Hashtable效率较低。
• Hashtable不允许null值，HashMap允许null值（key和value都允许，HashMap允许多条记录的值为null）
• 父类不同：Hashtable的父类是Dictionary，HashMap的父类是AbstractMap

（3）如何选择Hashtable和HashMap？

如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。 查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。

（4）所有带hash的前缀的Map集合的存储原理：

• 通过 new 关键字在 Heap 堆中申请空间
• 保存其中元素的空间，按照hash码，预设好一个个的空间，这个空间就是 Hash Bucket(哈希桶)
• 每个桶有自己的Hash编号 ，一开始有少量的 Hash Bucket
• 当程序试图将一个 key-value(Entry) 放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的Bucket位置。
• 如果该Bucket为空，直接存放入该Bucket;
• 如果该Bucket不为空，使用 equals 比较两个Entry 的 Key；
• if(true){新 value 将覆盖 Entry 原 value，key 不变}
• if(false){新 Entry 将与 Bucket中原 Entry 形成 Entry 链，而且新 Entry 位于 Entry 链的头部}

3.2 Map集合的遍历：

1、通过内部类Entry进行遍历

2、通过迭代器进行遍历，先获得Entry的Set集合

3、通过keySet方法获得键的Set集合，通过遍历键取值

4、通过map.values()获得所有值，但是不能获得键

代码演示：

package com.company.project.test1001; import java.util.HashMap; import java.util.Map; //Map集合的遍历 public class Demo { public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>(); map.put("A", "北京"); map.put("D", "上海"); map.put("C", "广东"); for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println(entry); } } }

结果：

A=北京 C=广东 D=上海