Java集合

并发集合

Java5介绍了并发集合,大部分位于java.util.concurrent并发包中。

  • ConcurrentHashMap
  • CopyOnWriteArrayList:目的是高效并发读取。很多应用场景中,要求读操作尽可能快,写操作可以相对慢。CopyOnWriteArrayList中利用CopyOnWrite机制优化到写入不会阻塞读取
  • ConcurrentLinkedQueue:通过CAS操作和锁分离,是高并发环境中性能最好的队列。
  • BlockingQueue:线程间数据共享阻塞队列接口,它有不同的实现。BlockingQueue让从队列中获取消息的服务线程在队列空时等待,当有消息后再将线程唤醒。主要操作它的put和take方法。
  • ConcurrentSkipListMap:随机数据结构,跳表。跳表的内部维护了分层的多个链表,使用锁分离机制,查询时间复杂度是O(lgn)。

ConcurrentHashMap

ConcurrentHashMap,不仅提供线程安全,还用锁分离和内部分区等现代技术提高了可扩展性。把实际map分割(segmentation)成若干部分,默认值为16,使的多线程减小争用。但其size()等方法可能需要全局锁而取得所有段的锁,性能反而比HashMap低。

(低并发)线程安全容器:

  • Collections.synchronizedMap()
  • Collections.synchronizedList()
  • Vector
  • Hashtable:大小增加到一定的时候,性能会急剧下降,因为迭代时整个map需要被锁定很长的时间。

BlockingQueue

ArrayBlockingQueue

LinkedBlockingQueue:通过takeLock、putLock两把锁实现了读数据和写数据的分离,实现了对独占锁分离。

 

PriorityQueue 保证最高或者最低优先级的的元素总是在队列头部,当遍历一个 PriorityQueue 时,没有任何顺序保证。
LinkedHashMap 维持的顺序是元素插入的顺序。LinkedHashMap 课保证遍历顺序是元素插入的顺序。
集合的排序:可以使用有序集合,如 TreeSet 或 TreeMap,或者使用有顺序的的集合,如List,然后通过 Collections.sort() 来排序。
打印数组:数组没有实现 toString() 方法,可以使用 Arrays.toString() 和 Arrays.deepToString() 方法来转为字符串再打印数组。
Java 中的 LinkedList 是单向链表还是双向链表。在 Eclipse,可以使用快捷键 Ctrl + T,直接在编辑器中打开该类检查源码。
Java 中的 TreeMap 是使用红黑树实现的。
在 Java 7 中,ArrayList 的默认大小是 10 个元素。Java 7 中 ArrayList 和 HashMap 类的代码片段:

// from ArrayList.java JDK 1.7
private static final int DEFAULT_CAPACITY = 10;

//from HashMap.java JDK 7
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

遍历 ArrayList 时移除一个元素,不是使用ArrayList 的 remove() ,而是使用Iterator 的 remove()方法,则不会出现 ConcurrentModificationException 异常。
想使用 Java 中增强的for-each 循环来遍历,只需要实现 Iterable 接口。或者实现 Collection 接口,默认就具有该属性。
Vector、Hashtable等是同步集合类,用同步方法来实现了线程安全, 而ArrayList、HashMap等不是线程安全的。

Java集合继承结构
集合继承结构

HashMap

由数组加链表实现

默认大小是16个元素(必须是2的幂),因为可以通过按位与计算余数,比求模更快。

Hashtable 与 HashMap

a) Hashtable 是 JDK 1 遗留下来的类,而 HashMap 是后来增加的。
b)Hashtable 是同步的,比较慢,但 HashMap 没有同步策略,所以会更快。
c)Hashtable 不允许有个空的 key,但是 HashMap 允许出现一个 null key。
大多数情况下,只要不涉及线程安全问题,Map基本都可以使用HashMap。HashMap的是无序的,允许将null用作键和值,非线程安全。HashMap不能保证元素的顺序,HashMap能够将键设为null,也可以将值设为null。
Hashtable,(注意大小写:不是HashTable),Hashtable不能将键和值设为null,否则运行时会报空指针异常错误,Hashtable是线程安全的。
HashSet 的内部采用 HashMap来实现。HashSet 允许有一个null key。

LinkedHashMap

LinkedHashMap增加了时间和空间上的开销,通过维护一个运行于所有条目的双向链表,LinkedHashMap保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。LinkedHashMap是有序、Key和Value都允许空、非线程安全的。LinkedHashMap可以认为是HashMap+LinkedList,即它既使用HashMap操作数据结构,又使用LinkedList维护插入元素的先后顺序。LinkedList每次访问一个元素(get或put),被访问的元素都会被提到最后面。
LinkedHashMap可以应用来实现LRUCache,LRU即Least Recently Used 最近最少使用。当缓存满了,优先淘汰最不常访问的数据。

