集合专题——单列集合

作者: 攻城老狮 | 来源:发表于2021-05-25 22:04 被阅读0次

集合专题——单列集合
集合总结
Java基础之常用集合
集合
java——集合
单列集合
Java集合
2-JAVA类的Collection集合
ArrayList|LinkList|栈和队列
Java基础之Collection集合

1 集合框架体系

单列集合

image-20210511092441523.png

双列集合

image-20210508143632963.png

2 Collection接口

2.1 Collection的常用方法测试

public class CollectionBaseMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection collection = new ArrayList();
        //1.add 添加单个元素
        collection.add("yorick");
        collection.add(10);
        collection.add(true);
        System.out.println("collection:"+collection);
        //2.remove 删除指定元素
        collection.remove(10);
        System.out.println("collection:"+collection);
        //3.contains 查找元素是否存在
        Sys tem.out.println(collection.contains("yorick"));
        //4.size 获取元素个数
        System.out.println(collection.size());
        //5.isEmpty 判断是否为空
        System.out.println(collection.isEmpty());
        //6.clear 清空
        collection.clear();
        System.out.println(collection.size());
        //7.addAll 添加多个元素
        Collection other = new ArrayList();
        other.add("tom");
        other.add("jerry");
        collection.addAll(other);
        System.out.println("collection:"+collection);
        //8.containsAll 查找多个元素是否存在
        System.out.println(collection.containsAll(other));
        //9.removeAll 删除多个元素
        collection.add("smith");
        collection.removeAll(other);
        System.out.println(collection.size());
    }
}

result

collection:[yorick, 10, true]
collection:[yorick, true]
true
2
false
0
collection:[tom, jerry]
true
1

2.2 Collection的遍历方法测试

使用迭代器遍历，并演示迭代器的使用方法

public class CollectionIterator {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection collection = new ArrayList();
        collection.add("yorick");
        collection.add("tom");
        collection.add("jerry");
        System.out.println("collection:"+collection);

        //1.得到collection对应的Iterator迭代器对象
        Iterator it = collection.iterator();
        //2.使用while循环遍历 快捷键 itit 显示所有快捷键 ctrl+j
        while(it.hasNext()){
            Object obj = it.next();
            System.out.println(obj);
        }
        //3.当while循环退出时候，it迭代器指向最后一个元素
        //it.next(); //NoSuchElementException
        //4.重置迭代器
        System.out.println("============");
        it = collection.iterator();
        //再遍历
        while (it.hasNext()) {
            Object obj = it.next();
            System.out.println(obj);
        }
    }
}

result:

collection:[yorick, tom, jerry]
yorick
tom
jerry
============
yorick
tom
jerry

使用增强for循环遍历

public class CollectionFor {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection collection = new ArrayList();
        collection.add("yorick");
        collection.add("tom");
        collection.add("jerry");
        System.out.println("collection:"+collection);
        //使用增强for循环遍历集合，底层仍然是迭代器(语法糖)
        for (Object obj : collection) {
            System.out.println(obj);
        }
    }
}

result:

collection:[yorick, tom, jerry]
yorick
tom
jerry

3 List接口

List集合类中元素有序（添加顺序和取出顺序一致），且可重复
List集合中每个元素都有对应的顺序索引，支持索引存取

3.1 List的常用方法测试

public class ListMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("tom");
        list.add("jerry");
        System.out.println("list:"+list);
        //1.add 在index位置插入ele元素
        list.add(1,"yorick");
        System.out.println("list:"+list);
        //2.addAll 从index位置开始将eles中所有元素插入
        List tempList = new ArrayList();
        tempList.add("tmp1");
        tempList.add("tmp2");
        list.addAll(1,tempList);
        System.out.println("list:"+list);
        //3.get 获取指定index位置的元素
        System.out.println(list.get(1));
        //4.indexOf 返回obj在集合首次出现的位置
        System.out.println(list.indexOf("yorick"));
        //5.lastIndexOf 返回obj在集合中末次出现的位置
        list.add("yorick");
        System.out.println(list.lastIndexOf("yorick"));
        //6.remove 移除指定index位置的元素
        list.remove(1);
        System.out.println("list:"+list);
        //7.set 设置指定index位置的元素为ele，替换
        list.set(0,"newele");
        System.out.println("list:"+list);
        //8.subList 从fromIndex 到toIndex位置的子集合
        // fromIndex <= xxx < toIndex
        List subList = list.subList(0, 2);
        System.out.println("subList:"+subList);
    }
}

result

