集合基础_泛型_Collection，List，LinkedList，Set接口，Map接口_一篇带你理解Java集合，HashMap，TreeMap
集合的引入Colletion接口的常用方法和集合遍历List接口特有方法和集合遍历ArrayListArrayList和Vector的区别和联系泛型自定义泛型结构泛型类和泛型接口泛型类细节泛型方法泛型参数存在继承关系通配符泛型的受限LinkedList的常用方法和集合遍历常用方法和集合遍历LinkedList原理图模拟LinkedList源码iterator(),Iterator,Iterable关系ListIterator迭代器Set接口Set和List接口的区别HashSet实现类HashSet底层其实就是HashMapHashSet简易原理图（后面有详细的）放入 HashSet中的数据，一定要重写两个方法： hashCode, equals疑问LinkedHashSet实现类比较器外部比较器和内部比较器谁好？TreeSetTreeSet底层原理：二叉树TreeSet二叉树遍历使用的是中序遍历TreeSet底层其实就是TreeMapMap接口Map常用方法HashTable实现类HashMap实现类HashMap源码解析：装填因子/负载因子为啥要设置成0.75？主数组的长度为2的倍数?LinkedHashMap实现类TreeMap实现类TreeMap源码解析Collections 工具类内容来源于马士兵教育的Java课程
集合的引入
数组，集合都是对多个数据进行存储操作的，简称为容器。
PS:这里的存储指的是内存层面的存储，而不是持久化存储（.txt,.avi,.jpg,数据库）。
数组：特点：
（1）数组一旦指定了长度，那么长度就被确定了，不可以更改。
int[] arr = new int[6];
（2）数组一旦声明了类型以后，数组中只能存放这个类型的数据。数组中只能存放同一种类型的数据。
int[] arr,String[] s,double[] d…
数组：缺点：
（1）数组一旦指定了长度，那么长度就被确定了，不可以更改。
（2）删除，增加元素 效率低。
（3）数组中实际元素的数量是没有办法获取的，没有提供对应的方法或者属性来获取
（4）数组存储：有序，可重复 ，对于无序的，不可重复的数组不能满足要求。
正因为上面的缺点，引入了一个新的存储数据的结构—>集合
集合会学习很多集合，为什么要学习这么多集合呢？因为不同集合底层数据结构不一样。集合不一样，特点也不一样
简易的集合结构图
Colletion接口的常用方法和集合遍历
public class InnerMethod {public static void main(String[] args) {/*Collection接口的常用方法增加：add(E e) addAll(Collection<? extends E> c)删除：clear() remove(Object o)修改：查看：iterator() size()判断：contains(Object o) equals(Object o) isEmpty()*///创建对象；接口不能创建对象，利用实现类创建对象Collection collection = new ArrayList();//调用方法//集合有一个特点：只能存放引用数据类型的数据，不能是基本数据类型//基本数据类型自动装箱，对应包装类。int--->Integercollection.add(12);collection.add(13);collection.add(14);collection.add(15);System.out.println(collection/*.toString*/);//[12, 13, 14, 15]//Arrays.asList可以帮我们把传进来的东西转成一个集合List integers = Arrays.asList(new Integer[]{12, 25, 36, 95,96});collection.addAll(integers);//将另一个集合添加入collection中System.out.println(collection);//collection.clear();清空集合System.out.println(collection);System.out.println("集合中元素的数量："+collection.size());System.out.println("集合是否为空："+collection.isEmpty());//删除数据boolean isRemove = collection.remove(12);System.out.println(collection);System.out.println("集合中数据是否删除成功："+isRemove);//equalsCollection collection2 = new ArrayList();collection2.add(12);collection2.add(13);collection2.add(14);collection2.add(15);Collection collection3 = new ArrayList();collection3.add(12);collection3.add(13);collection3.add(14);collection3.add(15);System.out.println(collection2.equals(collection3));System.out.println(collection2 == collection3);//contains(Object o)System.out.println("是否包含元素102："+collection3.contains(102));Collection collection4 = new ArrayList();collection4.add(12);collection4.add(13);collection4.add(14);collection4.add(15);collection4.add("abc");collection4.add(12.25);//对集合进行遍历（对集合元素进行查看）///方式1：增强for循环for (Object o:collection4){System.out.print(o+"\t");}System.out.println();//方式2：iterator()Iterator iterator = collection4.iterator();while (iterator.hasNext()){//通过 hasNext来判断是否有下一个元素，如果有下一个元素，那么返回true,// 如果没有下一个元素那么返回 falseSystem.out.print(iterator.next()+"\t");//12131415abc12.25}}
List接口特有方法和集合遍历
Collection有的方法下面并没有i写
public class InnerMethod {public static void main(String[] args) {/*List接口中常用方法：增加：add(int index, E element)删除：remove(int index) remove(Object o)修改：set(int index, E element)查看：get(int index)判断：*/List list = new ArrayList();list.add(12);list.add(12);list.add(12);list.add(15);System.out.println(list);//[12, 12, 12, 15]list.add(0, -5);System.out.println(list);//[-5, 12, 12, 12, 15]//setlist.set(2, -78);System.out.println(list);//[-5, 12, -78, 12, 15]//removelist.remove(0);//在集合中存入的是Integer类型数据的时候，调用remove方法调用的是：remove(int index)System.out.println(list);//[12, -78, 12, 15]list.add("abc");System.out.println(list);//[12, -78, 12, 15, abc]list.remove("abc");System.out.println(list);//[12, -78, 12, 15]//getObject o = list.get(0);System.out.println(o);//12//List集合 遍历：//方式1：普通for循环：for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}//增强for循环for (Object object:list){System.out.println(object);}//方式3：迭代器：Iterator iterator = list.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}}}
ArrayList
ArrayList和Vector内部方法和Collection，List内部方法一样或者相似。
JDK1.7之前源码：
底层数组，在调用构造器的时候，数组长度初始化10,扩容的时候扩展为原数组的1.5倍
JDK1.8之后源码
底层数组，在调用构造器的时候，底层数组为0,在调用add方法以后底层数组才重新赋值为新数组，新数组的长度为10–>节省了内存，在add后才创建长度为10的数组
ArrayList和Vector的区别和联系
联系：底层都是数组的扩容
区别： ArrayList底层扩容长度为原数组的1.5倍，线程不安全效率高， Vector底层扩容长度为原数组的2倍线程安全效率低（淘汰）
泛型
什么是泛型（Generic）：
泛型就相当于标签
形式：<>
集合容器类在设计阶段/声明阶段不能确定这个容器到底实际存的是什么类型的对象，所以在JDK1.5之前只能把元素类型设计为Object，JDK1.5之 后使用泛型来解决。因为这个时候除了元素的类型不确定，其他的部分是确定的。
例如关于这个元素如何保存，如何管理等是确定的，因此此时把元素的类型设计成一个参数，这个类型参数叫做泛型。Collection<E>, List<E>， ArrayList<E> 这个<E>就是类型参数，即泛型。
使用了泛型以后，可以确定集合中存放数据的类型，在编译时期就可以检查出来。
使用泛型你可能觉得麻烦，实际使用了泛型才会简单，后续的遍历等操作简单。
ArrayList al = new ArrayList();在JDK1.7以后可以写为：
ArrayList al = new ArrayList<>(); --<> —钻石运算符
public class FanXingYinru {public static void main(String[] args) {//创建一个ArrayList集合，向这个集合存入学生成绩//加入泛型的优点：在编译时期就会对类型进行检查，不是泛型对应的类型就不可以添加入这个集合。ArrayList<Integer> al = new ArrayList<Integer>();al.add(98);al.add(25);al.add(32);al.add(85);al.add(25);for (Integer i:al){System.out.println(i);}}}
自定义泛型结构
泛型类和泛型接口
泛型类的定义和实例化：
/* FanXingLei就是一个普通的类* FanXingLei<E> 就是一个泛型类* <>里面就是一个参数类型，但是这个类型是什么呢？这个类型现在是不确定的，相当于一个占位* 但是现在确定的是这个类型一定是一个引用数据类型，而不是基本数据类型*/public class FanXingLei<E> {int age;String name;E sex;public void a(E n){}public void b(E[] m){}}class Test{public static void main(String[] args) {//FanXingLei进行实例化//(1)实例化的时候不指定泛型：如果实例化的时候不明确的指定类的泛型，那么认为此泛型为Object类型FanXingLei fanXingLei = new FanXingLei();fanXingLei.a("abc");fanXingLei.a(17);fanXingLei.a(9.8);fanXingLei.b(new String[]{"a","b","c"});//（2）实例化的时候指定泛型：---》推荐方式FanXingLei<String> stringFanXingLei = new FanXingLei<String>();stringFanXingLei.sex = "男";stringFanXingLei.a("abc");stringFanXingLei.b(new String[]{"1","2","3"});}
父类指定泛型：
class FanXingLei2 extends FanXingLei<Integer>{}class Demo{public static void main(String[] args) {//指定父类泛型，那么子类就不需要再指定泛型了，可以直接使用FanXingLei2 fanXingLei2 = new FanXingLei2();fanXingLei2.a(19);}}
父类不指定泛型：
如果父类不指定泛型，那么子类也会变成一个泛型类，那这个E的类型可以在创建子类对象的时候确定：
class FanXingLei3<E> extends FanXingLei<E>{}class Demo2{public static void main(String[] args) {FanXingLei3<String> stringFanXingLei3 = new FanXingLei3<>();stringFanXingLei3.a("abc");stringFanXingLei3.sex="男";}}
泛型类细节
泛型类可以定义多个参数类型public class FanXing<A,B,C> {A age;B name;C sex;public void a(A m,B n,C x){}}
泛型类的构造器的写法：
不同的泛型的引用类型不可以相互赋值：
泛型如果不指定，那么就会被擦除，反应对应的类型为Object类型：
泛型类中的静态方法不能使用类的泛型：
不能直接使用E[]的创建数组：
泛型方法
1.什么是泛型方法？
不是带泛型的方法就是泛型方法泛型方法有要求：这个方法的泛型的参数类型要和当前的类的泛型无关换个角度：泛型方法对应的那个泛型参数类型 和 当前所在的这个类 是否是泛型类，泛型是啥 无关
2.泛型定义的时候，前面需要加
原因：原因：如果不加的话，会把T当做一种数据类型，然而代码中没有T类型那么就会报错
3.T的类型是在调用方法的时候确定的
4.泛型方法可否是静态方法？可以是静态方法;非泛型方法不可以是静态的
//*1.什么是泛型方法？*不是带泛型的方法就是泛型方法* 泛型方法有要求：这个方法的泛型的参数类型要和当前的类的泛型无关* 换个角度：* 泛型方法对应的那个泛型参数类型 和 当前所在的这个类 是否是泛型类，泛型是啥 无关* 2.泛型定义的时候，前面需要加<T>* 原因：原因：如果不加的话，会把T当做一种数据类型，然而代码中没有T类型那么就会报错* 3.T的类型是在调用方法的时候确定的* 4.泛型方法可否是静态方法？可以是静态方法;非泛型方法不可以是静态的*/public class Method<E> {//Method实例化的时候E就确定了//非泛型方法public void a(E a){//不可以是静态的}//泛型方法public static <T> void b(T a){}}class Demo{public static void main(String[] args) {Method<String> method = new Method<>();method.a("abc");method.b(12);//这里会出错，因为是静态的method.b(true);//这里会出错}}
泛型参数存在继承关系
class Test{//泛型参数存在继承关系的情况public static void main(String[] args) {Object o = new Object();String s = new String();o = s;//多态的一种形式Object[] objects = new Object[10];String[] strings = new String[10];objects = strings;//多态的一种形式List<Object> list = new ArrayList<>();List<String> list2 = new ArrayList<>();//list = list2;//出错//总结：A和B是子类父类的关系，但是G<A>和G<B>不存在继承关系的。是并列关系。}}
通配符
public class TongPeiFu {//出错，因为三种属于同一个东西，底部都是Object类型，重复定义了，并列关系，并不属于重载//在没有通配符的时候：//下面的a方法，相当于方法的重复定义，报错/*public void a(List<Object> list){}public void a(List<String> list){}public void a(List<Integer> list){}*/
引入通配符：
public static void main(String[] args) {List<Object> list = new ArrayList<>();List<String> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();List<?> list3 = null;//?就是通配符list3 = list;list3 = list1;list3 = list2;}
可以发现：
A 和 B是子类父类的关系，G<A>和G<B>不存在子类父类关系，是并列的；加入通配符？后，G<?>就变成了 G<A>和G<B>的父类
使用通配符：
public class TongPeiFu_2 {public void a(List<?> list) {内部遍历的时候用Object即可，不用？for (Object o:list){System.out.println(o);}//数据的写入操作//list.add("abc");-->不能随意的进行写入操作-->不能进行写入操作，除了写入空list.add(null);//数据的读取操作Object o = list.get(0);}}class Test2 {public static void main(String[] args) {TongPeiFu_2 fu2 = new TongPeiFu_2();fu2.a(new ArrayList<Integer>());fu2.a(new ArrayList<String>());fu2.a(new ArrayList<Object>());}}
泛型的受限
父类Person，子类Student
//Test测试类public class Test {public static void main(String[] args) {//a，b，c三个集合是并列关系List<Object> a = new ArrayList<>();List<Person> b = new ArrayList<>();List<Student> c = new ArrayList<>();//开始使用泛型受限:泛型的上限/*List<? extends Person>:相当于：List<? extends Person>是List<Person>的父类，是List<Person的子类>*/List<? extends Person> list = null;//list =a;//出错，Object不是Person的子类list =b;list =c;/*泛型的下限List<? super Person >相当于：List<? super Person >是List<Person>的父类，是List<Person的父类的父类>*/List<? super Person > list2 = null;list2 = a;list2 = b;//list2 = c;//出错，Student不是Person的父类}}
LinkedList的常用方法和集合遍历
常用方法和集合遍历
public class InnerMethod {public static void main(String[] args) {/*LinkedList常用方法：增加：addFirst（E e） addLast（E e）offer(E e) offerFirst(E e) offerLast(E e)删除： poll()pollFirst() pollLast() --->JDK1.6以后新出的方法，提高了代码的健壮性removeFirst() removeLast()--->早版本1.0修改：查看：element()getFirst() getLast()indexOf(Object o) lastIndexOf(Object o)peek()peekFirst() peekLast()判断：*///创建一个LinkedList集合对象：LinkedList<String> list = new LinkedList<>();list.add("a");list.add("b");list.add("c");list.add("d");list.add("d");list.add("b");list.add("e");list.addFirst("addFirst");list.addLast("addLast");list.offer("offfer");list.offerFirst("offerFirst");list.offerLast("offerLast");System.out.println(list);//LinkedList可以添加重复数据//删除System.out.println(list.poll());//删除头上的元素，并将元素输出System.out.println(list.pollFirst());System.out.println(list.pollLast());System.out.println(list.remove());System.out.println(list.removeFirst());System.out.println(list.removeLast());System.out.println(list);//LinkedList可以添加重复数据//list.clear();//清空集合//System.out.println(list);//System.out.println(list.pollFirst());//null//System.out.println(list.removeFirst());//会现异常//集合的遍历System.out.println("-----------");//普通for循环for (int i = 0; i < list.size(); i++) {System.out.println(list);}System.out.println("-----------");//增强for循环for (String s:list){System.out.println(s);}System.out.println("-----------");//迭代器Iterator<String> iterator = list.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}//下面这个迭代器方法好，节省内存，iterator2的生命周期短for (Iterator<String> iterator2 = list.iterator();iterator2.hasNext();){System.out.println(iterator2.next());}}}
LinkedList原理图
模拟LinkedList源码
public class Node {//节点类//三个属性//上一个元素地址private Node pre;//当前存入的元素private Object object ;//下一个元素地址private Node next;public Node getPre() {return pre;}public void setPre(Node pre) {this.pre = pre;}public Object getObject() {return object;}public void setObject(Object object) {this.object = object;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}@Overridepublic String toString() {return "Node{" +"pre=" + pre +", object=" + object +", next=" + next +'}';}}
public class NodeLinkedList {//链中一定有一个首节点Node first;//链中一定有一个尾节点Node last;//计数器int count = 0;//添加一个构造器public NodeLinkedList() {}//添加元素方法public void add(Object o){if (first == null){//说明你添加的是第一个元素Node node = new Node();node.setPre(null);node.setObject(o);node.setNext(null);//当前链中第一个节点变为nodefirst = node;//当前链中最后一个节点变为nodelast = node;}else{//证明已经不是链中的第一个节点//将添加的元素封装为一个Node对象Node node = new Node();node.setPre(last);//node的上一个节点一定是当前链中最后一个节点lastnode.setObject(o);node.setNext(null);//当前链中的最后一个节点的下一个元素要指向nodelast.setNext(node);//将最后一个节点变为nodelast = node;}//链中元素数量加1count++;}//得到集合中的元素的数量public int getSize(){return count;}//通过下标得到元素public Object get(int index){//获取链表的头元素Node n = first;for (int i = 0; i < index; i++) {n = n.getNext();}return n.getObject();}}class Test{public static void main(String[] args) {//创建一个NodeLinkedList集合对象NodeLinkedList list = new NodeLinkedList();list.add("a");list.add("b");list.add("c");System.out.println(list.getSize());System.out.println(list.get(0));}}
iterator(),Iterator,Iterable关系
ListIterator迭代器
public class ListIterator {public static void main(String[] args) {//ListIterator迭代器ArrayList<String> arrayList = new ArrayList<>();arrayList.add("12");arrayList.add("ac");arrayList.add("25");Iterator<String> iterator = arrayList.iterator();while (iterator.hasNext()){if ("12".equals(iterator.next())){arrayList.add("567");//java.util.ConcurrentModificationException}}}}
上面代码会出错。java.util.ConcurrentModificationException
出错原因：就是迭代器和list同时对集合进行操作：
解决办法：事情让一个“人”做 -->引入新的迭代器：ListIterator，迭代和添加操作都是靠ListIterator来完成的：
public class ListIteratorClass {public static void main(String[] args) {ArrayList<String> list = new ArrayList<>();list.add("aa");list.add("bb");list.add("cc");list.add("dd");list.add("ee");//在"cc"之后添加一个字符串"kk"ListIterator<String> it = list.listIterator();while(it.hasNext()){if("cc".equals(it.next())){it.add("kk");}}System.out.println(it.hasNext());System.out.println(it.hasPrevious());System.out.println("------------");//逆向遍历：while(it.hasPrevious()){System.out.println(it.previous());}System.out.println(it.hasNext());System.out.println(it.hasPrevious());System.out.println(list);}}
Set接口
Set和List接口的区别
List接口中：
不唯一（集合中可以含有相同的数据），有序（有索引，可以根据索引查询数据），遍历方式可以通过普通/增强for循环，迭代器
Set接口：
唯一（不可以有相同的数据），无序（数据可以无序摆放(不等于随机，按照一定规则摆放)，同时没有跟索引有关的方法），规则后续会讲到遍历方式只能通过增强for循环和迭代器
HashSet实现类
放入Integer类型数据：public class HashSetClass {public static void main(String[] args) {//创建一个集合HashSet<Integer> hs = new HashSet<>();hs.add(19);//truehs.add(22);hs.add(-1);hs.add(67);hs.add(19);//falsehs.add(0);hs.add(19);//falseSystem.out.println(hs.size());//5//唯一，无序System.out.println(hs);//[-1, 0, 19, 67, 22]}}
放入String类型数据：
public class HashSetClass2 {public static void main(String[] args) {//创建一个集合HashSet<String> hs = new HashSet<>();hs.add("a");hs.add("b");hs.add("b");hs.add("c");hs.add("e");hs.add("d");hs.add("f");System.out.println(hs.size());//6System.out.println(hs);//[a, b, c, d, e, f]
放入自定义的引用数据类型的数据：
public class StudentTest {public static void main(String[] args) {HashSet<Student> students = new HashSet<>();students.add(new Student(19,"Zhou"));students.add(new Student(20,"haha"));students.add(new Student(19,"Zhou"));students.add(new Student(30,"Zhou"));students.add(new Student(19,"嘻嘻"));System.out.println(students.size());//5//[HashSetClass3{age=20, name='haha'}, HashSetClass3{age=30, name='Zhou'}, HashSetClass3{age=19, name='Zhou'}, HashSetClass3{age=19, name='Zhou'}, HashSetClass3{age=19, name='嘻嘻'}]System.out.println(students);//自定义的类型不满足 唯一，无序的特点}}
可以看到：自定义的类型不满足 唯一，无序的特点（底层源码的原因，后面HashMap时会讲到），重写equals和hashCode就满足 唯一，无序的特点了
HashSet底层其实就是HashMap
public class HashSet<E>{//重要属性：private transient HashMap<E,Object> map;private static final Object PRESENT = new Object();//构造器：public HashSet() {map = new HashMap<>();//HashSet底层就是利用HashMap来完成的}public boolean add(E e) {return map.put(e, PRESENT)==null;}}
请看HashMap的源码解析。
HashSet简易原理图（后面有详细的）
放入 HashSet中的数据，一定要重写两个方法： hashCode, equals
@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age &&name.equals(student.name);}@Overridepublic int hashCode() {return Objects.hash(age, name);}
疑问
底层数组的长度是多少？底层数组的类型是什么？hashCode，equals方法朕的调用了吗？验证底层表达式是什么？同一个位置的数据向前放还是向后放？放入数组的数据是直接放的吗？是否封装成对象了？LinkedHashSet实现类
特点：唯一，有序（按照输入顺序进行输出）
其实就是在HashSet的基础上，多了一个总的链表，这个总链表将放入的元素串在一起，方便有序的遍历。元素之间维持着一条总的链表数据结构。
其他与HashSet相似。
比较器
以int类型为案例：比较的思路：将比较的数据做差，然后返回一个int类型的数据，将这个int类型的数值 按照 =0 >0 <0来比较大小
int a = 10;int b = 20;System.out.println(a-b); // =0 >0 <0
比较String类型数据：
String类实现了Comparable接口，这个接口中有一个抽象方法compareTo，String类中重写这个方法即可
String a = "A";String b = "B";System.out.println(pareTo(b));
比较double类型数据：
double a = 9.6;double b = 9.3;/* System.out.println((int)(a-b));*/System.out.println(((Double) a).compareTo((Double) b));
比较自定义的数据类型： 内部比较器
public class Student implements Comparable<Student>{private int age ;private double height;private String name;public Student(int age, double height, String name) {this.age = age;this.height = height;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public double getHeight() {return height;}public void setHeight(double height) {this.height = height;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Student{" +"age=" + age +", height=" + height +", name='" + name + '\'' +'}';}@Overridepublic int compareTo(Student o) {//按照年龄比较// return this.getAge() - o.getAge();//按照身高比较//return ((Double)this.getHeight()).compareTo((Double)o.getHeight());//按照姓名比较return this.getName().compareTo(o.getName());}}
public class Test {public static void main(String[] args) {Student s = new Student(10, 12.5, "haha");Student s2 = new Student(5, 25.5, "嘤嘤嘤");System.out.println(pareTo(s2));}}
外部比较器
public class Student{private int age ;private double height;private String name;public Student(int age, double height, String name) {this.age = age;this.height = height;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public double getHeight() {return height;}public void setHeight(double height) {this.height = height;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Student{" +"age=" + age +", height=" + height +", name='" + name + '\'' +'}';}}class BiJiaoQi implements Comparator<Student> {@Overridepublic int compare(Student o1, Student o2) {//比较年龄return o1.getAge() - o2.getAge();}}class BiJiaoQi2 implements Comparator<Student> {@Overridepublic int compare(Student o1, Student o2) {//比较年龄return o1.getName().compareTo(o2.getName());}}class BiJiaoQi3 implements Comparator<Student> {@Overridepublic int compare(Student o1, Student o2) {//在年龄相同的情况下 比较身高 年龄不同比较年龄if(o1.getAge() - o2.getAge() ==0){return ((Double)o1.getHeight()).compareTo((Double)o2.getHeight());}return o1.getAge() - o2.getAge();}}
public class Test {public static void main(String[] args) {Student s = new Student(10, 12.5, "haha");Student s2 = new Student(10, 25.5, "嘤嘤嘤");//获取外部比较器//在年龄相同的情况下 比较身高 年龄不同比较年龄Comparator qi = new BiJiaoQi3();System.out.println(pare(s, s2));}}
外部比较器和内部比较器谁好？
外部比较器，多态，扩展性好
TreeSet
特点：唯一，无序（没有按照输入顺序进行输出）， 有序（按照升序进行遍历）
//以Integer为例//底层利用的是内部比较器public class Test {public static void main(String[] args) {TreeSet<Integer> i = new TreeSet<>();i.add(12);i.add(4);i.add(-1);i.add(12);i.add(6);i.add(100);i.add(-25);System.out.println(i.size());System.out.println(i);//[-25, -1, 4, 6, 12, 100]
//String//底层利用的是内部比较器TreeSet<String> i2 = new TreeSet<>();i2.add("23");i2.add("lili");i2.add("23.0");i2.add("lili");i2.add("ZhouT");i2.add("嘻嘻");System.out.println(i2.size());System.out.println(i2);
自定义类型内部比较器：
public class Student implements Comparable<Student> {private int age ;private String name;public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Student(int age, String name) {this.age = age;this.name = name;}@Overridepublic String toString() {return "Student{" +"age=" + age +", name='" + name + '\'' +'}';}//内部比较器@Overridepublic int compareTo(Student o) {return this.getAge() - o.getAge();}}
public class Demo {public static void main(String[] args) {TreeSet<Student> i = new TreeSet<>();i.add(new Student(15, "xixi"));i.add(new Student(2, "1xixi"));i.add(new Student(7, "2xixi"));i.add(new Student(89, "3xixi"));i.add(new Student(23, "4xixi"));i.add(new Student(15, "5xixi"));System.out.println(i.size());//因为在设置规则的时候只设置了年龄，所以i.size=5,就算name不一样，但是跟后面name无关，所以就输出5//没有输出i.add(new Student(15, "5xixi"));System.out.println(i);}}
自定义类型外部比较器：
public class Student1{private int age;private String name;public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Student1(int age, String name) {this.age = age;this.name = name;}@Overridepublic String toString() {return "Student1{" +"age=" + age +", name='" + name + '\'' +'}';}}class BiJiaoQi implements Comparator<Student1>{@Overridepublic int compare(Student1 o1, Student1 o2) {return o1.getName().compareTo(o2.getName());}}
public class Demo1 {public static void main(String[] args) {//方法1：//利用外部比较器，必须自己制定Comparator<Student1> qi = new BiJiaoQi();TreeSet<Student1> i = new TreeSet<>(qi);i.add(new Student1(15, "xixi"));i.add(new Student1(2, "1xixi"));i.add(new Student1(7, "2xixi"));i.add(new Student1(89, "3xixi"));i.add(new Student1(23, "4xixi"));i.add(new Student1(15, "5xixi"));System.out.println(i.size());System.out.println(i);}}
Demo1类可以换一种写法：实际开发中利用外部比较器多，因为扩展性好（多态）
public class Demo1 {public static void main(String[] args) {//方法2：把Student类中的比较器BiJiaoQi()类删掉~//匿名内部类//利用外部比较器，必须自己制定：/*Comparator<Student1> com = new Comparator<Student1>() {@Overridepublic int compare(Student1 o1, Student1 o2) {return o1.getName().compareTo(o2.getName());}};TreeSet<Student1> ts = new TreeSet<>(com);ts.add(new Student1(10,"elili"));ts.add(new Student1(8,"blili"));ts.add(new Student1(4,"alili"));ts.add(new Student1(9,"elili"));ts.add(new Student1(10,"flili"));ts.add(new Student1(1,"dlili"));System.out.println(ts.size());System.out.println(ts);*///这种也行：TreeSet<Student1> ts = new TreeSet<>(new Comparator<Student1>() {@Overridepublic int compare(Student1 o1, Student1 o2) {return o1.getName().compareTo(o2.getName());}});ts.add(new Student1(10,"elili"));ts.add(new Student1(8,"blili"));ts.add(new Student1(4,"alili"));ts.add(new Student1(9,"elili"));ts.add(new Student1(10,"flili"));ts.add(new Student1(1,"dlili"));System.out.println(ts.size());System.out.println(ts);}}
TreeSet底层原理：二叉树
TreeSet二叉树遍历使用的是中序遍历
TreeSet底层的二叉树的遍历是按照升序的结果出现的，这个升序是靠中序遍历得到的。
先序遍历：根左右中序遍历：左根右后序遍历：左右根
TreeSet底层其实就是TreeMap
public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable{//重要属性：private transient NavigableMap<E,Object> m;private static final Object PRESENT = new Object();//在调用空构造器的时候，底层创建了一个TreeMappublic TreeSet() {this(new TreeMap<E,Object>());}TreeSet(NavigableMap<E,Object> m) {this.m = m;}public boolean add(E e) {return m.put(e, PRESENT)==null;}}
详细看HashMap的源码解析。
Map接口
Map常用方法
public class InnerMethod {//Map接口常用方法public static void main(String[] args) {/*增加：put(K key, V value)修改：删除：clear() remove(Object key)查询：entrySet() get(Object key) keySet() size() values()判断：containsKey(Object key) containsValue(Object value)equals(Object o) isEmpty()*///创建一个Map集合：Map<Key,Value>HashMap<String, Integer> hm = new HashMap<>();System.out.println(hm.put("lili", 12));//nullhm.put("nana", 25);hm.put("haha", 26);hm.put("lala", 25);//为什么这里输出12呢？而上面却输出null呢？System.out.println(hm.put("lili", 15));//12System.out.println(hm.size());//4,Key值重复只算一个System.out.println(hm);//{haha=26, nana=25, lili=15, lala=25}//hm.clear();清空集合//remove移除hm.remove("lala");System.out.println(hm);//{haha=26, nana=25, lili=15}//containsKey是否这个包含Key键System.out.println(hm.containsKey("nana"));//containValue是否包含这个Value值System.out.println(hm.containsValue(26));//equals方法HashMap<String, Integer> hm2 = new HashMap<>();hm2.put("lili", 15);hm2.put("nana", 25);hm2.put("haha", 26);System.out.println(hm2);System.out.println(hm == hm2);//false//既比较Key值，也比较Value值//equals进行了重写，比较的是集合中的值是否一致System.out.println(hm.equals(hm2));//true//判断是否为空System.out.println(hm2.isEmpty());//get来获取Value值System.out.println(hm.get("lili"));System.out.println("---------------");//keySet()对集合中的key进行遍历查看：Set<String> strings = hm.keySet();for (String s:strings){System.out.println(s);}System.out.println("----------");//values()对集合中的values进行遍历查看Collection<Integer> values = hm.values();for (Integer i:values){System.out.println(i);}System.out.println("------");//get(Object key)和KeySet结合起来Set<String> s = hm.keySet();for (String ss:s){//用get获取value值System.out.println(hm.get(ss));}//entrySet()获取Key和ValueSet<Map.Entry<String, Integer>> entries = hm.entrySet();for (Map.Entry<String, Integer> e:entries){System.out.println(e.getKey()+"\t"+e.getValue());}}}
HashTable实现类
JDK1.0就有的
与HashMap用法相同。
效率低，线程安全，key值不可以存入Null值
HashMap实现类
JDK1.2之后才有的
无序，唯一
效率高，线程不安全，key可以存入null值，并且key的nul值也遵循唯一的特点
必须重写equals和HashCode方法
HashMap源码解析：
public class Test {public static void main(String[] args) {//创建一个HashMap的对象：存储的是双列数据，键值对Key-ValueHashMap<Integer, String> hm = new HashMap<>();hm.put(1, "lala1");hm.put(2, "lala2");hm.put(3, "lala3");hm.put(4, "嘻嘻");hm.put(5, "lala5");hm.put(4, "嘤嘤嘤");//集合中元素的数量：5//集合中元素：{1=lala1, 2=lala2, 3=lala3, 4=嘤嘤嘤, 5=lala5}//?为什么是5呢？//在4=嘤嘤嘤中的那个4，到底是嘻嘻的4还是嘤嘤嘤的4呢？System.out.println("集合中元素的数量："+hm.size());System.out.println("集合中元素："+hm);}}
下面是源码：
public class HashMap<K,V>extends AbstractMap<K,V> //【1】继承的AbstractMap中，已经实现了Map接口//【2】又实现了这个接口，多余，但是设计者觉得没有必要删除，就这么地了implements Map<K,V>, Cloneable, Serializable{//【3】后续会用到的重要属性：先粘贴过来：static final int DEFAULT_INITIAL_CAPACITY = 16;//哈希表主数组的默认长度//定义了一个float类型的变量，以后作为：默认的装填因子，加载因子是表示Hsah表中元素的填满的程度//太大容易引起哈西冲突，太小容易浪费 0.75是经过大量运算后得到的最好值//这个值其实可以自己改，但是不建议改，因为这个0.75是大量运算得到的static final float DEFAULT_LOAD_FACTOR = 0.75f;transient Entry<K,V>[] table;//主数组,每个元素为Entry类型transient int size;int threshold;//数组扩容的界限值,门槛值 16*0.75=12 final float loadFactor;//用来接收装填因子的变量//【4】查看构造器：内部相当于：this(16,0.75f);调用了当前类中的带参构造器public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}//【5】本类中带参数构造器：--》作用给一些数值进行初始化的！public HashMap(int initialCapacity, float loadFactor) {//【6】给capacity赋值，capacity的值一定是 大于你传进来的initialCapacity 的 最小的 2的倍数int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;//【7】给loadFactor赋值，将装填因子0.75赋值给loadFactorthis.loadFactor = loadFactor;//【8】数组扩容的界限值,门槛值threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//【9】给table数组赋值，初始化数组长度为16table = new Entry[capacity];}//【10】调用put方法：public V put(K key, V value) {//【11】对空值的判断if (key == null)return putForNullKey(value);//【12】调用hash方法，获取哈希码int hash = hash(key);//【14】得到key对应在数组中的位置int i = indexFor(hash, table.length);//【16】如果你放入的元素，在主数组那个位置上没有值，e==null 那么下面这个循环不走//当在同一个位置上放入元素的时候for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//哈希值一样 并且 equals相比一样 //(k = e.key) == key 如果是一个对象就不用比较equals了if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//【17】走addEntry添加这个节点的方法：addEntry(hash, key, value, i);return null;}//【13】hash方法返回这个key对应的哈希值，内部进行二次散列，为了尽量保证不同的key得到不同的哈希码！final int hash(Object k) {int h = 0;if (useAltHashing) {if (k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h = hashSeed;}//k.hashCode()函数调用的是key键值类型自带的哈希函数，//由于不同的对象其hashCode()有可能相同，所以需对hashCode()再次哈希，以降低相同率。h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor)./*接下来的一串与运算和异或运算，称之为“扰动函数”，扰动的核心思想在于使计算出来的值在保留原有相关特性的基础上，增加其值的不确定性，从而降低冲突的概率。不同的版本实现的方式不一样，但其根本思想是一致的。往右移动的目的，就是为了将h的高位利用起来，减少哈西冲突*/h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}//【15】返回int类型数组的坐标static int indexFor(int h, int length) {//其实这个算法就是取模运算：h%length，取模效率不如位运算return h & (length-1);}//【18】调用addEntryvoid addEntry(int hash, K key, V value, int bucketIndex) {//【25】size的大小 大于 16*0.75=12的时候，比如你放入的是第13个，这第13个你打算放在没有元素的位置上的时候if ((size >= threshold) && (null != table[bucketIndex])) {//【26】主数组扩容为2倍resize(2 * table.length);//【30】重新调整当前元素的hash码hash = (null != key) ? hash(key) : 0;//【31】重新计算元素位置bucketIndex = indexFor(hash, table.length);}//【19】将hash,key,value,bucketIndex位置 封装为一个Entry对象：createEntry(hash, key, value, bucketIndex);}//【20】void createEntry(int hash, K key, V value, int bucketIndex) {//【21】获取bucketIndex位置上的元素给eEntry<K,V> e = table[bucketIndex];//【22】然后将hash, key, value封装为一个对象，然后将下一个元素的指向为e （链表的头插法）//【23】将新的Entry放在table[bucketIndex]的位置上table[bucketIndex] = new Entry<>(hash, key, value, e);//【24】集合中加入一个元素 size+1size++;}//【27】void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//【28】创建长度为newCapacity的数组Entry[] newTable = new Entry[newCapacity];boolean oldAltHashing = useAltHashing;useAltHashing |= sun.misc.VM.isBooted() &&(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash = oldAltHashing ^ useAltHashing;//【28.5】转让方法：将老数组中的东西都重新放入新数组中transfer(newTable, rehash);//【29】老数组替换为新数组table = newTable;//【29.5】重新计算threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}//【28.6】void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//【28.7】将哈希值，和新的数组容量传进去，重新计算key在新数组中的位置int i = indexFor(e.hash, newCapacity);//【28.8】头插法e.next = newTable[i];//获取链表上元素给e.nextnewTable[i] = e;//然后将e放在i位置 e = next;//e再指向下一个节点继续遍历}}}}
装填因子/负载因子为啥要设置成0.75？
如果装填因子是1， 那么数组满了再扩容，可以做到 最大的空间利用率
但是这是一个理想状态，元素不可能完全的均匀分布，很可能就哈西碰撞产生链表了。产生链表的话 查询时间就长了。
—>空间好，时间不好
那么有人说 ，把装填因子搞小一点，0.5， 如果是0.5的话，就浪费空间，但是可以做到 到0.5就扩容 ，然后哈西碰撞就少，
不产生链表的话，那么查询效率很高
—>时间好，空间不好
所以在空间和时间中，取中间值，平衡这个因素 就取值为 0.75
主数组的长度为2的倍数?
原因1：
这两个等效的前提就是 length必须是2的整数倍
原因2：如果不是2的整数倍，那么 哈西碰撞 哈西冲突的概率就高了很多
LinkedHashMap实现类
唯一，有序（按照输入顺序进行输出)
LinkedHashMap<String, Integer> hm3 = new LinkedHashMap<>();hm3.put("lili", 12);hm3.put("lili", 25);hm3.put("nana", 25);hm3.put("haha", 26);hm3.put("lala", 25);System.out.println(hm3.size());//4System.out.println(hm3);//{lili=25, nana=25, haha=26, lala=25}
TreeMap实现类
唯一，有序（升序或降序）
按照二叉树的原则
放入集合的key的数据对应的类型内部一定要实现比较器(内部比较器，外部比较器)
Key的类型为String类型：
public class TreeMapClass {public static void main(String[] args) {Map<String, Integer> tm = new TreeMap<>();tm.put("alili", 15);tm.put("elili", 111115);tm.put("blili", 115);tm.put("flili", 1111115);tm.put("clili", 1115);tm.put("dlili", 11115);tm.put("elili", 111115);System.out.println(tm.size());//{alili=15, blili=115, clili=1115, dlili=11115, elili=111115, flili=1111115}System.out.println(tm);}}
Key为自定义引用数据类型：
内部比较器：
public class Student implements Comparable<Student>{private int age ;private String name ;private double height ;public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public double getHeight() {return height;}public void setHeight(double height) {this.height = height;}public Student(int age, String name, double height) {this.age = age;this.name = name;this.height = height;}public Student() {}@Overridepublic String toString() {return "Student{" +"age=" + age +", name='" + name + '\'' +", height=" + height +'}';}@Overridepublic int compareTo(Student o) {return this.getName().compareTo(o.getName());}}
public class Test {public static void main(String[] args) {TreeMap<Student, Integer> tm = new TreeMap<>();tm.put(new Student(1967,"alili",120.5), 1);tm.put(new Student(119,"blili",120.5), 12);tm.put(new Student(129,"clili",120.5), 13);tm.put(new Student(9,"dlili",120.5), 14);tm.put(new Student(9,"dlili",120.5), 14);tm.put(new Student(1119,"elili",120.5), 15);System.out.println(tm.size());System.out.println(tm);}}
外部比较器：（Student类把Comparable删掉，把compareTo方法删除）
public class Test {//内部比较器public static void main(String[] args) {Map<Student, Integer> tm = new TreeMap<>(new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {return ((Double)o1.getHeight()).compareTo((Double)o2.getHeight());}//匿名内部类});tm.put(new Student(1967,"alili",120.50), 1);tm.put(new Student(119,"blili",120.500), 12);tm.put(new Student(129,"clili",120.5), 13);tm.put(new Student(9,"dlili",120.5), 14);tm.put(new Student(9,"dlili",120.5), 14);tm.put(new Student(1119,"elili",120.5), 15);System.out.println(tm.size());System.out.println(tm);}}
原理图：
TreeMap源码解析
public class TreeMap<K,V>{//重要属性：//外部比较器：private final Comparator<? super K> comparator;//树的根节点：private transient Entry<K,V> root = null;//集合中元素的数量：private transient int size = 0;//空构造器:public TreeMap() {comparator = null;//如果使用空构造器，那么底层就不使用外部比较器}//有参构造器：public TreeMap(Comparator<? super K> comparator) {parator = comparator;//如果使用有参构造器，那么就相当于指定了外部比较器}public V put(K key, V value) {//k,V的类型在创建对象的时候确定了//如果放入的是第一对元素，那么t的值为nullEntry<K,V> t = root;//在放入第二个节点的时候，root已经是根节点了//如果放入的是第一个元素的话，走入这个if中：if (t == null) {//自己跟自己比compare(key, key); // type (and possibly null) check//根节点确定为rootroot = new Entry<>(key, value, null);//size值变为1size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable paths//将外部比较器赋给cpr:Comparator<? super K> cpr = comparator;//cpr不等于null，意味着你刚才创建对象的时候调用了有参构造器，指定了外部比较器if (cpr != null) {do {parent = t;cmp = pare(key, t.key);//将元素的key值做比较//cmp返回的值就是int类型的数据：//要是这个值《0 =0 》0if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;else//cpm==0//如果key的值一样，那么新的value替换老的value 但是key不变 因为key是唯一的return t.setValue(value);} while (t != null);}//cpr等于null，意味着你刚才创建对象的时候调用了空构造器，没有指定外部比较器，使用内部比较器else {if (key == null)throw new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = pareTo(t.key);//将元素的key值做比较if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;//size加1 操作modCount++;return null;}}static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left = null;Entry<K,V> right = null;Entry<K,V> parent;boolean color = BLACK;}
Collections 工具类
Collections是一个工具类，我们主要的使用其中的方法；Collections属性被static修饰，不能创建对象，直接通过类名.方法名调用；Collection接口，Collections是一个类；public class InterMethod {public static void main(String[] args) {//Collections不支持创建对象，因为构造器私有化了/*Collections cols = new Collections();*///里面的属性和方法都是被static修饰，我们可以直接用类名.去调用即可：//常用方法：//addAll（）方法ArrayList<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("aaa");Collections.addAll(list, "ee","ff","hhh");Collections.addAll(list, new String[]{"String数组","zzz","b"});System.out.println(list);//binarySearch必须在有序的集合中查找某个元素的索引：--》排序：Collections.sort(list);//sort升序System.out.println(Collections.binarySearch(list, "aaa"));System.out.println(list);System.out.println("----------------------");//copy:替换方法ArrayList<String> list2 = new ArrayList<>();Collections.addAll(list2, new String[]{"qwe","zzz","bwr"});Collections.copy(list, list2);将list2的内容替换到list上去System.out.println(list);//[qwe, zzz, bwr, b, bbb, ccc, ee, ff, hhh, zzz]System.out.println(list2);//[qwe, zzz, bwr]//fill:填充Collections.fill(list, "yyy");//将list中的元素全部填充为yyySystem.out.println(list);//[yyy, yyy, yyy, yyy, yyy, yyy, yyy, yyy, yyy, yyy]}}
有不懂的地方可以私信~
内容来源于马士兵教育赵珊珊老师的Java笔记。
Java基础_集合基础_泛型_Collection List LinkedList Set接口 Map接口_一篇带你理解Java集合 HashMap TreeMap_21
