⛳ Java集合框架

news/2024/5/22 16:44:00

目录

  • ⛳ Java集合框架
    • 🎨 一、概述
    • 🏭 二、`Iterator`接口
      • 💭 2.1、基础用法
      • 🚜 2.2、原理
      • 🐾 2.3、为什么需要`iterator`接口
      • ☁ 2.4、`ListIterator`接口
      • 📢 2.5、`iterator`在集合中的实现例子
        • 2.5.1、`Iterator`在`ArrayList`的实现
        • 2.5.2、`Iterator`在`HashMap`的实现
      • 📝2.6、总结
    • 👣 三、`Collection`接口
      • 🎨 3.1、简介
      • 🏭 3.2、接口方法
      • 💻 3.3、`Collection`的使用
    • 📢 四、`List`接口
      • ⭐ 4.1、简介
      • ☁ 4.2、`ArrayList`类
      • 🚜 4.3、`LinkedList`类
      • 4.4、`Vector`类
      • **⭐ 面试题:请问ArrayList/LinkedList/Vector的异同? 谈谈你的理解? ArrayList底层是什么?扩容机制? Vector和ArrayList的最大区别?**
    • 📐 五、`Set`接口
      • 🎨 5.1、`HashSet`
        • 5.1.1、`HashSet`中的方法
        • 5.1.2、底层原理
        • 5.1.3、图解原理
      • 👣 5.2、`LinkedHashSet`
        • 5.2.1、`LinkedHashSet`的实现
      • 🎉 5.3、`TreeSet`
        • 5.3.1、自然排序
        • 5.3.2、定制排序
    • ⭐ 六、`Map`接口
      • 💖 6.1、`HashMap`
      • 📝 6.2、`LinkedHashMap`
      • 🚜 6.3、`TreeMap`
      • 🏭 6.4、`HashTable`
      • 🎉 6.5、`Properties`
    • 💬 七、`Collections`工具类

⛳ Java集合框架

🎨 一、概述

早在Java 2之前,Java 就提供了特设类。比如:DictionaryVectorStackProperties这些类用来存储和操作对象组。

虽然这些类都非常有用,但是它们缺少一个核心的,统一的主题。由于这个原因,使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。

集合框架被设计成要满足以下几个目标。

  • 该框架必须是高性能的。基本集合(动态数组,链表,树,哈希表)的实现也必须是高效的。
  • 该框架允许不同类型的集合,以类似的方式工作,具有高度的互操作性。
  • 对一个集合的扩展和适应必须是简单的。

为此,整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现,诸如: LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

image-20230807203828190

简化图:

image-20230807203906187

注:带有Produces没有implements(实现)的关系。

Java 集合类是特别有用的工具类,可用于存储数量不等的对象,并且可以实现常用的数据结构,栈,队列等。Java集合大致分为SetListMapQueue四种体系,其中Set代表无序,不可重复的集合,而List正好相反,List代表有序,可重复的大的集合;Map则代表具有映射关系的集合;Java 5 又增加了Queue体系集合,代表一种队列集合的实现。

🏭 二、Iterator接口

Iterator接口表示对集合进行迭代的迭代器。Iterator接口为集合而生,专门实现接口的集合。

凡是由Collection接口派生来的接口或类,都实现了iterator()方法,iterator()方法返回一个Iterator对象。

Map接口的实现方式是通过EntrySet内部类实现的。

💭 2.1、基础用法

  1. 使用集合的iterator()方法返回Iterator对象。
  2. while循环遍历。
  3. 使用IteratorhasNext()方法判断是否存在下一个可访问的元素。
  4. 使用Iteratornext()方法返回要访问的下一个元素。
import java.util.ArrayList;

import java.util.Iterator;

public class ArrayListTest {

        public static void main(String[] args) {

                 ArrayList testList = new ArrayList();
                  testList.add("String1");
                 testList.add("String2");
                 testList.add("String3");
            	// 获取迭代器
                 Iterator it = testList.iterator();
                 while(it.hasNext()) {  // 判断是否有下一个元素 (刚开始指向头结点)
                          String str = (String)it.next();  // 返回下一个元素
                          System.out.println(str);
                 }
        }
}

🚜 2.2、原理

JDK 中专门提供了一个遍历集合的接口java.util.IteratorIterator接口也是Java集合中的一员,但它与CollectionMap接口有所不同,Collection接口与Map接口主要用于存储元素,而Iterator主要用于迭代访问(即遍历)Collection中的元素

因此Iterator对象也被称为迭代器,使你能够通过循环来得到或删除集合的元素。ListIterator 继承了Iterator,以允许双向遍历列表和修改元素。

  • 方法:

    1. hasNext() :该方法会判断集合对象是否还有下一个元素,如果已经是最后一个元素则返回false。如果仍有元素可以迭代,则返回 true
    2. next():把迭代器的指向移到下一个位置,同时,该方法返回迭代的下一个元素。
    3. remove() 从迭代器指向的集合中移除迭代器返回的最后一个元素。
    4. default void forEachRemaining(Consumer<? super E> action):对剩下的所有元素进行处理,action则为处理的动作,意为要怎么处理
    boolean hasNext(); // 是否有下一个元素
    
    E next();   // 获取下一个元素
    
    // 移除元素
    default void remove() {
            throw new UnsupportedOperationException("remove");
        }
        
    // 对剩下的所有元素进行处理,action则为处理的动作,意为要怎么处理
    default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }
    

测试:DemoIterator

package org.example.f_interator;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/*
    java.util.Iterator接口:迭代器(对集合进行遍历)
    有两个常用的方法
        boolean hasNext() 如果仍有元素可以迭代,则返回 true。
                          判断集合中还有没有下一个元素,有就返回true,没有就返回false
        E next() 返回迭代的下一个元素。
                  取出集合中的下一个元素
    Iterator是一个接口,我们无法直接使用,需要使用Iterator接口的实现类对象,获取实现类的方式比较特殊
    Collection接口中有一个方法,叫iterator(),这个方法返回的就是迭代器的实现类对象
              Iterator<E> iterator() 返回在此 collection 的元素上进行迭代的迭代器。

    迭代器的使用步骤(重点):
        1.使用集合中的方法iterator()获取迭代器的实现类对象,使用Iterator接口接收(多态)
        2.使用Iterator接口中的方法hasNext判断还有没有下一个元素
        3.使用Iterator接口中的方法next取出集合中的下一个元素
 */
public class DemoIterator {
    public static void main(String[] args) {
        //创建一个集合对象
        Collection<String> coll = new ArrayList<>();
        //往集合中添加元素
        coll.add("姚明");
        coll.add("科比");
        coll.add("麦迪");
        coll.add("詹姆斯");
        coll.add("艾弗森");

        /*
            1.使用集合中的方法iterator()获取迭代器的实现类对象,使用Iterator接口接收(多态)
            注意:
                Iterator<E>接口也是有泛型的,迭代器的泛型跟着集合走,集合是什么泛型,迭代器就是什么泛型
         */
        //多态  接口            实现类对象
        Iterator<String> iterator = coll.iterator();


        /*
            发现使用迭代器取出集合中元素的代码,是一个重复的过程
            所以我们可以使用循环优化
            不知道集合中有多少元素,使用while循环
            循环结束的条件,hasNext方法返回false
         */
        while (iterator.hasNext()) {
            String e = iterator.next();
            System.out.print(e + " ");//姚明 科比 麦迪 詹姆斯 艾弗森
        }

        System.out.println("\n======================");

        for (Iterator<String> it2 = coll.iterator(); it2.hasNext(); ) {
            String e = it2.next();
            System.out.print(e + " ");//姚明 科比 麦迪 詹姆斯 艾弗森
        }

    }
}
  • 在获取迭代器的时候,会创建一个原集合的副本。同时会创建一个指针指向迭代器迭代集合的起始位置。
  • Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素,如果有,就把这个元素取出来,继续再判断,如果还有就再取出出来。一直把集合中的所有元素全部取出。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vqh9oK7Z-1691910477171)(C:\Users\gu653\AppData\Roaming\Typora\typora-user-images\image-20230809191910673.png)]

🐾 2.3、为什么需要iterator接口

iterator接口是为了定义遍历集合的规范,也是一种抽象,把在不同集合的遍历方式抽象出来,这样遍历的时候,就不需要知道不同集合的内部结构。

为什么需要抽象?

假设没有iterator接口,我们知道,遍历的时候只能通过索引,比如

for(int i=0;i<array.size();i++){
    T item = array[i];
}

这样一来,耦合程度比较高,如果使用的数据结构变了,就要换一种写法,不利于维护已有的代码。如果没有iterator,那么客户端需要维护指针,相当于下放了权限,会造成一定程度的混乱。抽象则是把遍历功能抽取出来,交给iterator处理,客户端处理集合的时候,交给更“专业”的它,it do it well.

