Java中的集合体系

集合体系

Collection(interface)
- Set(interface)
  - HashSet(class): extends AbstractSet(abstract class),implements Set(interface)
    - LinkedHashSet(class):extends HashSet(class),implements Set(interface)
  - TreeSet(class): extends AbstractSet(abstract class),implements NavigableSet(interface)
- List(interface)
  - ArrayList(class):extends AbstractList(abstract class),implements List(interface)
  - Vector(class):extends AbstractList(abstract class),implements List(interface)
  - LinkedList(class):extends AbstractSequentialList(abstract class),implements List(interface),Deque(Queue的子接口)
- Queue(interface):队列是一种特殊的线性表,FIFO的数据结构
  - PriorityQueue(class):extends AbstractQueue
Map(interface)
- HashMap(class):extends AbstractMap(abstract class),implements Map(interface)
  - LinkedHashMap(class):extends HashMap(class),implements Map(interface)
- HashTable(class):extends Dictionary(abstract class),implements Map(interface)
- TreeMap(class):extends AbstractMap(abstract class),implements NavigableMap(interface)

集合体系

Collection接口

Set接口，特点：无序，唯一

public class TreeSetExample {
    public static void main(String[] args) {
        User user1 = new User("zhangsan",18);
        User user2 = new User("lisi",18);
        User user3 = new User("lisi",20);
        User user4 = new User("lisi",20);
        User user5 = new User("wangwu",26);
        User user6 = new User("zhaoliu",15);

        TreeSet<User> treeSet = new TreeSet<>();
        treeSet.add(user1);
        treeSet.add(user2);
        treeSet.add(user3);
        treeSet.add(user4);
        treeSet.add(user5);
        treeSet.add(user6);

        for (User user : treeSet) {
            System.out.println(user);
        }
    }
}
class User {
    private String name;
    private Integer age;

