Fail-fast And fail-safe

我们可以通过迭代器遍历集合对象，迭代器分为fail-fast和fail-safe两种类型，fail-fast是指当我们通过迭代器遍历集合时，如果集合元素发生了修改，会抛出ConcurrentModificationException异常。fail-safe类迭代器则不会抛出这类异常。

Fail-fast case

1
2
3
4
5
6
7
8
9
10
11
12

public static void main(String[] args) {
    ArrayList<Integer>data = new ArrayList<>();
    data.add(1);
    data.add(2);
    data.add(3);
    Iterator<Integer> ptr = data.iterator();
    while (ptr.hasNext()){
        Integer a = ptr.next();
        System.out.println(a);
        data.remove(a);
    }
}

执行如上代码，在通过迭代器遍历集合时，对集合进行修改，删除了一个元素，迭代器在遍历时会抛出如下ConcurrentModificationException异常：

Fail-Fast Iterators internal working

以ArrayList为例，分析fail-fast的原理。ArrayList有一个迭代器内部类 ListItr, 我们在通过iterator()方法返回ArrayList对象的迭代器时就是返回这个类的一个实例。

1
2
3

public Iterator<E> iterator() {
    return new Itr();
}

内部类 ListItr 有一个属性expectedModCount，在创建 ListItr 实例时会赋值为modCount，而modCount则是在构建迭代器之前当前ArrayList实例的修改次数，当对ArrayList对象进行修改时，modCount的值都会加1。内部类 ListItr 有一个内部方法：

1
2
3
4

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

在通过迭代器调用next, add, remove, set等方法时，首先会执行如上checkForComodification方法，如果在这之前集合对象发生了修改，那modCount的值增加以后，将会执行if语句中泡出异常的操作。

但是如果我们使用内部类ListItr自身提供的修改方法，则不会抛出ConcurrentModificationException异常，因为这些方法实现会更新expectedModCount的值。

Fail-safe case

和fail-fast的迭代器不同，fail-safe类迭代器遍历集合时，如果对集合进行修改，会拷贝一份集合元素的副本，在副本上进行修改，所以不会抛出异常。以CopyOnWriteArrayList为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static void main(String[] args) {
    List<Integer> data = new CopyOnWriteArrayList<>();
    data.add(1);
    data.add(2);
    data.add(3);
    Iterator<Integer>iterator = data.iterator();
    while (iterator.hasNext()){
        Integer a = iterator.next();
        if (a==2){
            data.add(4); //modify while traverse over the collection.
        }
        System.out.print(String.valueOf(a)+' ');
    }
}

运行结果：

即时我们在遍历过程中对集合进行了添加元素，也不会体现在遍历结果中，因为是在另一个副本中进行添加的。

Fail-safe internal working

看一下是如何对副本进行操作的，以add方法为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray(); //return array, which store the element.
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); //array length incremented to original length + 1, and copy the original elements to newElement array.
        newElements[len] = e; //the last solt is e, which we want to add.
        setArray(newElements); //set the original array reference to newElements.
        return true;
    } finally {
        lock.unlock();
    }
}

可见添加元素是重新开辟了一份数组空间，添加了元素之后再修改数组引用。CopyOnWriteArrayList的迭代器遍历的却是原来的数组：

1
2
3
4
5
6
7
8
9

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0); //getArray() return the original array reference.
}
private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    //traverse the array by snapshot, the snapshot is the original array. elements may receive new array 
    //value, so we need use snapshot to store its reference.
    snapshot = elements; 
}

显然，使用CopyOnWriteArrayList的缺点也是明显的，首先，由于在副本上进行修改操作，遍历其上的迭代器不能反映出其最新的状态，其次，需要一份额外的内存空间，还需要对元素进行拷贝迁移，这也是很耗费性能的，所以应该尽量在读多写上的场景进行使用。

参考文献

Fail-fast and Fail-safe iterations in Java Collections

RN开发小结

什么是RN

