目录

Collection(集合)

集合是存储数据的一个容器,数组就是集合的一种。

不同集合实现原理对应不同数据结构(Data Structure),常见数据结构有:Array、Link、Set、Queue、Map、Tree、Heap,这些数据结构会对应不同数据使用场景,各有优缺点。而集合已经实现这些数据结构并提供很多常用方法,只要知道什么情况下用什么集合,集合里常见操作怎么用即可。

Collection 简介

常用的集合需要掌握 Collection 下两个接口 List 和 Set 名字也是对应同名数据接口:

classDiagram class iterator { <<interface>> +iterator() } class Collection { <<interface>> } class List { <<interface>> } class Set { <<interface>> } class SortedSet { <<interface>> } iterator <|-- Collection Collection <|-- List List <|.. ArrayList List <|.. Vector List <|.. LinkedList Collection <|-- Set Set <|.. HashSet HashSet <-- LinkedHashSet Set <|-- SortedSet SortedSet <|.. TreeSet

虚线是实现关系,实线是继承关系。

List

List 这种数据结构存储特点是带有索引有序存储,索引从 0 开始,遍历时先入先出,后入后出,换句话说是按照存入顺序输出,和数组不同的是它没容量限制。

java.util.List 接口有以下类实现:

  • java.util.ArrayList,底层采用数组(也叫顺序表)这种数据结构实现,非线程安全。增删元素效率低,查找元素效率高。
  • java.util.Vector,和 ArrayList 一样使用数组实现,但是有 synchronized 修饰,是线程安全的。一般用的少。
  • java.util.LinkedList,底层采用双向链表数据结构。非线程安全。增删元素效率高。

Set

Set 数据结构存储的数据是无序、不重复的。无序是指数据存入没有按顺序存储不像 List 有索引,因此取出的顺序可能不一致,不重复是指存入的元素不能相同。

java.util.Set 接口有以下常用实现:

  • java.util.HashSet,调用 HashSet 无参构造方法时,其实是在创建 HashMap 对象,所有数据存入实际是存到 HashMap Key 中,而 HashMap 底层数据结构是哈希表(Hash Table)。非线程安全。

    • java.util.LinkedHashSet 是 java.util.HashSet 子类,底层是调的 LinkedHashMap,对 HashSet 做了扩展,加了个 Linked,相比 HahSet 遍历效率更高。
  • java.util.SortedSet 接口继承自 java.util.Set 有以下常用实现:

    java.util.SortedSet 由于继承 java.util.Set 那么自然也是无需不可重复,它和 Set 区别在于,放入 SortedSet 集合里的数据会按照大小自动排序,也称作可排序集合。

    • java.util.TreeSet 是具体实现类,创建 TreeSet 时无参构造方法是在创建 TreeMap 对象,所有数据存入实际是存到 TreeMap Key 部分,而 TreeMap 底层数据结构是二叉树(Binary Tree),再具体点是红黑树。

Map 简介

Map 集合 和前面 List、Set 完全不同,Map 它不继承自 Collection,是 Key-Value 这种键值对方式存数据,也就是 Key 和 Value 都要存东西,存完调的时候通过 Key 来调 Value,有一点是 Key 不能重复,不然哪知道调用的是哪个 Value。

java.util.Map 接口有以下常用实现:

  • java.util.HashMap,底层数据结构是哈希表(Hash Table),非线程安全。数据可以存 null。

    • java.util.LinkedHashMap,继承自 java.util.HashMap,相比父类 HashMap 多了个 prev 和 next 引用,在遍历时可以按照添加数据的顺序进行输出。频繁遍历数据效率比 HashMap 高。
  • java.util.Hashtable,底层数据结构是哈希表(Hash Table),方法有 synchronized 修饰,是线程安全的。一般用的少。数据存储不能 null。

    • java.util.Properties,继承自 java.util.Hashtable,叫属性类,Properties 特点是 Key 和 Value 只能存 String 类型,如果存 null 就抛异常。
  • java.util.SortedSet,此接口继承自 java.util.Map 有以下常用实现:

    SortedSet 集合中的 Key 可以根据大小自动排序,称作可排序集合。

    • java.util.TreeMap,这里的 TreeMap 和前面 Set 中的 TreeMap 指的是同一个内容,这里再重复下 TreeMap 底层数据结构是二叉树(Binary Tree)。可以实现排序效果。
classDiagram class Map { <<interface>> } class SortedMap { <<interface>> } Map <|.. HashMap HashMap <|-- LinkedHashMap Map <|.. Hashtable Hashtable <|-- Properties Map <|-- SortedMap SortedMap <|.. TreeMap

总结

LIst 集合,存储数据有序排列,先存进去的数据遍历时先拿出来。

Set 集合,存储数据位置无序且数据不可重复。SortedSet 集合则支持自动排序,其余规则和 Set 集合一致。

Map 集合是通过 Key-Value 存储数据。

Collection 接口常用方法练习

Collection 位于 java.util.Collection,所有集合都会放在 java.util.* 包下。

public interface Collection<E> extends Iterable<E> { ... }

可以看到 Collection 是一个接口,<E> 就是泛型,并继承自 Iterable,在 IDEA 顺着点进去 public interface Iterable 发现也是个接口,这说明 Collection 是可迭代的。

根据 Collection 源码来看,有一系列方法,下面是常使用的方法:

  • int size(),返回集合中有几个元素。
  • boolean isEmpty(),看集合是不是空的,本质上就是看集合内元素个数是否为 0 。
  • boolean contains(Object o),调用 Object o 的 equals() 方法对比集合中每个元素是否匹配。
  • boolean containsAll(Collection<?> c),判断 c 这个集合是不是在在当前集合中。
  • Iterator<E> iterator(),用来遍历集合。
  • boolean add(E e),向集合增加一个元素。
  • boolean addAll(Collection<? extends E> c),将一个新集合里每一个元素添加到当前集合中。
  • boolean remove(Object o),从集合移除元素 o。
  • boolean removeAll(Collection<?> c),移除当前集合和传入的集合 c 的交集。删除俩集合中一样的数据。不一样的保留下来。
  • boolean retainAll(Collection<?> c),移除当前集合和传入的集合 c 的差集。删除俩集合中不一样的数据,一样的保留下来。
  • void clear(),清空集合元素。
  • Object[] toArray(),将集合转换为 Object 数组。

Collection 接口方法都由子类实现,学会一个实现类就都会啦,这里拿 ArrayList 做示例。

创建 CollectionTest01.java:

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

public class CollectionTest01 {
    public static void main(String[] args) {
        Collection i = new ArrayList();

        // boolean add()
        System.out.println("添加元素:");
        // 这里添加的基本数据类型本质上是编译器做了自动装箱(Java 1.5 添加),等同于 i.add(Integer.valueOf(1))。
        // 因为集合存的是引用类型的内存地址,而不是对象本身。其他基本数据类型也有对应包装类。
        System.out.println("\t" + i.add(1));
        System.out.println("\t" + i.add(new String("STRING")));
        Integer iz = Integer.valueOf(1);
        System.out.println("\t" + i.add(iz));

        // int size()
        // boolean addAll(Collection<? extends E> c)
        System.out.println("元素个数 addall 添加前个数:");
        System.out.println("\t" + i.size());
        Collection i1 = new ArrayList();
        i1.add("i11");
        i1.add("i12");
        i1.add("i12");
        i.addAll(i1);
        System.out.println("元素个数 addall 添加后:" + "\t" + i);

        // boolean contains(Object o)
        System.out.println("是否包含对象:");
        System.out.println("\t" + i.contains(1));
        System.out.println("\t" + i.contains(12));

        // boolean containsAll(Collection<?> c)
        System.out.println("是否包含 i1 集合?\n\t" + i.containsAll(i1));

        // boolean remove(Object o)
        System.out.println("移除元素:");
        System.out.println("\t" + "移除成功 " + i.remove(1));
        System.out.println("\t" + "不包含此元素 " + i.contains(1));
        System.out.println("\t" + "元素个数为 " + i.size());

        // boolean removeAll(Collection<?> c)
        Collection i2 = new ArrayList();
        i2.add("i11");
        i2.add("i12");
        i2.add("i12");
        i2.add("i13");
        Collection i3 = new ArrayList();
        i3.add("i11");
        i3.add("i12");
        i3.add("i12");
        System.out.println("移除集合中相同数据:");
        System.out.println("\tremoveAll 删除前集合:" + i2);
        System.out.println("\t要删除的集合:" + i3);
        i2.removeAll(i3);
        System.out.println("\tremoveAll 删除后集合:" + i2);

        // boolean retainAll(Collection<?> c)
        Collection i4 = new ArrayList();
        i4.add("i11");
        i4.add("i12");
        i4.add("i12");
        i4.add("i13");
        Collection i5 = new ArrayList();
        i5.add("i11");
        i5.add("i12");
        i5.add("i12");
        System.out.println("移除集合中不同数据:");
        System.out.println("\tremoveAll 删除前集合:" + i4);
        System.out.println("\t要删除的集合:" + i5);
        i4.retainAll(i5);
        System.out.println("\tremoveAll 删除后集合:" + i4);

        // boolean isEmpty()
        System.out.println("看集合是否为空:");
        System.out.println("\t" + i.isEmpty());

        // clear()
        i.clear();
        System.out.println("元素清空:");
        System.out.println("\t" + i.size());

        // Object[] toArray()
        System.out.println("将集合 i5 转换为数组:");
        Object[] collectionArray = i5.toArray();
        for (Object obj : collectionArray) {
            System.out.println("\t" + obj);
        }
    }
}

