java集合

参考马士兵老师Java集合全套视频

Java集合

【1】数组，集合都是对多个数据进行存储操作的，简称为容器（PS:这里的存储指的是内存层面的存储，而不是持久化存储。）

【2】数组：特点：

数组一旦制定了长度，那么长度就确定了，不可以更改。
数组一旦声明了类型以后，数组中只能存放这个类型的数据。数组中只能存放同一种类型的数据。

【3】数组：缺点：

数组长度不可以更改。
删除、增加元素效率低。
数组中实际元素的数量是没有办法获取的，没有提供对应的方法或者属性来获取的。
数组存储：有序，可重复，对于无序的，不可重复的需求数组不可以满足。

【4】正是由于上面的缺点，引入了一个新的存储数据的结构->集合

【5】集合一章会学习很多集合，为什么要学习这么多集合呢？
因为不同集合底层数据结构不一样。

【简要的集合结构图】
在这里插入图片描述

1.Collection接口

在这里插入图片描述

import java.util.*;

public class javaCollection {
    public static void main(String[] args) {
        /*
        Collection的常用方法：
        增加：add(E e) addAll(Collection<? extends E> c)
        删除：clear()  remove(Object o)
        修改：
        查看：iterator()   size()
        判断：contains(Object o) containsAll(Collection<?> c) equals(Object o)
         */
        //创建对象：接口不能创建对线，利用实现类创建对象
        Collection col = new ArrayList();
        //调用方法:
        //集合有一个特点：只能存放引用数据类型的数据，不能是基本数据类型
        col.add(18);//基本数据类型自动装箱
        col.add(12);
        col.add(11);
        col.add(17);
        col.add("abc");
        System.out.println(col);

        List list = Arrays.asList(new Integer[]{1,2,3,4,5});
        col.addAll(list);//将另一个集合添加到col中
        System.out.println(col);

        //集合中数据是否被删除
        System.out.println("集合是否包含元素5:"+col.contains(5));
        boolean isRemove = col.remove(5);
        System.out.println(col);
        System.out.println("集合中的数据是否删除成功:"+isRemove);

        //equals比较两个集合是否相同
        System.out.println(col.equals(list));

        //对集合遍历
        //方法一
        for(Object o:col){
            System.out.print(o+"\t");
        }
        System.out.println();
        //方法二
        Iterator it = col.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+"\t");
        }
        System.out.println();

        //清空
        col.clear();;
        System.out.println(col);
        System.out.println("集合中数据个数:"+col.size());
        System.out.println("集合是否为空:"+col.isEmpty());
    }
}

2.List接口

List相比于Collection扩展的方法都跟索引有关

import java.util.*;

public class javaCollection {
    public static void main(String[] args) {
       /*
       List接口中常用方法:
       增加：add(int index, E element)
       删除：remove(int index) remove(Object o)
       修改：set(int index,E element)
       查看：get(index)
       判断：
        */
        List list = new ArrayList();
        list.add(12);
        list.add(13);
        list.add("abc");
        list.add(2);
        System.out.println(list);
        //按位置添加
        System.out.println("按位置添加");
        list.add(0,"this is first element");
        System.out.println(list);

        //修改
        System.out.println("修改");
        list.set(0,"UPDATE");
        System.out.println(list);

        //删除
        System.out.println("删除");
        list.remove(2);//在集合中存入的是Integer类型数据的时候，调用remove方法调用的是:remove(int index)
        System.out.println(list);

        //查看
        System.out.println("查看");
        Object o = list.get(0);
        System.out.println(o);

        //遍历
        System.out.println("遍历");
        //方法一
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+"\t");
        }
        System.out.println();

        for(Object e:list){
            System.out.print(e+"\t");
        }
        System.out.println();

        Iterator it = list.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+"\t");
        }
        System.out.println();
    }
}

2.1 ArrayList

ArrayList原码类似StringBuilder。

两个重要属性：

Objecte[] elementData;
int size;

【JDK1.7原码】

调用空构造器的时候给底层数组elementData初始化，初始化长度为10.
长度不足的时候，调用grow方法扩容1.5倍。创建一个新的数组，并将旧数组的内容拷贝进新数组，并修改elementData的指针。

【JDK1.8原码】

调用空构造器的时候给底层数组elementData赋值一个空的数组{},在第一次调用add方法后，创造长度为10的数组。
在调用add方法的时候，会先检查数组长度，如果长度不足，扩容为1.5倍，如果原来长度是0，则设置长度为10。