list:[tom, jerry]
list:[tom, yorick, jerry]
list:[tom, tmp1, tmp2, yorick, jerry]
tmp1
3
5
list:[tom, tmp2, yorick, jerry, yorick]
list:[newele, tmp2, yorick, jerry, yorick]
subList:[newele, tmp2]

3.2 List的三种遍历方式

注：ArrayList，LinkedList，Vector均适用

public class ListFor {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        for (int i = 0; i < 5; i++) {
            list.add("yorick"+i);
        }

        //1.使用迭代器遍历
        System.out.println("===迭代器===");
        Iterator it = list.iterator();
        while (it.hasNext()) {
            Object obj = it.next();
            System.out.println(obj);
        }
        //2.使用增强for循环
        System.out.println("===增强for循环===");
        for (Object obj : list) {
            System.out.println(obj);
        }
        //3.普通for循环
        System.out.println("===普通for循环===");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

result

===迭代器===
yorick0
yorick1
yorick2
yorick3
yorick4
===增强for循环===
yorick0
yorick1
yorick2
yorick3
yorick4
===普通for循环===
yorick0
yorick1
yorick2
yorick3
yorick4

4 ArrayList

4.1 ArrayList特征

ArrayList允许添加全部类型的元素，包括null，并且可以添加多个
ArrayList底层是由数组实现的
ArrayList是线程不安全的（执行效率高），多线程情况下不建议使用ArrayList

4.2 ArrayList 相关机制

ArrayList中维护了一个Object类型的数组 elementData，transient Object[] elementData；（transient 表示瞬间的，该属性不会被序列化）
创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData容量的1.5倍
如果使用的是指定大小的构造器，初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData容量的1.5倍

4.3 ArrayList 源码分析

4.3.1 初始idea设置

去掉idea中对debug的阉割，可以查看全部的debug数据，并且可以看到null元素

image-20210508205239442.png

去掉idea对某些class直接跳过的限制

image-20210508204522229.png

4.3.2 ArrayList分析流程

编写测试程序

public class ArrayListSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        for (int i = 1; i <= 10; i++) {
            arrayList.add(i);
        }
        for (int i = 11; i <= 15; i++) {
            arrayList.add(i);
        }
        arrayList.add(233);
    }
}

构造方法

无参构造方法

//调用无参构造方法，默认将空的Object数组赋值给elementData
//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造方法

////调用有参构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { //直接开辟指定大小的Object数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { //和无参构造函数一致
        this.elementData = EMPTY_ELEMENTDATA;
    } else { //抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

进入add方法

//进入add方法后，在添加数据到数组之前，需要先判断是否需要扩容
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 检测增加1个元素后，是否需要扩容
    elementData[size++] = e;
    return true;
}

进入ensureCapacityInternal方法

//不干什么事情，先调用calculateCapacity获取当前最小需要的容量，再调用ensureExplicitCapacity实施扩容检测
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

进入calculateCapacity方法

//判断elementData是否是空数组，若是空数组则得到最小的容量为10，若不是空数组则直接返回需要扩容的最小容量值
//private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

进入ensureExplicitCapacity方法

//确认是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //记录修改次数，用于判断是否多线程出现问题

    // overflow-conscious code
    if (minCapacity - elementData.length > 0) //当需要的最小容量比当前数组的容量高的时候，进行grow扩容
        grow(minCapacity);
}

进入grow方法

//扩容方法，实现最终的数组扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //保存久的数组大小
    int newCapacity = oldCapacity + (oldCapacity >> 1); //使用右移的方法，扩容1.5倍
    if (newCapacity - minCapacity < 0) //若是无参构造第一次扩容，进入，赋值为10
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) //超过最大值
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); //按容量的需求，数组拷贝
}

查看扩容结果，从结果可以发现经过两次扩容后，集合数组大小变为22，符合预期

image-20210510100005019.png

5 Vector

5.1 Vector相关机制

Vector底层也是一个对象数组

protected Object[] elementData;

Vector是线程同步的，即线程安全，这是由于Vector的方法上面带有 synchronized 关键字

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

开发中，需要保证线程同步安全时候，考虑使用Vector
Vector若是无参构造，默认10的大小，满后按照2倍扩容。如果指定大小，则每次直接按2倍扩容。

5.2 Vector源码分析

编写测试程序

public class VectorSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Vector vector = new Vector();
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
        vector.add(233);
    }
}

debug，进入Vector的默认构造方法

//进入默认构造方法后，发现其调用了自身1个参数的构造重载方法，并传入了写死的值10，表示初始化数组的容量大小
public Vector() {
    this(10);
}

进入Vector的1个参数的构造方法

//发现1个参数的构造方法，实际上调用了两个参数的构造方法，除了传入之前的10大小的容量外，还传入了0，表示默认用户没有填写当数组满的时候，需要扩容的大小
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

