集合体系图

集合主要是两组(单列集合，双列集合)

Collection接口有两个重要的子接口 List Set，他们的实现子类都是单列集合

Map接口的实现子类是双列集合，存放的K-V

集合相关介绍 Collection

1.Collection接口实现类的特点

public interface Collection<E> extends Iterable<E>

1)collection实现子类可以存放多个元素，每个元素可以是Object

2)有些Collection的实现类，可以存放重复的元素，有些不可以

3)有些Collection的实现类，有些是有序的(List)，有些不是有序(Set)

4)Collection接口没有直接的实现子类，是通过它的子接口Set和 List来实现的

2.简单方法

Collection接口常用方法,以实现子类ArrayList来演示. CollectionMethod.java

1) add:添加单个元素

2) remove:删除指定元素

3) contains:查找元素是否存在.

4) size:获取元素个数

5) isEmpty:判断是否为空

6) clear:清空

7) addAll:添加多个元素

8) containsAll:查找多个元素是否都存在

9) removeAll:删除多个元素

package com.scy.collection;

import java.util.ArrayList;

public class CollectionMethod {
    public static void main(String[] args) {
        //add添加元素
        ArrayList arrayList = new ArrayList();
        arrayList.add("jack");
        arrayList.add(10);
        arrayList.add(true);
        System.out.println(arrayList);

        //remove 删除指定元素
        //arrayList.remove(0);//删除第一个元素
        arrayList.remove(true);//删除指定元素
        System.out.println(arrayList);

        //contains 查找指定元素是否存在
        System.out.println(arrayList.contains("jacks"));

        //size 返回元素个数
        System.out.println(arrayList.size());

        //isEmpty 判断是否为空
        System.out.println(arrayList.isEmpty());

        //clear 清空
        arrayList.clear();
        System.out.println(arrayList);

        //addAll 添加多个元素
        ArrayList arrayList1 = new ArrayList();
        arrayList1.add("三国演义");
        arrayList1.add("水浒传");
        arrayList.addAll(arrayList1);
        System.out.println(arrayList);

        //contains 查询多个元素
        System.out.println(arrayList.containsAll(arrayList1));

        //removeAll 删除多个元素
        arrayList.add("聊斋");
        arrayList.removeAll(arrayList1);
        System.out.println(arrayList);



    }


}

3.遍历集合

1.Collection接口遍历元素方式1-使用lterator(迭代器)

1.简单介绍

1) Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。

2)所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了lterator接口的对象,即可以返回一个迭代器。

3) Iterator的结构.[看一张图]

4) Iterator仅用于遍历集合，Iterator本身并不存放对象。

2.执行原理

提示：在调用iterator.next()方法之前必须要调用iterator.hasNext()·进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。

lterator iterator = coll.iterator();   //得到一个集合的迭代器

//hasNext():判断是否还有下一个元素
//next()    作用:1.下移 2.将下移以后集合位置上的元素返回

while(iterator.hasNext()){
//Object next = iterator.next();
System.out.println(iterator.next());
}

2.Collection接口遍历对象方式2-for循环增强

增强for循环，可以代替iterator迭代器，特点:增强for就是简化版的iterator,本质一样。只能用于遍历集合或数组。

基本语法

for(元素类型元素名:集合名或数组名){

访问元素

}

Tips: 1.使用增强for，在Collection遍历集合

2.增强for，底层仍是迭代器

3.for可以理解是简化版本的迭代器遍历

4.快捷方法iter

for(Object book : col){
    System.out.println("book = " + book);
}

List

1.List简介

List 接口是Collection 接口的子接口

1)List集合类中元素有序(即添加顺序和取出顺序一致)、且可重复[案例]

2) List集合中的每个元素都有其对应的顺序索引，即支持索引。

3)List容器中的元素都对应一个整数型的序号记载其在容器中的位置,可以根据序号存取容器中的元素。

4) JDK API中List接口的实现类有:jdk文档

常用的有:ArrayList、LinkedList和Vector。

2.方法介绍

public static void main(String[] args) {
        List<Object> list = new ArrayList<>();
        list.add("贾宝玉");
        list.add("薛宝钗");
        System.out.println(list);

        //void add(int index, Object ele):在index位置插入ele元素
        list.add(1, "scy");
        System.out.println(list);

        //boolean addAll(int index, Collection eles)从index位置开始吧所有的元素加进来
        List list1 = new ArrayList();
        list1.add("jack");
        list1.add("tom");
        list1.add("贾宝玉");
        list.addAll(0, list1);
        System.out.println(list);

        //Object get(int index) 获取指定位置出现的元素
        System.out.println(list.get(0));

        //int indexOf(Object obj) 返回obj在集合中首次出现的位置
        System.out.println(list);
        System.out.println(list.indexOf("贾宝玉"));

        //Object remove(int index) 删除指定index位置的元素，并返回此元素
        System.out.println(list.remove(1));


        //Object set(int index, Object ele)//设置指定index位置的元素为ele，相当于替换
        list.set(1, "scy");
        System.out.println(list);

        //List subList(int formIndex, int toIndex)//返回从fromIndex到toIndex位置的子集合
        List list2 = new ArrayList();
        //返回的是[0,2)
        list2 = list.subList(0, 2);
        System.out.println(list2);
    }