2.2 Vector实现类

两个重要属性：

Objecte[] elementData;
int size;
调用空构造器的时候给底层数组elementData初始化，初始化长度为10.
长度不足的时候，调用grow方法扩容2.0倍。创建一个新的数组，并将旧数组的内容拷贝进新数组，并修改elementData的指针。
add方法带synchronized修饰，是线程安全的。但是效率低，所以被淘汰了。

2.3 LinkedList

2.3.1 LinkedList常用方法

import java.util.*;

public class javaCollection {
    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(),-->新方法，不会随意抛异常
            removeFirst(),removeLast()
        修改：
        查看：element(),getFirst(),getLast(),indexOf(Obeject o),LastIndexOf(Object e),peek(),peekFirst(),peekLast()
        判断：
         */
        LinkedList<String> list = new LinkedList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("1");//LinkedList可以添加重复元素
        System.out.println(list);

        //添加头元素
        list.addFirst("this is first element1");
        System.out.println(list);
        list.offerFirst("this is first element2");
        System.out.println(list);

        //添加尾元素
        list.addLast("this is Last element1");
        System.out.println(list);
        list.offerLast("this is Last element2");

        //删除
        System.out.println(list);
        System.out.println(list.poll());
        System.out.println(list.pollFirst());
        System.out.println(list.pollLast());
        System.out.println(list);
        System.out.println(list.remove());
        System.out.println(list.removeFirst());
        System.out.println(list.removeLast());
        LinkedList<String> list2 = new LinkedList<>();
        System.out.println(list2.poll());
        //System.out.println(list2.remove());//会报错

        //LinkedList遍历
        //方法一
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("+========================");
        //方法二
        for(String s:list){
            System.out.println(s);
        }
        System.out.println("+========================");
        //方法三
        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("+========================");
        //方法四 该方法更好，for循环结束后会释放空间
        for (Iterator<String> it1 = list.iterator();it1.hasNext();){
            System.out.println(it1.next());
        }
    }
}

2.3.2 LinkedList底层原理

物理结构：跳转结构

逻辑结构：线性表（链表）

LinkedList底层使用双向链表。

2.3.3 LinkedList原码解析

属性

int size;//元素个数
Node next;//下个元素地址
Node prev;//上个元素地址
E item;//当前元素

方法

get(int index)：判断元素在链表的哪一部分，决定是从前往后找，还是从后往前找。

2.3.4 Iterable接口和Iterator抽象方法的关系

在这里插入图片描述

增强for循环底层也是用迭代器实现的。

2.3.5 ListIterator

允许并行修改。

import java.util.*;

public class javaCollection {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("e");
        list.add("f");
        //在c后面添加d
        //使用Iterator会出现并行错误
        ListIterator<String> it = list.listIterator();
        while (it.hasNext()){
            if("c".equals(it.next())){
                it.add("d");
            }
        }
        System.out.println(list);

        //逆向遍历
        while(it.hasPrevious()){
            System.out.println(it.previous());
        }
    }
}

3.泛型

【1】什么是泛型(Generic)

泛型就相当于标签，形式为:<>。集合容器类在设计阶段/声明阶段不能确定这个容器到底实际存的是什么类型的对象，所以在JDK1.5之前只能把元素类型设计为Object，JDK1.5之后使用泛型类解决，因为这个时候除了元素的类型不确定，其它的部分是确定的，例如关于这个元素如何保存的，如何管理等是确定的，因此此时把元素的类型设计成一个参数，这个类型参数叫做泛型。
Collection,List,这个就是类型参数，即泛型。

如果不使用泛型，有缺点：
一般我们在使用的时候基本上往集合中存入的都是相同类型的数据-便于管理，所以现在什么引用数据类型都可以存入集合，不方便。

【2】泛型的作用

使用了泛型以后，可以确定集合中存放数据的类型，在编译时期就可以检查出来。

【3】泛型的类型：都是引用数据类型，不能是基本数据类型。

3.1 自定义范型结构

3.1.1 泛型类

泛型具体使用如下

/**
 * @author：AFU
 * GenericTest就是一个普通的类
 * GenericTest<E> 就是一个泛型类
 * <>里面是一个参数类型，但是这个类型是什么呢？这个类型现在是不确定的，相当于一个占位
 * 但是现在确定的是这个类型一定是一个引用数据类型，而不是基本数据类型。
 */