运行输出:

添加元素:
    true
    true
    true
元素个数 addall 添加前个数:
    3
元素个数 addall 添加后:    [1, STRING, 1, i11, i12, i12]
是否包含对象:
    true
    false
是否包含 i1 集合?
    true
移除元素:
    移除成功 true
    不包含此元素 true
    元素个数为 5
移除集合中相同数据:
    removeAll 删除前集合:[i11, i12, i12, i13]
    要删除的集合:[i11, i12, i12]
    removeAll 删除后集合:[i13]
移除集合中不同数据:
    removeAll 删除前集合:[i11, i12, i12, i13]
    要删除的集合:[i11, i12, i12]
    removeAll 删除后集合:[i11, i12, i12]
看集合是否为空:
    false
元素清空:
    0
将集合 i5 转换为数组:
    i11
    i12
    i12

contains/remove/removeAll 方法详解

Collection.contains(Object o)Collection.remove(Object o)boolean removeAll(Collection<?> c) 本质上是调用传入 Object oeuqals() 方法去对这个集合里每个元素进行循环比较,比较成功就停止循环,contains 成功返回布尔值,remove 匹配成功就停止继续匹配做删除处理,removeAll 则是拿着 Collection<?> c 集合对当前所有元素进行匹配成功直到 c 元素都匹配完成。

所以需要对查找的对象 equals() 方法重写,得出正确结果,不然调用的是 Object 类中的 euqals() 方法是比较内存了。

创建 CollectionTest02.java:

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

public class CollectionTest02 {
    public static void main(String[] args) {
        Integer int1 = Integer.valueOf("123123");
        Integer int2 = Integer.valueOf("123123");;
        Collection collection = new ArrayList();
        collection.add(int1);
        System.out.println(collection.contains(int2));
    }
}

运行结果:

true

collection.contains(int2) 调用 int2 的 equals() 方法,而 Integer 重写过 equals() 固然比较的是值。所以结果返回 true。

创建 CollectionTest03.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Objects;

public class CollectionTest03 {
    public static void main(String[] args) {
        TestClass testClass1 = new TestClass(123123, "stz");
        TestClass testClass2 = new TestClass(123123, "stz");
        TestClass testClass3 = new TestClass(123123, "stz");
        Collection collection = new ArrayList();
        collection.add(testClass1);
        System.out.println(collection.contains(testClass2));
    }
}


class TestClass {
    private String testzz;
    private int int1;

    public TestClass(int int1, String testzz) {
        this.testzz = testzz;
        this.int1 = int1;
    }

    public boolean equals(Object o) {
        // 如果传入的对象是当前对象本身直接就是 true
        if (this == o) return true;
        // 如果不是当前对象本身又不是子类返回 false
        if (!(o instanceof TestClass)) return false;
        // 是当前子类对象,强转为当前类型
        TestClass testClass = (TestClass) o;
        // 比较当前类 int1 和传进来的对象 int1 数值是不是一样,Objects.equals(testzz, testClass.testzz)
        // 接着继续比较 private String testzz 和传进来的对象的 testzz 是不是一样
        // 因为 Objects.equals 方法首先比较俩 testzz 内存地址是不是一样,如果是就返回 true,不是就调用 private String testzz 的
        // equal方法,由于 private String testzz 是 String 类型所以调的是 String 对象的 euqals 方法,最终得到 true。
        return int1 == testClass.int1 && Objects.equals(testzz, testClass.testzz);
    }
}

运行返回:

true

如果把 euqals() 替换为下面方法就会返回 false。这说明了确实调用的对象的 contains()。

public boolean equals() {
    return false;
}

继续在 CollectionTest03.java main 方法中添加 remove 方法:

TestClass testClass4 = new TestClass(123123, "stz");
collection.add(testClass2);
System.out.println("删除前容量:" + collection.size());
collection.remove(testClass3);
System.out.println("删除后容量:" + collection.size());

运行返回:

删除前容量:3
删除后容量:2

从结果来看 testClass4 确实可以删除相对值的对象。

进到 remove() 方法源码也可以看到是调用实参对象的 equals(),collection.remove(testClass3); 调用的是 testClass3 对象 equals() 比较 collection 集合每个元素,只要比较成功一个立马停止后续比较动作并做删除处理(这里删除是将集合元素设置为 null)。

而是否比较成功就要看 testClass3 的 equals() 方法有没经过重写,一般来说经过重写后就算是两个不同对象只要值一样就返回 true。

Collection 遍历集合元素

所有 Collection 都是要实现 Iterator 接口的,要获取每个元素通过集合 iterator() 方法返回 Iterator 对象来遍历 List、Set 集合,Map 集合不支持因为没有继承。

创建 CollectionTest04.java 添加如下代码:

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

public class CollectionTest04 {
    public static void main(String[] args) {
        // Iterator<E> iterator()
        Collection z = new ArrayList();
        z.add("1s");
        z.add(new Object());
        z.add(2);

        System.out.println("迭代集合方式1-手动:");
        Iterator iterator = z.iterator();
        if (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.println("\t" + obj);
        }

        // 推荐写法 1
        System.out.println("迭代集合方式2-while:");
        while (iterator.hasNext()) {
            System.out.println("\t" + iterator.next());
        }

        System.out.println("迭代集合方式3-for:");
        Iterator iterator1 = z.iterator();
        for (int i = 0; i < z.size(); i++) {
            System.out.println("\t" + iterator1.next());
        }

        // 推荐写法 2,forEach 本质上也是调用迭代器来获取元素,可以下断点证明。
        System.out.println("迭代集合方式4-forEach:");
        for (Object obj : z) {
            System.out.println("\t" + obj);
        }
    }
}

运行输出:

迭代集合方式1-手动:
    1s
迭代集合方式2-while:
    java.lang.Object@6bf256fa
    2
迭代集合方式3-for:
    1s
    java.lang.Object@6bf256fa
    2
迭代集合方式4-forEach:
    1s
    java.lang.Object@6bf256fa
    2

明显看到是通过 iterator() 方法来获得 Iterator 对象,iterator 变量对象有三个元素,使用 “迭代集合方式 1” 手动取出一个后再获取就只剩俩了,再通过 while 循环方式继续按照顺序取第 2、3 俩元素,此时要是再使用 iterator.next() 就会报 NoSuchElementException 异常,因为元素已经全部取出,再没元素可访问,必须要重新获取迭代器对象循环获取。

整个 while 循环迭代元素的原理是,获取元素时 hasNext() 首先判断当前游标下一个元素是否存在。

迭代器执行过程1.png

存在就调用 next() 获取元素。游标首先在元素前面,调用 next() 游标下移并返回元素,hasNext() 就是用来做范围判断的,看还有没有下一个元素。

迭代器执行过程2.png

使用迭代器 remove() 方法要注意,只能使用迭代器对象的 remove() 而不是集合对象的 remove(),

创建 CollectionTest05.java 添加下面代码:

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

public class CollectionTest05 {
    public static void main(String[] args) {
        Collection z = new ArrayList();
        z.add("1s");
        z.add(new Object());
        z.add(2);

        System.out.println("迭代集合方式 3:");
        Iterator iterator3 = z.iterator();
        while (iterator3.hasNext()) {
            Object objElement = iterator3.next();
            z.remove(objElement);
            System.out.println("\t" + objElement);
        }

    }
}

运行结果:

迭代集合方式 3:
    1s
Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1043)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:997)
    at learnCollection.CollectionTest05.main(CollectionTest05.java:17)

在第二次循环出现异常。这是集合发生改变时需要重新获取迭代器对象,因为迭代器是指向集合元素的镜像,当第二次循环获取元素时发现迭代器与集合元素对不上就抛错。

使用迭代器本身的 remove 方法去删指当前 next() 指向的元素则不会出现问题,因为每次操作先把迭代器中的元素删除,之后会再去集合里删对应元素。

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

public class CollectionTest05 {
    public static void main(String[] args) {
        Collection z = new ArrayList();
        z.add("1s");
        z.add(new Object());
        z.add(2);

        System.out.println("迭代集合方式 3:");
        Iterator iterator3 = z.iterator();
        while (iterator3.hasNext()) {
            Object objElement = iterator3.next();
            iterator3.remove();
            System.out.println("\t" + objElement + " 被删除");
        }

        System.out.println("集合内容:" + z);
    }
}