3.三种遍历方式

iterator, 增强for, 普通for

   @Test
    public void test(){
        List list = new LinkedList();
        list.add("tom");
        list.add("jack");
        list.add("smith");
        list.add("vennasa");
        list.add("kristina");
    
        //遍历
        
        //1. 迭代器
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //增强for
        for (Object o : list) {
            System.out.println(o);
        }

        //普通for循环
        for(int i = 0; i < list.size(); i++){
            Object object = list.get(i);
            System.out.println(object);
        }
    }

ArrayList

1.简介

1)permits all elements, including null ,ArrayList可以加入null,并且多个

2)ArrayList是由数组来实现数据存储的

3)ArrayList 基本等同于Vector，除了ArrayList是线程不安全(执行效率高)看源码.,·在多线程情况下，不建议使用ArrayList

2.底层源码分析

tips:不能点源码，把setting里面的Debugger->Stepping->Do not step into the classes勾选去掉

1) ArrayList中维护了一个Object类型的数组elementData.transient Object[] elementData; //transient表示瞬同,短者的,表示该属性不会被序列化

2)当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍。

3)如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容,则直接扩容elementData为1.5倍。

 @Test
    public void test(){
        ArrayList list = new ArrayList();
        for(int i = 1; i <= 10; i++){
            list.add(i);
        }

        for(int i = 11; i <= 15; i++){
            list.add(i);
        }

        list.add(200);
        list.add(300);
    }

Debug 分析使用无参构造器，创建和使用ArrayList的源码

无参的演示，有参类似

第一步


创建了一个空的elementData数组={}

第二步 执行list.add

(1)先确定是否要扩容

(2)然后在执行赋值

第三步 该方法确定minCapacity DEFAULT_CAPACITY

(1)第一次扩容为10

第四步

(1) modCount++记录集合被修改的次数

(2)如果elementData的大小不够,就调用grow()去扩容

elementData.length指的是当前容量，比较的是：如果当前容量小于grow里面的容量，就扩容

第五步

(1)真的扩容

(2)使用扩容机制来确定要扩容到多大

(3)第一次newCapacity =10

(4)第二次及其以后，按照1.5倍扩容

(5)扩容使用的是Arrays.copyof()，优点是不会影响原来的数组

第六步

之后就不断返回，在add方法中，以数组的形式完成赋值

想看到debug的所有数据，把下面的勾选去掉

有参展示一段

Vector

1.简介

1) Vector类的定义说明

public class vector<E>extends AbstractList<E>implements List<E>，RandomAccess，cloneable，Serializable

2) Vector底层也是一个对象数组,protected Object[] elementData;

3) Vector是线程同步的，即线程安全, Vector类的操作方法带有synchronized

public synchronized E get(int index) {

if (index >= elementCount)

throw new ArraylndexOutOfBoundsException(index);return elementData(index);}

4)在开发中，需要线程同步安全时，考虑使用Vector

2.源码解读

 @Test
    public void test1() {
        Vector vector = new Vector();
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
    }

无参构造

第一步 默认10

第二步 如上

第三步  是否扩容

第四步 扩容

capacityIncrement:自定义扩容大小，不会…

有参构造

LinkedList

1.简介

1) LinkedList底层实现了双向链表和双端队列特点

2)可以添加任意元素(元素可以重复)，包括null

3)线程不安全，没有实现同步

2.底层操作机制

1)LinkedList底层维护了一个双向链表

2) LinkedList中维护了两个属性first和last分别指向首节点和尾节点

3)每个节点(Node对象)，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表.

4)所以LinkedList的元素的添加和删除,不是通过数组完成的,相对来说效率较高。

3.LinkedList源码解读

 public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
    }

第一步 空的LinkedList

1.LinkedList linkedList = new LinkedList();

public LinkedList() 0

2．这时linkeList的属性first = null last = null

第二步

第三步 将新的结点，加入到双向链表的最后

List集合选择

如何选择ArrayList和LinkedList:

1)如果我们改查的操作多，选择ArrayList

2)如果我们增删的操作多，选择LinkedList

3)一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList

4)在一个项目中，根据业务灵活选择，也可能这样，一个摸块使用的是ArrayList,另外一个模块是LinkedList.

5)线程不安全

Set简介

1.简单介绍

1)无序(添加和取出的顺序不一致)，没有索引

2)不允许重复元素，所以最多包含一个null

Set接口的常用方法：

和List接口一样,Set接口也是Collection的子接口，因此,常用方法和Collection接口一样

Set接口的遍历方式：同Collection的遍历方式一样,因为Set接口是Collection接口的子接口。