public class GenericTest<E> {
    int age;
    String name;
    E ses;

    public void a(E n){
        System.out.println(n.toString());
    }
}

//继承的情况
//父类指定泛型
class SubGenericTest extends GenericTest<Integer>{

}

//父类不指定泛型类型，子类需要声明为泛型类
class SubGenericTest2<E> extends GenericTest<E>{

}

class Test{
    public static void main(String[] args) {
        //GenericTest进行实例化
        //(1)实例化时不指定泛型,如果实例化的时候不明确的指定类的泛型，那么认为此泛型为Object类型
        GenericTest gt1 = new GenericTest();
        gt1.a("abc");
        gt1.a(12);

        //(2)实例化的时候指定类的泛型
        GenericTest<String> gt2 = new GenericTest<>();
        gt2.a("this is String");

        //继承的情况
        //父类指定泛型
        SubGenericTest sgt1 = new SubGenericTest();
        SubGenericTest2<String> sgt2 = new SubGenericTest2<>();
        sgt1.a(15);
        sgt2.a("this is String");
    }
}

一些泛型类的细节

泛型可以有多个参数类型

public class GenericTest02<A,B,C> {
    A age;
    B name;
    C sex;
    public void a(A m,B c,C d){
        
    }
}

泛型类的构造器里不用在写<>
不同的泛型的引用类型不可以相互赋值
泛型如果不指定，那么就会被擦除，反应对应的类型为Object类型
泛型类中的静态方法不能使用类的泛型。
不能直接使用E[]的创建

public class GenericTest02<A> {
    A age;
    public void a(A m){
        //不可以，A[] arr = new A[10];
        A[] arr = (A[])new Object[10];
    }
}

3.1.2 泛型方法

并不是带泛型的方法就叫泛型方法
泛型方法有要求，这个方法的泛型的参数类型要和当前的类的泛型无关（换个角度：泛型方法对应的那个泛型参数类型和当前所在的这个类是否是泛型类，泛型类是啥无关。
泛型方法定义的时候，前面要加上，如果不加的话，会将T当成一种数据类型，如果代码中没有T就会报错。
泛型方法在调用时才会确定泛型类型
泛型方法可以是静态方法。

public class GenericTest02<E> {
    //不是泛型方法
    public void a(E e){

    }
    //是泛型方法
    public <T> void b(T t){
        
    }
}

2.1.3 通配符

继承关系：A和B是子类父类的关系，但是G<A>和G<B>不存在继承关系，二是并列关系，因为泛型只是现在作用。

比如下面情况就会报错

import java.util.List;

public class GenericTest02<E> {
    //报错，因为两个方法参数实际上一样，泛型只是限制。
   public void a(List<Object> list){
       
   }
   public void a(List<String> list){
       
   }
}

可以修改为

import java.util.List;

public class GenericTest02<E> {
   public void a(List<?> list){
       //1.遍历用Object
       for(Object a:list){
           
       }
       //2.数据的写入操作
       //list.add("abc");会报错，因为不能随意的添加数据，因为通配符数据类型不确定
       
       //3.数据的读取操作
       Object s = list.get(0);//必须用Object类型读取
   }
}

import java.util.ArrayList;
import java.util.List;

public class GenericTest02<E> {
    public static void main(String[] args) {
        List<Object> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();

        List<?> list = null;
        list = list1;
        list = list2;
        list = list3;
    }
}

3.1.4 泛型受限

import java.util.ArrayList;
import java.util.List;
class Person{

}
class Student extends Person{

}

public class GenericTest02<E> {
    public static void main(String[] args) {
        //三个list是并列关系
        List<Object> list1 = new ArrayList<>();
        List<Person> list2 = new ArrayList<>();
        List<Student> list3 = new ArrayList<>();

        //开始使用泛型受限:属于泛型的上限
        //相当于List<? extends Person>是List<Person>的父类，是List<Person的子类>的父类
        List<? extends Person> list = null;
        list = list1;//报错
        list = list2;
        list = list3;

        //开始使用泛型首先：属于泛型的下限
        //相当于List<? super Person>是List<Person>的父类，是List<Person的父类>的父类
        List<? super Person> list4 = null;
        list4 = list1;
        list4 = list2;
        list4 = list3;//报错
    }
}

4.set集合接口

特点：

集合内元素唯一
无序（无序是相对于List接口，无序不等于随机）
没有跟索引相关的方法，遍历使用迭代器或增强for循环，但是不能用普通for循环。