运行返回:

迭代集合方式 3:
    1s 被删除
    java.lang.Object@13969fbe 被删除
    2 被删除
集合内容:[]

List 接口常用方法练习

常用方法:

  • void add(int index, E element),默认是直接在数组末尾插入元素,如果给指定索引就将其他数据后移在指定位置插入。
  • boolean addAll(Collection<? extends E> c),把集合 c 里所有元素添加到当前集合中。
  • E get(int index),返回元素。
  • int indexOf(Object o),返回元素第一次出现的索引。
  • int lastIndexOf(Object o),返回元素最后一次出现的索引。
  • E remove(int index),删除 List 指定索引元素并返回旧元素。默认传入 index 的是索引,如果要删除对象就 new Integer(1)
  • E set(int index, E element),替换指定索引元素替换并返回旧元素。
  • List<E> subList(int fromIndex, int toIndex),从当前集合中,获取从 fromIndex 开始到 toIndex 之前元素(左闭右开)。

创建 ListTest01.java:

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

public class ListTest01 {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add('a');
        list.add('a');
        list.add(0, 1);

        System.out.println("遍历 List:");
        for (int i = 0; i < list.size(); i++) {
            System.out.println("\t" + list.get(i));
        }

        List list1 = new ArrayList();
        list1.add(11);
        list1.add(22);
        list1.add(33);
        list1.add(44);
        list.addAll(list1);
        System.out.println("addall 集合:" + list);

        System.out.println("sublist 截取集合部分元素:" + list.subList(5, 7));

        System.out.println("'a' 第一次出现的索引位置:" + list.indexOf('a'));
        System.out.println("'a' 最后最后一次出现的索引位置:" + list.lastIndexOf('a'));
        System.out.println("重新设置索引为0的元素为数值0并返回旧元素:" + list.set(0, 0));
        System.out.println("索引0元素是:" + list.get(0));
        System.out.println("删除位于索引0的元素并返回旧元素:" + list.remove(0));
        System.out.println("遍历 List:");
        for (int i = 0; i < list.size(); i++) {
            System.out.println("\t" + list.get(i));
        }
    }
}

运行输出:

遍历 List:
    1
    a
    a
addall 集合:[1, a, a, 11, 22, 33, 44]
sublist 截取集合部分元素:[33, 44]
'a' 第一次出现的索引位置:1
'a' 最后最后一次出现的索引位置:2
重新设置索引为0的元素为数值0并返回旧元素:1
索引0元素是:0
删除位于索引0的元素并返回旧元素:0
遍历 List:
    a
    a
    11
    22
    33
    44

ArrayList

ArrayList 构造方法:

  • ArrayList()
  • ArrayList(int initialCapacity)
  • ArrayList(Collection<? extends E> c)

ArrayList 底层实现是数组,类型为 Object,Java8 里用默认无参构造方法初始化时,首先是个空数组,它的容量是在第一次调用 add() 初始化 10 个元素。

随着 add() 不断添加,一旦当前数组元素个数等数组长度就会自动扩容数组整体长度 1.5 倍。原理就是讲当前长度进行位移 >> 1,这样就能得到原有长度 50%,或者说 1.5 倍,紧接着使用 Array.copyOf() 去扩容。所以使用上要能在构造方法传入长度是确定最好的,避免多次扩容造成空间浪费。

另一个使用点是构造方法可以传入集合,相当于把集合作为元素存进数组。

创建 ArrayList01.java:

import java.util.ArrayList;
import java.util.HashSet;

public class ArrayListTest01 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();

        ArrayList arrayList1 = new ArrayList(20);


        HashSet hashset = new HashSet();
        hashset.add(1);
        hashset.add(2);
        hashset.add(3);

        ArrayList arrayList2 = new ArrayList(hashset);
        System.out.println(arrayList2.size());

    }
}

运行输出:

3

LinkedList

底层采用双向链表数据结构。

Singly linked list(单向链表)

链表由节点组成,节点分为 data 和 next 两部分,data 用于存储数据,next 是 下一个节点的内存地址。一堆节点形成单链,串起来像糖葫芦。

单向链表结构图.png

链表和数组不同,数组是一整块连续内存,链表是哪里空的就用哪的内存。

它俩再查找数据方式也不一样,假设我需要查末尾节点,那么需要从头节点查起一步步通过 Next 来获取下一个节点直到末尾节点的 Next 是 null 就停止表明没有下一个节点。对比数组则没此问题,因为数组是整块内存地址都是数值递进的,只要用数组起始地址计算立马就能得到指定位置的内存地址。如果说用 ArrayList 向末尾添加元素也没问题,效率并不低。

对比起来 LinkedList 检索上效率低,但增/删效率高,不用像数组一样增/删元素需要讲整个数组元素向前移动。

比如要在头节点后新增节点,需要先把头节点 Next 取消指向,这相当于删,删完后再将新节点赋值到头节点 Next,新节点中的 Next 指向头节点原来删除的 Next。当然这没考虑头节点前、尾节点后插入情况。

单向链表增删结构.png

Doubly linked list(双向链表)

双向链表比单向链表多了个 prev 指向前一个节点内存地址。

双向链表结构.png

和单项链表增删一样。在头节点后新增节点需要将头节点 Next 指向新节点,头节点下一个节点的 Prev 也要指向新节点,最后将新节点的 Prev 指向头节点,Next 指向原来头节点删掉的 Next 节点。

双向链表增删结构.png

add() 源码分析(待补充)

新增节点追加到链表尾部

remove() 源码分析(待补充)

默认移除 first 节点。

Vector

调用无参构造方法默认初始化为 10 个元素,add() 超过 10 自动扩容至原容量 2 倍。

所有方法由 synchronized 修饰,由线程同步是线程安全的。

Set 接口常用方法练习

Set 里没有什么新增方法,都是 Collection 中的方法。只是遍历时要注意没有索引,因此不能用普通 for 循环,都是通过迭代器和增for-each 遍历。

HashSet

add() 方法详解

Java7 中底层是数组+链表结构(Java8里是数组+链表+红黑树),就是数组里每个对象是链表。HashSet 初始化 后在 add 元素时数组默认初始化长度是 16。

元素不可重复:

  1. 对要添加进数组的元素调用自身 hashcode() 方法计算出唯一数值,接着调用哈希算法传入唯一数值计算出要存放数组的索引位置。
  2. 接着去看对应索引有没对象,没有直接存入。
    1. 如果对应索引有元素就先看要存入的元素和索引上的链表上每个节点 (链表可能有多节点)hash 值是不是一样,不一样说明不是相同元素,那么直接链表 last 节点的 next 属性指向将要添加的元素。
    2. 如果 hash 值一样就调要添加的元素 equals 方法比较索引对应链表上每个节点(链表可能有多个节点),如果为 true 说明俩对象就一样,那么就不进行添加,为 false 说明这是两个对象,既然索引已经有链表元素,那么就使用链表 last 节点的 next 指向要添加的元素。

元素存放无序:每次存放的索引位置通过 hash 算法得出,不像数组按照顺序一个个排队一样的添加进去。

HashSet add方法执行流程图.png

所以往 Set 中添加的对象一定要重写 hashcode 和 equals 方法,以避免无需、重复失效。如果是自重写这俩方法(其中hashCode IDEA 生成最好,不要自己写,全是 bug),要注意相同对象 equals 结果是 true,那 hashcode 产生的值也要一样。

LinkedHashSet

就在 HashSet 基础上添加了个 LInked,数组内元素单链变双链,对每个添加进链表的节点加上 prev 和 next 俩引用。有这俩引用就可以按照数据存入顺序进行遍历输出,整体遍历起来比 HashSet 效率高。

TreeSet

TreeSet 实例化时本质上也是调用 TreeMap 构造方法。而 add 方法去添加元素其实也是调用 TreeMap put 方法,只不过 value 部分被放上一个 Object 对象,不去使用。

创建 TreeSetTest01.java:

import java.util.TreeSet;

public class TreeSetTest01 {
    public static void main(String[] args) {
        TreeSet treeset = new TreeSet();
        treeset.add(123);
        treeset.add(1);
        treeset.add(456);
        treeset.add(2);
        System.out.println(treeset);
    }
}

运行输出

[1, 2, 123, 456]

add(E e) 能够排序的原因是被添加的元素 e 已经实现了 Comparable 接口 public int compareTo(T o) 方法,是在此方法内定义了排序规则。String 类型比较规则是按照首字母 ASCII 大小升序排序,Integer、Double、..... 等包装类也是如此。

如果添加不同类型对象那么就会报错,因为两种不同对象比较规则也会不同,排序最好是对同一种对象进行操作排序。

创建 TreeSetTest02.java:

import java.util.TreeSet;

public class TreeSetTest02 {
    public static void main(String[] args) {
        TreeSet treeset = new TreeSet();
        treeset.add(123);
        treeset.add("1");
        /*
        多个不同对象不能同时比较。会抛错:
        Exception in thread "main" java.lang.ClassCastException:
        class java.lang.Integer
        cannot be cast to class
        java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
         */
    }
}

运行输出:

Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
    at java.base/java.lang.String.compareTo(String.java:125)
    at java.base/java.util.TreeMap.put(TreeMap.java:566)
    at java.base/java.util.TreeSet.add(TreeSet.java:255)
    at learnCollection.TreeSetTest02.main(TreeSetTest02.java:9)

传入自定义类型也是无法比较,因为当前类型不是 Comparable 或者其子类不能向下转型,所以抛类型转换错误。

创建 TreeSetTest03.java:

import java.util.TreeSet;

public class TreeSetTest03 {
    public static void main(String[] args) {
        TreeSet<Keyboard> treeset = new TreeSet<>();
        treeset.add(new Keyboard("Cherry", 108, 479));
        treeset.add(new Keyboard("Filco", 87, 1599));
        treeset.add(new Keyboard("SteelSeries", 108, 1499));
        treeset.add(new Keyboard("Razer", 108, 699));
    }
}

class Keyboard {
    private String name;
    private int key;
    private double price;

    public Keyboard(String name, int key, double price) {
        this.name = name;
        this.key = key;
        this.price = price;
    }
}

运行输出:

Exception in thread "main" java.lang.ClassCastException: class learnCollection.Keyboard cannot be cast to class java.lang.Comparable (learnCollection.Keyboard is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
    at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
    at java.base/java.util.TreeMap.put(TreeMap.java:536)
    at java.base/java.util.TreeSet.add(TreeSet.java:255)
    at learnCollection.TreeSetTest03.main(TreeSetTest03.java:8)

给 TmpClass 实现 Comparable 接口 compareTo(T o) 方法,比较规则通过数字三种情况确定俩对象谁大谁小:

  1. >0,表示当前对象大于比较的对象。
  2. <0,表示当前对象小于比较的对象。
  3. =0,表示当前对象等于比较的对象,说明俩对象一样,当前对象就不添加进集合中。

创建 TreeSetTest04java:

import java.util.TreeSet;

public class TreeSetTest03 {
    public static void main(String[] args) {
        TreeSet<Keyboard> treeset = new TreeSet<>();
        treeset.add(new Keyboard("Cherry", 108, 479));
        treeset.add(new Keyboard("Filco", 87, 1599));
        treeset.add(new Keyboard("SteelSeries", 104, 1499));
        treeset.add(new Keyboard("Razer", 108, 699));

        for (Keyboard k : treeset) {
            System.out.println(k);
        }
    }
}

class Keyboard implements Comparable {
    private String name;
    private int key;
    private double price;

    public Keyboard(String name, int key, double price) {
        this.name = name;
        this.key = key;
        this.price = price;
    }

    @Override
    public int compareTo(Object o) {
        Keyboard o1 = (Keyboard) o;
        return this.key - o1.key; // 按照键盘键数升序排序
    }

    @Override
    public String toString() {
        return "Keyboard{" +
                "name='" + name + '\'' +
                ", key=" + key +
                ", price=" + price +
                '}';
    }
}

运行输出:

Keyboard{name='Filco', key=87, price=1599.0}
Keyboard{name='SteelSeries', key=104, price=1499.0}
Keyboard{name='Cherry', key=108, price=479.0}

add 方法添加元素时,第一个元素会被当作 ROOT 节点被添加进去,后续添加的元素会调用 compareTo 方法从当前节点的 ROOT 节点进行比较,比当前节点小的元素放入左边,大的话就放入右节点,遵循平衡二叉树存入数据左小右大原则。

这里设置的规则是 this.key - o1.key,只要当前被添加的元素 key 键数小于被比较的键就放入左节点,大就放入右节点,最后发现 Razer 没有添加成功,因为与 Cherry 键数 key 相等,自然不被添加进集合。

如果非要添加进去那么可以将规则改以下,这样键数等于 0 的情况将比较价格,如果价格也相同就直接放入左节点,但实际情况最好按照需求细化排序规则。

@Override
public int compareTo(Object o) {
    Keyboard o1 = (Keyboard) o;
//      return this.key - o1.key;
    int sortSizeResult = this.key - o1.key;
    if (sortSizeResult == 0) {
        // 键盘键数一致就按照价格升序排序。
        return (int) (this.price - o1.price) >= 0 ? 1 : -1;
    }
    return sortSizeResult;
}

运行输出:

Keyboard{name='Filco', key=87, price=1599.0}
Keyboard{name='SteelSeries', key=104, price=1499.0}
Keyboard{name='Cherry', key=108, price=479.0}
Keyboard{name='Razer', key=108, price=699.0}

另一种实现自定义规则的方式是 TreeSet 实例化时传入比较器对象 TreeSet(Comparator<? super E> comparator),通过实现 Comparator 接口 int compare(T o1, T o2) 来定义排序规则。

创建 TreeSetTest04.java:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetTest03 {
    public static void main(String[] args) {
        Comparator<Keyboard> keyboardComparator = new Comparator<>() {
            @Override
            public int compare(Keyboard o1, Keyboard o2) {
                int sortSizeResult = o1.getKey() - o2.getKey();
                if (sortSizeResult == 0) {
                    // 键盘键数一致就按照价格升序排序。
                    return (int) (o1.getPrice() - o2.getPrice()) >= 0 ? 1 : -1;
                }
                return sortSizeResult;
            }
        };
//        TreeSet<Keyboard> treeset = new TreeSet<>();
        TreeSet<Keyboard> treeset = new TreeSet<>(keyboardComparator);
        treeset.add(new Keyboard("Cherry", 108, 479));
        treeset.add(new Keyboard("Filco", 87, 1599));
        treeset.add(new Keyboard("SteelSeries", 104, 1499));
        treeset.add(new Keyboard("Razer", 108, 699));

        for (Keyboard k : treeset) {
            System.out.println(k);
        }
    }
}

class Keyboard implements Comparable {
    private String name;
    private int key;
    private double price;

    public Keyboard(String name, int key, double price) {
        this.name = name;
        this.key = key;
        this.price = price;
    }

    public int getKey() {
        return key;
    }

    public double getPrice() {
        return price;
    }

    @Override
    public int compareTo(Object o) {
        Keyboard o1 = (Keyboard) o;
//      return this.key - o1.key;
        int sortSizeResult = this.key - o1.key;
        if (sortSizeResult == 0) {
            // 键盘键数一致就按照价格升序排序。
            return (int) (this.price - o1.price) >= 0 ? 1 : -1;
        }
        return sortSizeResult;
    }

    @Override
    public String toString() {
        return "Keyboard{" +
                "name='" + name + '\'' +
                ", key=" + key +
                ", price=" + price +
                '}';
    }
}

运行输出:

Keyboard{name='Filco', key=87, price=1599.0}
Keyboard{name='SteelSeries', key=104, price=1499.0}
Keyboard{name='Cherry', key=108, price=479.0}
Keyboard{name='Razer', key=108, price=699.0}

输出结果和 TreeSetTest03.java 修改规则后一致,而且是通过构造方法传入的比较器以后就只使用比较器,不再调被添加元素的 compareTo 方法,这是源码中写的,验证结果也正确。

那这两种排序方式使用哪种?第一种就是排序规则常年不变,可以直接在类里实现,第二种可以灵活指定排序规则,方便随时修改。

Generic(泛型)

集合中的泛型

泛型在集合中用处是限制集合元素存储数据的类型。

例如下面初始化 myArrayList 只能存 String 类型的数据,其他类型存入,抛出编译时异常。

Collection<String> myArrayList = new ArrayList<String>();

这种语法看起来很奇怪,直接把它分为两部分看 Collection<String> myArrayListnew ArrayList<String>()

其中 Collection<String> 类型则表示指向的对象是 Collection 子类或者是它本身,里面存的数据类是 String,方便对编译器说 myArrayList 这个变量只能存 String,给变量 myArrayList 做了个做类型约束。

new ArrayList<String>(); 说明集合只能存 String 类型元素,这一点可以用过 IDEA 验证,输入new ArrayList<String>().add(),会提示 add 方法只能输入 String 类型。

generic类型约束.jpg

从 Java7 开始新增自动类型推断(Type Inference)特性,创建对象时可以简写为 <>,因为通过类型就已经约束了变量 myArrayList,最后 new ArrayList<>() 会自己通过引用类型的泛型标识符 <String> 去替换 <>

Collection<String> myArrayList = new ArrayList<>();

如果泛型使用错误,就无法约束。通过以下代码测试,发现 myArrayList 并未做限制,依旧可以存入任意类型。只不过使用 add 方法这行 IDEA 会提示 Unchecked call to 'add(E)' as a member of raw type 'java.util.Collection',原因是没有明确 myArrayList 变量存什么数据。

Collection myArrayList = new ArrayList<String>();
myArrayList.add("S123");
myArrayList.add(123);
System.out.println(myArrayList);

反过来也是一样,照样爆 Unchecked 编译问题。

Collection<String> myArrayList = new ArrayList();
myArrayList.add("123");
System.out.println(myArrayList);

使用了泛型另一个好处是可以减少向下转型操作,全由 JVM 帮你添加向下转型。

创建 GenericTest01.java:

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

public class GenericTest01 {
    public void noGeneric() {
        ArrayList arrayList = new ArrayList();
        arrayList.add(12);
        arrayList.add("str");

        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            Object numObj = iterator.next();
            if (numObj instanceof Integer) {
                int num = (int) numObj;
                System.out.println(num);
            }
        }
    }

    public void generic() {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(123);
        // java: 不兼容的类型: java.lang.String无法转换为java.lang.Integer
        // arrayList.add("str");

        // 迭代器也可指定泛型,避免向下类型转换。
        Iterator<Integer> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            int num = iterator.next();
            System.out.println(num);
        }
    }

    public static void main(String[] args) {
        GenericTest01 genericTest01 = new GenericTest01();
        genericTest01.noGeneric();
        genericTest01.generic();
    }
}