值得注意的是,集合类的整体不是继承了iterator接口,而是继承了iterable接口,通过iterable接口的方法返回iterator的对象。值得注意的是,iteratorremove()方法,是迭代过程中唯一安全的修改集合的方法,为何这样说?

如果使用for循环索引的方式遍历,删除掉一个元素之后,集合的元素个数已经变化,很容易出错。例如

for(int i=0;i<collection.size();i++){
    if(i==2){
        collection.remove(i);
    }
}

iteratorremove()方法则不会出错,因为通过调用hasNext()next()方法,对指针控制已经处理得比较完善。

☁ 2.4、ListIterator接口

ListIterator继承于Iterator接口,功能更强大,只能用于访问各种List类型,使用List类型的对象list,调用listIterator()方法可以获取到一个指向list开头的ListIterator

image-20230809193600570

从上面图片接口看,这个接口具有访问下一个元素,判断是否有下一个元素,是否有前面一个元素,判断是否有前一个元素,获取下一个元素的索引,获取上一个元素的索引,移除元素,修改元素,增加元素等功能。和普通的Iterator不一样的是,ListIterator的访问指针可以向前或者向后移动,也就是双向移动。

boolean hasNext();  //是否还有元素 

E next();   //获取下一个元素

boolean hasPrevious();  //是否有上一个元素

E previous();   // 获取上一个元素

int nextIndex();    //获取下一个索引

int previousIndex();    //获取上一个索引

void remove();  //移除

void set(E e); //更新

void add(E e); //添加元素

测试:

List<String> list =
    new ArrayList<String>(Arrays.asList("Book","Pen","Desk"));
// 把指针指向第一个元素
ListIterator<String> lit = list.listIterator(1);
while(lit.hasNext()){
    System.out.println(lit.next());
}
System.out.println("===================================");
//指针指向最后一个元素列表中的最后一个元素修改ChangeDesk。
lit.set("ChangeDesk");
// 往前面遍历
while(lit.hasPrevious()){
    System.out.println(lit.previous());
}

结果:

Pen
Desk
===================================
ChangeDesk
Pen
Book

如果点开ArrayList的源码,看到与ListIterator相关的部分,我们会发现其实ArrayList在底层实现了一个内部类ListItr,继承了Itr,实现了ListIterator接口。这个Itr其实就是实现了Iterator,实现了基本的List迭代器功能,而这个ListItr则是增强版的专门为List实现的迭代器。里面使用cursor作为当前的指针(索引),所有函数功能都是操作这个指针实现。

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            // 设置当前指针 
            cursor = index;
        }

        public boolean hasPrevious() {
            // 不是第一个元素就表明有前一个元素
            return cursor != 0;
        }
        // 获取下一个元素索引
        public int nextIndex() {
            return cursor;
        }

        // 获取前面一个元素索引
        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            //检查是否被修改
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            // 返回前一个元素
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

在上面方法中,有很多校验,比如checkForComodification(),意为检查是否被修改,list中的元素修改有可能导致数组越界。

📢 2.5、iterator在集合中的实现例子

iterator只是一个接口,相当于一个规范,所有的子类或者继承类实现的时候理论上应该遵守,但是不一样的继承类/子类会有不一样的实现。

2.5.1、IteratorArrayList的实现

iterator只是一个接口,一个规范,虽然里面有个别方法有默认实现,但是最重要也最丰富的的,是它在子类中的实现与拓展,现在来看在ArrayList 中的实现。ArrayList并没有直接去实现iterator接口,而是通过内部类的方式来操作,内部类为Itr,

private class Itr implements Iterator<E> {
    // 下一个元素的索引(指针)
    int cursor;       // index of next element to return
    // 最后一个元素指针索引
    int lastRet = -1; // index of last element returned; -1 if no such
    // 修改次数(版本号)
    int expectedModCount = modCount;

    Itr() {}
    // 是否有下一个元素
    public boolean hasNext() {
        return cursor != size;
    }

    // 下一个元素
    @SuppressWarnings("unchecked")
    public E next() {
        //安全检查
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    // 移除
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 依次处理剩下的元素
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }
    // 安全检查,检查是否被修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

从上面的源码可以看到,很多关于被修改的检查,集合会追踪修改(增删改)的次数(modCount 又称版本号),每一个迭代器会单独立维护一个计数器,在每次操作(增删改),检查版本号是否发生改变,如果改变,就会抛出ConcurrentModificationException() 异常,这是一种安全保护机制。
安全检查,快速失败机制实现主要和变量modCountexpectedModCount,以及一个checkForComodification()方法有关,也就是expectedModCount是内部类的修改次数,从字面意思看是指理论上期待的修改次数,modCount是外部类的修改次数,创建的时候,会将modCount赋值给expectedModCount,两者保持一致,如果在迭代的过程中,外部类的modCount对不上expectedModCount,n那么就会抛出ConcurrentModificationException异常。

2.5.2、IteratorHashMap的实现

首先,HashMap里面定义了一个HashIterator,为什么这样做呢?因为HashMap存储结构的特殊性,里面有Entry<key,value>,所以遍历就有三种情况,一个是Key,一个是Value,另一个就是Entry,这三个的迭代遍历都有相似性,所以这里根据抽象原则,定义了一个Hash迭代器。

    abstract class HashIterator {
        // 下一个节点
        Node<K,V> next;
        
        // 当前节点
        Node<K,V> current;     // current entry
        // 期望修改次数
        int expectedModCount;  // for fast-fail
        // 索引
        int index;             // current slot

        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { 
                // 指向第一个不为空的元素
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        // 是否有下一个节点
        public final boolean hasNext() {
            return next != null;
        }

        // 获取下一个节点
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        // 移除
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

之后分别定义KeyIterator,ValueIterator,EntryIterator,继承于HashIterator

// 遍历key
final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}
// 遍历value
final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

//遍历entry
final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

📝2.6、总结

关于Iterator,其实就是一个迭代器,可简单地理解为遍历使用,主要功能是指向一个节点,向前或者向后移动,如果数据结构复杂就需要多个迭代器,比如HashMap,可以避免多个迭代器之间相互影响。每一个迭代器都会有

expectedModCount 和modCount,就是校验这个迭代过程中是否被修改,如果修改了,则会抛出异常。

👣 三、Collection接口

🎨 3.1、简介

Collection 接口是 List、 Set 和 Queue 接口的父接口,该接口里定义的方法既可用于操作 Set 集合,也可用于操作 List 和 Queue 集合。

JDK不提供此接口的任何直接实现,而是提供更具体的子接口(如: Set和List)实现。

在 Java5 之前, Java 集合会丢失容器中所有对象的数据类型,把所有对象都当成 Object 类型处理; 从 JDK 5.0 增加了泛型以后, Java 集合可以记住容器中对象的数据类型。

🏭 3.2、接口方法

  • 添加

    1. add(Object obj)
    2. addAll(Collection coll)
  • 获取有效元素的个数

    1. int size()
  • 清空集合

    1. void clear()
  • 是否是空集合

    1. boolean isEmpty()
  • 是否包含某个元素

    1. boolean contains(Object obj): 是通过元素的equals方法来判断是否是同一个对象
    2. boolean containsAll(Collection c): 也是调用元素的equals方法来比较的。 拿两个集合的元素挨个比较。
  • 删除

    1. boolean remove(Object obj) : 通过元素的equals方法判断是否是要删除的那个元素。 只会删除找到的第一个元素
    2. boolean removeAll(Collection coll): 取当前集合的差集
  • 取两个集合的交集

    1. boolean retainAll(Collection c):如果此集合包含指定集合中的所有元素,则返回true。
  • 集合是否相等

    • boolean equals(Object obj)
  • 转成对象数组

    • Object[] toArray()
  • 遍历

    • iterator(): 返回迭代器对象,用于集合遍历

💻 3.3、Collection的使用

    @Test
    public void test1() {
        Collection c1 = new ArrayList();

        //添加元素
        c1.add("hello");
        c1.add("world");
        c1.add("tom");
        c1.add("jarray");
        c1.add(123); //自动装箱int->Integer
        c1.add(456);

        //添加自定义对象
        c1.add(new User("马云", 45));
        c1.add(new User("马化腾", 35));

        //删除对象
        c1.remove("tom");
//        c1.clear(); //清空


        System.out.println("isEmpty = " + c1.isEmpty());

        String s1 = new String("hello");
        System.out.println("contains = " +  c1.contains(s1)); //true,比较内容

        System.out.println(c1);

    }

contains方法:调用equals,比较内容,因为string实现了equals比较,所以String比较内容,使用User自定义equals,查看contains结果:

User.java:

