1.1.6.ArrayList底层源码

从构造方法来入手。new ArrayList(22) 底层声明了一个Object类型的数组 名字elementData
  Object[] elementData

  public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) { //大于0
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { //等于初始化为一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else { //抛出一个异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

==========add("java01")======E理解为Object类型================  
   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 扩容  ensureCapacityInternal 扩容的函数
        elementData[size++] = e;  //把元素赋值给数组的相应位置
        return true;
    }
==========indexOf("java02") 判断元素在集合中第一次的位置=============
     public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i])) //和数组中的每个元素内容进行比对
                    return i;  //返回元素在集合中位置
        }
        return -1;
    }   

===========size() 请求数组的长度======================
 public int size() {
        return size;
    }   

============contain("java05")判断元素是否在集合中==============
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
===============get(1) 获取指定位置的元素========
   public E get(int index) {
        rangeCheck(index); //判断指定的位置是否合法 

        return elementData(index);
    }  

    E elementData(int index) {
        return (E) elementData[index];
    } 

============toString() 为什么不打印对象的引用地址 
    [java01, java02, java03, java02]因为重写了Object里面的toString方法。
    
 public String toString() {
        Iterator it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }   

通过对ArrayList方法的底层代码分析：底层就是对数组的操作。
ArrayList的底层就是基于数组实现的。

ArrayList是一个集合,底层维护的是数组结构,查询比较快,增删慢

 1.2.LinkedList集合

LinkedList 是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好。
LinkedList是一个集合,底层维护的是链表结构,增加和删除效率比较高（只需要改变链表的指向），它的查询效率慢（每次查询数据 从头查询或者从尾查询）

1.2.1.创建集合对象

LinkedList linkedlist = new LinkedList(); //没有默认长度

1.2.2.添加操作

linkedlist.add("java1");
linkedlist.add(11);
linkedlist.add(1.1);
linkedlist.add(true);

linkedlist.addFirst("java11"); //添加到头部
linkedlist.addLast("java11111"); //添加到尾部
System.out.println(linkedlist);

1.2.3.删除操作

//删除操作
linkedlist.remove(2); //删除指定位置的元素
linkedlist.removeFirst(); //删除头部元素
linkedlist.removeLast(); //删除尾部元素
System.out.println(linkedlist);

1.2.4.修改操作

//修改操作
linkedlist.set(1,"java11");//在下标为1的位置插入 java11
System.out.println(linkedlist);

1.2.5.查询操作

//查询操作
Object o = linkedlist.get(2); //根据下标获取指定位置的元素 

int size = linkedlist.size(); //获取集合长度

boolean empty = linkedlist.isEmepty();//判断集合是否为空

boolean b = linkedlist.contains("java1"); //判断元素是否在集合中存在

Object first = linkedlist.getFirst(); //获取第一个元素

Object last = linkedlist.getLast(); //获取最后一个元素
System.out.println(last);

1.2.6.LinkedList底层源码

1.凡是查询源码 ，我们都是从类的构造方法入手:
     /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
 该类的构造方法内是空的，没有任何的代码。 但是该类中有三个属性。   
    transient int size = 0; //索引
   
    transient Node first; //第一个元素对象 
   
    transient Node last; //表示最后一个元素对象。
 