React Native是Facebook基于React 开源的移动端开发框架，React是一个通过声名式UI构建组件的JavaScript库，React Native结合了原生的流畅和React的特性，是目前比较流行的移动端开发框架之一。通过声明组件，组合这些组件，完成App开发的复杂功能，这些组件虽然都是使用JavaScript开发，但是最终渲染都会使用原生API，所以渲染的流畅程度并不会太差。

为什么使用RN

• RN具备跨端的特性，目前支持iOS和Android。目前大多数公司的移动端应用都会在iOS和Android两个平台上同时开发，开发一个feature或者修复一个bug，通常需要两个开发人员。使用React Native，开发的程序可以兼容两个平台，虽然有一些差异需要针对特定平台处理，但是还是可以节约一部分开发人力。
• 灵活更新，不需要等待发版。使用React Native开发的程序，会被打成bundle，供用户下载使用，不需要等待发版周期，这对于一些紧急需求是非常必要的。而且对于iOS的应用，很多时候应用商店会审核不过，导致用户很难体验到新的功能。一些线上bug可能需要发布热更新或者只能等待下一版本修复，但是React Native可以灵活修复，修复版本可以覆盖几乎所有用户。
• 对于开发人员来说，React Native基本上实现了所见即所得，一次修改，快速检验效果，这相比native开发所需要的漫长打包时间，大大提升了开发体验。

Key Tech

React Native通过声明式UI开发组件，然后组合组件开发出更加复杂的组件。组件分为函数式组件和类组件，函数式组件是无状态组件，类组件具备自己的状态和生命周期方法，后来为了减少类组件中各种生命周期方法的样板代码和复用状态的困难，提供了Hook，使得可以使用函数组件使用state和生命周期等特性。

• useState，这是一个hook，我们可以通过它为组件存储一个状态，并在适当的时机修改它。对于一般的变量，函数退出后它就会消失，但是对于useState定义的变量，会被保留。