    @Override
    public boolean equals(Object o) {
        System.out.println("User equals()....");
//        return super.equals(o);
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        User user = (User) o;

        if (age != user.age) return false;
        return name != null ? name.equals(user.name) : user.name == name;
    }

测试:

//添加自定义对象
User u1 = new User("马云", 45);
User u2 = new User("马云", 45);
User u3 = new User("马云", 45);
c1.add(u1);
c1.add(u2);
c1.add(new User("马化腾", 35));
System.out.println(c1.size());  // 3
System.out.println("contains马云 = " + c1.contains(u3)); //调用equals,比较内容,返回true

📢 四、List接口

Collection 接口:单列集合,用来存储一个一个的对象

​ List 接口:存储有序的、可重复的数据 ----> “动态”数组

​ ArrayList :作为 List 接口的主要实现类,线程不安全、效率高、底层用Object[] elementData(推荐)

​ LinkedList:对于频繁插入、删除操作,使用此类的效率比ArrayList高;底层使用双向链存储 (看情况—推荐)

​ Vector:作为List接口的古老实现;线程安全,效率低,底层使用Object[] elementData存储 (不推荐)

⭐ 4.1、简介

  • 鉴于Java中数组用来存储数据的局限性,我们通常使用List替代数组
  • List集合类中元素有序、且可重复,集合中的每个元素都有其对应的顺序索引。
  • List容器中的元素都对应一个整数型的序号记载其在容器中的位置,可以根据序号存取容器中的元素。
  • JDK APIList接口的实现类常用的有: ArrayListLinkedListVector

List接口方法

List除了从Collection集合继承的方法外, List 集合里添加了一些根据索引来操作集合元素的方法。

  • **void add(int index, Object ele)😗*在index位置插入ele元素
  • boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
  • **Object get(int index)😗*获取指定index位置的元素
  • **int indexOf(Object obj)😗*返回obj在集合中首次出现的位置
  • **int lastIndexOf(Object obj)😗*返回obj在当前集合中末次出现的位置
  • **Object remove(int index)😗*移除指定index位置的元素,并返回此元素
  • **Object set(int index, Object ele)😗*设置指定index位置的元素为ele
  • **List subList(int fromIndex, int toIndex)😗*返回从fromIndex到toIndex位置的子集合
@Test
public void test1() {
    List list = new ArrayList();

    list.add("aaa");
    list.add("bbb");
    list.add("aaa");
    list.add("aaa");
    list.add(0, 111);
    list.add(0, 222);
    list.add(0, 333);

    //get
    System.out.println(list.get(3));

    //indexOf
    System.out.println(list.indexOf("aaa"));
    System.out.println(list.lastIndexOf("aaa"));

    //remove
    list.remove(0);
    list.remove("aaa");

    System.out.println(list);

    System.out.println(list.subList(0, 3));

}

☁ 4.2、ArrayList

ArrayList 是长度可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的数组空间,把原有数据复制到新数组中。 ArrayList 支持对元素的快速随机访问,但是插入与删除时速度通常很慢,因为这个过程很有可能需要移动其他元素。

  • ArrayList 是 List 接口的典型实现类、主要实现类

  • 本质上, ArrayList是对象引用的一个”变长”数组

  • ArrayList的JDK1.8之前与之后的实现区别?

    • JDK1.7: ArrayList像饿汉式,直接创建一个初始容量为10的数组
    • JDK1.8: ArrayList像懒汉式,一开始创建一个长度为0的数组,当添加第一个元素时再创建一个始容量为10的数组
  • Arrays.asList(…) 方法返回的 List 集合, 既不是 ArrayList 实例,也不是Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合

@Test
public void test01(){
    // 1、创建List
    // 可以使用以下方法创建一个空的List或具有初始元素的List:
    List<String> emptyList = new ArrayList<>();
    List<Integer> numbers1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    List<String> fruits = new LinkedList<>(Arrays.asList("apple", "banana", "orange"));

    // 2、访问List元素 List的元素可以通过索引来访问,索引从0开始计数。
    String firstFruit = fruits.get(0);
    System.out.println(firstFruit);  // 输出:apple

    ///3、修改List元素 List中的元素是可变的,可以通过索引来修改特定位置的值。
    fruits.set(0, "pear");
    System.out.println(fruits);  // 输出:[pear, banana, orange]

    // 4、添加和删除List元素 可以使用add()方法向List末尾添加元素,使用add(index, element)方法在指定位置插入元素。
    // 使用remove(index)方法或者remove(element)方法删除List中的元素。
    fruits.add("grape");
    fruits.add(1, "kiwi");
    fruits.remove(2);
    System.out.println(fruits);  // 输出:[pear, kiwi, orange, grape]

    // 5、List切片和拼接 List不支持直接切片操作,
    // 但可以使用subList()方法获取指定范围的子列表。
    // 也可以使用addAll()方法将多个List拼接为一个List。
    List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    List<Integer> subList = numbers.subList(1, 4);
    System.out.println(subList);  // 输出:[2, 3, 4]

    List<Integer> moreNumbers = new ArrayList<>(Arrays.asList(6, 7, 8));
    numbers.addAll(moreNumbers);
    System.out.println(numbers);  // 输出:[1, 2, 3, 4, 5, 6, 7, 8]


    // 6、List排序和反转 List可以使用Collections工具类的sort()方法进行排序,
    // 默认按照自然顺序排序。可以使用Collections的reverse()方法将List逆序排列。
    List<Integer> numbers6 = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
    Collections.sort(numbers6);
    System.out.println(numbers6);  // 输出:[1, 2, 5, 8, 9]

    Collections.reverse(numbers6);
    System.out.println(numbers6);  // 输出:[9, 8, 5, 2, 1]

    // 7、List的常见操作和方法 List支持许多常见的操作和方法,如长度计算、成员检查、最大/最小值查找等。
    List<Integer> numbers7 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    System.out.println(numbers7.size());  // 输出:5

    System.out.println(numbers7.contains(3));  // 输出:true

    System.out.println(Collections.max(numbers7));  // 输出:5
    System.out.println(Collections.min(numbers7));  // 输出:1

    // 8、List与其他数据结构的转换 List可以通过Arrays.asList()方法将数组转换为List,
    // 也可以使用toArray()方法将List转换为数组。
    String[] fruitsArray = {"apple", "banana", "orange"};
    List<String> fruitsList = Arrays.asList(fruitsArray);
    System.out.println(fruitsList);  // 输出:[apple, banana, orange]

    Integer[] numbersArray = numbers.toArray(new Integer[numbers.size()]);
    System.out.println(Arrays.toString(numbersArray));  // 输出:[1, 2, 3, 4, 5]


    // 9、高级List操作技巧 List还支持更高级的操作技巧,
    // 如Lambda表达式和Stream API的运用。
    // 可以使用forEach()方法遍历List,并利用stream()方法进行过滤、映射、聚合等操作。
    List<Integer> numbers9 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

    numbers9.forEach(System.out::println);  // 输出:1 2 3 4 5

    List<Integer> filteredNumbers = numbers9.stream()
        .filter(n -> n % 2 == 0)
        .collect(Collectors.toList());
    System.out.println(filteredNumbers);  // 输出:[2, 4]
}

🚜 4.3、LinkedList

LinkedList 的本质是双向链表。与 Array List 相比 , **LinkedList 的插入和删 除速度更快,但是随机访问速度很慢。**测试表明,对于 IO 万条的数据,与 ArrayList 相比,随机提取元素时存在数百倍的差距。除继承 AbstractList 抽象类外, LinkedList 还实现了另一个接口 Deque ,即 double-ended queue。这个接口同时具有队列和枝的性质。LinkedList 包含 3 个重要的成员 size 、first、 last 。 size 是双向链表中节点的个数。first 和 last 分别指向第一个和最后一个节点的引用。 LinkedList 的优点在于可以将零散的内存单元通过附加引用的方式关联起来,形成按链路顺序序查找的线性结构,内存利用率较高。

新增方法:

  • void addFirst(Object obj)
  • void addLast(Object obj)
  • Object getFirst()
  • Object getLast()
  • Object removeFirst()
  • Object removeLast()

LinkedList: 双向链表, 内部没有声明数组,而是定义了Node类型的first和last,用于记录首末元素。同时,定义内部类Node,作为LinkedList中保存数据的基本结构。 Node除了保存数据,还定义了两个变量:

  • prev变量记录前一个元素的位置
  • next变量记录下一个元素的位置

案例:

    /**
     * 1. 有序:插入顺序
     * 2. 允许重复
     * 3. 底层是数组,默认大小10,每次扩容1.5倍
     *      - jdk1.7:默认大小10
     *      - jdk1.8 默认大小0,第一次使用时初始化成10
     * 4:添加和删除,性能差,随机遍历性能好
     */
    @Test
    public void test2() {
        List list = new ArrayList();

        list.add("ccc");
        list.add("ccc");
        list.add("bbb");
        list.add("aaa");

        User u1 = new User("马云", 45);
        User u2 = new User("马化腾", 38);
        list.add(u1);
        list.add(u1);
        list.add(u2);

        //方式1
        for (Object o : list) {
            System.out.println(o);
        }
        System.out.println("-------------");
        //方式2
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("-------------");
        for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
            Object obj =  iterator.next();
            System.out.println(obj);
        }
    }

    /**
     * 1. 底层原理:基于双向链表实现
     * 2. 插入和删除块,遍历性能差
     * 3. 可以直接操作头和尾
     * 4. 有序(插入顺序),容许重复
     */
    @Test
    public void test3() {
        LinkedList list = new LinkedList();

        list.add("ccc");
        list.add("ccc");
        list.add("bbb");
        list.add("aaa");

        User u1 = new User("马云", 45);
        User u2 = new User("马化腾", 38);
        list.add(u1);
        list.add(u1);
        list.add(u2);

        list.addFirst("1111");
        list.addLast("2222");

        System.out.println(list.getLast());

        //方式1
        for (Object o : list) {
            System.out.println(o);
        }

    }

4.4、Vector

  • Vector 是一个古老的集合, JDK1.0就有了。大多数操作与ArrayList相同,区别之处在于Vector是线程安全的。

  • 在各种list中,最好把ArrayList作为缺省选择。当插入、删除频繁时,使用LinkedList; Vector总是比ArrayList慢,所以尽量避免使用。

  • 新增方法:

    • void addElement(Object obj)
    • void insertElementAt(Object obj,int index)
    • void setElementAt(Object obj,int index)
    • void removeElement(Object obj)
    • void removeAllElements()

⭐ 面试题:请问ArrayList/LinkedList/Vector的异同? 谈谈你的理解? ArrayList底层是什么?扩容机制? Vector和ArrayList的最大区别?

  • ArrayList和LinkedList的异同二者都线程不安全,相对线程安全的Vector,执行效率高。此外, ArrayList是实现了基于动态数组的数据结构, LinkedList基于链表的数据结构。对于随机访问get和set, ArrayList觉得优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove, LinkedList比较占优势,因为ArrayList要移动数据。
  • ArrayList和Vector的区别Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized),属于强同步类。因此开销就比ArrayList要大,访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。 Vector每次扩容请求其大小的2倍空间,而ArrayList是1.5倍。 Vector还有一个子类Stack。

📐 五、Set接口

Set 是不允许出现重复元素的集合类型。 Set 体系最常用的是 HashSet 、 TreeSet和 LinkedHashSet 三个集合类。 HashSet 从源码分析是使用 HashMap 来实现的,只是Value 固定为一个静态对象,使用 Key 保证集合元素的唯一性,但它不保证集合元素的顺序。 TreeSet 也是如此,从源码分析是使用 TreeMap 来实现的,底层为树结构,在添加新元素到集合中时,按照某种比较规则将其插入合适的位置 。 LinkedHashSet 继承自 HashSet , 具有 HashSet 的优点,内部使用链表维护了元素插入顺序。

🎨 5.1、HashSet

HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null元素。

public class HashSet<E>  
extends AbstractSet<E>  
implements Set<E>, Cloneable, java.io.Serializable  

HashSet继承AbstractSet类,实现Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干实现,从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection,它维持它自己的内部排序,所以随机访问没有任何意义。
基本属性:

// 底层使用HashMap来保存HashSet中所有元素。
private transient HashMap<E, Object> map;

// 定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。
private static final Object PRESENT = new Object();

HashMap只能存入一个null键,那么HashSet也就只能有一个null值。

构造函数:
从构造函数中可以看出HashSet所有的构造都是构造出一个新的HashMap,其中最后一个构造函数,为包访问权限是不对外公开,仅仅只在使用LinkedHashSet时才会发生作用。

5.1.1、HashSet中的方法

因为HashSet是基于HashMap,所以对于HashSet,其方法的实现过程是非常简单的。

  1. iterator()
    iterator()方法 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层实际调用底层HashMap的keySet来返回所有的key。 可见HashSet中的元素,只是存放在了底层HashMap的key上, value使用一个static final的Object对象标识。
public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

2.size()
返回此set中的元素的数量(set的容量)。底层实际调用HashMap的size()方法返回Entry的数量,就得到该Set中元素的个数,即HashMap容器的大小。

public int size() {
        return map.size();
    }

3.isEmpty()
isEmpty()判断HashSet()集合是否为空,如果此set不包含任何元素,则返回true。 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。

public boolean isEmpty() {
        return map.isEmpty();
    }

4.contains(Object o)
contains(),判断某个元素是否存在于HashSet()中,存在返回true,否则返回false。更加确切的讲应该是要满足这种关系才能返回true:(onull ? enull : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

public boolean contains(Object o) {
        return map.containsKey(o);
    }

5.add()
add()如果此 set 中尚未包含指定元素,则添加指定元素。如果此Set没有包含满足(enull ? e2null : e.equals(e2)) 的e2时,则将e2添加到Set中,否则不添加且返回false。由于底层使用HashMap的put方法将key = e,value=PRESENT构建成key-value键值对,当此e存在于HashMap的key中,则value将会覆盖原有value,但是key保持不变,所以如果将一个已经存在的e元素添加中HashSet中,新添加的元素是不会保存到HashMap中,所以这就满足了HashSet中元素不会重复的特性。

public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

6.remove()
remove()如果指定元素存在于此 set 中,则将其移除。底层使用HashMap的remove方法删除指定的Entry。

public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

7.clear()
clear()从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。

public void clear() {
        map.clear();
    }

8.clone()
底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并没有复制这些元素本身。

public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

5.1.2、底层原理

HashSet它是基于HashMap实现的,HashSet底层使用HashMap来保存所有元素,因此HashSet的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成的。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

	// 底层使用hashmap来保存hashset中所有的元素
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    // 定义一个虚拟的object对象作为hashmap的value,将次对象定义为static final,放在map的值的位置
    private static final Object PRESENT = new Object();

	// 默认无参构造,实际底层初始化一个空的hashmap,并使用默认初始容量为16和加载因子为0.75
    public HashSet() {
        map = new HashMap<>();
    }

	// 构造一个指定Collection中元素的新set,实际底层使用默认的加载因子为0.75和足以包含指定Collection中	// 左右元素的初始容量来定义一个hashmap
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

	// 以指定的initialCapacity和loadFactor构造一个空的set,实际底层以相同的参数,构造一个空的map集合
	// initialCapacity:初始容量,loadFactor:加载因子
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

	// 指定初始长度创建一个空的集合,实际使用一样的参数,与加载因子为0.75构造一个空的map
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

	// 指定初始长度和加载因子构造一个新的空链接哈希集合
	// 此构造函数为包含访问权限,不对外公开,实际只是对LinkedHashSet的支持
	// 实际以指定的参数创建一个空的LinkedHashMap集合
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

key 、value 存储一个静态的 new Object
image-20230809214702461

  • HashSet 集合判断两个元素相等的标准: 两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等。

  • 对于存放在Set容器中的对象, 对应的类一定要重写equals()和hashCode(Objectobj)方法,以实现对象相等规则。即: “相等的对象必须具有相等的散列码” 。

  • 向HashSet中添加元素的过程:

    • 当向 HashSet 集合中存入一个元素时, HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值, 然后根据 hashCode 值, 通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。 (这个散列函数会与底层数组的长度相计算得到在数组中的下标, 并且这种散列函数计算还尽可能保证能均匀存储元素, 越是散列分布,该散列函数设计的越好)
    • 如果两个元素的hashCode()值相等, 会再继续调用equals方法, 如果equals方法结果为true, 添加失败; 如果为false, 那么会保存该元素, 但是该数组的位置已经有元素了,那么会通过链表的方式继续链接。
    • 如果两个元素的 equals() 方法返回 true,但它们的 hashCode() 返回值不相等, hashSet 将会把它们存储在不同的位置,但依然可以添加成功。
  • image-20230809215243555

//下面不同的字符串就有相同的hashCode
 System.out.println("ABCDEa123abc".hashCode());  // 165374702
 System.out.println("ABCDFB123abc".hashCode()); //  165374702

HashSet底层也是HashMap, 初始容量为16, 当如果使用率超过0.75, (16*0.75=12)就会扩大容量为原来的2倍。 (16扩容为32, 依次为64,128…等)

  1. 重写hashCode和equals原则

(1) hashCode

  • 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值。
  • 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode()方法的返回值也应相等。
  • 对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。

(2) equals

  • 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写hashCode(),根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是, 根据Object.hashCode()方法,它们仅仅是两个对象。
  • 因此,违反了**“相等的对象必须具有相等的散列码”。**
  • 结论:复写equals方法的时候一般都需要同时复写hashCode方法。 通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

案例:

public class Person {
    private String name;
    private int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "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;
    }

    //判断两个对象是否相等,对象是否存在,对象的name和age是否相等
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                Objects.equals(name, person.name);
    }

    //返回对象的name和age的hash值
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