运行输出:

12
123

noGeneric 方法不使用泛型默认所有对象都可 add,在迭代时使用 instanceof 避免类型错误,最后需要把取出的 Object 元素进一步向下转型才能使用。

generic 方法则不会出现这个问题,使用泛型指定 arrayList 集合只能存 Integer 数值,存其他对象就会报错,在迭代对象上使用泛型则可以减少类型转换的问题放心使用,没必要检查完类型还要向下转型。

自定义泛型类

前面仅仅是使用集合中的泛型,那它们的泛型是怎么定义出来的呢?如果也自己的类中也想使用泛型,那么就需要在类、接口名后面添加 <标识符>,如果有多个标识符就以逗号分隔 <标识符1, 标识符2>,一般来说标识符名称为 T、E、K、V、N,当然也可以随便任意字符,T、E 、K、V 分别对应 Type、Element、Key、Value、Number 的缩写,定义在类或者接口后面这种类型术语叫 Generic Types。

定义完成后这些类型可以使用在方法返回类型、形参类型等等地方使用,作为类型约束。

下面代码在 Test 类名后面定义了个 <T> 泛型标识符,此标识符在实例变量 T tmpVariable 作为的类型使用,public T testReturn(T paramName) 是在方法上返回类型、参数类型上使用 T。

所有标识符定义完只需创建实例时告诉 Java 泛型具体引用类型,这样才会生效,而且是定义了几个就要传入几个。

创建 GenericTest02.java:

public class GenericTest02 {
    public static void main(String[] args) {
        // 直接在使用时指定泛型标识符类型为 String。
        Test<String> test = new Test<>("");
        Test<Integer> test1 = new Test<>(0);

        String returnStringValue = test.testReturn("传入字符串");
        int returnIntValue = test1.testReturn(1);
        // 一旦确定泛型类型后旧无法传入其他类型参数。否则会产生编译时错误。
        //String returnStringValue1 = test.testReturn(2);
        //Integer returnIntegerValue1 = test1.testReturn("");
        System.out.println(returnIntValue);
        System.out.println(returnStringValue);

        // 通过获取 tmpVariable 实例变量类型可以确定类型标识符已经被替换。
        System.out.println(test.getVarType());
        System.out.println(test1.getVarType());

        Test test3 = new Test(1);
        System.out.println(test3.testReturn(222));
        System.out.println(test3.getVarType());
    }
}

/**
 * @param <T> 在类名后面定义泛型标识符
 */
class Test<T> {
    private T tmpVariable;

    public Test(T tmpVariable) {
        this.tmpVariable = tmpVariable;
    }

    /**
     * @param paramName 形参使用泛型标识符 T,此标识符会在实际对象初始化时指定。
     * @return 返回形参
     */
    public T testReturn(T paramName) {
        return paramName;
    }

    /**
     * @return 返回实例变量 tmpVariable 的类型名称
     */
    public String getVarType() {
        return tmpVariable.getClass().getName();
    }
}

运行输出:

1
传入字符串
java.lang.String
java.lang.Integer

Test<String> test = new Test<>("");,就是在创建 Test 类对象是也是在引用类型后面添加尖括号里面放上 String,这说明 Test 泛型标识符是 String 类型,那么里面所有用到 <T> 的地方都会替换为 <String>,通过 getVarType 方法就证明了这点。

使用泛型后可以发现调用 test.testReturn 方法只能传递指定泛型标识符类型的数据,输入其他数据则会报编译错误,见第 10-11 行代码。

如果声明了泛型,但实际使用上不指定类型默认泛型的类型是 Object。但是不使用泛型默认编译时则提示 Unchecked 错误,见第 19-21 行代码。

PS D:\gbb\learn\JavaProgrammingFundamentals\src\learnCollection> javac -encoding utf-8 .\GenericTest02.java
注: .\GenericTest02.java使用了未经检查或不安全的操作。
注: 有关详细信息, 请使用 -Xlint:unchecked 重新编译。

创建一个泛型是 String 那就只能放 String 类型的数据了吗?不是这样的除了 String 它的子类也是可以的。

创建 GenericTest03.java:

import java.util.ArrayList;

public class GenericTest03 {
    public static void main(String[] args) {
        // 可以包含 Animal 的子类。
        ArrayList<Animal> animal = new ArrayList<>();
        animal.add(new Pig());
        animal.add(new Animal());
        System.out.println(animal);

        ArrayList<Object> animal1 = new ArrayList<>();
        animal1.add(new Object());
        animal1.add(new String("1"));
        System.out.println(animal1);

        // 反过来则不行
//        ArrayList<Pig> animal2 = new ArrayList<>();
//        ArrayList<String> animal3 = new ArrayList<>();
//        animal2.add(new Animal());
//        animal3.add(new Object());


    }
}

class Animal {
}

class Pig extends Animal {
}

在形参中使用给某个类或接口指定泛型需要加上 customTypeName<>。创建 GenericTest033.java。

public class GenericTest033 {
    public static void main(String[] args) {
        // customCallable 接口泛型类型是 Integer,customCallable<Integer>。
        customCallable<Integer> customCallable = new customCallable<>() {
            @Override
            public Integer call() {
                return 1;
            }
        };
        // customClass 类泛型类型是 String,customClass<String>。
        new customClass<String>(customCallable);
    }
}

interface customCallable<T> {
    T call();
}

class customClass<V> {
    public customClass(customCallable<V> parm) {
        System.out.println(parm.call());
    }
}

这里创建了 customClass 类,主要功能是调用 parm 参数 call 方法,parm 参数限定类型是 customCallable 接口类型,泛型使用类定义的 <V>

可以看到 GenericTest033 类 main 方法中 customCallable 接口泛型类型为 Integer,customClass 类泛型类型为 String,说明只能接收 customCallable<String>,但实际传递的是 customCallable<Integer>,运行完会报错。

java: 不兼容的类型: learnThread.customCallable<java.lang.Integer>无法转换为learnThread.customCallable<java.lang.String>

这就是用泛型当于做检查。如何解决此问题?

customClass 形参要 customCallable 为 String,那实际传递 String 就是了。

public class GenericTest033 {
    public static void main(String[] args) {
        // 已经更正类型错误。
        // customCallable 接口泛型类型是 String,customCallable<String>。
        customCallable<String> customCallable = new customCallable<>() {
            @Override
            public String call() {
                return "1";
            }
        };
        // customClass 类泛型类型是 String,customClass<String>。
        new customClass<String>(customCallable);
    }
}

另一个不推荐的用法是使用原始类型 Raw Type,虽然也能运行成功不报错。

public class GenericTest033 {
    public static void main(String[] args) {
        // customCallable 没有使用泛型,使用的是原始类型。
        customCallable customCallable = new customCallable() {
            @Override
            public Integer call() {
                return 1;
            }
        };
        // customClass 类泛型类型是 String,customClass<String>。
        new customClass<String>(customCallable);
    }
}

自定义泛型接口

自定义范型接口在实现或继承时要给出实际类型,如果不给最好也指明 <Object> 以避免 UnChecked 错误。

创建:GenericTest04.java:

public class GenericTest04 implements Test02 {
    @Override
    public String echo(String s) {
        return s;
    }
}

interface Test01<T> {
    T echo(T t);
}

interface Test02 extends Test01<String> {
}

这里就在 Test01 接口定义了泛型 <T>,Test02 接口去继承时就要写指定类型,这样 GenericTest05 类实现方法时就可以直接传 String。