• useEffect，可以将其看作以下三个函数的组合，当组件渲染完成以后，我们可能需要执行一些操作，那我们可以将这些操作放到useEffect中调用，useEffect会保存传递的函数，在每次渲染以后调用。有一些操作是需要在组件unmount之后删除的，防止内存泄露，可在useEffect的return语句中返回，进行删除。

  1 2 3

  componentDidMount() {} componentDidUpdate(){} componentWillUnmount(){}

  ​

  1 2 3 4 5

  useEffect(() => { // Have a timer call the function every 5 seconds using setInterval const timer = setInterval(() => {}, 5000); return () => clearInterval(timer); }, []);

• useRef可以用来返回一个可变的ref对象，对象的改变不会触发组件的重新渲染，在整个组件生命周期内是唯一的。

• useMemo，useMemo返回类型不限的值，只有当依赖项变化时才会触发重新计算，

• useCallBack，返回可被记忆的回调，每次依赖项改变时，都能生成新的回调。

踩坑记录

1、在实现两个组件重叠的效果中，往往需要使用绝对定位。使用绝对定位的的组件会脱离文档流，以最近的父布局作为参考，决定位置。但是这必须要指定其自身的高度或者宽度。

2、使用绝对定位有可能使组件被置于其他组件之下，导致点击事件被屏蔽，可以通过动态修改pointer-events属性来决定是否拦截点击事件。

参考文献

• React Hook

volatile

volatile可以保证修饰变量的可见性和有序性，对于被volatile修饰的变量，对其进行单个读写，等价于被synchronized修饰的读操作或者写操作。

如何保证可见性

实现情况视处理器而定，在intel处理器上，对被volatile修饰的变量进行写操作的指令，在翻译为汇编指令时，会加上lock前缀，处理器在执行这一指令时，会将缓存行中的数据写会内存，其他CPU会通过嗅探总线，如果本地内存内缓存了此变量，会时当前值无效，重新读取。

如何保证有序性

在对volatile进行读写操作指令在编译为字节码时，会通过在指令序列中插入内存屏障指令来预防编译器和处理器为提高执行效率而进行的指令重排序，以此保证执行的有序性。

synchronized

java中的每一个对象都可以作为锁，使用synchronized加锁，根据使用场景，有三种不同的情况：

• 对于普通同步方法，锁是实例对象；
• 对于同步代码块，锁是当前类的Class对象（访问当前类方法和属性的入口）；
• 对于同步方法块，锁是括号中配置的对象。
  synchronized用的锁是存在Java对象头里的，Java对象头中的Mark Word默认存储对象的hashCode，分段年龄和锁标记位。

fianl域的内存语义

编译器和处理器对于final域的的处理，在进行重排序时需要遵守两个规则：

• 在构造函数内对一个final域的写入与随后将这个引用赋值给其他引用的操作不能重排；
• 初次读一个包含final域对象的引用，与随后读这个final域，不能重排。
  实现以上规则同样是依赖在字节码指令序列中插入内存屏障。

Condition接口

synchronized关键字配合Object类提供的wait(), wait(long timeout),notify(), notifyAll()等方法，可以实现等待/通知模式。Condition接口也提供了类似的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public interface Condition {
//进入等待状态，直到其他线程调用signal()或者signalAll()方法进行唤醒。或者其他线程中断当前线程。如果当前线程返回，则已经重新获得锁。
void await() throws InterruptedException;

//不可中断
void awaitUninterruptibly();

//超时后返回，单位为毫秒
long awaitNanos(long nanosTimeout) throws InterruptedException;

//超时后返回，单位为 TimeUnit中的枚举
boolean await(long time, TimeUnit unit) throws InterruptedException;

//超时到将来的具体时间
boolean awaitUntil(Date deadline) throws InterruptedException;

//唤醒一个线程
void signal();

//唤醒所有线程
void signalAll();
}

Lock接口

synchronized进行加锁时，都是隐式加锁，不容易因为释放锁导致出错，Lock接口需要显式加锁，更加灵活。Lock接口具备synchronized关键字所不具备的灵活性：

• 超时加锁，在指定时间内如果尚未获取到锁，返回false，如果在超时等待的时间内被中断，则抛出异常，获取到锁则返回true。
• 可以响应中断，在线程获取锁的过程中，可以响应中断，避免死锁发生。
• 非阻塞的获取锁，使用synchronized加锁，如果没有获得锁，则会进入阻塞状态，Lock加锁则是进入等待状态。

AbstractQueuedSychronizer

AQS的设计是基于模版方法mo模式的，使用者需要继承AQS，重写指定的方法，然后组合到同步组件当中使用。同步组件对外提供的调用方法，可以委托给AQS子类具体执行。

AQS的使用

同步器提供了三个方法，可以线程安全的访问同步的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13

private volatile int state;

protected final int getState() {
    return state;
}

protected final void setState(int newState) {
    state = newState;
}

protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

具体同步组件只需视情况实现以下方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//独占式获取同步状态，在具体实现中，需要原子判断当前state是否符合预期（为旧值，其他线程未修改），如果符合，将状态设置为新值。
protected boolean tryAcquire(long arg) {
    throw new UnsupportedOperationException();
}

//释放同步状态
protected boolean tryRelease(long arg) {
    throw new UnsupportedOperationException();
}

//共享式获取
protected long tryAcquireShared(long arg) {
    throw new UnsupportedOperationException();
}

//共享式释放
protected boolean tryReleaseShared(long arg) {
    throw new UnsupportedOperationException();
}

//判断当前状态是否被独占
protected boolean isHeldExclusively() {
    throw new UnsupportedOperationException();
}

同步组件对外提供了一些模版方法，供外部查询和操作同步状态，这些方法可以支持超时和中断的独占式获取和共享式获取同步状态。值得注意的是，这些方法都已经被final修饰，不可重写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

AQS的实现

同步队列

同步器依赖内部的同步队列来完成同步状态的管理，当前线程获取同步状态失败时，会将当前线程以及等待状态信息构成一个Node加入到队尾，同时会阻塞当前线程，当同步状态被释放时，会从队列首部唤醒节点中的线程，使其尝试获取同步状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

NOde的部分字段
static final class Node {
    volatile int waitStatus;

    volatile Node prev;

    volatile Node next;

    volatile Thread thread;

    Node nextWaiter;


}

AQS使用同步队列维护获取同步状态失败而阻塞的的线程，head指向头节点，每次获取状态失败的线程构成节点以后加入队列尾部。首节点是获取到同步状态的线程，当其释放同步状态时，会将首节点设置为其后继节点。

1
2
3
4
5
6
7
8
9
10

private final boolean compareAndSetHead(Node update) {
    return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

/**
 * CAS tail field. Used only by enq.
 */
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}

为什么使用ConcurrentHashMap

HashMap是线程不安全的，在多线程执行put操作过程中，有可能会试容量达到阈值，触发扩容操作，HashMap的扩容操作会将数组容量扩大为当前数组长度的两倍，重新遍历HashMap，将每一个链表中的元素进行重新hash，存入新的HashMap中。如果是多线程进行put，会出现链表成环，导致HashMap的get操作无法结束，CPU利用率达到100%；老生常谈，HashMap的死循环

HashTable几乎提供了与HashMap相同的操作，但是HashMap的很多方法都是通过synchronized修饰的，多线程操作会导致线程阻塞，即便是多个只进行查询操作的线程，这样使得效率非常低下。

我们可以使用Collections提供的封装方法，得到线程安全的Map。但是看了下面SynchronizedMap的实现，是使用了一个Object对象作为锁，同样每一个操作方法都被synchronized修饰了，可见效率也不高。如果需要线程安全且比较高效的HashMap，可以使用ConcurrentHashMap。

1
2
3

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

为什么ConcurrentHashMap是线程安全的

ConcurrentHashMap是由Segment数组和HashEntry数组组成的，Segment是一种可重入锁，HashEntry用于存储键值对数据。一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构，每个Segment守护一个HashEntry数组的元素，当需要对数组中的元素进行修改时，必须先获得对应Segment的锁。

初始化

• 初始化segments数组，通过conrencyLevel计算数组长度，必须是2的整数幂。
• 初始化segmentShift和segmentMask，segmentShift用于定位参与散列运算的位数，segmentMask是参与与hash做与运算的掩码，为size-1.
• 初始化每一个segment，每一个HashEntry长度同样需要是2的整数幂长度。

get操作

get操作是不需要获取锁的，因为每一个HashEntry节点的value已经被volatile修饰了，可以保证读到的值是最新的值。
定位节点分为两步，首先定位目标segment，然后再定位具体的节点

1
2

hash >>> segmentShift) & segmentMask  // 定位Segment所使用的hash算法 
int index = hash & (tab.length - 1);  // 定位HashEntry所使用的hash算法

put操作

在进行put操作时，首先定位到具体的segment，会对当前segment进行加锁，然后判断是否需要扩容，如果需要扩容，只对当前segment执行扩容操作，最后再添加元素，这不同于HashMap，HashMap添加节点以后进行扩容，如果以后都不再添加元素，这也许是一次无效扩容。

查询size

每个Segment使用volatile维护了一个表示当前segment内元素数量的count，但是显然对每个segment中count进行求和的操作不是原子性的。ConcurentHashMap还维护了一个变量，modCount，每次对ConcurrentHashMap中元素的修改操作会使得当前变量加1，所以在对count进行求和之前，保留modCount的副本，在求和以后如果modCount没有发生变化，证明求和这段时间没有线程对容器内元素进行操作，对count的求和是可靠的，如果modCount发生了改变，则需要重新求和，连续两次容器的大小都没有成功正确统计到，则对所有的segment加锁然后求和。

Java集合框架是一类用来存放元素的容器，主要分为实现了Map接口和实现了Collection接口的两类，前者存放的元素是一对key-value的映射，要求key唯一，后者存放的是单个元素，其中实现了Set接口的容器要求容器中的元素不可重复。

泛型

所谓泛型，就是类型参数话，集合框架下定义的容器希望不被局限于某一类元素，而是一套通用框架，可以存放除基本类型以为的其他类型。在集合容器变量声明时使用某一类型，那么此容器就只能存放这一类型的元素，并且容器中的元素可以调用这一类型元素可以调用的方法。

Collection类

ArrayList

ArrayList是通过数组实现的List，具有快速随机查找的特点，但是删除元素和插入元素效率较低。常用的API有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int size();
public boolean isEmpty()
public boolean contains(Object o)
public int indexOf(Object o)
public Object[] toArray() //返回一个包含当前所有元素的数组
public int lastIndexOf(Object o)

public E set(int index, E element)
public E get(int index)
public void add(int index, E element) //在指定下标插入元素
public boolean add(E e) 
public boolean remove(Object o) //删除指定下标的元素
public E remove(int index)
public void clear()
public boolean addAll(Collection<? extends E> c) //在当前列表后依次添加c中的元素

ArrayList实现了Cloneable接口，可以实现存储元素引用的浅拷贝，即两个容器中引用对象仍然相同，实现了Serializable接口，支持序列化和反序列化。

LinkedList

使用链表实现，每个节点item引用对象，和next，pre两个指针。LinkedList实现了Deque接口，可以从链表双端对链表进行操作。由于实现方式是链表，所以LinkedList具有插入和删除比较快，随机访问较慢的特点。LinkedList具有很多双端操作链表的API，可以认为如果不带显式的first和last方法，那么删除元素默认在链表尾部进行，添加元素在链表头部进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
public boolean removeLastOccurrence(Object o)
public boolean removeFirstOccurrence(Object o)

public E pop()
public void push(E e)
public E pollFirst() //删除链表首部元素
public E pollLast() 
public E peekFirst() //取得链表头节点
public E peekLast()  //取得链表尾节点
public boolean offerFirst(E e) 
public boolean offerLast(E e)

LinkedList不是线程安全的，如果有多个线程同时对LinkedList的结构进行修改（增加或者删除节点），有可能会导致链表出现环状。可以使用如下方法进行包装得到线程安全的List。

1

public static <T> List<T> synchronizedList(List<T> list)

Vector

Vector是线程安全的，有可能引起线程不安全的操作和获取相关Vector信息的值的方法都被synchronized修饰了。但是在不要求线程安全的场景下，推荐使用ArrayList代替Vector，性能更好。

Stack

Stack是继承自Vector的集合，具有后进先出的特点。

1
2
3
4
5

public E push(E item)
public synchronized E pop()
public boolean empty()
public synchronized int search(Object o)
public synchronized E peek() 

HashSet

HashSet实现了Set接口，可以保证元素的容器中元素唯一，但是不保证有序。HastSet是通过HashMap实现的，保证容器中元素唯一的方式是，每次插入的元素实际是作为(key,value)中的key，value是一个Object对象，HashMap是可以保证存入元素key是唯一的，所以HashSet能够保证容器中的元素唯一。

1
2
3

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashSet同样是线程不安全的，如果需要在多线程场景中使用hashSet，推荐如下封装：

1

Set s = Collections.synchronizedSet(new HashSet(...));

LinkedHashSet

继承自HashSet，与HashSet相同，可保证元素唯一，使用LinkedHashMap实现，可以保证插入元素顺序可知。

TreeSet

实现了SortedSet接口，可以保证容器内元素不重复，可排序。

Map类

实现了Map接口的容器类用来存放的元素是一组key到value的映射关系，LinkedHashMap继承自HashMap，可以在HashMap的基础上保证存入顺序是可知的。

HashMap

LinkedHashMap

1
2
3
4
5
6

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

LinkedHashMap实现这一功能的方式是，其中的每一个节点，都有两个指针，before和after，分别指向前一个插入节点，和后一个插入的节点。

LinkedhashMap是如何保证插入顺序有序的？重写了HashMap的newNode方法，将当前插入节点的before指针指向了插入前的尾节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void main(String[] args) {
    Map<String, Integer> scores = new LinkedHashMap<>();
    scores.put("chemistry", 93);
    scores.put("math", 98);
    scores.put("biology", 92);
    scores.put("english", 97);
    scores.put("physics", 94);
    scores.put("chinese", 99);
    scores.put("geography", 95);
    Iterator<Map.Entry<String, Integer>> iterator = scores.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Integer> score = iterator.next();
        System.out.println("subject: " + score.getKey() + " score: " + score.getValue());
    }
}

TreeMap

基于红黑树实现的，对可对key进行排序的NavigableMap。

reference：
https://zhuanlan.zhihu.com/p/34490361