测试:

public class Demo03HashSetSavePerson {
    public static void main(String[] args) {
        //创建HashSet集合存储Person
        HashSet<Person> set = new HashSet<>();
        Person p1 = new Person("红花", 20);
        Person p2 = new Person("红花", 20);
        Person p3 = new Person("红花", 21);
        Person p4 = new Person("绿叶", 21);
        //重写hashCode方法和equals方法之后
        System.out.println(p1.hashCode());
        System.out.println(p2.hashCode());

        System.out.println(p1 == p2);           //false  自定义类在重写equals方法后,==比较的是引用的是不是同一块内存地址
        System.out.println(p1.equals(p2));      //true   自定义类在重写equals方法后,equals比较的是引用的对象内容是否相同
        set.add(p1);
        set.add(p2);
        set.add(p3);
        set.add(p4);
        Iterator<Person> itr = set.iterator();
        while (itr.hasNext()) {
            System.out.println(itr.next());
        }
    }
}

结果:

image-20230809215915600

可以看到在重写hashCode和equals方法之后,hashCode相同而且equals方法返回true,则两个对象判断同一对象,不会重复出现在集合中。

5.1.3、图解原理

1.7 版本:image-20230809220158030

1.8 版本:image-20230809220409252

image-20230809220517080

1.7原理总结:

  1. 底层结构:哈希表.(数组+链表)
  2. 数组的长度默认为16,加载因子为0.75
  3. 首先会先获取元素的哈希值,计算出在数组中应存入的索引
    1. 判断该索引处是否为null
    2. 如果是null,直接添加
    3. 如果不是null,则与链表中所有的元素,通过equals方法进行比较属性值只要有一个相同就不存入,如果都不一样,就存入.

1.8原理总结:

  1. 底层结构:哈希表.(数组+链表+红黑树)
  2. 当挂在下面的元素过多,那么不利于添加,也不利于查询,所以在1.8之后
    1. 当链表长度超过8的时候,自动转换为红黑树
    2. 存储流程不变.

对于HsahSet中保存对象,一定注意正确重写equalshsahCode方法,以保证存入的对象唯一性.

👣 5.2、LinkedHashSet

  1. LinkedHashSetHashSet的子类
  2. LinkedHashSet根据元素的hashCode值来决定元素的存储位置,但它同时使用链表维护元素的次序,这是的元素看起来是以插入顺序保存的。
  3. LinkedHashSet添加性能略低于HashSet,但在迭代访问Set里的全部元素时有很好的性能。(因为底层维护了一个hash表+双向链表)
  4. LinkedHashSet底层是一个LinkedHashMap,维护的链表是一个双向链表
  5. LinkedHashSet 不允许集合元素重复

image-20230812113044725

5.2.1、LinkedHashSet的实现

对于LinkedHashSet而言,它继承与HashSet、有基于LinkedHashMap来实现。

LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可。LinkedHashSet的源代码如下:

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    /**
     * 构造一个带有指定初始容量和加载因子的新空链接哈希set。
     *
     * 底层会调用父类的构造方法,构造一个有指定初始容量和加载因子的LinkedHashMap实例。
     * @param initialCapacity 初始容量。
     * @param loadFactor 加载因子。
     */
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    /**
     * 构造一个带指定初始容量和默认加载因子0.75的新空链接哈希set。
     *
     * 底层会调用父类的构造方法,构造一个带指定初始容量和默认加载因子0.75的LinkedHashMap实例。
     * @param initialCapacity 初始容量。
     */
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    /**
     * 构造一个带默认初始容量16和加载因子0.75的新空链接哈希set。
     *
     * 底层会调用父类的构造方法,构造一个带默认初始容量16和加载因子0.75的LinkedHashMap实例。
     */
    public LinkedHashSet() {
        super(16, .75f, true);
    }

    /**
     * 构造一个与指定collection中的元素相同的新链接哈希set。
     * 
     * 底层会调用父类的构造方法,构造一个足以包含指定collection
     * 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。
     * @param c 其中的元素将存放在此set中的collection。
     */
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