如果 Test02 接口不愿意写具体类型,最好写上 <Object>,继续把 GenericTest04 改写下。

public class GenericTest04 implements Test02 {
    @Override
    public Object echo(Object o) {
        return null;
    }
}

interface Test01<T> {
    T echo(T t);
}

interface Test02 extends Test01<Object> {
}

实现单个接口时也要指明接口具体类型是啥。

创建 GenericTest05.java:

public class GenericTest05 implements Test01<Integer> {
    @Override
    public Integer echo(Integer integer) {
        return null;
    }
}

interface Test01<T> {
    T echo(T t);
}

当在 Test01 指定了类型是 Integer 那么定义的 <T> 就相当于 Integer 所有使用到的地方都替换上。

泛型接口定义限制

  1. 泛型不能 new。不能创建泛型 T[] new T[],因为 new T[] 的缘故,此时的 T 还不知道是什么类型,数组实例化时需要类型呀,可此时的 T 在类实例化时
  2. 接口静态属性常量不能使用泛型。原因是类加载先于对象创建,创建时并没给定类型,所以没法创建成功。

创建 GenericTest06.java。

public class GenericTest06<T> {
    static T var; // 不能定义
    T[] arr = new T[10]; // Type parameter 'T' cannot be instantiated directly

    public <G> static G echo(G content) { // 不能在静态方法上定义 Identifier or type expected
        return content;
    }
}

自定义泛型方法

在方法修饰符和返回类型中间处定义泛型 <标识符> 叫泛型方法,术语叫做 Generic Methods。

public <标识符> void func() {标识符 p}

方法修饰符位置定义了泛型可以在返回类型、参数类型使用。

创建 GenericTest077.java:

public class GenericTest077 {
    public <T> void generic(T p, T t) {
        System.out.println("p 泛型类型是:" + p.getClass().getName());
        System.out.println("t 泛型类型是:" + t.getClass().getName());
    }

    public static void main(String[] args) {
        GenericTest077 genericTest077 = new GenericTest077();

        String test = "String 类型";
        int num = 1;

        genericTest077.generic(test, num);
    }
}

运行输出:

p 泛型类型是:java.lang.String
t 泛型类型是:java.lang.Integer

GenericTest077 类里定义了 generic 方法,在修饰符处定义了泛型,参数类型处使用了泛型。

main 方法定义了 String testint num 两个变量,可以直接传入泛型方法 generic,最后方法处理时原封不动输出对应类型。

接收任意类型参数在普通方法只能定义重载方法,只用一个方法完全做不到,有了泛型大大提高了方法类型灵活性和安全性。

泛型继承和通配符

泛型里标识符之间没有继承关系,无法使用多态:

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

public class GenericTest07 {
    public static void main(String[] args) {
        List<String> listStr = null;
        ArrayList<Object> listObj;
//        listObj = listStr; // 无继承关系

        List<Object> listObj1;
        List<String> listStr1 = null;
//        listObj1 = listStr1; // 无继承关系

        List<Object> listObj2;
        ArrayList<Object> listStr2 = null;
        listObj2 = listStr2; // 有继承关系
    }
}

为了解决以上问题,可以设置通配符来把泛型限制到一个范围,要传只能传范围内的:

  • <?>,可以传任意类型进来。

  • <? extent ClassName>,类型可以传递 ClassName 本身或者 ClassName 子类。定义了上限。

  • <? super ClassName>,类型可以传递 ClassName 本身或者 ClassName 父类类。定义了下限。

变量 listObj1、listObj2 加了 <?> 后就可以指向其他泛型了:

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

public class GenericTest08 {
    public static void main(String[] args) {
        List<String> listStr = null;
        ArrayList<?> listObj = null;
//        listObj = listStr; // 不能指向,因为 ArrayList 是 List 子类

        Collection<?> listObj1;
        List<String> listStr1 = null;
        listObj1 = listStr1; // Collection 是 List 父类可以指向

        List<?> listObj2;
        List<String> listStr2 = null;
        listObj2 = listStr2;
    }
}

创建了 echo 方法参数类型是 GenericTest08<?> 表示可以接收 GenericTest08 类型和其子类任意泛型。但你传类型外的就不行。

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

public class GenericTest08<T> {
    // 可以接收 GenericTest08 类的任意泛型
    public void echo(GenericTest08<?> p) {
        System.out.println(p);
    }


    public static void main(String[] args) {
        GenericTest08<String> stringGenericTest08 = new GenericTest08<>();
        GenericTest08<Integer> stringGenericTest09 = new GenericTest08<>();
        GenericTest08<Object> stringGenericTest10 = new GenericTest08<>();
        stringGenericTest08.echo(stringGenericTest09);
        stringGenericTest08.echo(stringGenericTest10);
        stringGenericTest08.echo(new Test02()); // 成功,因为 Test02 是 GenericTest08 子类
//        stringGenericTest08.echo(new String("1")); // 无法添加 GenericTest08 本身或其子类以外类型的数据。
    }

    @Override
    public String toString() {
        return "GenericTest08{}";
    }
}

class Test02 extends GenericTest08<String> {
    @Override
    public String toString() {
        return "Test02{}";
    }
}

echo 方法使用 GenericTest08<? extends Test02> 限定 GenericTest08 泛型类型为 Test02 本身和 Test02 的子类,符合条件才会接收。下面代码只有变量 stringGenericTest10、stringGenericTest11 符合条件:

public class GenericTest08<T> {
    // 可以接收 GenericTest08 类的 Test02 泛型和 Test02 子类泛型。
    public void echo(GenericTest08<? extends Test02> p) {
        System.out.println(p);
    }


    public static void main(String[] args) {
        GenericTest08<String> stringGenericTest08 = new GenericTest08<>();
        GenericTest08<Integer> stringGenericTest09 = new GenericTest08<>();
        GenericTest08<Test02> stringGenericTest10 = new GenericTest08<>();
        GenericTest08<Test03> stringGenericTest11 = new GenericTest08<>();
//        stringGenericTest08.echo(new Test02()); // 报错,只能提供对应泛型类型,而不是对象。
//        stringGenericTest08.echo(stringGenericTest09); // 报错,Integer 不在 Test02 和其子类范围内。
        stringGenericTest08.echo(stringGenericTest10);
        stringGenericTest08.echo(stringGenericTest11);
//        stringGenericTest08.echo(new String("1")); // 无法添加 GenericTest08 本身或其子类以外类型的数据。
    }

    @Override
    public String toString() {
        return "GenericTest08{}";
    }
}

class Test03 extends Test02 {
    @Override
    public String toString() {
        return "Test02{}";
    }
}

class Test02 {
    @Override
    public String toString() {
        return "Test02{}";
    }
}

echo 方法 GenericTest08<? super Test03> 就表明只能传递 Test03 泛型和 Test03 父类的泛型,除此之外都不接收。在 main 方法中只有stringGenericTest10、stringGenericTest11、stringGenericTest12 这三个变量添加成功,因为这三变量指向 Test02、Test03、Object 类型,要么是 Test03 本身或者是它父类。

public class GenericTest08<T> {
    // 可以接收 GenericTest08 类 Test03 泛型和它的父类泛型
    public void echo(GenericTest08<? super Test03> p) {
        System.out.println(p);
    }


    public static void main(String[] args) {
        GenericTest08<String> stringGenericTest08 = new GenericTest08<>();
        GenericTest08<Integer> stringGenericTest09 = new GenericTest08<>();
        GenericTest08<Test02> stringGenericTest10 = new GenericTest08<>();
        GenericTest08<Test03> stringGenericTest11 = new GenericTest08<>();
        GenericTest08<Object> stringGenericTest12 = new GenericTest08<>();
//        stringGenericTest08.echo(new Test02()); // 报错,只能提供对应泛型类型,而不是对象。
//        stringGenericTest08.echo(stringGenericTest09); // 报错,Integer 不是 Test02 本身也不是它父类。
        stringGenericTest08.echo(stringGenericTest10);
        stringGenericTest08.echo(stringGenericTest11);
        stringGenericTest08.echo(stringGenericTest12);
//        stringGenericTest08.echo(new String("1")); // 无法添加 GenericTest08 本身或其父类以外类型的数据。
    }

    @Override
    public String toString() {
        return "GenericTest08{}";
    }
}

class Test03 extends Test02 {
    @Override
    public String toString() {
        return "Test02{}";
    }
}

class Test02 {
    @Override
    public String toString() {
        return "Test02{}";
    }
}

Map 接口常用方法练习