1.可以使用迭代器

2.增强for

3.不能使用索引的方式来获取.

遍历简介

public class set {
    public static void main(String[] args) {
    //1．以Set接口的实现类 HashSet来讲解Set接口的方法
    //2. set接口的实现类的对象(Set接口对象)，不能存放重复的元素，可以添加一个null
    //3. set接口对象存放数据是无序(即添加的顺序和取出的顺序不一致)
    //4．注意:取出的顺序的顺序虽然不是添加的顺序，但是他的固定。
        Set set = new HashSet();
        set.add("join");
        set.add("lucy");
        set.add(null);
        set.add("mary");
        set.add("scy");
        set.add("join");
        set.add(null);
        System.out.println(set);

        //1.遍历方式1：迭代器
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //2.增强for
        for (Object o : set) {
            System.out.println(o);
        }

        //set接口不能通过索引获取
    }
}

HashSet

1.HashSet简单介绍

1)HashSet实现了Set接口

2) HashSet实际上是HashMap，看下源码.(图)

3)可以存放null值，但是只能有一个null

4) HashSet不保证元素是有序的,取决于hash后，再确定索引的结果.(即，不保证存放元素的顺序和取出顺序一致)

5)不能有重复元素/对象.在前面Set 接口使用已经讲过

2.基本说明

 Set set1 = new HashSet<Object>();
        System.out.println(set1);

        set1.add("lucy"); //可以添加
        set1.add("lucy"); //添加失败
        set1.add(new Dog("jack")); //ok
        set1.add(new Dog("jack")); //ok
        System.out.println(set1);

        //看源码，add到底发生了什么
        set1.add(new String("scy"));//可以
        set1.add(new String("scy"));//添加失败
        System.out.println(set1);

3.扩容机制

1.HashSet底层是HashMap

2.添加一个元素时，先得到hash值-会转成->索引值

3.找到存储数据表table,看这个索引位置是否已经存放的有元素

4.如果没有，直接加入

5.如果有，调用equals 比较，如果相同，就放弃添加,如果不相同，则添加到最后

6.在Java8中,如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)

4.源码解读

public class HashSetSource {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");

        System.out.println(hashSet);
    }
}

第一步

第二步

第三步

(static) PRESENT = new 0bject();

value = PRESENT

番外hash 该方法会执行hash(key）得到key对应的hash值算法h = key. hashCode()) ^ (h >>> 16)

第四步 关键代码

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table就是 HashMap的一个数组，类型是 Node[]
        //if 语句表示如果当前table 是null，或者大小=0
        //就是第一次扩容，到16个空间。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
        //并把这个位置的对象，赋给p
        //(2)判断p 是否为null
        //(2.1)如果p 为null，表示还没有存放元素，就创建一个Node (key="java",value=PRESENT)
        //(2.2）就放在该位置tab[i] = newNode(hash,key, value, null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //并且满足下面两个条件之一:
            //(1)准备加入的key 和p指向的Node结点的key 是同一个对象
            //(2) p指向的Node 结点的 key 的equals()和准备加入的key比较后相同
            //就不能加入
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判断p是不是一颗红黑树
            //如果是一颗红黑树，就调用putTreeVal ,来进行添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //如果table对应索引位置，已经是一个链表，就使用for循环比较
            //(1)依次和该链表的每一个元素比较后，都不相同，则加入到该链表的最后
            //注意在把元素添加到链表后，立即判断该链表是香已经达到8个结点
            //就调用treeifyBin() 对当前这个链表进行树化(转成红黑树)
            //if (tab == null ll (n = tab.length)< MIN_TREEIFY_CAPACITY(64)) resize();
            //如果上面条件成立，先table扩容。
            //只有上面条件不成立时，才进行转成红黑树
            //(2）依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
    }

必须重写hashCode和equals，因为hashCode是判断你再哪个链表下，equals判断两个对象是否相等，少一个都不行

LinkedHashSet

1.简介

1) LinkedHashSet是 HashSet的子类

2) LinkedHashSet底层是一个 LinkedHashMap，底层维护了一个数组+双向链表

3) LinkedHashSet根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序这使得元素看起来是以插入顺序保存的.

4) LinkedHashSet 不允许添重复元素

2.源码分析

  public static void main(String[] args) {
        Set set = new LinkedHashSet();
        set.add(new String ("Aa"));
        set.add(123);
        set.add(123);
        set.add("jsp");
        //1. LinkedHashSet加入顺序和取出元素数据的顺序一致
        //2. LinkedHashSet底层维护的是一个LinkedHashMap(是HashMap的子类)
        //3. LinkedHashSet底层结构〔数组table+双向链表)
        //4．添加第一次时，直接将 数组table扩容到16，存放的结点类型是 LinkedHashHap$Entry
        //5．数组是 HashMap$Node[]存放的元素/数据是 LinkedHashMap$Entry类型
    }