在父类HashSet中,专为LinkedHashSet提供的构造方法如下,该方法为包访问权限,并未对外公开。

	/**
     * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
     * 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
     *
     * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
     * @param initialCapacity 初始容量。
     * @param loadFactor 加载因子。
     * @param dummy 标记。
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }

由上述源代码可见, LinkedHashSet 通过继承 HashSet ,底层使用 LinkedHashMap ,以很简单明了的方式来实现了其自身的所有功能。

🎉 5.3、TreeSet

TreeSetSortedSet接口实现类,TreeSet可以确保集合元素处于排序状态。

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2中排序方式:自然排序 或者 根据创建TreeSet是提供的Comparator进行排序。这取决于使用的构造方法。

TreeSet的性能比HashSet差,但是我们在需要排序的时候可以用TreeSet因为他是自然排序也就是升序。TreeSet是有序的Set集合,因此支持add()remove()get()等方法。

TreeSet的特点:

  • 有序(内容有序)
  • 不能有重复

新增呢的方法(SortedSet接口中的方法)如下:

  • Comparator comparator():返回定制排序器

  • Object fisrt():返回集合中当前的第一个(最低)元素

  • Object last():返回此集合中当前的最后一个(最高)元素

  • Object lower(Object e):返回此集合中的最大元素严格小于给定元素,如果没有这样的元素,则返回null

  • Object higher(Object e):返回集合中严格大于给定元素 e 的最小元素,即大于 e 的最小值。

    TreeSet<Integer> set = new TreeSet<>();
    set.add(1);
    set.add(3);
    set.add(5);
    set.add(7);
    
    Integer result = set.higher(4);
    System.out.println(result); // 输出 5
    
    result = set.higher(7);
    System.out.println(result); // 输出 null,因为集合中没有大于 7 的元素
    
  • Object subSet(fromElement, toElement):返回集合中处于指定范围内的元素子集。返回的子集是半开区间 [fromElement, toElement)

    TreeSet<Integer> set = new TreeSet<>();
    set.add(1);
    set.add(3);
    set.add(5);
    set.add(7);
    
    Set<Integer> subset = set.subSet(3, 6);
    System.out.println(subset); // 输出 [3, 5]
    
    subset = set.subSet(1, 4);
    System.out.println(subset); // 输出 [1, 3]
    
  • SortedSet headSet(toElement):返回的子集是原始集合中最小的元素到 toElement 之间(不包括 toElement)的所有元素。

  • SortedSet tailSet(fromElement):返回一个包含大于等于给定参数 fromElement 的所有元素的子集。

  • TreeSet 两种排序方法: 自然排序和定制排序。默认情况下, TreeSet 采用自然排序。

  • TreeSet底层使用红黑树结构存储数据,特点:有序,查询速度比List快

img

5.3.1、自然排序

  • 自然排序: TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列

  • 如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable接口。

  • 实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

  • Comparable 的典型实现:

    • BigDecimal、 BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较
    • Character:按字符的 unicode值来进行比较
    • Boolean: true 对应的包装类实例大于 false 对应的包装类实例
    • String:按字符串中字符的 unicode 值进行比较
    • Date、 Time:后边的时间、日期比前面的时间、日期大
  • 向TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。

  • 因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。

  • 对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值。如果返回值等于 0 的话表示两个对象相等。

  • 当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0。否则,让人难以理解。 equals() 和 compareTo(Object obj)两个方法的判断条件应该保持一致。

compareTo(Object obj)方法的返回值:

  • 0:相等,添加失败
  • -1:小,放到左子树
  • 1:大,放到右子树

案例:

public class User implements Comparable {

    private String name;
    private int age;

    public User() {
    }

    public User(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 "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    //按照姓名从大到小排列,年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof User){
            User user = (User)o;
//            return -this.name.compareTo(user.name);
//            int compare = -this.name.compareTo(user.name);
            int compare = this.name.compareTo(user.name);
            if(compare != 0){
                return compare;
            }else{
                return Integer.compare(this.age,user.age);
            }
        }else{
            throw new RuntimeException("输入的类型不匹配");
        }

    }

}

测试:

public class TreeSetDemo1 {

    @Test
    public void test1() {
        System.out.println("cc".compareTo("ccc"));

//        System.out.println(Integer.compare(3, 2));
    }

    public static void main(String[] args) {
        User u1 = new User("aaa", 35);
        User u2 = new User("bbb", 36);
        User u3 = new User("ccc", 83);
        User u4 = new User("ccc", 30);
        User u5 = new User("ccc", 74);
        User u6 = new User("eee", 39);
        User u7 = new User("fff", 40);
        User u8 = new User("ggg", 40);
        User u9 = new User("ggg", 40);

        TreeSet set = new TreeSet();
        set.add(u1);
        set.add(u2);
        set.add(u3);
        set.add(u4);
        set.add(u5);
        set.add(u6);
        set.add(u7);
        set.add(u8);
        set.add(u9);


        for (Object o : set) {
            System.out.println(o);
        }


    }
}

5.3.2、定制排序

  • TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator接口来实现。 需要重写compare(T o1,T o2)方法。

  • 利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。

  • 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。

  • 此时, 仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。

  • 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。

  • 定制排序器方法compare返回值

    • 0:相等,添加失败
    • -1:小,放到左子树
    • 1:大,放到右子树
public class TreeSetDemo1 {

    public static void main(String[] args) {
        User u1 = new User("aaa", 35);
        User u2 = new User("bbb", 35);
        User u3 = new User("ccc", 35);
        User u4 = new User("ccc", 30);
        User u5 = new User("ccc", 74);
        User u6 = new User("eee", 39);
        User u7 = new User("fff", 3);
        User u8 = new User("ggg", 2);
        User u9 = new User("ggg", 1);

        //定制排序器,匿名内部类
        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                User u1 = (User) o1;
                User u2 = (User) o2;
//                return -Integer.compare(u1.getAge(), u2.getAge());
                return u1.getName().compareTo(u2.getName());
            }
        };

        TreeSet set = new TreeSet(com);
        set.add(u1);
        set.add(u2);
        set.add(u3);
        set.add(u4);
        set.add(u5);
        set.add(u6);
        set.add(u7);
        set.add(u8);
        set.add(u9);


        for (Object o : set) {
            System.out.println(o);
        }


    }
}

⭐ 六、Map接口

💖 6.1、HashMap

  • 允许使用null键和null值,与HashSet一样,不保证映射的顺序。
  • 所有的key构成的集合是Set:无序的、不可重复的。所以, key所在的类要重写:equals()和hashCode()
  • 所有的value构成的集合是Collection:无序的、可以重复的。所以, value所在的类要重写: equals()
  • 一个key-value构成一个entry
  • 所有的entry构成的集合是Set:无序的、不可重复的
  • HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true,hashCode 值也相等。
  • HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true。
  1. JDK1.7前存储结构

    1. image-20230813144329179
    2. JDK 7及以前版本: HashMap是数组+链表结构(即为链地址法)
      • HashMap的内部存储结构其实是数组和链表的结合。 当实例化一个HashMap时,系统会创建一个长度为Capacity的Entry数组, 这个长度在哈希表中被称为容量(Capacity), 在这个数组中可以存放元素的位置我们称之为“桶” (bucket), 每个bucket都有自己的索引, 系统可以根据索引快速的查找bucket中的元素。
      • 每个bucket中存储一个元素, 即一个Entry对象, 但每一个Entry对象可以带一个引用变量, 用于指向下一个元素, 因此, 在一个桶中, 就有可能生成一个Entry链。而且新添加的元素作为链表的head。
      • **添加元素的过程:**向HashMap中添加entry1(key, value), 需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到), 此哈希值经过处理以后, 得到在底层Entry[]数组中要存储的位置i。 如果位置i上没有元素, 则entry1直接添加成功。 如果位置i上已经存在entry2(或还有链表存在的entry3, entry4), 则需要通过循环的方法, 依次比较entry1中key和其他的entry。 如果彼此hash值不同, 则直接添加成功。 如果hash值相同, 继续比较二者是否equals。 如果返回值为true, 则使用entry1的value去替换equals为true的entry的value。 如果遍历一遍以后, 发现所有的equals返回都为false,则entry1仍可添加成功。 entry1指向原有的entry元素。
      • HashMap的扩容: 当HashMap中的元素越来越多的时候, hash冲突的几率也就越来越高, 因为数组的长度是固定的。 所以为了提高查询的效率, 就要对HashMap的数组进行扩容, 而在HashMap数组扩容之后, 最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置, 并放进去, 这就是resize。
      • 那么HashMap什么时候进行扩容呢? 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 , 就 会 进 行 数 组 扩 容 , loadFactor 的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75, 这是一个折中的取值。 也就是说, 默认情况**下, 数组大小(DEFAULT_INITIAL_CAPACITY)为16, 那么当HashMap中元素个数超过160.75=12(这个值就是代码中的threshold值, 也叫做临界值) 的时候, 就把数组的大小扩展为 2*16=32, 即扩大一倍, 然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作, 所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
  2. JDK 8存储结构

    1. JDK 8版本发布以后: HashMap是数组+链表+红黑树实现。
    2. image-20230813144507760
    3. HashMap的内部存储结构其实是数组+链表+树的结合。 当实例化一个HashMap时, 会初始化initialCapacity和loadFactor, 在put第一对映射关系时, 系统会创建一个长度为initialCapacity的Node数组, 这个长度在哈希表中被称为容量(Capacity), 在这个数组中可以存放元素的位置我们称之为“桶” (bucket), 每个bucket都有自己的索引, 系统可以根据索引快速的查找bucket中的元素。
    4. 每个bucket中存储一个元素, 即一个Node对象, 但每一个Node对象可以带一个引用变量next, 用于指向下一个元素, 因此, 在一个桶中, 就有可能生成一个Node链。 也可能是一个一个TreeNode对象, 每一个TreeNode对象可以有两个叶子结点left和right, 因此, 在一个桶中, 就有可能生成一个TreeNode树。 而新添加的元素作为链表的last, 或树的叶子结点。
    5. HashMap扩容: 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 , 就 会 进 行 数 组 扩 容 , loadFactor 的 默 认 值(DEFAULT_LOAD_FACTOR)为0.75, 这是一个折中的取值。 也就是说, 默认情况下, 数组大小(DEFAULT_INITIAL_CAPACITY)为16, 那么当HashMap中元素个数超过160.75=12(这个值就是代码中的threshold值, 也叫做临界值)的时候, 就把数组的大小扩展为 2*16=32, 即扩大一倍, 然后重新计算每个元素在数组中的位置, 而这是一个非常消耗性能的操作, 所以如果我们已经预知HashMap中元素的个数, 那么预设元素的个数能够有效的提高HashMap的性能。
    6. HashMap树化和链化: 当HashMap中的其中一个链的对象个数如果达到了8个,此时如果capacity没有达到64,那么HashMap会先扩容解决,如果已经达到了64,那么这个链会变成树,结点类型由Node变成TreeNode类型。当然,如果当映射关系被移除后,下次resize方法时判断树的结点个数低于6个,也会把树再转为链表。
    7. 扩容和树化举个例子:
      • 初始情况下,hashmap 的capacity为16,因子为0.75。
      • 当hashmap桶内元素小于等于8,且size小于12时,不进行扩容和树化的操作。
      • 当hashmap桶内元素为9,因为capacity为16,因此不进行树化,而选择扩容,将capacity扩容为32。
      • 当hashmap桶内元素为10,因为capacity为32,因此不进行树化,而选择扩容,将capacity扩容为64。
      • 当hashmap桶内元素大于10,由于capacity已经达到64,此时进行树化。
      • 最后当HashMap中元素个数超过48(64*0.75=48),进行扩容
    • JDK1.8HashMap新变化

      • HashMap map = new HashMap();//默认情况下,先不创建长度为16的数组
      • 当首次调用map.put()时,再创建长度为16的数组
      • 数组为Node类型,在jdk7中称为Entry类型
      • 形成链表结构时,新添加的key-value对在链表的尾部(七上八下)
      • 当数组指定索引位置的链表长度>8时,且map中的数组的长度> 64时,此索引位置上的所有key-value对使用红黑树进行存储。
    1. HashMap源码中的重要常量
    • DEFAULT_INITIAL_CAPACITY : 默认16,HashMap的默认容量
    • MAXIMUM_CAPACITY :默认2^30, HashMap的最大支持容量
    • DEFAULT_LOAD_FACTOR:默认0.75, HashMap的默认加载因子
    • TREEIFY_THRESHOLD:默认8 Bucket中链表长度大于该默认值,转化为红黑树
    • UNTREEIFY_THRESHOLD: 默认6,Bucket中红黑树存储的Node小于该默认值,转化为链表
    • MIN_TREEIFY_CAPACITY: 默认64,桶中的Node被树化时最小的hash表容量。(当桶中Node的数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。)
    • table: 存储元素的数组,总是2的n次幂
    • entrySet: 存储具体元素的集合
    • size: HashMap中存储的键值对的数量
    • modCount: HashMap扩容和结构改变的次数。
    • threshold: 扩容的临界值, =容量*填充因子
    • loadFactor: 填充因子
    1. HashMap源码中的重要方法
    • resize:扩容
    • treeifyBin:树化
    • untreeify:链化
    1. 扩容
    • 默认HashMap产生,capacity默认容量0,第一次使用时,扩容成16
    • 当元素个数超过12,会扩容resize
    • 每次扩容一倍
    1. 树化
    • TREEIFY_THRESHOLD:树化的阈值,默认8

    • UNTREEIFY_THRESHOLD: 链化的阈值,默认6

    • MIN_TREEIFY_CAPACITY: 最小树化的容量,默认64,如果元素个数没有超过这个阈值(64),即使链超过8,会先进行扩容,超过64才进行树化

    • 比如下面所有元素的hashCode相同

      • 第一个元素,扩容到16
      • 第二个元素,形成链,链里面2个元素
      • …一直到链中有8个元素
      • 第9个元素,执行resize扩容到32
      • 第10个元素,执行resize扩容到64
      • 第11个元素,执行treeifyBin()方法树化
        • Node(next) 链
        • TreeNode(left,right)红黑树
    1. 链化
    • 链的数量小于6,执行untreeify方法变成链
public class User {

    private String name;
    private int age;

    public User() {
    }

    public User(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 "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

//    @Override
//    public boolean equals(Object o) {
//        System.out.println("User equals()....");
        return super.equals(o);
//        if (this == o) return true; //内存地址相同返回true
//        if (o == null || getClass() != o.getClass()) return false;
//
//        User user = (User) o;
//
//        if (age != user.age) return false;
//        return name != null ? name.equals(user.name) : user.name == name;
//    }

    /**
     *      * 注:**为什么hashCode中,用31这个数子?
     *      *
     *      * - 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
     *      * - 并且31只占用5bits,相乘造成数据溢出的概率较小。
     *      * - 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。 (提高算法效率)
     *      * - 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除! (减少冲突)
     * @return
     */
    @Override
    public int hashCode() { //return name.hashCode() + age;
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

测试:

public class TreeifyDemo1 {

    public static void main(String[] args) {
        Map map = new HashMap();
        User u1 = new User("马云", 45);
        User u2 = new User("马云", 45);
        User u3 = new User("马云", 45);
        User u4 = new User("马云", 45);
        User u5 = new User("马云", 45);
        User u6 = new User("马云", 45);
        User u7 = new User("马云", 45);
        User u8 = new User("马云", 45);
        User u9 = new User("马云", 45);
        User u10 = new User("马云", 45);
        User u11 = new User("马云", 45);
        User u12 = new User("马云", 45);

        map.put(u1, "a");
        map.put(u2, "a");
        map.put(u3, "a");
        map.put(u4, "a");
        map.put(u5, "a");
        map.put(u6, "a");
        map.put(u7, "a");
        map.put(u8, "a");
        map.put(u9, "a");
        map.put(u10, "a");
        map.put(u11, "a");
        map.put(u12, "a");


        map.remove(u12);
        map.remove(u11);
        map.remove(u10);
        map.remove(u9);
        map.remove(u8);
        map.remove(u7);
        map.remove(u6);
        map.remove(u5);
        map.remove(u4);
        map.remove(u3);
        map.remove(u2);
        map.remove(u1);


        System.out.println(map);

    }
}
  1. 哈希取模算法*
  • 调用对象的hashCode(),确定数组中的槽位,确定数组中的槽位,采用的哈希取模算法

  • put(key) -> (n-1) & hash

  • 要求容量必须是2的n次方

    • (n-1) & hash = hash % n

面试题:HashMap的容量,为什么必须是2的n次幂

image-20230813144712931

HashMap使用n-1 & hash得到槽位地址,这个运算n必须是2的n次幂,结论当容量是2的n次幂的时候(16,32…)

hash % n = (n-1) & hash,因为位运算性能高

如果初始容量不是2的n次幂,HashMap调用tableSizeFor自动转换成大于这个数最小的2的n次幂

📝 6.2、LinkedHashMap

LinkedHashSet和LinedHashMap的关系,从逻辑上这两个集合实现方式完全一致,只是LinkedHashSet使用LinkedHashMap实现,只有key,而value是一个静态的空对象

●底层使用链表实现
●有顺序(插入顺序),没有重复的集合

    public static void main(String[] args) {
        LinkedHashSet set = new LinkedHashSet();
        set.add("zzz");
        set.add("zzz");
        set.add("zzz");
        set.add("yyy");
        set.add("yyy");
        set.add("xxx");
        set.add("xxx");
        set.add("fff");
        set.add("eee");
        set.add("www");
        set.add("111");
        set.add("222");
        set.add("333");
        set.add("666");
        set.add("555");
        set.add("444");

        for (Object o : set) {
            System.out.println(o);
        }
    }

image-20230813145137265

🚜 6.3、TreeMap

  • TreeSet使用TreeMap实现,只是value使用静态空对象,只是用key实现TreeSet

  • TreeMap存储 Key-Value 对时, 需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

  • TreeSet底层使用红黑树结构存储数据

  • TreeMap 的 Key 的排序:

    • 自然排序: TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClasssCastException
    • 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口
  • TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0,1,-1

    • 0:对象相等,添加失败
    • -1:比对象小,添加到左边
    • 1:比对象打,添加到右边
  • image-20230813145425861

    1. 自然排序
    • 类实现Comparable接口,进行排序

    • public class User implements Comparable {
      
          private String name;
          private int age;
      
          public User() {
          }
      
          public User(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 "User{" +
                      "name='" + name + '\'' +
                      ", age=" + age +
                      '}';
          }
      
          //按照姓名从大到小排列,年龄从小到大排列
          @Override
          public int compareTo(Object o) {
              if(o instanceof User){
                  User user = (User)o;
      //            return -this.name.compareTo(user.name);
      //            int compare = -this.name.compareTo(user.name);
                  int compare = this.name.compareTo(user.name);
                  if(compare != 0){
                      return compare;
                  }else{
                      return Integer.compare(this.age,user.age);
                  }
              }else{
                  throw new RuntimeException("输入的类型不匹配");
              }
      
          }
      
      }
      
      
      public class TreeMapDemo1 {
      
      
          public static void main(String[] args) {
              User u1 = new User("ggg", 35);
              User u2 = new User("ggg", 35);
              User u3 = new User("ccc", 83);
              User u4 = new User("ccc", 30);
              User u5 = new User("ccc", 74);
              User u6 = new User("eee", 39);
              User u7 = new User("fff", 40);
              User u8 = new User("aaa", 40);
              User u9 = new User("bbb", 40);
      
              TreeMap map = new TreeMap();
              map.put(u1, "a");
              map.put(u2, "a");
              map.put(u3, "a");
              map.put(u4, "a");
              map.put(u5, "a");
              map.put(u6, "a");
              map.put(u7, "a");
              map.put(u8, "a");
              map.put(u9, "a");
      
      
              for (Object o : map.entrySet()) {
                  System.out.println(o);
              }
      
      
          }
      }
      
    1. 定制排序
    • 使用Comparator,插入TreeSet定制排序器
    • 定制排序器和自然排序都存在是,定制优先
  • public class User implements Comparable {
    
        private String name;
        private int age;
    
        public User() {
        }
    
        public User(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 "User{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        //按照姓名从大到小排列,年龄从小到大排列
        @Override
        public int compareTo(Object o) {
            if(o instanceof User){
                User user = (User)o;
    //            return -this.name.compareTo(user.name);
    //            int compare = -this.name.compareTo(user.name);
                int compare = this.name.compareTo(user.name);
                if(compare != 0){
                    return compare;
                }else{
                    return Integer.compare(this.age,user.age);
                }
            }else{
                throw new RuntimeException("输入的类型不匹配");
            }
    
        }
    }
    
  • public class TreeMapDemo1 {
    
    
        public static void main(String[] args) {
            User u1 = new User("ggg", 35);
            User u2 = new User("ggg", 35);
            User u3 = new User("ccc", 83);
            User u4 = new User("ccc", 30);
            User u5 = new User("ccc", 74);
            User u6 = new User("eee", 39);
            User u7 = new User("fff", 40);
            User u8 = new User("aaa", 40);
            User u9 = new User("bbb", 40);
    
            Comparator com = new Comparator() {
                @Override
                public int compare(Object o1, Object o2) {
                    if(o1 instanceof User && o2 instanceof User){
                        User u1 = (User) o1;
                        User u2 = (User) o2;
    
                        return -Integer.compare(u1.getAge(), u2.getAge());
    
    //                    int compare = u1.getName().compareTo(u2.getName());
    //                    if(compare != 0){
    //                        return compare;
    //                    }else{
    //                        return Integer.compare(u1.getAge(), u2.getAge());
    //                    }
                    }else{
                        throw new RuntimeException("输入的类型不匹配");
                    }
                }
            };
    
            TreeMap map = new TreeMap(com);
            map.put(u1, "a");
            map.put(u2, "a");
            map.put(u3, "a");
            map.put(u4, "a");
            map.put(u5, "a");
            map.put(u6, "a");
            map.put(u7, "a");
            map.put(u8, "a");
            map.put(u9, "a");
    
    
            for (Object o : map.entrySet()) {
                System.out.println(o);
            }
    
    
        }
    }
    

🏭 6.4、HashTable

  • Hashtable是个古老的 Map 实现类, JDK1.0就提供了。不同于HashMap,Hashtable是线程安全的。
  • Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询速度快,很多情况下可以互用。
  • 与HashMap不同, Hashtable 不允许使用 null 作为 key 和 value
  • 与HashMap一样, Hashtable 也不能保证其中 Key-Value 对的顺序
  • Hashtable判断两个key相等、两个value相等的标准, 与HashMap一致。
public class HashTableDemo1 {

    public static void main(String[] args) {
        Hashtable map = new Hashtable();
        map.put("aaaa", 11);
        map.put("aaaa", 1111);
        map.put("bbbb", 22);
        map.put("cccc", 33);
        map.put("dddd", 44);
        map.put("eeee", 55);
        map.put("eeee", 5555);
        map.put("ffff", 666);
        map.put("gggg", 666);
        map.put("hhhh", 666);
        map.put("3333", 666);
        map.put("4444", 666);
        map.put("1111", 666);
        map.put("2222", 666);
//        map.put(null, 666); //不能存null

        for (Object key : map.entrySet()) {
            System.out.println(key + " " + map.get(key));
        }


    }
}

🎉 6.5、Properties

  • Properties 类是 Hashtable 的子类,该对象用于处理属性文件
  • 由于属性文件里的 key、 value 都是字符串类型,所以 Properties 里的 key和 value 都是字符串类型
  • 存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法

user.dir = 项目目录

username=root
password=123456
jdbc.url=jdbc:mysql://localhost:3306/test
jdbc.driver=com.mysql.driver.Driver
public class PropertiesDemo1 {

    public static void main(String[] args) throws IOException {
        Properties properties = new Properties();
//        FileInputStream in  = new FileInputStream("F:\\work\\lxs\\49_java_basic\\01-Java-基础\\9-集合\\code\\java-demo9\\jdbc.properties");
        //文件在user.dir目录下,可以使用下面相对目录
        FileInputStream in  = new FileInputStream("jdbc.properties");
        properties.load(in);

        System.out.println(properties.getProperty("username"));
        System.out.println(properties.getProperty("password"));
        System.out.println(properties.getProperty("jdbc.url"));
        System.out.println(properties.getProperty("jdbc.driver"));
        in.close();

    }
}

💬 七、Collections工具类

  • Collections 是一个操作 Set、 List 和 Map 等集合的工具类

  • Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

  • 排序操作: (均为static方法)

    • reverse(List): 反转 List 中元素的顺序
    • shuffle(List): 对 List 集合元素进行随机排序
    • sort(List): 根据元素的自然顺序对指定 List 集合元素按升序排序
    • sort(List, Comparator): 根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
    • swap(List, int, int): 将指定 list 集合中的 i 处元素和 j 处元素进行交换
  • 查找、替换

    • Object max(Collection): 根据元素的自然顺序,返回给定集合中的最大元素
    • Object max(Collection, Comparator): 根据 Comparator 指定的顺序,返回给定集合中的最大元素
    • Object min(Collection)
    • Object min(Collection, Comparator)
    • int frequency(Collection, Object): 返回指定集合中指定元素的出现次数
    • void copy(List dest,List src):将src中的内容复制到dest中
    • boolean replaceAll(List list, Object oldVal, Object newVal): 使用新值替换List 对象的所有旧值
  • Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题

    • image-20230813150120602
public class CollectionsDemo1 {

    @Test
    public void test1() {
        List list = new ArrayList();

        list.add("zzz");
        list.add("xxx");
        list.add("yyy");
        list.add("mmm");
        list.add("nnn");
        list.add("aaa");
        list.add("aaa");
        list.add("111");
        list.add("111");
        list.add("222");
        list.add("333");
        list.add("444");
//        list.add(555);
//        list.add(666);
//        list.add(new Date());



        System.out.println(list);

        Collections.reverse(list); //反转
        System.out.println("reverse =" + list);

        Collections.shuffle(list); //随机排序
        System.out.println("shuffle =" + list);

        //自然排序必须类型一致
        Collections.sort(list); //自然排序
        System.out.println("sort =" + list);

        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                String s1 = (String) o1;
                String s2 = (String) o2;
                return -s1.compareTo(s2);
            }
        };

        Collections.sort(list, com); //定制排序
        System.out.println("sort =" + list);

        Collections.swap(list, 0, 1); //0,1交换
        System.out.println("sort =" + list);

        System.out.println("max=" + Collections.max(list)); //自然排序最大

        System.out.println("frequency=" + Collections.frequency(list, "aaa")); //自然排序最大

        List syncList = Collections.synchronizedList(list);  //返回线程安全的集合
        syncList.add("666");
    }

}