进入Vector的2个参数的构造方法

//第一个参数表示初始化容量大小，第二个参数表示数组满后扩容的大小，若为0表示按照默认的2倍扩容
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0) //抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity]; //创建了指定容量的Object类型数组
    this.capacityIncrement = capacityIncrement; //指定扩容大小
}

出了构造函数，进入Vector的add方法，查看源码

//add方法上有synchronized 关键字说明有加锁机制保证线程安全。添加元素方式，首先会判断是否需要扩容，之后将元素添加至Object数组
public synchronized boolean add(E e) {
    modCount++; //记录修改次数
    ensureCapacityHelper(elementCount + 1); //确认容量是否满足要求
    elementData[elementCount++] = e; //添加元素
    return true;
}

进入ensureCapacityHelper方法

//该方法查看一下需要的最小容量是否已经比当前的数组容量还要高，若无法满足容量要求则进入grow实现扩容，若满足容量要求则返回
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); //扩容
}

进入grow方法

//实现对数组的扩容，首先查看用户是否定义了capacityIncrement的值，若定义了按照用户的要求进行扩容，若没有定义默认为0，则按照2倍的大小扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity); //2倍扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); //复制数组
}

查看扩容结果，从结果可以发现经过扩容后，集合数组大小变为20，为原来的2倍，符合预期

image-20210510103151731.png

6 LinkedList

6.1 LinkedList相关机制

LinkedList实现了双向链表和双端队列的特点
可以添加任意元素，可重复可为null
线程不安全，没有实现同步机制

6.2 LinkedList源码分析

编写测试程序

public class LinkedListSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        System.out.println("linkedList:"+linkedList);
    }
}

进入LinkedList的默认构造函数

//空构造函数，什么都没做
public LinkedList() {
}

进入LinkedList的add方法

//实际上调用linkLast方法，实现对元素的尾插操作
public boolean add(E e) {
    linkLast(e);
    return true;
}

进入linkLast方法

//实现将元素尾插至双向链表中，其中last记录尾部元素，first记录头部元素
void linkLast(E e) {
    final Node<E> l = last; //获取尾部结点
    final Node<E> newNode = new Node<>(l, e, null); //生成新结点，（prev指向插入前的尾结点，last指向null表示该新元素在最后）
    last = newNode; //更新当前的尾部结点为新结点
    if (l == null) //添加的第一个结点，让first指向它
        first = newNode;
    else //让倒数第二个结点的next指向新结点
        l.next = newNode;
    size++; //元素个数+1
    modCount++; //修改次数+1
}

7 Set接口

7.1 Set相关特征

Set中的元素是无序的（添加和取出的顺序不一致），没有索引
不允许存在重复的元素，所以最多包含一个null
注：虽然取出的顺序和添加的顺序不一致，但是取出的顺序是固定的，不会改变

7.2 Set的添加，删除，遍历方法

public class SetBaseMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add("yorick");
        set.add("tom");
        set.add("yorick");
        set.add(null);
        set.add("jerry");
        set.add(null);
        System.out.println("set:"+set);

        set.remove("tom");
        System.out.println("set:"+set);

        System.out.println("===使用迭代器遍历===");
        Iterator it = set.iterator();
        while(it.hasNext()){
            Object obj = it.next();
            System.out.println(obj);
        }

        System.out.println("===使用增强for循环遍历===");
        for (Object obj : set) {
            System.out.println(obj);
        }
    }
}

result

set:[null, tom, jerry, yorick]
set:[null, jerry, yorick]
===使用迭代器遍历===
null
jerry
yorick
===使用增强for循环遍历===
null
jerry
yorick

8 HashSet

8.1 HashSet相关特征

HashSet底层实际上是HashMap

public HashSet() {
    map = new HashMap<>();
}

可以存放null值，但是只能有一个null
满足Set的所有特征

8.2 HashSet底层机制

执行添加的流程

HashSet底层是HashMap
添加元素时，先得到hash值，之后转化为索引值
找到存储数据表table，看这个索引位置是否已经存放元素
- 如果没有，直接加入
- 如果有，调用equals方法比较，如果相同就放弃添加，如果不同则添加到最后
在Java8中，如果一条链表的元素个数超过8（TREEIFY_THRESHOLD），并且table的大小超过64（MIN_TREEIFY_CAPACITY）就会进行树化（红黑树）

扩容转红黑树机制