LinkedHashMap相关问题:
java.lang.ClassCastException: java.util.LinkedHashMap cannot be cast to xxx。
rpc远程调用在底层还是使用的HTTPClient,所以在传递参数的时候,必定要有个顺序,不然服务层在接的时候就出问题了,所以它才会转为LinkedHashMap。spring 有一个类叫ModelMap,继承了linkedhashMap,即 public class ModelMap extends LinkedHashMap,所以一个接口返回的结果就可以直接用ModelMap来接。注意ModelMap是没有泛型的,不管返回的结果是什么类型的map,泛型是多复杂的map,都可以直接new一个Modelmap,用它来接返回的结果。

Java 中使用 Collections 的最佳实践

a)使用正确的集合类。如果不需要同步列表,使用 ArrayList 而不是 Vector。
b)优先使用并发集合。不是对集合进行同步并,发集合提供更好的可扩展性。
c)使用接口表示和访问集合。如使用List存储 ArrayList,使用 Map 存储 HashMap 。
d)使用集合的时候使用泛型。
e)使用迭代器来循环集合。

线程安全的集合

喂,SHE
喂(V,Vector)
S(Stack)
H(Hashtable)
E(Enumeration)

生产者消费者模型

在现实中许多线程问题都属于生产者消费者模型。较低级的解决方式是用wait和notify,更好的办法是用Semaphore 或者 BlockingQueue。

生产者消费者模型,准确地说应该是“生产者-消费者-仓储”模型,有以下几点需要明确:
1、生产者仅仅在仓储未满时候生产,仓满则停止生产。
2、消费者仅仅在仓储有产品时候才能消费,仓空则等待。
3、当消费者发现仓储没产品可消费时候会通知生产者生产。
4、生产者在生产出可消费产品时候,应该通知等待的消费者去消费。

生产者消费者问题是研究多线程程序时绕不开的经典问题之一,它描述是有一块缓冲区作为仓库,生产者可以将产品放入仓库,消费者则可以从仓库中取走产品。解决生产者/消费者问题的常用方法是采用某种机制保护生产者和消费者之间的同步,常用的同步方法是采用信号或加锁机制,保证资源在任意时刻至多被一个线程访问。

如下代码示例,使用了BlockingQueue阻塞队列来线程间共享数据:

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * java多线程模拟生产者消费者问题
 * 
 * ProducerConsumerApplication是主类,Producer生产者,Consumer消费者,Product产品,Storage仓库
 */
public class ProducerConsumerApplication {
    public static void main(String[] args) {
        ProducerConsumerApplication pc = new ProducerConsumerApplication();
        Storage s = pc.new Storage();
        Producer p1 = pc.new Producer("生产者1", s);
        Producer p2 = pc.new Producer("生产者2", s);
        Consumer c1 = pc.new Consumer("消费者1", s);
        Consumer c2 = pc.new Consumer("消费者2", s);
        Consumer c3 = pc.new Consumer("消费者3", s);

        ExecutorService service = Executors.newCachedThreadPool();
        service.submit(p1);
        service.submit(p2);
        service.submit(c1);
        service.submit(c2);
        service.submit(c3);
    }

    /**
     * 消费者
     */
    class Consumer implements Runnable {
        private String name;
        private Storage s = null;

        public Consumer(String name, Storage s) {
            this.name = name;
            this.s = s;
        }

        public void run() {
            try {
                while (true) {
                    System.out.println(name + "准备消费产品.");
                    Product product = s.pop();
                    System.out.println(name + "已消费(" + product.toString() + ").");
                    Thread.sleep(500);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 生产者
     */
    class Producer implements Runnable {
        private String name;
        private Storage s = null;

        public Producer(String name, Storage s) {
            this.name = name;
            this.s = s;
        }

        public void run() {
            try {
                while (true) {
                    Product product = new Product((int) (Math.random() * 10000)); // 产生0~9999随机整数
                    System.out.println(name + "准备生产(" + product.toString() + ").");
                    s.push(product);
                    System.out.println(name + "已生产(" + product.toString() + ").");
                    Thread.sleep(500);
                }
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }
        }
    }

    /**
     * 仓库,用来存放产品
     */
    public class Storage {
        BlockingQueue queues = new LinkedBlockingQueue(10);

        /**
         * 生产
         */
        public void push(Product p) throws InterruptedException {
            queues.put(p);
        }

        /**
         * 消费
         */
        public Product pop() throws InterruptedException {
            return queues.take();
        }
    }

    /**
     * 产品
     */
    public class Product {
        private int id;

        public Product(int id) {
            this.id = id;
        }

        public String toString() {
            // 重写toString方法
            return "产品:" + this.id;
        }
    }
}

发表评论