4.1 HashSet

HashSet调用hashcode方法确定哈希值，并通过表达式和哈希值确定在数组中的存放位置。

底层就是HashMap

底层原理：数组+链表 = 哈希表

【疑问】

数组的长度是多少
数组的类型是什么
hashCode，equals方法针对调用了吗？要验证
底层表达式是什么？
同一个位置的数据向前放还是向后放？
放入数组中的数据，是直接放的吗？是否封装为对象了？

注意：如果放入HashSet中的数据是引用型数据，一定要重写两个方法，hashcode和equals方法。

import java.util.*;

public class javaCollection {
    public static void main(String[] args) {
        //创建一个HashSet集合
        HashSet<Integer> hs = new HashSet<>();
        System.out.println(hs.add(11));//true
        hs.add(5);
        hs.add(2);
        System.out.println(hs.add(11));//false
        hs.add(5);
        System.out.println(hs.size());//输出3
        System.out.println(hs);//输出[2, 5, 11] 无序、唯一

        //自定义的类型不满足唯一、无序的特点.需要重写hashcode和equals方法
        HashSet<student> hs1 = new HashSet<>();
        hs1.add(new student(10,"lili"));
        hs1.add(new student(10,"lili"));
        hs1.add(new student(11,"lili"));
        hs1.add(new student(12,"lili2"));
        hs1.add(new student(13,"lili3"));
        System.out.println(hs1);
    }
}

4.1.1 LinkedHashSet

特点：

有序（按照输入顺序进行输出，多了一个按输入顺序构建的链表）
唯一

4.2 TreeSet

底层使用TreeMap

4.2.1 比较器

比较的思路：将比较的数据做差，然后返回一个int类型的数据，将这个int类型的数值，按照=0,>0,<0处理

内部比较器：实现Comparable接口，重写compareTo方法。
外部比较器：使用一个类实现Comparator接口，重写compare方法，也可以用匿名内部类。

外部比较器更好，多态，扩展性好。

（1）存入Integer、String类型数据

特点：唯一，无序（没有按输入顺序进行输出），有序（按照升序进行遍历）

原理：底层——二叉树（使用内部比较器），使用中序遍历。

（2）放入自定义类型数据

利用内部比较器：必须实现Comparator接口，重写compareTo方法。
利用外部比较器：实现外部比较器的类，将外部比较器的对象作为参数传给TreeSet构造器作为参数。

5.Map接口

5.1 HashMap

特点：无序、唯一

特点是按照key进行总结的，因为底层key遵照哈希表的结构（数组+链表）

哈希表的原理：比如放入这个集合的数据对应的哪个类，必须重写hashCode方法和equals方法。

import java.util.*;

public class javaCollection {
    public static void main(String[] args) {
        /*
        增加：put(K key,V value)
        删除：clear() remove(Object key)
        修改：
        查找：get(Object key) entrySet() keySet()
        判断：containsKey(Object key) containsValue(Object value) equals(Object o) isEmpty()
         */
        //创建一个Map集合
        Map<String,Integer> map = new HashMap<>();
        map.put("aa",1111);
        System.out.println(map.put("bb",2222));//输出null
        map.put("cc",3333);
        System.out.println(map.put("bb",4444));//输出2222
        System.out.println(map.size());//输出3
        System.out.println(map);//输出{aa=1111, bb=4444, cc=3333}
        System.out.println(map.get("bb"));//4444


        Map<String,Integer> map2 = new HashMap<>();
        map2.put("aa",1111);
        System.out.println(map2.put("bb",2222));//输出null
        map2.put("cc",3333);
        System.out.println(map2.put("bb",4444));//输出2222
        System.out.println(map==map2);//false
        System.out.println(map.equals(map2));//true

        //map.clear();//清空
        //System.out.println(map);
        map.remove("aa");
        System.out.println(map);//{bb=4444, cc=3333}

        System.out.println(map.isEmpty());//false

        //按key遍历
        System.out.println(map.keySet());//[bb, cc]
        for(String s: map.keySet()){
            System.out.println(s);
        }

        //查看value
        System.out.println(map.values());//[4444, 3333]
        for(int v:map.values()){
            System.out.println(v);
        }

        //按Entry遍历
        /*
        输出
        bb	4444
        cc	3333
         */
        for(Map.Entry<String,Integer> e:map.entrySet()){
            System.out.println(e.getKey()+"\t"+e.getValue());
        }
    }
}

5.1.1 HashMap和HashTable比较