HashSet底层是HashMap，第一次添加时，table会扩容至16，临界值（threshold）是 16*加载因子0.75，为12
如果table数组使用到了临界值12，就会扩容到16*2，为32的容量，并且计算新的临界值为32 * 0.75 为24，以此类推
在Java8中，如果一条链表的元素个数超过8（TREEIFY_THRESHOLD），并且table的大小超过64（MIN_TREEIFY_CAPACITY）就会进行树化（红黑树）。否则仍然采用数组扩容机制
元素只要加入，size++，与加入到数组第一个位置，还是挂载到链表上无关

8.3 HashSet源码分析

编写测试程序

public class HashSetSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("yorick");
        hashSet.add("tom");
        hashSet.add("yorick");
        System.out.println("HashSet:"+hashSet);
    }
}

进入HashSet的构造方法

//HashSet的底层可以发现是HashMap
public HashSet() {
    map = new HashMap<>();
}

进入add方法

//add方法实际上是向map中存放了一组键值对，其中键为添加的元素，而值使用默认的Object对象，作为占位的作用
//private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null; //添加成功返回null，失败返回已经存在的数值
}

进入put方法

//实际调用putval方法，首先获取键的hash值，然后和键值对一起作为参数传入
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

进入hash方法

//通过调用对象的hashCode方法获取哈希值，并对该hash值进行算法运算得到最终的hash返回
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

进入putVal方法，重点

//实现最终的向数值+链表的结构中添加元素的方法
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是否是空，是空说明是第一次添加元素，需要对table进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果当前计算的table数值下标位置没有元素，则创建新结点并放在该位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //当前计算的下标位置有元素
    else {
        Node<K,V> e; K k;
        //判断第一个头元素，如果hash值一样，并且equals判断相同，说明是相同元素，无法添加
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果是树节点，按照树的方式插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //按链表的方式插入
        else {
            //死循环，遍历该链表
            for (int binCount = 0; ; ++binCount) {
                //如果当前节点的下一个位置为null，则将该元素直接挂载
                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;
                }
                //判断下一个位置元素的hash值和equals的值，若为相同元素则退出，不同则将下一个元素的引用给p，继续遍历链表的剩余元素
                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; //若key相同，则替换value值
            afterNodeAccess(e);
            //返回该值，说明添加失败
            return oldValue;
        }
    }
    //修改次数+1
    ++modCount;
    //如果当前元素个数超过了临界值，则对数值进行扩容操作
    if (++size > threshold)
        resize();
    //为继承HashMap的子类提供的接口，用于实现子类的特有方法
    afterNodeInsertion(evict);
    //添加成功，返回null
    return null;
}

进入resize方法

//resize方法实现对table的扩容操作
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //获取原始的数值容量，初次为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //获取原始的数值临界值，初次为0
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //初次扩容，使用其默认的初始值
    //static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 默认初始容量16
    //static final float DEFAULT_LOAD_FACTOR = 0.75f; 默认加载因子0.75
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //创建一个容量为newCap的新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //将新数组给到table
    table = newTab;
    //如果原始table有元素，需要遍历获取到每个元素，然后加入到新数组中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //让元素数值中的对象为null GC回收
                oldTab[j] = null;
                //如果只有一个头部元素，后面链表没有元素
                if (e.next == null)
                    //重新计算加入到table的索引位置
                    newTab[e.hash & (newCap - 1)] = e;
                //如果为树结构，则对红黑树的处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

8.4 HashSet的应用案例

/*
案例：定义Employee类，包含：private成员属性name，salary
要求：1.创建3个Employee放入HashSet中
     2.当name值相同时，认为是相同员工，不能添加到HashSet集合中
 */
@SuppressWarnings({"all"})
public class HashSetExercise {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("yorick",6000.0));
        hashSet.add(new Employee("tom",4000.0));
        hashSet.add(new Employee("jerry",5000.0));
        hashSet.add(new Employee("tom",3000.0));
        System.out.println("HashSet:"+hashSet);

    }
}

@Data
@AllArgsConstructor
class Employee{
    private String name;
    private double salary;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return Objects.equals(name, employee.name);
    }

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

    @Override
    public String toString() {
        return "\nEmployee{" +
                "name='" + name + '\'' +
                ", salary=" + salary +
                '}';
    }
}

result

# 最后一个tom 没有添加成功，这是由于重写了hashcode和equels方法，导致只通过name来判别
HashSet:[
Employee{name='tom', salary=4000.0}, 
Employee{name='jerry', salary=5000.0}, 
Employee{name='yorick', salary=6000.0}]

9 LinkedHashSet

9.1 LinkedHashSet基本说明

LinkedHashSet是HashSet的子类
LinkedHashSet的底层是一个LinkedHashMap，底层维护了一个数值+双向链表
LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表来维护元素的次序，使得元素看起来是以插入顺序保存
LinkedHashSet不允许添加重复元素