http://lihuaxi.xjx100.cn/news/1442801.html

相关文章

模拟实现消息队列(以 RabbitMQ 为蓝本)

目录 1. 需求分析1.1 介绍一些核心概念核心概念1核心概念2 1.2 消息队列服务器&#xff08;Broker Server&#xff09;要提供的核心 API1.3 交换机类型1.3.1 类型介绍1.3.2 转发规则&#xff1a; 1.4 持久化1.5 关于网络通信1.5.1 客户端与服务器提供的对应方法1.5.2 客户端额外…

数学分析:曲线曲面积分

这一章还是很重要的&#xff0c;可以看到为什么dt1^dt2和dt1dt2是一样的。 可以看到&#xff0c;核心还是黎曼和&#xff0c;我们把两种微分的黎曼和都列出来&#xff0c;并且证明两个相等&#xff0c;即可。 这里要注意&#xff0c;微分形式的积分&#xff0c;在黎曼和的情况…

java中函数式接口、Stream流、方法引用、junit单元测试、反射、注解

函数式接口&#xff1a; 在java中有且仅有一个抽象方法的接口称为函数式接口&#xff0c;但是可以包含其它的默认的或静态的方法。 格式&#xff1a; 修饰符 interface 接口名称 {public abstract 返回值类型 方法名称(可选参数);// 其他非抽象方法 }函数式接口&#xff1a;…