常用方法:

  • V put(K key, V value),向集合存入 key-vaue 元素。
  • V get(Object key),通过 key 获取 value。
  • V remove(Object key),通过 key 移除 key-value。
  • int size(),获取 key-value 元素个数。
  • boolean containsKey(Object key),使用 key 的 equals 方法对集合每个 key 进行比较。
  • boolean containsValue(Object value),使用 value 的 equals 方法对集合每个 value 进行比较,注意重写。
  • boolean isEmpty(),判断 Map 集合元素是否为 0。
  • void clear(),清空 Map 集合元素。
  • Set<K> keySet(),把 Map 集合里所有 key 存入Set 集合返回。
  • Collection<V> values(),获取 Map 集合里所有 value 存入 Collection 集合并返回 。
  • Set<Map.Entry<K,V>> entrySet(),把 Map 集合里所有 key-value 封装成 Map.Entry 对象最后存入 Set 集合。

创建 MapTest01.java:

import java.util.Collection;
import java.util.HashMap;
import java.util.Set;

public class MapTest01 {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>();

        // V put(K key, V value)
        hashMap.put("StrKey", 1);
        hashMap.put("StrKey1", 2);
        hashMap.put("StrKey1", 3);
        hashMap.put(null, 4);
        hashMap.put(null, null);


        // V get(Object key)
        int num1 = hashMap.get(new String("StrKey1"));
        int num2 = hashMap.get("StrKey");
        Object nullObj3 = hashMap.get(null);
        System.out.println("get() 获取 value:");
        System.out.println("\t" + num1);
        System.out.println("\t" + num2);
        System.out.println("\t" + nullObj3);

        // V remove(Object key)
        System.out.println("删除 key 对象:\n\t" + hashMap.remove(null));

        // int size()
        System.out.println("Map 集合元素个数:\n\t" + hashMap.size());

        // boolean containsKey(Object key)
        System.out.println("集合中包含 key 这个对象吗?:\n\t" + hashMap.containsKey(new String("StrKey")));

        // boolean containsValue(Object value)
        System.out.println("集合中包含 value 这个对象吗?:\n\t" + hashMap.containsValue(1));

        // boolean isEmpty()
        System.out.println("Map 集合是不是空的:\n\t" + hashMap.isEmpty());

        // Set<K> keySet()
        Set<String> keyMap = hashMap.keySet();
        System.out.println("遍历 key:");
        for (String strKey : keyMap) {
            System.out.println("\t" + strKey);
        }

        // Collection<V> values()
        Collection<Integer> collectionValues = hashMap.values();
        System.out.println("遍历 value:");
        for (int intValue : collectionValues) {
            System.out.println("\t" + intValue);
        }

        // void clear()
        hashMap.clear();
        System.out.println("清空集合:\n\t" + hashMap.isEmpty());
    }
}

运行输出:

get() 获取 value:
    3
    1
    null
删除 key 对象:
    null
Map 集合元素个数:
    2
集合中包含 key 这个对象吗?:
    true
集合中包含 value 这个对象吗?:
    true
Map 集合是不是空的:
    false
遍历 key:
    StrKey1
    StrKey
遍历 value:
    3
    1
清空集合:
    true

遍历 Map 集合通常两个方式,要么通过 keySet() 得到 key 使用 get() 方法调用,另一种是调用 entrySet() 把集合里每个 key-value 封装成 Map.Entry 对象存入 Set 集合,最后遍历集合元素调通过 getKey 和 getValue 方法得到具体内容。

创建 MapTest02.java:

import java.util.*;

public class MapTest02 {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>();

        hashMap.put("StrKey", 1);
        hashMap.put("StrKey1", 2);

        // 遍历方式1,通过 key 获取 value,采用 Iterator 和 for-each 的方式遍历 key
        Set<String> keyset = hashMap.keySet();
        System.out.println("Map 集合遍历方式一 for-each:");
        for (String strKey : keyset) {
            int mapValue = hashMap.get(strKey);
            System.out.println("\t" + strKey + ":" + mapValue);
        }

        Iterator<String> iterator = keyset.iterator();
        System.out.println("Map 集合遍历方式一 Iterator:");
        while (iterator.hasNext()) {
            String key = iterator.next();
            System.out.println("\t" + key + ":" + hashMap.get(key));
        }

        // 遍历方式2,使用 iterator 同时遍历 key 和 value 集合
        Collection<Integer> values = hashMap.values();
        iterator = keyset.iterator();
        Iterator<Integer>iterator1 = values.iterator();
        System.out.println("Map 集合遍历方式二 Iterator:");
        while (iterator.hasNext() & iterator1.hasNext()) {
            String key = iterator.next();
            int value = iterator1.next();
            System.out.println("\t" + key + ":" + value);
        }

        // 遍历方式3,使用 forEach 遍历 Set 集合中的 Map.Entry 对象
        Set<Map.Entry<String, Integer>> setObj = hashMap.entrySet();
        System.out.println("Map 集合遍历方式三:");
        for (Map.Entry<String, Integer> entryObj : setObj) {
            System.out.println("\t" + entryObj.getKey() + ":" + entryObj.getValue());
        }
    }
}

运行输出:

Map 集合遍历方式一 for-each:
    StrKey1:2
    StrKey:1
Map 集合遍历方式一 Iterator:
    StrKey1:2
    StrKey:1
Map 集合遍历方式二 Iterator:
    StrKey1:2
    StrKey:1
Map 集合遍历方式三:
    StrKey1:2
    StrKey:1

HashMap

在 HashSet 介绍过对应数据结构,而 HashSet 本质上也是创建 HashMap。

HashMap 底层是 “数组+单项链表”,也叫哈希/散列表。

HashMap 结构:
new HashMap() Java8 里 new 完不会直接创建数组,而是 put() 添加时初始长度是 16 的 Node[] table 一维数组,里面存放着 HashMap$Node 静态内部类对象,这个 Node 对象就是单向链表节点,它包含 hash、key、value、next 四个属性,其中 hash 的值是调用 key 的 hashCode() 生成的结果,此结果通过 hash 算法计算出的数值是数组存放元素的下标索引,key 和 value 就是put 方法对应的实参 k 和 v,next 表示单项链表下一个节点引用。

HashMap 扩容:

默认 加载因子(DEFAULT_LOAD_FACTOR)是0.75,此数值表示 HashMap 容量达到 75% 就根据已有数组长度扩容两倍,例如默认容量是 16 加载因子是 0.75,相当于 16 * 0.75,那么临界值就是12,但是此数值可以在实例化时传入,比如 new HashMap(16, 1),第一个值是指定集合初始长度,第二个值是加载因子。为了散列分布均匀集合初始长度在指定是最好是二的倍数。

put(K key, V value) 原理

  1. 使用 put(k, v) 时调用 k.hashCode() 计算出值,接着使用 hash 算法得出数组具体索引下标位置。

  2. 如果对应数组对应位置没有元素就直接添加 Node 对象成功。有数据就调用 k.equals() 比较单向链表每个节点(链表可能有一个或多个节点)的 k:

    1. 返回 true(k 相同)就直接将对应节点 value 替换为 v
    2. 返回 false 说明所有节点没发现 k 相同,就把 Node 对象作为单向链表 last 节点存入(具体是不是存到单向链表 last 节点,各个 Java 版本不同,Java7 里是存到 first 节点,Java8 存到 last 节点)。

Java8 里数组索引对应链表节点 THREEIFY_THRESHOLD 数大于 8 并且数组长度大于等于 64,这时索引对应的链表直接转为红黑树存储。使用原因是大量节点调 euqals() 红黑树相比单向链表遍历起来会快些。转完红黑树后如果你 remove 数据一旦节点小于 8 数组长度也小于 64 就又给你转回链表。

另一点是要重写 key 的 hashCode、equals 方法。

hashCode 重写怎么让哈希算法算法能够把要存入的对象平均分布到不同的索引下(散列分布均匀),这是个问题,不然每次 hashCode 计算都得出相同的 hash 值,通过 hash 算法也会得出同一个索引,每次都存到同一个索引下的单向链表,Hash 表数组的优势就没充分使用。

get(Object key) 原理

  1. 计算 key 的 hashCode(),通过 hash 算法得到索引值。
  2. 去数组对应索引查找元素,如果没有发现元素 return null。有元素就比较每个的 调用 key.equals() 方法比较单向链表每个节点,key.equals() 返回 true 就 return 对应 value,返回 false 就 return null。

entrySet() 遍历原理

前面是直接使用 entrySet 方法遍历集合,但是它的原理却不清楚,使用下面代码解读:

HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("StrKey", 1);
hashMap.put("StrKey1", 2);

Set<Map.Entry<String, Integer>> setObj = hashMap.entrySet();
for (Map.Entry<String, Integer> entryObj : setObj) {
    System.out.println("\t" + entryObj.getKey() + ":" + entryObj.getValue());
}

调用 entrySet() 方法将返回 Set EntrySet 集合,该集合里面存放 Map.Entry 类型对象,而 Map.Entry 对象的引用指向 HashMap$Node 对象,能够指向是因为 HashMap$Node 实现了 Map.Entry 接口所以可以向上转型,HashMap$Node 实现了 Map.Entry 接口 getKey、getValue 方法,这样就可以获取 k 和 v。