HashMap: JDK1.2 效率高线程不安全 key可以存入null值，并且key的null值也遵循唯一的特点

HashTable: JDK1.0 效率低线程安全 key不可以存入null

5.1.2 LinkedHashMap

特点：唯一，有序（按照输入顺序进行输出）

5.2 TreeMap

特点：唯一、有序（按照升序或降序）

原理：二叉树，key遵照二叉树的特点，放入集合的key的数据对应的类型内部一定要实现比较器。

底层：使用红黑树。要使用比较器。

底层结点属性：

E key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

使用：

import java.util.*;


class Student implements Comparable<Student>{
    int age;
    String name;
    double height;

    @Override
    public int compareTo(Student o) {
        return this.age-o.age;
    }

    public Student(int age, String name, double height) {
        this.age = age;
        this.name = name;
        this.height = 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;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", height=" + height +
                '}';
    }

    @Override
    public 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 && Double.compare(student.height, height) == 0 && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name, height);
    }
}

public class javaCollection {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("blili",1234);
        map.put("blili",2345);
        map.put("clili",2445);
        map.put("alili",2245);
        map.put("dlili",2545);
        System.out.println(map.size());//4
        System.out.println(map);//{alili=2245, blili=2345, clili=2445, dlili=2545}

        Map<Student,Integer> map1 = new TreeMap<>();
        //必须重写hashCode和equals方法，还有compareTo方法
        map1.put(new Student(19,"blili",170.5),1001);
        map1.put(new Student(18,"blili",150.5),1001);
        map1.put(new Student(19,"alili",180.5),1001);
        map1.put(new Student(17,"clili",140.5),1001);
        map1.put(new Student(10,"dlili",160.5),1001);

        System.out.println(map1.size());//4
        System.out.println(map1);//{Student{age=10, name='dlili', height=160.5}=1001, Student{age=17, name='clili', height=140.5}=1001, Student{age=18, name='blili', height=150.5}=1001, Student{age=19, name='blili', height=170.5}=1001}

    }
}

5.3 HashMap

HashMap的数据结构

jdk1.7:数组+链表
jdk1.8以后：数组+链表+红黑树

HashMap中数组中每个元素Node<K,V>有四个属性：

hash
key
value
next

HashMap底层的数组类型为：Entry，每个元素也要用Entry类型封装。

底层遇到哈希冲突使用链地址法，每次遇到新的元素，将新的元素替换旧的元素，返回旧的元素。

底层重要属性：

//定义了默认长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//定义了最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//定义了加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//底层数组
transient Node<K,V>[] table;
//添加的元素数量
transient int size;
//用来表示数组扩容的边界值，门槛值 值为capacity*loadFactor
int trheshold;
//用来接收加装填因子
final float loadFactor;

【有前提】底层用哈希值算位置的时候与数组长度进行“与”运算。相当于求余。

5.3.1 经典面试题

（1）装填因子，负载因子，加载因子为什么是0.75？

装填因子设置为1：空间利用率得到了很大的满足，很容易碰撞，但是查询效率低。0.75是时间和空间进行折中的结果。

（2）主数组的长度为什么必须为2^n？

原因1：h&(length-1)等效求余的前提就是length必须是2的幂。

原因2：防止哈希冲突，位置冲突。

6 Collections工具类

import java.util.*;


public class javaCollection {
    public static void main(String[] args) {
        //Collections不支持创建对象，因为构造器私有化了
        //Collections cols = new Collections();
        //里面的属性和方法都是被static修饰，可以直接用类名.去调用即可
        //常用方法：
        //(1)addAll：
        ArrayList<String> list = new ArrayList<>();
        System.out.println(list);//[]
        Collections.addAll(list,"f","e","a","b","c","d");
        System.out.println(list);//[f, e, a, b, c, d]


        //(2)sort 可以传比较器
        Collections.sort(list);//[a, b, c, d, e, f]
        System.out.println(list);

        //(3)binarySearch 需要有序
        System.out.println(Collections.binarySearch(list,"c"));//2

        //(4)copy：替换方法
        ArrayList<String> list2 = new ArrayList<>();
        Collections.addAll(list2,"g","h","i");
        Collections.copy(list,list2);
        System.out.println(list);//[g, h, i, d, e, f]
        System.out.println(list2);//[g, h, i]

        //(5)fill
        Collections.fill(list2,"a");
        System.out.println(list2);//[a, a, a]
    }
}