编辑

集合

2019-07-09 网络 java-basics java-basics

---

• content

概览

Iterator

方法列表：

• hasNext()
• next() //比较expectedModCount与modCount，不相等则抛出ConcurrentModificationException异常
• remove() //比较expectedModCount与modCount，不相等则抛出ConcurrentModificationException异常
• forEachRemaining() //jdk1.8新增对lambda表达式支持

Iterator是一种fail-fast的实现，对元素遍历的时候不允许修改，如果发生修改操作则下一次next()方法执行时则抛出ConcurrentModificationException异常

for-each是通过iterator来实现的

ListIterator

可以通过List.listIterator()方法产生ListIterator，它继承自Iterator，比Iterator多了以下方法：

• hasPrevious()、previous() //不光能向后遍历，还能向前遍历
• nextIndex()、previousIndex() //返回索引位置
• add() //可以在游标前添加元素
• set() //可以修改游标指向的元素

Collection

介绍

遍历Collection的方式：

1.for-each

Collection<Person> persons = new ArrayList<Person>();
for (Person person : persons) {
    System.out.println(person.name);  
}

2.Iterator

Collection<Person> persons = new ArrayList<Person>();
Iterator iterator = persons.iterator();
while (iterator.hasNext) {
    System.out.println(iterator.next);  
}

3.stream api

Collection<Person> persons = new ArrayList<>();
persons.stream().forEach(p->{
    System.out.println(p.name);
});
persons.stream().forEach(new Consumer<Person>() {
    @Override
    public void accept(Person person) {
        System.out.println(person.name);
    }
});

List

存储在List中的元素具有以下特点：有序，可重复，可为null

通过元素对象的equals()来比较是否相等

List.subList(int fromIndex,int toIndex)方法并不是生成一个新的List，仅仅是对原始List的引用，所以对subList的操作会影响到原List

ArrayList

非线程安全，通过数组实现，初始大小10，加载因子1，满了之后默认扩容%50

适合随机访问get(index)，在中间add/delete性能差

遍历时不允许修改，否则抛出ConcurrentModificationException异常

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
Iterator<String> it = list.iterator();
while(it.hasNext()){
    System.out.println("list is:"+list);
    String str = it.next();
    System.out.println(str);
    if(str.equals("B")) {
        list.remove("E");
    }
    if(str.equals("C")) {
        list.add("CC");
    }
    if(str.equals("D")) {
        list.set(0, "D");
    }
}

ArrayList实现RandomAccess接口，遍历时使用get(index)的方式比Iterator的方式快

//更快
for(int i=0, n=list.size(); i < n; i++) {
    list.get(i);
}
//较慢
Iterator iterator=list.iterator();
while(iterator.hasNext()){
    iterator.next();
}

CopyOnWriteArrayList

线程安全，是ArrayList的线程安全的版本，适用于读多写少的并发场景，与ArrayList不同，它允许在遍历时修改元素，每一次修改操作都是通过创建底层数组的新副本的方式来实现，内存使用比纯ArrayList多

上面ArrayList的示例中第一行修改为CopyOnWriteArrayList则运行正常

List<String> list = new java.util.concurrent.CopyOnWriteArrayList<>();
//...

Collections.synchronizedList vs CopyOnWriteArrayList

CopyOnWriteArrayList和Collections.synchronizedList是实现线程安全的列表的两种方式。两种实现方式分别针对不同情况有不同的性能表现，其中CopyOnWriteArrayList的写操作性能较差，而多线程的读操作性能较好。而Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多，而读操作因为是采用了synchronized关键字的方式，其读操作性能并不如CopyOnWriteArrayList。因此在不同的应用场景下，应该选择不同的多线程安全实现类。

LinkedList

非线程安全，通过双向链表实现，实现Deque接口(双端队列)，不存在元素个数限制，没有扩容机制，元素是有序的，允许Null，所有指定位置操作都是从头开始遍历

适合频繁插入、删除，不适合随机访问

继承自AbstractSequentialList抽象类，没有实现RandomAccess接口，Iterator遍历比for-each遍历速度快

LinkedList<String> linkedList = new LinkedList<>();

//速度较慢
for(int i=0;i<linkedList.size();i++){
    linkedList.get(i);
}

//速度更快
Iterator iterator = linkedList.iterator();
while(iterator.hasNext()){
    iterator.next();
}

Vector、Stack（不推荐使用）