    public User(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

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

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

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

运行结果:

Exception in thread "main" java.lang.ClassCastException: cn.huazai.main.collection_interface.User cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at cn.huazai.main.collection_interface.TreeSetExample.main(TreeSetExample.java:21)

修改后:

解决方式1(User类实现Comparable):

public class TreeSetExample {
    public static void main(String[] args) {
        User user1 = new User("zhangsan",18);
        User user2 = new User("lisi",18);
        User user3 = new User("lisi",20);
        User user4 = new User("lisi",20);
        User user5 = new User("wangwu",26);
        User user6 = new User("zhaoliu",15);
        User user7 = new User("zhangsan",14);

        TreeSet<User> treeSet = new TreeSet<>();
        treeSet.add(user1);
        treeSet.add(user2);
        treeSet.add(user3);
        treeSet.add(user4);
        treeSet.add(user5);
        treeSet.add(user6);
        treeSet.add(user7);

        for (User user : treeSet) {
            System.out.println(user);
        }
    }
}
class User implements Comparable<User> {
    private String name;
    private Integer age;

    //省略getter setter 以及重写toString

    @Override
    public int compareTo(User u) {
        //return -1; //表示放在红黑树左边 倒序输出 LIFO(后进先出)
        //return 1; //表示放在红黑树右边 顺序输出 FIFO(先进先出)
        //return 0; //表示元素相同,忽略,不存入

        //姓名的长度,如果姓名长度小的就放在左子树，否则放在右子树
        int num = this.name.length() - u.name.length();
        //姓名的长度相同，不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。
        //如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。
        //如果这两个字符串相等，则结果为 0
        int num1 = num == 0 ? this.name.compareTo(u.name) : num;
        //姓名的长度和内容相同，不代表年龄相同，所以还要判断年龄
        int num2 = num1 == 0 ? this.age - u.age : num1;
        System.out.println("this.name:"+this.name+",u.name:"+u.name+",num2:"+num2);
        return num2;
    }
}

执行结果:

this.name:zhangsan,u.name:zhangsan,num2:0
this.name:lisi,u.name:zhangsan,num2:-4
this.name:lisi,u.name:zhangsan,num2:-4
this.name:lisi,u.name:lisi,num2:2
this.name:lisi,u.name:lisi,num2:0
this.name:wangwu,u.name:lisi,num2:2
this.name:wangwu,u.name:zhangsan,num2:-2
this.name:zhaoliu,u.name:lisi,num2:3
this.name:zhaoliu,u.name:zhangsan,num2:-1
this.name:zhaoliu,u.name:wangwu,num2:1
this.name:zhangsan,u.name:lisi,num2:4
this.name:zhangsan,u.name:zhaoliu,num2:1
this.name:zhangsan,u.name:zhangsan,num2:-4
User{name='lisi', age=18}
User{name='lisi', age=20}
User{name='wangwu', age=26}
User{name='zhaoliu', age=15}
User{name='zhangsan', age=14}
User{name='zhangsan', age=18}

解决方式2(TreeSet传入接口Comparator的实现的有参构造):

public class TreeSetExample {
    public static void main(String[] args) {
        User user1 = new User("zhangsan",18);
        User user2 = new User("lisi",18);
        User user3 = new User("lisi",20);
        User user4 = new User("lisi",20);
        User user5 = new User("wangwu",26);
        User user6 = new User("zhaoliu",15);
        User user7 = new User("zhangsan",14);

        TreeSet<User> treeSet = new TreeSet<>((o1,o2)->{
            //比名字字数
            int num = o1.getName().length()-o2.getName().length();
            //字数一样比名字(String自己的对比方式)
            int num1 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;
            //名字一样比年龄
            int num2 = num1 == 0 ? o1.getAge() - o2.getAge() : num1;
            //如果依然为0表示两个相同的用户,将会返回0,被忽略而不加入集合中
            return num2;
        });
        treeSet.add(user1);
        treeSet.add(user2);
        treeSet.add(user3);
        treeSet.add(user4);
        treeSet.add(user5);
        treeSet.add(user6);
        treeSet.add(user7);

        for (User user : treeSet) {
            System.out.println(user);
        }
    }
}

结果与方式1相同,并没有实质改变,只是定义比较器的位置不一样了而已

Set接口的各个实现类对比:

HashSet
- 底层数据结构是哈希表（无序，唯一）
LinkedHashSet
- 底层数据结构是链表和哈希表(FIFO插入有序,唯一)
TreeSet
- 底层数据结构是红黑树（唯一，有序）
- 不能存null*1

HashSet：哈希表依赖hashCode()和equals()来保证元素的唯一性

LinkedHashSet：由链表保证元素的有序性，由哈希表保证元素的唯一性

TreeSet：元素排序通过实现Comparable接口或使用TreeSet(Comparator)有参构造排序

*1：

public class SetTest {
    public static void main(String[] args) {
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add(null);
        System.out.println(hashSet);
        
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(null);
        System.out.println(linkedHashSet);
        
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add(null);
        System.out.println(treeSet);
    }
}

执行结果:
[null]
[null]
Exception in thread "main" java.lang.NullPointerException
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at cn.huazai.main.collection_interface.SetTest.main(SetTest.java:22)

List接口，特点：有序，可重复

List接口的各个实现类对比:

ArrayList
- 优点：底层数据结构为数组，查询快，增删慢
- 缺点：线程不安全（效率高）
Vector
- 优点：底层数据结构为数组，查询快，增删慢
- 缺点：效率低（线程安全）
LinkedList
- 优点：底层数据结构为链表，查询慢，增删快
- 缺点：线程不安全（效率高）

小实验：

测试是否可以存null值

public class ListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add(null);
        System.out.println(arrayList);

        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add(null);
        System.out.println(linkedList);

        Vector<String> vector = new Vector<>();
        vector.add(null);
        System.out.println(vector);
    }
}

执行结果：
[null]
[null]
[null]

总结：List接口的实现类ArrayList、LinkedList、Vector均可以存null值。

测试线程是否安全

//ArrayList:
public class ListExample {
    public static void main(String[] args) throws InterruptedException {
        ArrayList<Integer> arrayList = new ArrayList<>(10000);
        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                for (int j = 0; j < 100; j++) {
                    arrayList.add(j);
                }
            }).start();
        }
        Thread.sleep(1000);
        System.out.println(arrayList.size()); //测试多次，打印的结果总是少于1000，线程不安全
    }
}