9.2 LinkedHashSet底层机制

在LinkedHashSet中维护了一个Hash表和双向链表（有head和tail两个标志位，记录头和尾）
每一个节点都有pre和next属性，可以形成双向链表
在添加一个元素时，先求hash值，再求索引，确定该元素再hash表中的位置，然后将添加的元素加入到双向链表（若存在则不添加）
遍历LinkedHashSet能确保插入顺序和遍历顺序一致

9.3 LinkedHashSet源码分析

编写测试程序

public class LinkedHashSetSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add("yorick");
        linkedHashSet.add("tom");
        linkedHashSet.add("jerry");
        System.out.println("LinkedHashSet:"+linkedHashSet);
    }
}

进入LinkedHashSet的构造方法

//实际上调用了父类HashSet的构造方法
public LinkedHashSet() {
    super(16, .75f, true);
}

//可以看出LinkedHashSet实际上底层创建了LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

进入add方法

//实际上LinkedHashSet调用的是父类HashSet的add方法
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

//依次调用put，putval方法
与HashSet一致

进入newNode方法，在LinkedHashSet中对newNode方法进行了重载

//创建的新结点是Entry类型，Entry是Node子类
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //用于执行双向链表的连接操作
    linkNodeLast(p);
    return p;
}

进入Entry的构造方法

//可以看出Entry是LinkedHashSet的静态内部类，继承了父类中的静态内部类Node，在其基础上增加了指向前驱结点的before和指向后驱结点的after属性
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

进入linkNodeLast方法

//实现对双向链表的构造
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail; //保存当前双向链表的尾指针
    tail = p; //让尾指针指向新添加的元素
    if (last == null) //如果是第一个元素，则令双向链表的头指针指向该元素
        head = p;
    else { //插入到链表
        p.before = last;
        last.after = p;
    }
}

9 TreeSet

9.1 TreeSet相关特征

TreeSet底层调用的是TreeMap
使用TreeSet提供的构造器，可以传入一个比较器来指定排序规则
若不传入比较器，需要元素本身实现Comparable接口。源码可以看到优先使用比较器，若没有提供比较器才会调用实现了Comparable接口的元素本身的比较方法。

9.2 TreeSet使用

使用比较器

public class TreeSetSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        //通过传入比较器，实现按分数从低到高排序
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                Student stu1 = (Student) o1;
                Student stu2 = (Student) o2;
                return (int) (stu1.getScore() - stu2.getScore());
            }
        });
        treeSet.add(new Student("yorick",83));
        treeSet.add(new Student("tom",67));
        treeSet.add(new Student("jerry",97));
        System.out.println(treeSet);
    }
}

class Student{
    private String name;
    private double score;

    public Student(String name, double score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

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

元素对象实现Comparable接口

public class TreeSetSourceCode {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Student("yorick",83));
        treeSet.add(new Student("tom",67));
        treeSet.add(new Student("jerry",97));
        System.out.println(treeSet);
    }
}

class Student implements Comparable{
    private String name;
    private double score;

    public Student(String name, double score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }
    //通过对象实现比较接口，实现按分数从低到高排序
    @Override
    public int compareTo(Object o) {
        Student stu1 = this;
        Student stu2 = (Student) o;
        return (int) (stu1.getScore() - stu2.getScore());
    }
}

集合专题——单列集合
1 集合框架体系单列集合image-20210511092441523.png 双列集合 2 Collectio...
集合总结
集合集合分为单列集合和双列集合两种：一.单列集合： Collection是单列集合的顶级接口：其中有三类集合...
Java基础之常用集合
集合分为单列集合(Collection)和双列集合(Map)，先说单列集合Collection Collecti...
集合
常用集合类单列集合 Collection：Iterable 是单列集合类的根接口 Collection用于存储一...
java——集合
集合概述集合按照存储结构可以分为两大类单列集合Collection Collection（单列集合类的跟接口）有...
单列集合
List集合 1.List常见集合ArrayList和LinkedList 1.ArrayList是一种单列...
Java集合
单列集合（Collection）单列集合类的根接口，用于：存储一系列符合某种规则的元素。 List 集合有序...
2-JAVA类的Collection集合
Collection集合 32. Collection接口定义的是所有单列集合中共性的方法所有的单列集合都可以使...
ArrayList|LinkList|栈和队列
ArrayList 集合的体系：----------| Collection 单列集合的根接口---------...
Java基础之Collection集合
标题常用集合 Java集合中,几个常用集合关系图 Collection单列集合中常用集中集合关系 Collecti...