【AI】p54-p58导航网络、蓝图和AI树实现AI随机移动和跟随移动、靠近玩家挥拳、AI跟随样条线移动思路

p54-p58导航网络、蓝图和AI树实现AI随机移动和跟随移动、靠近玩家挥拳、AI跟随样条线移动思路 p54导航网格p55蓝图实现AI随机移动和跟随移动AI Move To&#xff08;AI进行移动&#xff09;Get Random Pointln Navigable Radius&#xff08;获取可导航半径内的随机点&#xff09…

python基础环境建设(pip、anaconda)

1.pip 配置文件路径&#xff1a; centos&#xff1a;~/.pip/pip.conf windows: C:\Users\admin\AppData\Roaming\pip\pip.ini 文件内容&#xff1a; [global] index-url http://IP/repository/pypi-tsinghua/simple trusted-hostIP今天centos7.9、python3.6环境 pip install…

pytorch从python转 c++涉及到的数据保存加载问题;libtorch

pytorch 从python 转 c涉及到的数据保存加载问题 1. torch.nn.Module 保存 state_dict 无法被 c访问&#xff0c;只能转化为 python字典 python代码 model ThreeLayer_FCNN_Net() model.load_state_dict(ret_load) w {k: v for k, v in model.state_dict().items()} torch…

影视站用什么cms好?

影视站是指用于提供电影、电视剧、综艺等视频资源的网站。由于影视站需要频繁更新大量的内容&#xff0c;因此使用一个好的内容管理系统&#xff08;CMS&#xff09;非常重要。以下是几个受欢迎的影视站CMS的介绍。最新下载地址&#xff1a;roulang WordPress WordPress是目前…

uniapp input输入框placeholder文本右对齐

input输入框placeholder文本右对齐 给input标签加上placeholder-class&#xff0c;这个是给placeholder设置样式&#xff0c;右对齐这就是text-align:right;字体颜色之类依次编辑即可。