//LinkedList:
public class ListExample {
    public static void main(String[] args) throws InterruptedException {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                for (int j = 0; j < 100; j++) {
                    linkedList.add(j);
                }
            }).start();
        }
        Thread.sleep(1000);
        System.out.println(linkedList.size()); //测试多次，打印的结果始终少于1000，线程不安全
    }
}

//Vector:
public class ListExample {
    public static void main(String[] args) throws InterruptedException {
        Vector<Integer> vector = new Vector<>();
        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                for (int j = 0; j < 100; j++) {
                    vector.add(j);
                }
            }).start();
        }
        Thread.sleep(1000);
        System.out.println(vector.size()); //测试多次，打印的结果始终是1000，线程安全
    }
}

//...使线程不安全的集合结果也为1000，加入synchronized代码块,使用此类的class作为锁
public class ListExample {
    public static void main(String[] args) throws InterruptedException {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                for (int j = 0; j < 100; j++) {
                    synchronized (ListExample.class) {
                        linkedList.add(j);
                    }
                }
            }).start();
        }
        Thread.sleep(1000);
        System.out.println(linkedList.size()); //1000
    }
}

Map接口

Map接口中各个实现类的对比：

HashMap
- 无序，线程不安全（效率高），允许存null值
- 初始容量：16，加载因子：0.75，扩容增量：原有容量的1倍（容量始终为2的指数）
HashTable
- 有序，线程安全（效率低），不允许存null值
- 初始容量：11，加载因子：0.75，扩容增量：2*原数组长度+1
TreeMap
- 不允许存null值
- key必须可排序（引用类型实现Comparable接口，或定义时使用参数为Comparator接口的构造初始化）
ConcurrentHashMap
- 线程安全
- 不允许key为null值 ```java //使用HashMap测试线程是否安全 public class TestTreeMap { public static void main(String[] args) throws InterruptedException { HashMap<String, String> hashMap = new HashMap<>(); for (int i = 0; i < 100; i++) { new Thread(() -> { for (int j = 0; j < 100; j++) { hashMap.put(UUID.randomUUID().toString(), “老铁没毛病”); } }).start(); } Thread.sleep(1000); System.out.println(hashMap.size()); //经过多次测试，结果均不足10000，线程不安全 } }
//换成ConcurrentHashMap public class TestTreeMap { public static void main(String[] args) throws InterruptedException { ConcurrentHashMap<String, String> concurrentHashMap = new ConcurrentHashMap<>(); for (int i = 0; i < 100; i++) { new Thread(() -> { for (int j = 0; j < 100; j++) { concurrentHashMap.put(UUID.randomUUID().toString(), “老铁没毛病”); } }).start(); } Thread.sleep(1000); System.out.println(concurrentHashMap.size()); //经过多次测试，结果总是10000 } } ```
Queue接口，特点：无序，可重复
- 没有实现的阻塞接口的LinkedList
- 实现了java.util.Queue接口和java.util.AbstractQueue接口，内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue

add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
offer       添加一个元素并返回true       如果队列已满，则返回false
poll         移除并返问队列头部的元素    如果队列为空，则返回null
peek       返回队列头部的元素             如果队列为空，则返回null
put         添加一个元素                      如果队列满，则阻塞
take        移除并返回队列头部的元素     如果队列为空，则阻塞

对比：

PriorityQueue
- PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。
ConcurrentLinkedQueue
- ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。

ArrayBlockingQueue在构造时需要指定容量，并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列，此队列按 FIFO（先进先出）原则对元素进行排序。

PriorityBlockingQueue是一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元素要具有比较能力。

DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

PriorityQueue

```java public class QueueExample { public static void main(String[] args) { PriorityQueue priorityQueue = new PriorityQueue<>(); priorityQueue.add("你好世界"); priorityQueue.add("鸡儿"); priorityQueue.add("老铁"); priorityQueue.add("老铁"); //priorityQueue.add(null); //空指针异常 System.out.println(priorityQueue);
```
  Object[] objects = priorityQueue.toArray();
  System.out.println(Arrays.toString(objects));   } }
