容器在物理层面分为两类，内存连续和内存不连续的容器

  • 内存连续的主要有数组、ArrayList、Set
  • 内存不连续的主要有HashMap,LinkedList

JAVA最原始的数组有两个:Hashtable和Vector
这里我们聊一下这两个容器的发展历程

Hashtable -> HashMap -> SynchronizedHashMap -> ConcurrentHashMap

    1. Hashtable
      最原始的Hashtable的所有方法都是加了synchronized，因此是线程安全的，但是效率较低
    1. HashMap
      HashMap 线程不安全，效率提升，适用单线程情况下。
    1. SynchronizedHashMap
      HashMap 可以借助 Collections.synchronziedMap()保证线程安全，底层使用 synchronized 同步代码块，效率比 Hashtable 高。
Map<UUID, UUID> m = Collections.synchronizedMap(new HashMap<>());

部分底层代码
通过锁住一个final的称为mutex的Object对象来线程安全，相比于Hashtable而言，Hashtable直接在方法上添加synchronized关键字，SynchronizedHashMap锁住的是代码块，效率会提升一些，但是差距不大。

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
  • ConcurrentHashMap

适用于大量并发情况下提高集合的效率和安全。使用了 CAS + synchronized 代码块锁。保证安全的同时，性能均也很高。
相比于上面的几种容器，ConcurrentHashMap在写的效率较低，但是在读的效率上具有极大的提高。

但是ConcurrentHashMap并不一定是最好的容器，类似synchronized与CAS的性能问题，在每种容器都有自己适合的地方。

Vector -> List -> ConcurrentLinkedQueue

首先，思考一个问题

有N张火车票，每张票都有一个编号
同时有10个窗口对外售票
请写一个模拟程序

1.使用List

但是，List不是线程安全的，在票将要售空的时候，有多个线程都会读到size>0,进而销售票，然而此时的票数已经空了，因此会出现超量销售的问题。

public class TicketSeller1 {
    static List<String> tickets = new ArrayList<>();

    static {
        for (int i = 0; i < 10000; i++) tickets.add("票编号：" + i);
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                while (tickets.size() > 0) {
                    System.out.println("销售了--" + tickets.remove(0));
                }
            }).start();
        }
    }
}

2.使用线程安全的Vector

尽管Vector是线程安全的，但是仍然会出现上一种解法的问题
就算操作A和B都是同步的，但A和B组成的复合操作也未必是同步的，仍然需要自己进行同步，就像这个程序，判断size和进行remove必须是一整个的原子操作

public class TicketSeller2 {
    static Vector<String> tickets = new Vector<>();
    
    static {
        for (int i = 0; i < 1000; i++) tickets.add("票 编号：" + i);
    }

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                while (tickets.size() > 0) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println("销售了--" + tickets.remove(0));
                }
            }).start();
        }
    }
}

3.使用List，并通过synchronized将size和remove方法锁在一个代码块里

public class TicketSeller3 {
    static List<String> tickets = new ArrayList<>();

    static {
        for (int i = 0; i < 1000; i++) tickets.add("票 编号：" + i);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (tickets) {
                        if (tickets.size() <= 0) break;
                        System.out.println("销售了--" + tickets.remove(0));
                    }
                }
            }).start();
        }
    }
}

使用ConcurrentQueue提高并发性

public class TicketSeller4 {
    static Queue<String> tickets = new ConcurrentLinkedQueue<>();

    static {
        for (int i = 0; i < 1000; i++) tickets.add("票 编号：" + i);
    }

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                while (true) {
                    String s = tickets.poll();
                    if (s == null) break;
                    else System.out.println("销售了--" + s);
                }
            }).start();
        }
    }
}

hhhhh