• Vector：线程安全，通过数组实现，初始大小10，默认扩容1倍(可以构造函数设置capacityIncrement)，类似于ArrayList，但是由于所有操作都加锁，性能差
• Stack：线程安全，继承自Vector，是实现了FILO（先进后出）的堆栈，提供了pop/posh/peek方法，性能差，推荐使用Dequeue/ArrayDeque（Double Ended Queue）替代，实现更完善

Collections.synchronizedList vs Vector

1. 两者扩容机制不一样，Collections.synchronizedList扩容50%，Vector扩容100%
2. Collections.synchronizedList可以指定锁定对象
3. Collections.synchronizedList可以将所有的List的子类转换成线程安全的类，包括LinkedList等
4. Collections.synchronizedList可以将传入的List转换称为线程安全的List(将传入的List当成底层数据源，外面做了一层封装)，但是在使用Iterator遍历的时候还是需要手动加锁，Vector是全部操作都加锁

Set

存储在Set中的元素具有以下特点：不可重复

CopyOnWriteArraySet

基于CopyOnWriteArrayList实现

TreeSet

默认初始容量16，超过0.75倍则扩容100%，支持自然顺序，add/delete/contains效率低

通过TreeMap实现，仅使用TreeMap的Key，内部实现同TreeMap一样，都是基于红黑树

HashSet

默认初始容量16，超过0.75倍则扩容100%，不保证有序，性能与容量有关

实现Set接口，通过HashMap实现，仅使用HashMap的Key

LinkedHashSet

继承自HashSet，保证元素的插入顺序

通过LinkedHashMap实现

Queue

一般情况Queue里面不允许添加null，它提供了添加、删除、检查的方法都存在两种形式，一种是操作失败则抛异常，令一种则不抛异常但是返回特殊值：

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()
{: .table.table-bordered }

PriorityQueue类

默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字母顺序排列，可以指定Comparator自定义元素排序规则

BlockingQueue接口

线程安全的队列，一般遵循FIFO（先进先出），常用于消费者模式（利用put、take阻塞方法）

	抛出异常	返回特殊值	阻塞	超时
入队	add(e)	offer(e)	put(e)	offer(e, time, unit)
出队	remove()	poll()	take()	poll(time, unit)
检查	element()	peek()
{: .table.table-bordered }

ArrayBlockingQueue

初始化必须指定大小。

put、take的实现方式是 Object[]数组+ReentrantLock+Condition ， 操作使用同一把锁，多CPU无法并行读和写。

//基本使用方法示例

Queue<String> queue  = new ArrayBlockingQueue<>(3);

//队列为空时，使用element()获取元素会抛异常，使用peek()则返回null，take()会阻塞
//String e0 = queue.element();
String e0 = queue.peek();
System.out.println(e0);
//((ArrayBlockingQueue<String>) queue).take();

//添加元素，不管offer()还是add()方法，添加null都不允许，会抛出异常
//queue.offer(null);
//queue.add(null);
queue.offer("add1");
queue.add("add2");
((ArrayBlockingQueue<String>) queue).put("add3");

//当队列满时再添加，add()会抛出异常，offer()返回false，put()会阻塞
//queue.add("add4");
boolean addSuccess = queue.offer("add4");
((ArrayBlockingQueue<String>) queue).put("add4");

//获取队列头部元素，不删除
String e1 = queue.element();
System.out.println(e1);
String e2 = queue.peek();
System.out.println(e2);

//获取队列头部元素，并删除
String e3 = ((ArrayBlockingQueue<String>) queue).take();
System.out.println(e3);
String e4 = queue.remove();
System.out.println(e4);
String e5 = queue.poll();
System.out.println(e5);

//生产者-消费者示例
import java.util.Random;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
public class Producer implements Runnable {
    BlockingQueue blockingQueue;
    Random random = new Random(1000000);
    public Producer(BlockingQueue blockingQueue){
        this.blockingQueue = blockingQueue;
    }