通过 forEach 最终调用 EntrySet 集合 Iterator 方法遍历出每个节点,通过节点 getKey、getValue 方法获取 k 和 v。

同理 keySet()values() 也是分别往 Set 集合和 Collection 集合里存。

Hashtable

Hashtable$Entry[] 数组默认初始化长度 11,加载因子(DEFAULT_LOAD_FACTOR)是 0.75,当大于等于 11 * 0.75 计算出的临界值后就扩容 oldCapacity << 2 + 1 相当于old_length * 2 + 1

其他内容与 HashMap 无异。

Properties

Properties 继承自 Hashtable,常用来读配置文件用。

常用方法:

  • Object put(Object key, Object value),添加键值对并返回添加的对象,k 和 v 一般来说是存 String 类型,不能为 null,因为后续通过 IO 流来读会方便。如果是相同的 key 一样用新 value 覆盖旧 value。
  • Object get(Object key),通过 k 获取 v 并 return 获取的 value。
  • Object remove(Object key),通过 k 删除 value 并 return 被删除的 value。

创建 PropertiesTest01.java:

public class PropertiesTest01 {
    public static void main(String[] args) {
        Properties properties = new Properties();
        properties.put("test", "1");
        properties.put("test", 2);
//        properties.put("test", null); // NullPointerException
//        properties.put(null, 2); // NullPointerException
        System.out.println(properties);
        System.out.println(properties.get("test"));
        System.out.println(properties.remove("test"));
    }
}

TreeMap

TreeMap put 两个元素 key 相同时而且比较结果 0,那么会拿新 value 替换掉老 value。其他原理 reeMap 和 TreeSet 一致

创建 TreeMapTest01.java:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapTest01 {
    public static void main(String[] args) {
        Comparator<Keyboard> keyboardComparator = new Comparator<>() {
            @Override
            public int compare(Keyboard o1, Keyboard o2) {
                int sortSizeResult = o1.getKey() - o2.getKey();
                return sortSizeResult;
            }
        };

        TreeMap<Keyboard, Integer> treemap = new TreeMap<>(keyboardComparator);
        treemap.put(new Keyboard("Cherry", 108, 479), 1);
        treemap.put(new Keyboard("Filco", 87, 1599), 2);
        treemap.put(new Keyboard("SteelSeries", 104, 1499), 3);
        treemap.put(new Keyboard("Razer", 108, 699), 4); // 直接把 Cherry 的value 1 替换为 4

        for (Map.Entry<Keyboard, Integer> entry : treemap.entrySet()) {
            System.out.println(entry.getKey() + "====" + entry.getValue());
        }
    }
}

class Keyboard {
    private String name;
    private int key;
    private double price;

    public Keyboard(String name, int key, double price) {
        this.name = name;
        this.key = key;
        this.price = price;
    }

    public int getKey() {
        return key;
    }

    @Override
    public String toString() {
        return "Keyboard{" +
                "name='" + name + '\'' +
                ", key=" + key +
                ", price=" + price +
                '}';
    }
}

运行输出:

Keyboard{name='Filco', key=87, price=1599.0}====2
Keyboard{name='SteelSeries', key=104, price=1499.0}====3
Keyboard{name='Cherry', key=108, price=479.0}====4

可以看到 Cherry 的值不是 1 了,而是被替换为 4。

Collections 工具类

Collections 用于操作集合,位于 java.util.Collections。

常用方法:

  • sort(List<T> list),对 List 集合进行排序。需要 list 实现排序规则,要么是实现 Comparable 接口 public int compareTo(T o) 方法。

    sort(List<T> list, Comparator<? super T> c),另一种方式就是直接传入比较器对象,参见 TreeSet 实现 Comparator 排序一章。

  • reverse(List<?> list),把 list 反转。

  • shuffle(List<?> list),随机打乱 List 集合内元素顺序,可以联想到洗牌这种每次重置后随机的操作。不支持 Map 是因为存入时就是无序的。

  • swap(List<?> list, int i, int j),将 list 索引 i 和索引 j 数据位置互换,让索引 i 的数据存入到索引 j,索引 j 的数据存入索引 i。

  • frequency(Collection<?> c, Object o),返回元素 o 在集合 c 出现的次数。

  • addAll(Collection<? super T> c, T... elements),向集合 c 添加一个或多个元素。

  • min(Collection<? extends T> coll),调用 coll 定义的排序规则,返回排序后的最小值

    min(Collection<? extends T> coll, Comparator<? super T> comp),调用 coll 指定排序规则 comp 返回排序后的最小值。

  • max(Collection<? extends T> coll),调用 coll 定义的排序规则,返回排序后的最大值
    max(Collection<? extends T> coll, Comparator<? super T> comp),调用 coll 指定排序规则 comp 返回排序后的最大值。

  • copy(List<? super T> dest, List<? extends T> src),将 src 集合内容赋值到 dest 集合里。这需要 dest 集合长度至少和 src 相等,不然抛异常。填充方式:1.循环 src.size() 元素个数将 dest 填充 null 以保证两个集合长度一致,2.创建 dest 集合时使用 Arrays.asList() 方法创建 src.size() 长度数组填充 null,但是这样会影响到扩容临界值计算。

  • replaceAll(List<T> list, T oldVal, T newVal),将集合中的所有 oldVal 替换为 newVal,但要注意重写 oldVal 的 equals 方法,不然在 list 就没法找到对应 oldVal 自然无法替换为 newValue。

  • synchronizedList(List<T> list),直接传入 list 变成线程安全,像是其他集合也有类似方法,只不过换下名称,例如:synchronizedMap(Map<K,V> m)

创建:CollectionsTest01.java:

import java.util.*;

public class CollectionsTest01 {
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<>();
        strings.add("a");
        strings.add("c");
        strings.add("d");
        strings.add("b");
        strings.add("b");

        // sort(List<T> list)
        System.out.println("排序前:" + strings);
        Collections.sort(strings);
        System.out.println("排序后:" + strings);

        // reverse(List<?> list)
        System.out.println("反转前:" + strings);
        Collections.reverse(strings);
        System.out.println("反转后:" + strings);

        // shuffle(List<?> list)
        System.out.println("打乱前:" + strings);
        Collections.shuffle(strings);
        System.out.println("打乱后:" + strings);

        // swap(List<?> list, int i, int j)
        System.out.println("数据交换前:" + strings);
        Collections.swap(strings, 0, 1);
        System.out.println("数据交换后:" + strings);

        // frequency(Collection<?> c, Object o)
        System.out.println("元素 b 出现的次数:" + Collections.frequency(strings, "b"));

        // addAll(Collection<? super T> c, T... elements)
        System.out.println("数据添加前:" + strings);
        Collections.addAll(strings, "新添加的1", "新添加的2", "新添加的3");
        System.out.println("数据添加后:" + strings);

        // min(Collection<? extends T> coll)
        // max(Collection<? extends T> coll)
        System.out.println("集合中最小值:" + Collections.min(strings));
        System.out.println("集合中最大值:" + Collections.max(strings));

        // copy(List<? super T> dest, List<? extends T> src)
        // 填充方式 0
//        ArrayList<String> strings1 = new ArrayList<>(Arrays.asList(new String[strings.size()]));
        ArrayList<String> strings1 = new ArrayList<>();
        System.out.println("复制前:" + strings1);
        // 填充方式 1
//        for (String s : strings) {
//            strings1.add(null);
//        }
        // 填充方式 2
        for (int i = 0; i < strings.size(); i++) {
            strings1.add(null);
        }

        Collections.copy(strings1, strings);
        System.out.println("复制后" + strings1);

        System.out.println("strings 元素 b 被替换前:" + strings);
        Collections.replaceAll(strings, "b", "zzzz");
        System.out.println("strings 元素 b 被替换 zzz 后:" + strings);
    }
}

运行输出:

排序前:[a, c, d, b, b]
排序后:[a, b, b, c, d]
反转前:[a, b, b, c, d]
反转后:[d, c, b, b, a]
打乱前:[d, c, b, b, a]
打乱后:[d, b, b, a, c]
数据交换前:[d, b, b, a, c]
数据交换后:[b, d, b, a, c]
元素 b 出现的次数:2
数据添加前:[b, d, b, a, c]
数据添加后:[b, d, b, a, c, 新添加的1, 新添加的2, 新添加的3]
集合中最小值:a
集合中最大值:新添加的3
复制前:[]
复制后[b, d, b, a, c, 新添加的1, 新添加的2, 新添加的3]
strings 元素 b 被替换前:[b, d, b, a, c, 新添加的1, 新添加的2, 新添加的3]
strings 元素 b 被替换 zzz 后:[zzzz, d, zzzz, a, c, 新添加的1, 新添加的2, 新添加的3]

最近更新:

发布时间:

讨论讨论

Asia/Shanghai