```

//输出结果： [你好世界, 老铁, 老铁, 鸡儿] [你好世界, 老铁, 老铁, 鸡儿]

```java
public class QueueTest {
    public static void main(String[] args) {
        Queue<String> priorityQueue = new PriorityQueue<>(Arrays.asList("年后", "123", "456", "hu", "老铁", "GG"));
        System.out.println(priorityQueue);

        priorityQueue.add("1231");
        priorityQueue.add("123");

//        System.out.println(priorityQueue.remove()); //返回队列的head,并移除,跟poll()的唯一区别就是如果队列为empty则抛出NoSuchElementException
//        System.out.println(priorityQueue.element()); //返回队列的head,但不移除,跟peek()的唯一区别就是如果队列为empty则抛出NoSuchElementException
//        System.out.println(priorityQueue.poll()); //返回队列的head,并移除他,如果队列为empty,则返回null
//        System.out.println(priorityQueue.peek()); //返回队列的head,但不移除,如果队列为empty,则返回null

        System.out.println(priorityQueue);
    }
}

//输出结果：
[123, hu, 456, 年后, 老铁, GG]
[123, 123, 1231, hu, 老铁, GG, 456, 年后]


public class QueueTest {
    public static void main(String[] args) {
        Queue<String> priorityQueue = new PriorityQueue<>();
        priorityQueue.add("年后");
        priorityQueue.add("123");
        priorityQueue.add("456");
        priorityQueue.add("hu");
        priorityQueue.add("老铁");
        priorityQueue.add("GG");
//        Queue<String> priorityQueue = new PriorityQueue<>(Arrays.asList("年后", "123", "456", "hu", "老铁", "GG"));
        System.out.println(priorityQueue);

        priorityQueue.add("1231");
        priorityQueue.add("123");

//        System.out.println(priorityQueue.remove()); //返回队列的head,并移除,跟poll()的唯一区别就是如果队列为empty则抛出NoSuchElementException
//        System.out.println(priorityQueue.element()); //返回队列的head,但不移除,跟peek()的唯一区别就是如果队列为empty则抛出NoSuchElementException
//        System.out.println(priorityQueue.poll()); //返回队列的head,并移除他,如果队列为empty,则返回null
//        System.out.println(priorityQueue.peek()); //返回队列的head,但不移除,如果队列为empty,则返回null

        System.out.println(priorityQueue);
    }
}

//输出结果：
[123, hu, 456, 年后, 老铁, GG]
[123, 123, 1231, hu, 老铁, GG, 456, 年后]

public class QueueExample {
    public static void main(String[] args) {
        PriorityQueue<Object> priorityQueue = new PriorityQueue<>();
        //priorityQueue.add(new Object()); //Exception in thread "main" java.lang.ClassCastException: java.lang.Object cannot be cast to java.lang.Comparable
        //priorityQueue.add(null); //空指针异常
        System.out.println(priorityQueue);
    }
}

ConcurrentLinkedQueue

public class QueueExample {
    public static void main(String[] args) {
        ArrayBlockingQueue<String> arrayBlockingQueue = new ArrayBlockingQueue<>(5);
        arrayBlockingQueue.add("123");
        arrayBlockingQueue.add("321");
        arrayBlockingQueue.add("321");
        arrayBlockingQueue.add("222");
        arrayBlockingQueue.add("132");
        System.out.println(arrayBlockingQueue);
    }
}
  
//运行结果：
[123, 321, 321, 222, 132]

参考资料：

Java集合中List,Set以及Map等集合体系详解

Java中的集合体系

这个也是个基础鸭😝😝😝

集合体系

Collection接口

Set接口，特点：无序，唯一

List接口，特点：有序，可重复

小实验：

Map接口

Queue接口，特点：无序，可重复

PriorityQueue

ConcurrentLinkedQueue

CATALOG

FEATURED TAGS

FRIENDS