    @Override
    public void run() {
        try {
            while (true) {
                TimeUnit.MILLISECONDS.sleep(1000);

                int value = random.nextInt();

                System.out.println("producing: "+ value);

                blockingQueue.put(value);
            }
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}


import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
public class Consumer implements Runnable {
    BlockingQueue blockingQueue;
    String consumerName;
    public Consumer(BlockingQueue blockingQueue, String consumerName){
        this.blockingQueue = blockingQueue;
        this.consumerName=consumerName;
    }

    @Override
    public void run() {
        try {
            while (true) {
                TimeUnit.MILLISECONDS.sleep(1000);
                Object value = blockingQueue.take();
                System.out.println(consumerName+" take value: "+value);
            }
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
public class App {
    public static void main(String[] args) {
        BlockingQueue blockingQueue = new LinkedBlockingQueue();
        Producer p=new Producer(blockingQueue);
        Consumer c1=new Consumer(blockingQueue,"c1");
        Consumer c2=new Consumer(blockingQueue,"c2");
        new Thread(p).start();
        new Thread(c1).start();
        new Thread(c2).start();
    }
}

LinkedBlockingQueue（推荐）

默认长度为Integer.MAX_VALUE（可能导致OOM），也可以构造函数自己指定。

put、take操作使用各自不同的锁，读写操作可以并行，吞吐量高于ArrayBlockingQueue；使用的count参数是AtomicInteger类型，因为可能存在读写操作同时来更新。

ConcurrentLinkedQueue、ConcurrentLinkedDeque

ArrayBlockingQueue，LinkedBlockingQueue都是使用ReentrantLock机制，put/take方法在没有元素存在的情况下线程阻塞

ConcurrentLinkedQueue、ConcurrentLinkedDeque使用CAS，不会阻塞

PriorityBlockingQueue

可以指定排序方式

Deque

继承自Queue接口，有以下实现类：ArrayDeque（数组双端队列）、LinkedList（链表双端队列），LinkedBlockingDeque（阻塞链表双端队列），ConcurrentLinkedDeque（当做并发环境的栈使用）

它提供了完整的操作队列头部和尾部元素的方法：

	First Element (Head)	First Element (Head)	Last Element (Tail)	Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()
{: .table.table-bordered }

可以FIFO当队列用：

Queue Method	Equivalent Deque Method
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()
{: .table.table-bordered }

也可以FILO当栈用（替代Stack）：

Stack Method	Equivalent Deque Method
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()
{: .table.table-bordered }

• ConcurrentLinkedDeque

线程安全，可以当做并发环境的栈使用，没有使用锁，更高效

Node + CAS

• LinkedBlockingDeque

线程安全，也可以当做栈使用，提供阻塞功能，使用锁机制

Node + ReentrantLock + Condition.await()

Collections工具类

Collections.synchronizedList(List<T> list)

Collections.synchronizedMap(Map<K,V> map)

sort：归并排序

shuffle：随机打乱

reverse：反转元素顺序

swap：交换

binarySearch：二分查找

Arrays工具类

Map

HashMap

非线程安全，默认初始容量16，加载因子0.75，超过0.75倍则扩容100%，允许一个null键

HashMap是无序的，存入的顺序和遍历的顺序不一定一致（实际在遍历的时候很多情况下是跟存入的顺序一致的）

JDK1.7中使用数组+链表的形式

JDK1.8中的HashMap使用数组+链表形式，如果链表长度>8，则链表转换为红黑树

• 为什么HashMap线程不安全？

  a. put的时候导致的多线程数据不一致。

  b. 另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%）。原因见参考文章。

HashTable

线程安全，默认初始容量11，加载因子0.75，超过0.75倍则扩容100%+1

LinkedHashMap

非线程安全，继承自HashMap，在HashMap的基础上又维护一个双向链表，存放元素插入顺序

TreeMap

非线程安全，间接实现SortedMap接口，按照key排序，可以指定comparator自定义排序规则，内部实现为红黑树

ConcurrentHashMap

ConcurrentHashMap 和 HashMap 对比介绍 JDK1.7 vs1.8

JDK1.7中ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。get方法不加锁。

JDK1.8中同HashMap一样采用了链表+数组/红黑树，抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

常见问题

ArrayList与Array的区别

• Array长度固定，不可以随意添加、删除，而ArrayList是动态的
• Array只能存储相同类型数据，ArrayList可以存储不同类型
• Array可以存储基本类型+包装类型，ArrayList只能存储包装类型

ArrayList与LinkedList的区别

• ArrayList基于数组实现，随机访问性能好，从中间添加、删除元素的性能差，因为要调整其它元素位置，会动态扩容
• LinkedList基于双向链表实现，随机访问新能差，添加、删除元素性能好，没有扩容机制

参考

Java集合框架

Java集合深入理解

Java并发编程–BlockingQueue

透彻理解Java并发编程

五分钟搞懂红黑树

二叉树之BST、AVL和RBT

ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)

为什么HashMap线程不安全

为什么可以使用位运算(&)来实现取模运算(%)呢？

• 前一篇: vagrant virtualbox
• 后一篇: dns

添加评论

文章目录