================ add的源码=====E:理解为Object类型=================
   public boolean add(E e) {
        linkLast(e);
        return true;
    }

   void linkLast(E e) {
        final Node l = last;
        //上一个节点   数据  下一个节点
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    
==================Node的源码 内部类=======================  
   private static class Node { //泛型--object
        E item; //数据
        Node next; //下一个节点
        Node prev; //上一个节点

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
 

 1、==================== get(1)-----获取元素========================
   public E get(int index) {
        checkElementIndex(index); //检查index下标是否正确。
        return node(index).item;  //李四Node对象
    }
 ========================node(index)=============================
 Node node(int index) {
        //>> 位运算二进制运算 ----- size >> 1 一半的意思size/2
        if (index < (size >> 1)) { //前半部分
            Node x = first; 
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  //后半部分
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

分析：LinkedList查询效率低,因为它要一个节点一个节点的往后找.

ArrayList和LinkedList特点比较

ArrayList：

数据结构实现，查询快、增删慢

JDK1.2版本，运行效率快、线程不安全。

I. JDK8的ArrayList，实际初始长度是0
II. 首次添加元素时，需要实际分配数组空间，执行数组扩容操作
III. 真正向数组中插入数据，（Lazy懒）用的时候再创建，或再加载，有效的降低无用内存的占用

LinkedList：

I. 链表（链接列表）结构存储，查询慢、增删快。
————————————————
版权声明：本文为CSDN博主「S9264L」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/S9264L/article/details/104664580

2.Set集合

Set接口特点

• Set接口是无序(没有按数据的添加次序呈现)的

• Set接口中的数据不允许重复

• Set接口无法通过下标访问数据

• 查找慢，插入删除快(底层数据结构是哈希表和红黑树)

• Set集合使用equals()和hashCode()方法实现元素去重

2.1.HashSet集合

2.1.1.创建HashSet对象

//如果没有指定容器的大小,默认为16， 负载因子为0.75
HashSet hashSet = new HashSet();

HashSet hashSet = new HashSet(16); //初始容器的大小

//loadFactor:0.7f 表示负载因子 当空间使用70%时,要求扩容
HashSet hashSet = new HashSet(16,0.7f);

负载因子：好比饮水机有四桶水,目前用掉了三桶水(75%)的时候，就要给送水工打电话,让过来送水.

2.1.2.添加元素

//添加操作
hashSet.add("java1");
hashSet.add(true);
hashSet.add(null);
hashSet.add(12);
hashSet.add("java2");

HashSet hashSet2 = new HashSet(); //创建另一个hashSet2对象
hashSet.add("胡歌");
hashSet.add("周杰伦");
hashSet.add("彭于晏");

hashSet.addAll(hashSet2); //把hashSet2中的每个元素添加到hashSet中
System.out.println(hashSet); //元素不能重复 无序

运行结果: 

按照哈希表排序输出.

2.1.3.删除元素

//删除元素
hashSet.remove("彭于晏");

hashSet.clear();    //清空容器集合

System.out.println(hashSet);

2.1.4.查询元素

Set是无序的,所以不能get()获取元素,也不能set()修改元素.

//查询元素
boolean empty = hashSet.isEmpty();    //判断集合是否为空
System.out.println(empty);    

boolean b = hashSet.contains("刘德华");    //判断元素是否在集合中
System.out.println(b);

2.1.5.hashSet的遍历

(1)通过foreach遍历

//遍历    foreach
for(Object o : hashSet){
    System.out.println(o);
}

(2)通过迭代器来遍历

//迭代器遍历
Iterator iterator = hashSet.iterator();    //获取迭代器对象  有序(有下标)
while(iterator.hasNext()){    //判断指针是否能够移动
    Object next = iterator.next();    //指针移动并获取当前元素
    System.out.println(next);
}

迭代器（iterator）有时又称游标（cursor）是程序设计的软件设计模式，可在容器对象（container，例如链表或数组）上遍访的接口，设计人员无需关心容器对象的内存分配的实现细节。

HashSet类中没有提供根据集合索引获取索引对应的值的⽅法，

因此遍历HashSet时需要使⽤Iterator迭代器。Iterator的主要⽅法如下

2.1.6.hashSet的底层源码 

从构造函数说起:
    /**
     * Constructs a new, empty set; the backing HashMap instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
 在创建一个HashSet的对象时，底层创建的是HashMap。我们说hashset的底层原理时，我们就在后HashMap的原理就行。 讲HashMap时给大家说原理。

HashSet避免对象重复的规则:

1）如果对象的hashCode值不同，则不用判断equals方法，就直接存到HashSet中。

2）如果对象的hashCode值相同，需要用equals方法进行比较，如果结果为true，则视为相同元素，不存储。如果结果为false，视为不同元素，进行存储。

 注意：如果对象元素要存储到HashSet中，必须覆盖hashCode方法和equals方法。才能保证从对象中的内容的角度保证唯一。

 2.2.TreeSet集合

 TreeSet中的方法和HashSet中的方法一模一样 只是他们的实现不一样。
TreeSet 基于TreeMap 实现。TreeSet可以实现有序(按照自己的方式排序)集合，但是有序性需要通过比较器实现。

TreesSet特点:

• 有序  ：可以保证数据的逻辑次序(我们要自己提供排序规则)

• 不重复

• 添加、删除、判断元素存在性效率比较高

• 线程不安全

TreeSet对元素进行排序的方式:

1) 如果是基本数据类型和String类型，无需其它操作，可以直接进行排序。

2) 对象类型元素排序，需要实现Comparable接口，并覆盖其compareTo方法。

3) 自己定义实现了Comparator接口的排序类，并将其传给TreeSet，实现自定义的排序规则。

2.2.1.创建TreeSet集合

TreeSet treeSet = new TreeSet();

2.2.2.添加操作

 存储String类型.

TreeSet treeSet = new TreeSet();
treeSet.add("java1");
treeSet.add("java2");
treeSet.add("java5");
treeSet.add("java4");
treeSet.add("java3");

Sytem.out.println(treeSet):

存储一个对象类型:

TreeSet treeSet = new TreeSet();
treeSet.add(new Student("张三",15));
treeSet.add(new Student("李四",12));
treeSet.add(new Student("王五",14));

System.out.println(treeSet);

通过运行我们发现出现如下的错误:

 发现:TreeSet中的元素必须实现Comparable接口 方可放入TreeSet

解决方法有两个:

// TreeSet : 1.保证数据逻辑有序 2.不重复

// 实现有序的两种方式

// a. 自定义类型实现Comparable接口，实现里面的compareTo方法

// b. 自定义一个比较器对象实现Comparator接口，实现里面的commpare方法

第一个:让你的类实现Comparable接口

package com.qy151.test1;

import java.util.HashSet;
import java.util.TreeSet;

/**
 * @author : wzh
 * @date 2022/4/17 15:24:23
 */
public class Test1 {
    public static void main(String[] args) {
      
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Student("张三",15));
        treeSet.add(new Student("李四",12));
        treeSet.add(new Student("王五",14));

        System.out.println(treeSet);
    }
}
//学生类
class Student implements Comparable{
    private String name;
    private int age;

    public Student(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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    //排序：---返回如果大于0 表示当前元素比o大  如果返回-1 当前添加的元素比o小  返回0表示相同元素。
    @Override
    public int compareTo(Object o) {    //传参
        if(o instanceof Student){     //判断要比较的目标类型和当前类型是否一致
             return -1;
        }
        //把Object类型转为Student类型
        Student student= (Student) o;
        System.out.println(this+"===================>"+o);
        //如果当前数据的年龄大于参数年龄-->返回1,往后排
        if(this.age>student.age){    
            return 1;
        }
        //如果当前数据的年龄小鱼参数年龄-->返回-1,往前排
        if(this.age返回0 重复不录入
        return 0;
    }
}

第二种: 在创建TreeSet时指定排序的对象。  

我们之前 创建过TreeSet对象。
  TreeSet treeSet=new TreeSet(); 但是在创建对象时 并没有为其指定排序得规则，那么就要求该集合得元素有排序规则。 如果元素得类已经创建完成，不能修改该类得源码，这时我们又想把该类得对象放入得TreeSet容器中。 这时就需要你在创建TreeSet时指定排序得规则。

public static void main(String[] args) {
        //Comparator comparator
        // 在TreeSet构造中，传入自己定义的比较器
        TreeSet treeSet = new TreeSet(new MyComparator());  //为TreeSet容器指定了排序规则
        treeSet.add(new Student("张三",15));
        treeSet.add(new Student("李四",15));
        treeSet.add(new Student("王五",16));
        treeSet.add(new Student("赵六",17));
        System.out.println(treeSet);

        //遍历
        for(Object o : treeSet){
            System.out.println(o);
        }

        Iterator iterator = treeSet.iterator();//获取迭代器对象
        while(iterator.hasNext()){  //判断指针能否移动
            Object next = iterator.next();  //获取元素并移动指针
            System.out.println(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 +
                '}';
    }

    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;
    }
}

//自定义排序类实现Comparator接口进行排序

public class MyComparator implements Comparator {   //需要实现Comparator的抽象方法
    @Override
    public int compare(Object o1, Object o2) {
        //先判断两个要比较的数据是否是相同类型的
        if((o1 instanceof Student)&&(o2 instanceof  Student)) {
            Student student1 = (Student) o1;
            Student student2 = (Student) o2;
            if (student1.getAge() > student2.getAge()) {
                return 1;
            } else if (student1.getAge() < student2.getAge()) {
                return -1;
            } else {
                return student1.getName().compareTo(student2.getName());
            }
        }else{
            return -1;
        }
    }
}

3.Map接口 属于键值对模式

Map接口特点:

• 以键值对方式存储数据（Collection是单值集合）

• 键不能重复，键重复时，后面的数据会覆盖前面的数据

• 可以存储null

• 键值对数据无序

 3.1.HashMap实现类

map中得每个元素属于键值对模式。 如果往map中添加元素时 需要添加key 和 value. 它也属于一个接口，该接口常见得实现类有: HashMap.

HashMap实现了Map接口，拥有Map接口的基本特点。HashMap线程不安全，效率高。HashMap的底层是由哈希表、链表加红黑树构成的。

3.1.1.创建Map对象

//默认初始化大小为16,负载因子为0.75
Map map = new HashMap();
//初始化大小
Map map = new HashMap(15);
//初始化大小   负载因子
Map map = new HashMap(20,0.7f);

3.1.2.添加操作

//添加操作 key : name  value : 张三
map.put("name","张三");    //注意:要求map的key必须唯一
map.put("age",15);
map.put("name1","李四");//因为key不能重复,所以后者会把前者覆盖

Map map1 = new HashMap();
map1.put("name2","王五");
map1.put("age",14);
map.putAll(map1);    //把map1的每个元素添加到map中

map.putIfAbsent("age",25);    //如果指定的key存在,则不放入map中,如果不存在则存入

System.out.println(map);

3.1.3.删除操作

map.remove("age");    //根据指定的key移除元素
map.clear();    //清空map中的元素
System.out.println(map);

3.1.4.修改操作

map.replace("name","孙七");    //替换元素
System.out.println(map);

3.1.5.查询操作

boolean f = map.containsKey("name");    //判断map中是否存在指定的key

Object o = map.get("name");    //根据指定的key获取对应的value值

Set keys = map.keySet();    //返回map中的所有key
System.our.println(keys);

//遍历map

for(Object o : keys){
    Object value = map.get(o);
    System.out.println(k+" : "+value);
}

3.1.6.HashMap底层原理

JDK1.7和JDK1.8它们是有区别的：

        JDK1.7使用的数据结构:      数组+链表    而且链表插入模式为   头部插入(造成死循环)

        JDK1.8使用的数据结构:     数组+链表+红黑树     而且链表的插入模式是  尾部插入

从构造函数入口:
  /**
     * Constructs an empty HashMap with the default initial capacity
     * (16) and the default load factor (0.75).
     */
   public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

HashMap的put()和get()的实现

1) map.put(key,value)实现原理

第一步：首先将k,v封装到Node对象当中（节点）。

第二步：它的底层会调用K的hashCode()方法得出hash值。

第三步：通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equals。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

2) map.get(key) 实现原理

第一步：先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。

第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

总结

JDK1.8 HashMap原理

HashMap的原理,存储元素使用的put(key,value),根据key的hash计算出相应的哈希值,根据相应的算法求出该元素在数组中的位置,如果求出的哈希值相同,则成为哈希冲突(哈希碰撞),会根据equals来判断元素是否一致,如果equals不同,则存入单向链表上，如果哈希碰撞的个数超过8个,则把链表转换为红黑二叉树.

JDK1.7和JDK1.8它们是有区别的：

        JDK1.7使用的数据结构:      数组+链表    而且链表插入模式为   头部插入(造成死循环)

        JDK1.8使用的数据结构:     数组+链表+红黑树     而且链表的插入模式是  尾部插入

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                 //如果key得hash值相同，判断key得equals是否相同，替换原来得元素
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 判断链表得长度是否超过8个
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 把链表转换为红黑树结构
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

完结！！！！