LRUCache的Java实现

发表于 2019-04-21 | 分类于 Java

LRUCache简介

没错，面试的时候让我写LRUCache，当时只知道需要一个HashMap和一个链表，但是考虑的问题不全名，也没有考虑到多线程的问题。回来以后学习了下LRUCache的一些Java实现，其实可以套用LinkedHashMap，很多方法都给实现好了，当然也可以使用HashMap+链表，但是后者写起来更加复杂，当时面试的情况，感觉是让我利用LinkedHashMap数据结构。

首先缓存的大小是固定的，给缓存分配一个固定的大小。
每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。
需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。

熟悉LinkedHashMap的话可以继承LinkedHashMap来实现LRU缓存。因此需要去查看LinkedHashMap的源码。顺手写了一篇LinkedHashMap源码剖析，写的不是很深刻，不过可以了解其大概的实现方案。

LinkedHashMap实现LRUCache

LinkedHashMap自身实现了顺序存储，通过其初始化参数accessOrder可以指定其顺序方式，accessOrder为false时，采用默认的存储顺序，按照插入顺序存储，也就是一个FIFO缓冲实现，因为最老的总在最前面。而accessOrder为true时，采用的是访问顺序存储，也就是最近读取的数据放在最前面，最早读取的数据放在最后面。同时还有一个判断是否删除最老数据的方法，默认返回false，而我们需要当前缓存的长度小于链表长度时删除链表头的元素。

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/3
 * 继承LinkedHashMap实现
 */
public class LRUCache1<K, V> extends LinkedHashMap<K, V> {
    //缓存的大小
    private int cacheSize;
    //初始化时保证LinkedHashMap的初始大小要大于CacheSize+1，否则会发生扩容
    public LRUCache1(int cacheSize) {
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }
    /**
     * 重写该方法，当连表的size大于CacheSize时删除最老元素
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        LRUCache1<String, String> lruCache1 = new LRUCache1<>(6);
        for (int i = 0; i < 6; i++) {
            lruCache1.put(i+"", i * i + "");
        }
        System.out.println(lruCache1.toString());
        lruCache1.put("s", "s");
        System.out.println(lruCache1.toString());
        lruCache1.put("2", "2222");
        System.out.println(lruCache1.toString());
        lruCache1.get(1+"");
        System.out.println(lruCache1.toString());
    }
}

运行结果：

0:0 1:1 2:4 3:9 4:16 5:25
1:1 2:4 3:9 4:16 5:25 s:s
1:1 3:9 4:16 5:25 s:s 2:2222
3:9 4:16 5:25 s:s 2:2222 1:1

继承实现方式，由于继承了Map接口，在多线程环境中使用时可以使用Collections.synchronizedMap()方法来实现线程安全操作。

LinkedHashMap的委托实现

不采用继承，而是采用委托的机制，需要自己进行线程同步来适应多线程场景。

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/3
 * LinkedHashMap的委托方法
 */
public class LRUCache2<K, V> {
    //缓存大小
    private final int CACHE_SIZE;
    //默认加载因子
    private final float DEFAULT_LOAD_FACTOR = 0.75f;
    //缓存容器
    private LinkedHashMap<K, V> map;
    //初始化过程中,传入缓存的大小，根据缓存大小和默认factor来计算
    // LinkedHashMap的初始容量，确保其不会产生扩容操作。
    // 从而完成了map容器的初始化内容。
    public LRUCache2(int cacheSize) {
        this.CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
        map = new LinkedHashMap<K,V>(capacity, DEFAULT_LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CACHE_SIZE;
            }
        };
    }
    /**
     * 多线程put方法，需要加锁
     * @param key
     * @param value
     */
    public synchronized void put (K key, V value) {
        map.put(key, value);
    }
    /**
     * 多线程get方法，需要加锁
     * @param key
     * @return
     */
    public synchronized V get(K key) {
        return map.get(key);
    }
    /**
     * 多线程remove方法，需要加锁
     * @param key
     */
    public synchronized void remove(K key) {
        map.remove(key);
    }
    /**
     * 多线程getAll方法，需要加锁
     * @return
     */
    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }
    /**
     * 多线程size方法，需要加锁
     * @return
     */
    public synchronized int size() {
        return map.size();
    }
    /**
     * 多线程clear方法，需要加锁
     */
    public synchronized void clear() {
        map.clear();
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry entry : map.entrySet()) {
            sb.append(String.format(" %s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        LRUCache2<Integer, String> lruCache2 = new LRUCache2<>(5);
        for (int i = 0; i < 5; i++) {
            lruCache2.put(i,"" + i);
        }
        System.out.println(lruCache2.toString());
        lruCache2.put(5,"5");
        System.out.println(lruCache2.toString());
        lruCache2.get(2);
        System.out.println(lruCache2.toString());
        lruCache2.put(6,"6");
        System.out.println(lruCache2.toString());
        lruCache2.remove(4);
        System.out.println(lruCache2.toString());
    }
}

运行结果

1:1  2:2  3:3  4:4  5:5
1:1  3:3  4:4  5:5  2:2
3:3  4:4  5:5  2:2  6:6
3:3  5:5  2:2  6:6

LRU Cache的链表+HashMap实现

该方法可以理解为手动实现一个LinkedHashMap，同时需要自己处理所线程的问题。

import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/3
 * 链表+HashMap实现
 */
public class LRUCache3<K, V> {
    //缓存容量
    private final int CACHE_SIZE;
    //链表头
    private Entry head;
    //链表尾
    private Entry tail;
    //HashMap容器
    private HashMap<K, Entry<K, V>> hashMap;
    /**
     * 初始化HashMap容器和cacheSize
     * @param cacheSize 容量
     */
    public LRUCache3(int cacheSize) {
        this.CACHE_SIZE = cacheSize;
        hashMap = new HashMap<>();
    }
    /**
     * put方法，加锁
     * @param key
     * @param value
     */
    public synchronized void put (K key, V value) {
        Entry entry = getEntry(key);
        //hashmap中不存在key对应的entry时，新增
        if (entry == null) {
            //判断是否需要删除最老的节点
            if (hashMap.size() >= CACHE_SIZE) {
                hashMap.remove(tail.key);
                removeLast();
            }
            entry = new Entry();
            entry.key = key;
        }
        //修改
        entry.value = value;
        moveToFirst(entry);
        hashMap.put(key, entry);
    }
    /**
     * get方法，多线程加锁
     * @param key
     * @return
     */
    public synchronized V get(K key) {
        Entry<K, V> entry = hashMap.get(key);
        if (entry == null)
            return null;
        moveToFirst(entry);
        return entry.value;
    }
    /**
     * 删除
     * @param key
     */
    public synchronized void remove(K key) {
        Entry entry = getEntry(key);
        //从链表中删除
        if (entry != null) {
            if (entry.pre != null)
                entry.pre.next = entry.next;
            if (entry.next != null)
                entry.next.pre = entry.pre;
            if (entry == head)
                head = entry.next;
            if (entry == tail)
                tail = entry.pre;
        }
        //从HashMap中删除
        hashMap.remove(key);
    }
    //调整entry到链表头
    private void moveToFirst(Entry entry) {
        if (entry == head)
            return;
        if (entry.pre!= null)
            entry.pre.next = entry.next;
        if (entry.next != null)
            entry.next.pre = entry.pre;
        if (head == null || tail == null) {
            head = tail = entry;
            return;
        }
        entry.next = head;
        head.pre = entry;
        head = entry;
        entry.pre = null;
    }
    //移除链表尾的元素
    private void removeLast() {
        if (tail != null) {
            tail = tail.pre;
            if (tail == null)
                head = null;
            else
                tail.next = null;
        }
    }
    //从hashmap中获取key对应的Entry
    private Entry<K, V> getEntry(K key) {
        return hashMap.get(key);
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Entry entry = head;
        while (entry != null) {
            sb.append("").append(entry.key).append(":").append(entry.value).append("  ");
            entry = entry.next;
        }
        return sb.toString();
    }
    /**
     * Entry内部类，双链表实现
     * @param <K>
     * @param <V>
     */
    class Entry<K,V> {
        public Entry pre;
        public Entry next;
        public K key;
        public V value;
    }
    public static void main(String[] args) {
        LRUCache3<Integer, String> lruCache3 = new LRUCache3<>(5);
        for (int i = 0; i < 5; i++) {
            lruCache3.put(i,"" + i);
        }
        System.out.println(lruCache3.toString());
        lruCache3.put(5,"5");
        System.out.println(lruCache3.toString());
        lruCache3.get(2);
        System.out.println(lruCache3.toString());
        lruCache3.put(6,"6");
        System.out.println(lruCache3.toString());
        lruCache3.remove(4);
        System.out.println(lruCache3.toString());
    }
}

运行结果：

4:4  3:3  2:2  1:1  0:0  
5:5  4:4  3:3  2:2  1:1  
2:2  5:5  4:4  3:3  1:1  
6:6  2:2  5:5  4:4  3:3  
6:6  2:2  5:5  3:3

继承LinkedHashMap实现FIFO缓存

FIFO缓存只需要继承LinkedHashMap采用其默认的输出顺序就可以。

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/3
 * 继承实现FIFO缓存
 */
public class FIFOCache<K, V> extends LinkedHashMap<K, V>{
    //缓存的大小
    private int cacheSize;
    //初始化时保证LinkedHashMap的初始大小要大于CacheSize+1，否则会发生扩容
    public FIFOCache(int cacheSize) {
        super(16, 0.75f);
        this.cacheSize = cacheSize;
    }
    /**
     * 重写该方法，当连表的size大于CacheSize时删除最新插入的元素
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        FIFOCache<String, String> f = new FIFOCache<>(6);
        for (int i = 0; i < 6; i++) {
            f.put(i+"", i * i + "");
        }
        System.out.println(f.toString());
        f.put("s", "s");
        System.out.println(f.toString());
        f.put("5", "2222");
        System.out.println(f.toString());
        f.get(1 + "");
        System.out.println(f.toString());
    }
}

输出结果：

0:0 1:1 2:4 3:9 4:16 5:25
1:1 2:4 3:9 4:16 5:25 s:s
1:1 2:4 3:9 4:16 5:2222 s:s
1:1 2:4 3:9 4:16 5:2222 s:s

JDK源码之LinkedHashMap源码剖析

发表于 2019-04-21 | 分类于 Java

LinkedHashMap继承了HashMap类并实现了Map接口，其内部维护了一个双向链表，在每次插入数据或者修改访问数据，在双链表中会存在相应的增删高的操作，从而实现将无序的HashMap通过双链表将其管理为有序状态的map类型。

内部节点

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中的节点Entry继承了HashMap中内部类Node，为其添加两个链表以实现节点之间的有序存储。

//Hashmap中的节点
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //omit
    }

同时存在两个成员变量，head和tail指向双链表的首尾两端，以及一个accessOrder，accessOrder指定双链表的迭代顺序，如果其为true，则采用访问顺序，如果为false，则采用插入顺序。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;
/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

构造方法

/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量和扩展因子
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量，使用默认的扩展因子0.75
 * @param  initialCapacity the initial capacity
 * @throws IllegalArgumentException if the initial capacity is negative
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，使用默认的初始容量16和扩展因子0.75
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}
/**
 * 通过一个map构造一个按照插入顺序迭代的Hashmap对象，
 * 初始容量为大于map的值,扩展因子0.75
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //批量插入一个map到本集合中
    putMapEntries(m, false);
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量和扩展因子，和迭代顺序
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

新增节点

LinkedHashMap添加节点采用的是HashMap中的put方法。在putVal方法中调用了newNode()方法。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
          //omit...
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

LinkedHashMap重写了构建节点newNode()方法。

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;
}

每次构建新节点时，通过linkNodeLast(p)将新节点链接在内部双向链表的尾部。

// link at the end of list
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;
    }
}

putVal方法中最后调用了afterNodeInsertion(evict),很容易发现，在HashMap中这个方法是空的，而LinkedHashMap中重写了这些方法，用于对相应操作之后对双链表的修改。如果是按照

// hashMao中的预留函数
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //判断是否需要移除最老的值
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
//默认是不移除的，但是如果要实现缓存，需要删除最老的值。实现LRUCache需要重写该方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

Demo展示：

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
            System.out.println(map.toString());
        }
    }
}

{1=1}
{1=1, 2=2}
{1=1, 2=2, 3=3}
{1=1, 2=2, 3=3, 4=4}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 3=3, 4=4, 5=5, 6=6}

删除节点

LinkedHashMap没有重写删除节点，调用HashMap中的删除方法。删除之后通过调用重写之后的afterNodeRemoveal()这个回调方法来对双链表进行调整。

//删除节点e时，需要相应调整双链表
void afterNodeRemoval(Node<K,V> e) { // unlink
   LinkedHashMap.Entry<K,V> p =
       (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
   //链表节点中只有e一个节点
   p.before = p.after = null;
   //e为头节点
   if (b == null)
       head = a;
   else
       b.after = a;
   //e为尾节点
   if (a == null)
       tail = b;
   else
       a.before = b;
}

Demo展示

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
            System.out.println(map.toString());
        }
        map.remove(6);
        System.out.println(map.toString());
        map.remove(3);
        System.out.println(map.toString());
    }
}

{1=1, 2=2}
{1=1, 2=2, 3=3}
{1=1, 2=2, 3=3, 4=4}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 3=3, 4=4, 5=5, 6=6}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 4=4, 5=5}

查找节点

没错，LinkedHashMap重写了get方法及getOrDefaul方法,比较简单，就是查找，查找完之后，如果迭代顺序采用是访问顺序，则需要调用函数afterNodeAccess来调整双向链表。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}

//将访问过的节点移动至内部的双向链表的尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

Demo展示

按照插入顺序输出

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
        }
        System.out.println(map.toString());
        map.get(3);
        map.get(6);
        System.out.println(map);
    }
}

1 2	{1=1, 2=2, 3=3, 4=4, 5=5, 6=6} {1=1, 2=2, 3=3, 4=4, 5=5, 6=6}

按照访问顺序输出，accessOrder=true

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> orderMap = new LinkedHashMap<Integer, String >(16,0.75f, true);
        for (int i = 1; i < 7; i++) {
            orderMap.put(i, "" + i);
        }
        System.out.println(orderMap.toString());
        orderMap.get(3);
        System.out.println(orderMap);
        orderMap.get(1);
        System.out.println(orderMap);
    }
}

1
2
3

{1=1, 2=2, 3=3, 4=4, 5=5, 6=6}
{1=1, 2=2, 4=4, 5=5, 6=6, 3=3}
{2=2, 4=4, 5=5, 6=6, 3=3, 1=1}

containsValue方法

HashMap中的containsValue方法：

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

LinkedHashMap中：

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

显然，后者的实现更加的高效。

遍历

LinkedHashMap中重写了entrySet()方法:

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new LinkedEntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

重写之后迭代LinkedHashMap就是从内部维护的双链表的表头开始循环输出。

总结

LinkedHashMap继承HashMap，只需要重写几个方法，来改变其迭代遍历的顺序。同时在插入数据，访问数据，修改数据，会增加双链表上的节点或者调整顺序，来决定迭代时的输出顺序。
相应操作的回调函数，HashMap中有相应的空方法，也就意味着LinkedHashMap只需要重写这几个回调函数，而不用重写插入和删除方法。
LinkedhashMap重写了get方法。
LinkedHashMap优化了containsValue方法，提高其遍历性能。

测试代码

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
//            System.out.println(map.toString());
        }
        System.out.println(map.toString());
//        map.remove(6);
//        System.out.println(map.toString());
//        map.remove(3);
//        System.out.println(map.toString());
        map.get(3);
        map.get(6);
        System.out.println(map);
        Map<Integer,String> orderMap = new LinkedHashMap<Integer, String >(16,0.75f, true);
        for (int i = 1; i < 7; i++) {
            orderMap.put(i, "" + i);
        }
        System.out.println(orderMap.toString());
        orderMap.get(3);
        System.out.println(orderMap);
        orderMap.get(1);
        System.out.println(orderMap);
    }
}

JDK源码之HashMap和ConcurrentHashMap理解

发表于 2019-04-21 | 分类于 Java

HashMap

hashhMap本质是数组+链表。根据key取得hash值，然后计算出数组下标，如果多个key对应到同一个下标，就用链表连接起来，最新插入的数据在链表头。
HashMap继承AbstractHashMap，实现了Map，Cloneable，Serializable接口
HashMap设计线程不安全的。
对键值对的描述，Node：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        ...
      }

hashmap中键值对的存储形式为链表节点，hasCode相同的节点位于一个桶中。

1
2
3

public final int hashCode() {
     return Objects.hashCode(key) ^ Objects.hashCode(value);
 }

红黑树

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    ...
  }

HashMap构造函数

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

HashMap的构造方法中的三个重要的参数：

capacity:容量，表示数组容量大小
loadFactor:比例，扩容用
threshold：最多容纳的Entry数=capacity*loadFactory，如果当前元素个数多于这个就要扩容（capacity扩容为2倍）
- static final int TREEIFY_THRESHOLD： JDK1.8 新加，Entry链表最大长度，当桶中节点数目大于该长度时，将链表转成红黑树存储；
- static final int UNTREEIFY_THRESHOLD：JDK1.8 新加，当桶中节点数小于该长度，将红黑树转为链表存储；
- static final int DEFAULT_INITIAL_CAPACITY: 默认键值队个数为16

get方法

public V get(Object key) {
       Node<K,V> e;
       return (e = getNode(hash(key), key)) == null ? null : e.value;
   }
   final Node<K,V> getNode(int hash, Object key) {
           Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
           if ((tab = table) != null && (n = tab.length) > 0 &&
               (first = tab[(n - 1) & hash]) != null) {
               if (first.hash == hash && // always check first node
                   ((k = first.key) == key || (key != null && key.equals(k))))
                   return first;
               if ((e = first.next) != null) {
                   if (first instanceof TreeNode)
                       return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                   do {
                       if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))
                           return e;
                   } while ((e = e.next) != null);
               }
           }
           return null;
       }

先查找对应桶的首元素，然后根据红黑树结构OR链表结构对应查找。

put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

散列分布策略：键值对的槽位 = （容量-1） * hash(key)
- 键值对槽位是键值对在tab数组的索引，本质为其hash值对容量取余，但是位运算更快。
  1
  2
  3
  4
  static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
HashMap更新和新增的核心思想：
- 根据键值对key的hashCode计算键值对的HashMap中的槽位
- 判断是否空桶或者发生Hash冲突
- 解决hash冲突：根据桶组织形式是红黑树或者链表进行对应插入操作，链表插入操作完成之后，检查是否超过链表阈值，超过将链表转换成红黑树
- 最后检查键值对总数是否超过阈值，超过阈值调用resize（）进行rehash操作。

resize方法

final Node<K,V>[] resize() {
       Node<K,V>[] oldTab = table;
       int oldCap = (oldTab == null) ? 0 : oldTab.length;
       int oldThr = threshold;
       int newCap, newThr = 0;
       if (oldCap > 0) {
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1; // double threshold
       }
       else if (oldThr > 0) // initial capacity was placed in threshold
           newCap = oldThr;
       else {               // zero initial threshold signifies using defaults
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       if (newThr == 0) {
           float ft = (float)newCap * loadFactor;
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
       threshold = newThr;
       @SuppressWarnings({"rawtypes","unchecked"})
           Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
       table = newTab;
       if (oldTab != null) {
           for (int j = 0; j < oldCap; ++j) {
               Node<K,V> e;
               if ((e = oldTab[j]) != null) {
                   oldTab[j] = null;
                   if (e.next == null)
                       newTab[e.hash & (newCap - 1)] = e;
                   else if (e instanceof TreeNode)
                       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   else { // preserve order
                       Node<K,V> loHead = null, loTail = null;
                       Node<K,V> hiHead = null, hiTail = null;
                       Node<K,V> next;
                       do {
                           next = e.next;
                           if ((e.hash & oldCap) == 0) {
                               if (loTail == null)
                                   loHead = e;
                               else
                                   loTail.next = e;
                               loTail = e;
                           }
                           else {
                               if (hiTail == null)
                                   hiHead = e;
                               else
                                   hiTail.next = e;
                               hiTail = e;
                           }
                       } while ((e = next) != null);
                       if (loTail != null) {
                           loTail.next = null;
                           newTab[j] = loHead;
                       }
                       if (hiTail != null) {
                           hiTail.next = null;
                           newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
       return newTab;
   }

当键值对总数超过阈值时，HashMap通过resize方法实现重散列rehash，容量增加为原来的2倍。

remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

ConcurrentHashMap

在HashMap的基础上，ConcurrentHashMap放弃了分段锁机制，利用CAS+Synchronized来保证并发更新的安全，低层依然采用数组+链表+红黑树的存储结构

重要属性

/**
 * The array of bins. Lazily initialized upon first insertion.
 * Size is always a power of two. Accessed directly by iterators.
 */
transient volatile Node<K,V>[] table;

table:默认为null，懒加载，初始化发生在第一次插入的时候，默认大小16，大小总为2的幂次方，用来存储节点数据，可以由迭代器直接调用。

/**
 * The next table to use; non-null only while resizing.
 */
private transient volatile Node<K,V>[] nextTable;

nextTable:默认为null，扩容时新生成的数组，其大小为原数组的两倍。

/**
 * Table initialization and resizing control.  When negative, the
 * table is being initialized or resized: -1 for initialization,
 * else -(1 + the number of active resizing threads).  Otherwise,
 * when table is null, holds the initial table size to use upon
 * creation, or 0 for default. After initialization, holds the
 * next element count value upon which to resize the table.
 */
private transient volatile int sizeCtl;

sizeCtl:默认为0，用来控制table初始化和扩容操作，-1表示table正在初始化，-N表示有N-1个线程正在进行扩容操作。如果table未被初始化，表示table需要初始化的大小，如果table初始化完成，表示table的容量，默认为0.75

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
    ...
  }

Node:保存key,value以及key的hash值的数据结构，val和next由violate修饰，保证并发可见性。

static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
        ...
}

ForwardingNode：特殊的Node节点，hash值为-1，其中存储nextTable的引用，只有table发生扩容时才有用，作为一个占位符放在table中表示当前节点为null或者已经被移动。

初始化

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}

会自动调整输入的证书为2的幂次方。

private static final int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

由于初始化在第一次插入数据时进行，则要确保只有一次初始化：

/**
   * Initializes table, using the size recorded in sizeCtl.
   */
  private final Node<K,V>[] initTable() {
      Node<K,V>[] tab; int sc;
      while ((tab = table) == null || tab.length == 0) {
          if ((sc = sizeCtl) < 0)
              Thread.yield(); // lost initialization race; just spin
          else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
              try {
                  if ((tab = table) == null || tab.length == 0) {
                      int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                      @SuppressWarnings("unchecked")
                      Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                      table = tab = nt;
                      sc = n - (n >>> 2);
                  }
              } finally {
                  sizeCtl = sc;
              }
              break;
          }
      }
      return tab;
  }

sizeCtl默认值为0，如果ConcurrentHashMap实例化时有传参数，sizeCtl会是一个2的幂次方的值。所以和自行第一次put操作的线程会执行compareAndSwapInt方法修改sizeCtl值为-1，有且只有一个线程能够修改成功，其他线程通过Thread.yield()让出CPU时间片等待table初始化完成。

put方法

public V put(K key, V value) {
    return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

put采用CAS+synchronized实现并发插入或更新操作。

hash算法获取key的hash值
table中定位索引的位置，n为table的大小
获取table中对应索引的元素f，Unsafe.getObjectVolatile来确保获取的数据为最新的。
f为空，说明该位置第一次插入节点，用Unsafe.compareAndSwapObject插入Node节点。如果CAS成功，说明Node节点已经插入，随后检查当前容量是否需要扩容。如果CAS失败，说明有其他线程提前插入了节点，自旋重新尝试在这个位置插入节点。
如果f的值为-1，说明f是当前ForwardingNode节点，意味着有其他线程进行扩容，则一起进行扩容操作。
其余情况把新的Node节点按照链或者红黑树的方式插入到合适的位置，这个过程采用同步内置锁实现。

table扩容

private final void addCount(long x, int check) {
       CounterCell[] as; long b, s;
       if ((as = counterCells) != null ||
           !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
           CounterCell a; long v; int m;
           boolean uncontended = true;
           if (as == null || (m = as.length - 1) < 0 ||
               (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
               !(uncontended =
                 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
               fullAddCount(x, uncontended);
               return;
           }
           if (check <= 1)
               return;
           s = sumCount();
       }
       if (check >= 0) {
           Node<K,V>[] tab, nt; int n, sc;
           while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                  (n = tab.length) < MAXIMUM_CAPACITY) {
               int rs = resizeStamp(n);
               if (sc < 0) {
                   if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                       sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                       transferIndex <= 0)
                       break;
                   if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                       transfer(tab, nt);
               }
               else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                            (rs << RESIZE_STAMP_SHIFT) + 2))
                   transfer(tab, null);
               s = sumCount();
           }
       }
   }

当table容量不足时，及table的元素数量达到容量阈值sizeCtl，需要经table扩容：

构建一个nextTable,大小为table的两倍
- 通过Unsafe.compareAndSwapInt修改sizeCtl的值，保证只有一个线程能够输出化nextTable,扩容后数组长度为原来的两倍，但是容量是原来的1.5。
把table的数据复制到nextTable中
- 首先根据运算得到遍历的次数i,然后利用tabAt方法获得i位置的元素f,初始化一个forwardNode实例fwd。
- 如果f == null，则在table的i位置放入fwd。
- 如果f是链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上，移动完成，采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
- 如果f是TreeBin节点，也做一个反序处理，并判断是否需要untreeify，把处理的结果分别放在nextTable的i和i+n的位置上，移动完成，同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd

get方法

public V get(Object key) {
       Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
       int h = spread(key.hashCode());
       if ((tab = table) != null && (n = tab.length) > 0 &&
           (e = tabAt(tab, (n - 1) & h)) != null) {
           if ((eh = e.hash) == h) {
               if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                   return e.val;
           }
           else if (eh < 0)
               return (p = e.find(h, key)) != null ? p.val : null;
           while ((e = e.next) != null) {
               if (e.hash == h &&
                   ((ek = e.key) == key || (ek != null && key.equals(ek))))
                   return e.val;
           }
       }
       return null;
   }

ConcurrentHashMap是一个并发散列表的实现，它允许完全并发的读取，并且支持给定数量的并发更新。相比于HashTable和同步包装的HashMap，适用一个全局的锁来同步不同线程的并发访问，同一时间点，只能有一个线程持有锁，也就是说在同一个时间点，只有一个线程能访问容器，这虽然保证了多线程的并发访问安全，但是同时也和导致对容器的访问变成串行的了。1.6中采用ReentrantLock分段锁的方式，使用多个线程在不同的segment上进行写操作不会发生阻塞行为。1.8中采用内置锁synchronized。

JDK1.8 新特性

发表于 2019-04-21 | 分类于 Java

Alt text

接口的默认方法

Java8允许我们给接口添加一个非抽象的方法实现，只需要使用default关键字即可，这个特征被称作扩展方法。

首先我们定义一个接口，该接口有一个抽象方法print和一个具体方法defaultPrint();

public interface InterfaceEnhancement {
    void print();
    default void defaultPrint(String string) {
        System.out.println( string + "接口可以添加default修饰的非抽象方法了");
    }
}

实现了该接口一个类如下，并对其进行调用：

class InterfaceEnhancementDemo implements InterfaceEnhancement {
    @Override
    public void print() {
        System.out.println("实现类实现了InterfaceEnhancement中的print方法");
    }
    public static void main(String[] args) {
        InterfaceEnhancementDemo IED = new InterfaceEnhancementDemo();
        IED.print();
        IED.defaultPrint("传给接口中的方法的字符串");
    }
}

运行结果如下：

1 2	实现类实现了InterfaceEnhancement中的print方法传给接口中的方法的字符串接口可以添加default修饰的非抽象方法了

考虑到Java中只有单继承，如果需要给一个类赋予新特性，通常是使用接口来实现。允许接口中写具体的实现方法，实现对接口功能的扩展，避免了单继承的弊端。

Lambda表达式

Java中对字符串进行排序，可以通过传入一个List对象和一个比较器来制定顺序排列。如下：

public class LambdaDemo {
    public static void main(String[] args) {
        List<String> strings = Arrays.asList("1","2","3","11","12","5");
        System.out.println(strings.toString());
        Collections.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        System.out.println(strings.toString());
    }
}

Lambda表达式提供了更加简洁的写法：

1
2
3

Collections.sort(strings, (o1, o2) -> o1.compareTo(o2));
//或者
Collections.sort(strings, String::compareTo);

函数式接口

每一个Lambda表达式对应着一个类型，通常是接口类型。函数式接口指的是仅仅只包含一个抽象方法的接口，每一个该类型的lambda表达式都会被匹配到这个抽象方法中，该接口也可以添加默认方法。

因此实际上，我们可以把Lambda当成任意只包含一个抽象方法的接口类型，确保你的接口一定达到这个要求，只需要给接口添加@FunctionalInterface注解，编译时会检查接口中是否只存在一个抽象方法。

@FunctionalInterface
public interface FunctionalInterfaceDemo<K,V> {
    V get(K key);
}
public class FITest {
    public static void main(String[] args) {
        FunctionalInterfaceDemo<String, String> functionalInterfaceDemo = key -> key + "12";
        String result = functionalInterfaceDemo.get("functionInterface");
        System.out.println(result);
    }
}

实际上不添加注解，程序也是可以正确执行的。而将Lambda表达式映射到一个但方法的接口上，在其他语言中已经有实现了。单一方法的接口使得Lambda表达式更加的简洁。

方法与构造函数引用

Java中允许你使用::关键字来传递方法或者构造函数的引用，下面有一个实例：

public class Person {
    String name;
    int age;
    Person(){
    }
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public interface PersonFactory<P extends Person> {
    P create(String name, int age);
}
public class PersonTest {
    public static void main(String[] args) {
        PersonFactory<Person> personPersonFactory = Person::new;
        Person person = personPersonFactory.create("Peter", 18);
    }
}

可以看出Person::new获取Person类的构造函数的引用，Java编译器会根据create方法的签名来选取合适的构造方法。

Lambda作用域

Lambda表达式中访问外层作用域和匿名方法中的方式类似，可以直接访问final修饰的外层局部变量，实例的字段及静态变量。

访问局部变量

public class LocalDemo {
    public static void main(String[] args) {
        final int num = 123;
        FunctionalInterfaceDemo<String, String> functionalInterfaceDemo = key -> key + num;
        System.out.println(functionalInterfaceDemo.get("123"));
    }
}

final不强制要求添加
不添加final，num也不能被后面的程序修改，隐式的final。

访问字段和静态变量

public class FieldAndStaticFieldDemo {
    static int staticNum;
    int normalNum;
    void testScope() {
        FunctionalInterfaceDemo<Integer, Integer> f = (key) -> {
            normalNum = 513;
            return key +12;
        };
        FunctionalInterfaceDemo<Integer, Integer> f1 = (key) -> {
            staticNum = 1234455;
            return key + 12;
        };
    }
}

访问接口的默认方法

JDK1.8中包含了很多内建的函数式接口，如之前常用的Comparator或者Runnable接口，这些接口都增加了@FunctionInterface注解以便可以使用Lambda表达式。同样提供了很多全新的Lambda接口。

Predicate接口

@FunctionalInterface
public interface Predicate<T> {
    boolean test(T t);
}

该接口只有一个参数，返回boolean类型的值。改接口包含多种默认方式来将Predicate组合成其他复杂的逻辑：

Predicate<String> predicate = s -> s.length() > 0;
System.out.println(predicate.test("foo"));
System.out.println(predicate.negate().test("foo"));
Predicate<Boolean> nonNull = Objects::nonNull;
Predicate<Boolean> isNull = Objects::isNull;

Function接口

@FunctionalInterface
public interface Function<T, R> {
    R apply(T t);
}

只有一个参数并且返回一个结果，附带了一些组合方法。

1 2	Function<String, Integer> function = Integer::valueOf; Function<String, String> function1 = s -> s + 11;

Supplier接口

@FunctionalInterface
public interface Supplier<T> {
    T get();
}

返回一个任意范式的值。

Consumer接口

@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);
}

Comparator接口

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
}

Optional接口

不是函数式接口，是用来放置空指针异常的辅助类型。

Stream接口

表示能应用中哎一组元素上一次执行的操作序列。Stream操作分为中间操作或者最终操作两种，最终操作返回以特定类型的计算结果，而中间操作返回Stream本身。可以将多个操作穿起来。Stream创建过程中需要指定一个数据源。

public class StreamFuture {
    public static void main(String[] args) {
        List<String> stringCollection = new ArrayList<>();
        stringCollection.add("ddd2");
        stringCollection.add("aaa2");
        stringCollection.add("bbb1");
        stringCollection.add("aaa1");
        stringCollection.add("bbb3");
        stringCollection.add("ccc");
        stringCollection.add("bbb2");
        stringCollection.add("ddd1");
        System.out.println(stringCollection.toString());
        //Filter过滤
        stringCollection.stream().filter(s -> s.startsWith("b")).forEach(System.out::println);
        //Sort排序
        stringCollection.stream().sorted().filter(s -> s.startsWith("b")).forEach(System.out::println);
        // map操作
        stringCollection.stream().map(String::toUpperCase).sorted().forEach(System.out::println);
        //Match 匹配操作
        System.out.println(stringCollection.stream().anyMatch(s -> s.startsWith("a")));
        System.out.println(stringCollection.stream().allMatch(s -> s.length() > 0));
        System.out.println(stringCollection.stream().noneMatch(s -> s.startsWith("h")));
        // count计数
        long count = stringCollection.stream().filter(s -> s.startsWith("b")).count();
        System.out.println(count);
        // reduce规约
        Optional<String> reduce = stringCollection.stream().sorted().reduce((s1,s2) -> s1 + "##" + s2);
        reduce.ifPresent(System.out::println);
    }
}

* Filter过滤：通过一个Predicate接口来过滤并只保留符合条件的元素，该操作属于中间操作，所以在过滤后可以将结果来应用其他Stream操作。forEach需要一个函数来对过滤后的 元素依次执行。forEach时一个最终操作，不能在其之后再执行Stream操作。

* Sort排序：排序是一个中间操作。

* Map映射：中间操作map，会将元素根据指定的Function接口来依次将元素转换成另外的对象，如将小写转换成大写

* Match匹配：检测指定的Predicate是否匹配整个Stream，最终操作。

* Count计数，最终操作，返回Stream中元素的个数，返回值为long

* Reduce规约，将stream中的多个元素规约为一个元素，通过Optional接口来接收结果

上述的输出结果如下：

[ddd2, aaa2, bbb1, aaa1, bbb3, ccc, bbb2, ddd1]
bbb1
bbb3
bbb2
bbb1
bbb2
bbb3
AAA1
AAA2
BBB1
BBB2
BBB3
CCC
DDD1
DDD2
true
true
true
3
aaa1##aaa2##bbb1##bbb2##bbb3##ccc##ddd1##ddd2

并行Stream

多个线程并行计算。

public class MultiStreams {
    public static void main(String[] args) {
        List<String> strings = new ArrayList<>(1000000);
        for (int i = 0 ; i < strings.size(); i++) {
            UUID uuid = UUID.randomUUID();
            strings.add(uuid.toString());
        }
        //串行计算
        long time1 = System.nanoTime();
        strings.stream().sorted();
        long end1 = System.nanoTime();
        long mills = TimeUnit.NANOSECONDS.toMillis(end1 - time1);
        System.out.println("串行Stream排序1000万个数的时间为" + mills + "ms");
        //并行计算
        long time2 = System.nanoTime();
        strings.stream().sorted();
        long end2 = System.nanoTime();
        long mill2 = TimeUnit.NANOSECONDS.toMillis(end2 - time2);
        System.out.println("串行Stream排序1000万个数的时间为" + mill2 + "ms");
    }
}
串行Stream排序1000万个数的时间为1ms
串行Stream排序1000万个数的时间为0ms

实际上，并行计算不一定会快于串行运算，影响的因素很多：

数据大小输入数据的大小会影响并行化处理对性能的提升。将问题分解之后并行化处理，再将结果合并会带来额外的开销。因此只有数据足够大、每个数据处理管道花费的时间足够多
时，并行化处理才有意义。
源数据结构，每个管道的操作都基于一些初始数据源，通常是集合。将不同的数据源分割相对容易,这里的开销影响了在管道中并行处理数据时到底能带来多少性能上的提升。
装箱,处理基本类型比处理装箱类型要快。
核的数量，极端情况下，只有一个核，因此完全没必要并行化。显然，拥有的核越多，获得潜在性能提升的幅度就越大。在实践中，核的数量不单指你的机器上有多少核，更是指运行时你的机器能使用多少核。这也就是说同时运行的其他进程，或者线程关联性（强制线程在某些核或CPU上运行）会影响性能。
单元处理开销，比如数据大小，这是一场并行执行花费时间和分解合并操作开销之间的战争。花在流中每个元素身上的时间越长，并行操作带来的性能提升越明显。

Date API

Java8中包含了一组全新的时间日期API，简单介绍下：

Clock时钟：访问当前日期和时间的方法，对时区敏感。
Timezones时区：ZoneID来标志时区。
LocalTime本地时间：没有时区信息的时间
LocalDate本地日期
LocalDateTime：本地日期时间

Annotation注解

Java8中吃吃了多重注解。

@interface Hints {
    Hint[] value();
}
@Repeatable(Hints.class)
@interface Hint {
    String value();
}

Java8中允许一个类型的注解使用多次

使用包装类当容器来存多个注解

1 2	@Hints({@Hint("hint1"), @Hint("hint2")}) class Person {}

使用多重注解

1
2
3

@Hint("hint1")
@Hint("hint2")
class Person {}

JDK源码之ArrayList源码剖析

发表于 2019-04-21 | 分类于 Java

ArrayList是Java集合类中一个非常重要的实现类，低层实现为数组，在随机存储方面性能很高，但是在增删数据方面性能一般。平常使用的很多，但是还没有系统的取读取其源码。

继承关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  ...
}

ArrayLis继承了AbstractList抽象类

ArrayList实现了List接口，RandomAccess接口，Cloneable接口和Serializable接口。

List接口：一开始以为List接口都是很熟悉的东西，结果注释了下源码，发现还是有很多新加的特性，比如可分割迭代器这种，从来没有用过，不过今天的重点不在这里。

public interface List<E> extends Collection<E> {
    //返回列表的长度
    int size();
    //列表是否为空
    boolean isEmpty();
    //列表中是否包含某个元素
    boolean contains(Object o);
    //获取列表的迭代器
    Iterator<E> iterator();
    //将列表转换成一个Object数组
    Object[] toArray();
    //将列表转换成任意类型的数组
    <T> T[] toArray(T[] a);
    //向列表中添加元素e
    boolean add(E e);
    //从列表中移除元素o
    boolean remove(Object o);
    //看列表中是否包含另一个集合的全部元素
    boolean containsAll(Collection<?> c);
    //将一个集合加入到列表中
    boolean addAll(Collection<? extends E> c);
    //将一个集合在指定位置加入到列表中
    boolean addAll(int index, Collection<? extends E> c);
    //将列表中属于另一个集合的元素都移除
    boolean removeAll(Collection<?> c);
    //移除所有不在另一个集合中的元素，取交集
    boolean retainAll(Collection<?> c);
    //对所有元素进行统一操作
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    //根据给定的比较器对列表进行排序
    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    //清空列表
    void clear();
    // 判断两个列表是否相等
    boolean equals(Object o);
    //返回列表的哈希值
    int hashCode();
    //获取index位置的元素
    E get(int index);
    //将index位置元素的值设定为element
    E set(int index, E element);
    //在指定位置添加元素
    void add(int index, E element);
    //移除index位置的元素
    E remove(int index);
    //元素o的最靠前的下标
    int indexOf(Object o);
    //元素o最靠后的下标
    int lastIndexOf(Object o);
    //返回迭代器列表
    ListIterator<E> listIterator();
    //返回指定位置之后的迭代器列表
    ListIterator<E> listIterator(int index);
    //返回字列表
    List<E> subList(int fromIndex, int toIndex);
    //返回并行迭代器列表
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

RandomAccess接口：是一个空的接口，目的是为了标明实现该接口的List是否支持随机访问，支持的话访问会更加高效。Java中有很多空接口是为了起到标记的作用，看ArrayList源码时需要注意这一点的作用。
1
2
public interface RandomAccess {
}
Cloneable接口：目的是为了表明实现了该接口的对象可以调用clone方法来实现对象的复制，设计模式中原型模式就是用的这个特性，该特性jdk1.0就已经支持了，可以说很Java了。
1
2
public interface Cloneable {
}
Serializable接口：序列化接口是为了标记一个对象的状态是否能序列化到文件，提供了一种内存中对象的保存和加载机制，也是个标记接口。
1
2
public interface Serializable {
}

可以看出，ArrayList除了三个标记接口外，最重要的还是List接口方法的实现。

成员变量

//序列化接口的VersionID，序列化时记录到文件中，反序列化过程中进行版本校验。
private static final long serialVersionUID = 8683452581122892189L;
//ArrayList初始的列表大小
private static final int DEFAULT_CAPACITY = 10;
//共享的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
 //共享空数组，专门给默认大小使用的。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 //ArrayList数据保存的位置，不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList中元素的个数
private int size;

构造方法

总结来说，ArrayList的构造方法有啥三个，默认长度的，指定长度的，根据集合类生成的。

// 创建一个指定大小的ArrayList
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
// 创建一个默认大小（10）的ArrayList
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 根据给定的集合，创建包含该集合的所有元素的ArrayList
public ArrayList(Collection<? extends E> c) {
    // 将给定集合元素存储到elementData数组中
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 返回的不是Object数组时，进行数组复制操作
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 空数组时，为elementData赋值
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

trimToSize()方法

该方法是将ArrayList的容量设置为当前size的大小。目的是为了缩减ArrayList的存储空间，ArrayList的容量为开辟的数组长度，size为存进去的元素个数。当我们只需要对ArrayList做查询操作，而不需要进行新增操作，则可以trim节省内存空间。

public void trimToSize() {
    // 继承自AbstractList，防止多线程操作情况下，List发生结构性变化。
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

JDK源码里面三元表达式用的比较多，if判断用的比较少，以后需要多使用三元表达式，很简洁直观。

size()方法

// 返回列表中的元素个数
public int size() {
    return size;
}

isEmpty()方法

// 判断ArrayList是否为空
public boolean isEmpty() {
    return size == 0;
}

contains(Object o)方法

//调用indexof方法来判断一个对象是否在ArrayList中
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

indexOf(Object o) 方法

//判断一个元素是否在列表中，如果存在，返回第一个靠前位置的下标，如果不存在，返回-1。
public int indexOf(Object o) {
    // 如果传入的对象为null,则看有没有对象为null在列表中
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    // 调用Object的equals方法来进行比较两个元素是否相等
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf(Object o) 方法

//找到一个元素在列表中最后一个出现的索引并返回，没找到返回-1，和indexOf方法，只是遍历数组时倒叙遍历而已，不赘述。
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

clone()方法

// clone方法是Object类的方法，返回当前ArrayList的一个副本
public Object clone() {
    try {
        // v为赋值的实例属性
        ArrayList<?> v = (ArrayList<?>) super.clone();
        //数据和modCount赋值
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

toArray()方法

//返回一个Object数组，直接调用Arrays中的copyof方法
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

toArray(T[] a)方法

// 将ArrayList中的元素赋值到一个数组中去
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 如果a的长度小于ArrayList的长度，返回一个包含ArrayList所有元素的数组
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 将ArrayList额elementData数组复制到a数组，然后将a数组的size位置赋值为空。
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

get(int index)方法

// 获取指定下标的元素并返回，可以看出get方法其实就是两个方法的封装
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
 // 检查index是否超出了ArrayList的size。
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 从elementData中返回index位置的元素。
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

set(int index, E element)方法

// 将指定index下的元素设置为element，并返回旧的值。
public E set(int index, E element) {
    // index的范围检验
    rangeCheck(index);
    // 获取旧的值
    E oldValue = elementData(index);
    // 更新elementData中的值
    elementData[index] = element;
    return oldValue;
}

add(E e)方法

// 将元素e添加到ArrayList的末尾
public boolean add(E e) {
    // 校验size+1是否超过了ArrayList的大小
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在elementData中赋值
    elementData[size++] = e;
    return true;
}

add之前，首先需要检查是否存在数组越界的问题，这个由ensureCapacityInternal来确保，如果发生了越界则进行扩容。

// 验证minCapacity是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    // elementData为默认的空值时，也就是第一次插入元素，最小容量为两者的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 验证是否需要对elementData进行扩容
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 需要进行扩容，调用grow方法进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// elementData的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 进行必要的扩容操作，确保elementData可以存放所有的元素
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新的容量为原来容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 不够的话，直接将需要的元素数设置为数组长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将原来的数组元素复制到新的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int index, E element)方法

// 在指定位置index处添加指定元素element
public void add(int index, E element) {
    // 检查index是否小于elementData的长度
    rangeCheckForAdd(index);
    // 检查elementData中添加一个元素是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将elementData数组index位置之后的元素向后移动，在index位置添加element，size++
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

remove(int index)方法

// 移除指定index位置的元素并返回该元素
public E remove(int index) {
    // 检查index是否小于elementData长度
    rangeCheck(index);
    modCount++;
    // 旧值
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index位置的元素顺次向前移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    // 返回旧值
    return oldValue;
}

remove(Object o)方法

// 从ArrayList中删除从0开始第一个遇到的o元素，成功返回true，失败返回false
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            // 找到o的下标
            if (o.equals(elementData[index])) {
                // 移除元素index
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 快速移除index下标处的元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index位置的元素顺次向前移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

clear()方法

// 从ArrayList中移除所有元素
public void clear() {
    modCount++;
    // 将elementData中所有元素设置为空
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}

addAll(Collection<? extends E> c)方法

// 将指定集合c中的所有元素都添加到列表尾部，成功返回true，失败返回false
public boolean addAll(Collection<? extends E> c) {
    // 将集合c转换成数组a存储
    Object[] a = c.toArray();
    int numNew = a.length;
    // 扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将数组a添加到elementData数组之后
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

addAll(int index, Collection<? extends E> c)方法

// 将指定集合c中的所有元素都添加到列表指定位置index只有，成功返回true，失败返回false
public boolean addAll(int index, Collection<? extends E> c) {
    // index合法性检查
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    // 扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 原数组需要移动的数量
    int numMoved = size - index;
    if (numMoved > 0)
        // 将原数组index位置之后的元素，后移newNum个位置
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 将数组a复制到index位置之后的空间
    System.arraycopy(a, 0, elementData, index, numNew);
    // size更新
    size += numNew;
    return numNew != 0;
}

removeAll(Collection<?> c)

// 从ArrayList中移除集合c中的所有元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 将ArrayList和c的交集元素保存或者丢弃，到局部变量elementData，最后一个下标为w
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 出现异常，没有完全遍历完
        if (r != size) {
            // 将r右边的元素直接复制到w右边
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // 将w下标之后的元素设置为null
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

retainAll(Collection<?> c) 方法

// 取并集
public boolean retainAll(Collection<?> c) {
    // 非空检查
    Objects.requireNonNull(c);
    // 返回差集
    return batchRemove(c, true);
}

序列化与反序列化

// 序列化方法，将列表状态写入数据流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
// 反序列化方法
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in capacity
    s.readInt(); // ignored
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

listIterator(int index)方法

这部分内容没有仔细去看，暂不注解，后面会进行完善。

// 获取列表指定位置的迭代器对象
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
// 获取list开头的迭代器对象
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
// Itr 内部类
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    public boolean hasNext() {
        return cursor != size;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
// ListItr内部类
private class ListItr extends Itr implements ListIterator<E> {
    // 构造方法
    ListItr(int index) {
        super();
        cursor = index;
    }
    // 是否有上一个迭代对象
    public boolean hasPrevious() {
        return cursor != 0;
    }
    // 获取当前迭代对象的下标
    public int nextIndex() {
        return cursor;
    }
    // 获取上一个迭代对象的下标
    public int previousIndex() {
        return cursor - 1;
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

subList(int fromIndex, int toIndex)方法

// 从列表中取出指定位置的子列表
public List<E> subList(int fromIndex, int toIndex) {
    // 起点和终点的下标检查
    subListRangeCheck(fromIndex, toIndex, size);
    // 调用SubList内部类来实现字列表的实现
    return new SubList(this, 0, fromIndex, toIndex);
}
// 起点和终点的下标检查
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}
// SubList内部类，对ArrayList数组直接进行增删改查，只是为其限定了边界
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;
    // 构造方法，父列表，偏移量，fromIndex，toIndex
    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return ArrayList.this.elementData(offset + index);
    }
    public int size() {
        checkForComodification();
        return this.size;
    }
    public void add(int index, E e) {
        rangeCheckForAdd(index);
        checkForComodification();
        parent.add(parentOffset + index, e);
        this.modCount = parent.modCount;
        this.size++;
    }
    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = parent.remove(parentOffset + index);
        this.modCount = parent.modCount;
        this.size--;
        return result;
    }
    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        parent.removeRange(parentOffset + fromIndex,
                           parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }
    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;
        checkForComodification();
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }
}

forEach(Consumer<? super E> action)方法

// Collection方法中的增强型for循环
@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

Sort方法

// 传入比较器，对ArrayList进行排序
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

Java面试题总结

发表于 2019-04-21 | 分类于 Java

Volatile

volatile的特性

禁止指令重排
可见性（对volatile修饰的成员变量进行修改，会立即同步到内存中，其他线程是可见的）

Volatile的可见性

* 写一个Volatile变量时，Java内存模型会把线程对应的本地内存中的共享变量刷新到主内存中。

![Alt text](/img/JavaInterview-1.png)

* 当读一个volatile变量时，Java内存模型会把线程对应的本地内存设置为无效，线程接下来将从主内存中读取共享变量。

![Alt text](/img/JavaInterview-2.png)

Volatile的重排序

1. 当第二个操作为volatile写操作时，不管第一个操作时什么，都不能进行重排序。这个规则确保volatile写之前的所有操作都不会重排序到volatile之后。

2. 当第一个操作为volatile读操作时，不管第二个操作是什么，都不能进行重排序。这个规则确保volatile读之后的所有操作都不会被重排到volatile之前。

3. 当第一个操作时volatile写操作时，第二个操作时volatile读操作，不能进行重排序。

也就是说两个volatile变量操作不能进行重排序。

内存屏障

内存屏障（Memory Barrier，或有时叫做内存栅栏，Memory Fence）是一种CPU指令，用于控制特定条件下的重排序和内存可见性问题。Java编译器也会根据内存屏障的规则禁止重排序。（也就是让一个CPU处理单元中的内存状态对其它处理单元可见的一项技术。）

内存屏障可以被分为以下几种类型：

LoadLoad屏障：对于这样的语句Load1; LoadLoad; Load2，在Load2及后续读取操作要读取的数据被访问前，保证Load1要读取的数据被读取完毕。
StoreStore屏障：对于这样的语句Store1; StoreStore; Store2，在Store2及后续写入操作执行前，保证Store1的写入操作对其它处理器可见。
LoadStore屏障：对于这样的语句Load1; LoadStore; Store2，在Store2及后续写入操作被刷出前，保证Load1要读取的数据被读取完毕。
StoreLoad屏障：对于这样的语句Store1; StoreLoad; Load2，在Load2及后续所有读取操作执行前，保证Store1的写入对所有处理器可见。它的开销是四种屏障中最大的。

在大多数处理器的实现中，这个屏障是个万能屏障，兼具其它三种内存屏障的功能。

内存屏障阻碍了CPU采用优化技术来降低内存操作延迟，必须考虑因此带来的性能损失。为了达到最佳性能，最好是把要解决的问题模块化，这样处理器可以按单元执行任务，然后在任务单元的边界放上所有需要的内存屏障。采用这个方法可以让处理器不受限的执行一个任务单元。合理的内存屏障组合还有一个好处是：缓冲区在第一次被刷后开销会减少，因为再填充改缓冲区不需要额外工作了。

happens-before原则

程序次序规则：一个线程内，按照代码顺序，书写在前的操作先行发生于书写在后面的操作。
锁定规则：一个unlock操作先行发生于后面对同一个所的lock操作
volatile变量原则：对一个变量的写操作先行发生于对后面对这个变量的读操作
传递规则：如果操作A先与操作B，而操作B又先于操作C，则可以得出操作A先行发生于操作C。
线程启动规则：Thread对象的start()方法先行发生于此线程的每一个动作
线程中断规则：对线程interrupt()方法的调用先行发生于被中断线程的代码检测到中断时间的发生。
线程终结规则：线程中所有的操作都先行发生于线程的终止检测，我们可以通过Thread.join()方法结束，Thread.isAlive()的返回值手段检测线程已经终止执行
对象终结规则：一个对象的初始化先行发生于他的finalize()方法。

Java是如何实现跨平台的

Java号称一次编译到处执行，一次编译指的是.java文件通过编译器编译为.class文件，也就是字节码文件。JVM虚拟机负责将字节码文件在不同的操作系统实现运行，也就是在.class文件与操作系统低层之间，JVM就像是一个适配器，不同的操作系统对应不同的JVM。

简述扫描微信二维码登录的流程

用户A访问微信网页版，微信服务器会为这个会话生成一个唯一的ID。
用户A打开自己的微信并扫描这个二维码，并提示用户是否确认登录。
确认登录之后，手机上的微信客户端将微信账号和扫描这个得到的ID一起提交到服务器
服务器将这个ID和用户A的微信号绑定在一起，并通知网页版微信，这个ID对应的微信号为用户A，记载用户A的微信信息。

Java线程有那些状态，这些状态是如何转变的

Alt text

当一个线程执行了start方法后，不代表这个线程就会立即被执行，只代表这个线程处于可运行的状态，最终由OS的线程调度来决定哪个可运行状态下的线程被执行。
一个线程一次被选中执行是有时间限制的，这个时间段叫做CPU的时间片，当时间片用完但线程还没有结束时，这个线程又会变为可运行状态，等待OS的再次调度；在运行的线程里执行Thread.yeild()方法同样可以使当前线程变为可运行状态。
在一个运行中的线程等待用户输入、调用Thread.sleep()、调用了其他线程的join()方法，则当前线程变为阻塞状态。
阻塞状态的线程用户输入完毕、sleep时间到、join的线程结束，则当前线程由阻塞状态变为可运行状态。
运行中的线程调用wait方法，此线程进入等待队列。
运行中的线程遇到synchronized同时没有拿到对象的锁标记、等待队列的线程wait时间到、等待队列的线程被notify方法唤醒、有其他线程调用notifyAll方法，则线程变成锁池状态。
锁池状态的线程获得对象锁标记，则线程变成可运行状态。
运行中的线程run方法执行完毕或main线程结束，则线程运行结束。

*需要注意的是Java多线程的阻塞状态，分为三种：

等待阻塞， obj.wait()方法，进入等待队列中
同步阻塞，获取synchronized等同步锁时，进入锁池中
其他阻塞， Thread.sleep()， t.join(), IO请求等、*

List接口、Set接口、Map接口的区别

List和Set接口继承自Collection接口，而Map和Collection是一个级别的接口。

Collection表示一组对象,这些对象也称为collection的元素;一些 collection允许有重复的元素,而另一些则不允许;一些collection是有序的,而另一些则是无序的;JDK中不提供此接口的任何直接实现,它提供更具体的子接口(如 Set 和 List)实现;Map没有继承Collection接口,Map提供key到value的映射;一个Map中不能包含相同key,每个key只能映射一个value;Map接口提供3种集合的视图,Map的内容可以被当做一组key集合,一组value集合,或者一组key-value映射;

List接口：元素有放入顺序，元素可重复，可为空值

List是一种有序的Collection，可以通过索引访问集合中的数据。所有的索引返回的方法都有可能抛出一个IndexOutOfBoundsException异常，subList(int fromIndex, int toIndex)返回的前闭后开。

所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ];
所有的List中可以有null元素，例如[ tom,null,1 ];
基于Array的List（Vector，ArrayList）适合查询，而LinkedList（链表）适合添加，删除操作;

实现类：
- LinkedList：低层基于链表实现，随机查询性能较差，增加删除节点很快。
- ArrayList：低层基于数组实现的，随机查询性能高，增加删除效率很差，线程不安全的类。
- Vector：低层基于数组实现的，随机查询性能高，增加删除效率很差，线程安全的类。

Set接口：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的）

Set具有与Collection完全一样的接口。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用：表现不同的行为)Set不保存重复的元素。
存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。
实现类：
- HashSet: 为快速查找设计的Set。低层为HashMap实现，存入HashSet的对象必须定义hashCode()。
- LinkedHashSet: 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。
- TreeSet: 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

Map接口：key-value形式的元素

Map接口有三个实现类：HashMap，HashTable，LinkeHashMap
- HashMap非线程安全，高效，支持null；
- HashTable线程安全，低效，不支持null
- SortedMap有一个实现类：TreeMap

Cookie和Session的区别

cookie是一种发送到客户浏览器的文本串句柄，并保存在客户机硬盘上，可以用来某个WEB站点会话间持久化的保持数据。
session指的是访问者从到达某个特定主页到离开位置的哪段时间，Session其实是利用Cookie进行信息处理，当用户首先进行了请求后，服务端就在用户浏览器上创建了一个Cookie，当这个Session结束时，Cookie过期。这个Cookie的唯一目的是为每一个用户提供唯一的身份认证。

cookie数据存放在客户的浏览器上，session数据放在服务器上，cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗,如果主要考虑到安全应当使用session。session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能，如果主要考虑到减轻服务器性能方面，应当使用COOKIE。单个cookie在客户端的限制是3K，就是说一个站点在客户端存放的COOKIE不能3K。将登陆信息等重要信息存放为SESSION;其他信息如果需要保留，可以放在COOKIE中

相同之处是cookie和Session都可以用来跟踪浏览器用户身份的会话方式。
区别：

Cookie	Session
Cookie保存在客户端	session数据保存在服务器端
浏览器使用的是Cookie，则所有数据都会保存在浏览器端，比如当你登录之后，服务器设置了Cookie用户名，当你再次请求服务器的时候，浏览器会将用户名一块发送给服务器。	web端使用的是Session，则所有数据都保存在服务器上，客户端每次请求服务器的时候会发送当前会话的SessionID，服务器根据当前SessionID判断相应的用户数据标志，以确定用户是否登录。
Cookie容易被伪造，安全性不高	Session安全性较高
cookie的有效期是存储的时候设置好的	session的有效期由服务器决定

equals和hashCode方法

equals方法是用来判断两个对象是否相等，Object类中的equals方法相等的含义是两个引用指向同一个对象，很多类比如String，Integer等类重写equals方法，认定两个对象的值相等就是相等的。equals方法的性质有以下几个：
- 自反性，对于任意不为null的引用值x,x.equals(x)一定时true
- 对称性，x.equals(y)为true，y.equals(x)一定为true
- 传递性，x.equals(y)是true，同时y.equals(z)是true，那么x.equals(z)一定是true
- 一致性，如果用于equals比较的对象信息没有被修改的话，多次调用时x.equals(y)要么一致地返回true要么一致地返回false。
  重写equals方法时，hashCode方法也要被重写，因为两个对象相等，其hashCode一定要相等
hashCode给对象返回一个HashCode值，主要用于hash tables，比如HashMap。
- 一个对象没有被更改，则其hashCode返回值不会改变。
- 两个对象相等，则其hashCode一定相等。
- 一般来讲，Object类定义的hashCode方法对于不同的对象返回不同的哈希值。
集合中使用
- 当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。
- 相等的对象必须有相同的哈希码
- 如果两个对象的hashCode相同，他们不一定相等。
- 换句话说，equals()方法不相等的两个对象，hashcode()有可能相等（我的理解是由于哈希码在生成的时候产生冲突造成的）。反过来，hashcode()不等，一定能推出equals()也不等；hashcode()相等，equals()可能相等，也可能不等。

Java中CAS算法

乐观锁与悲观锁
- 乐观锁会直接进行操作了，失败了重试。
- 悲观锁会先加锁，加锁成功才去操作。synchronized为悲观锁
- 悲观锁不管对象存在不存在竞争，都会对其进行加锁，当并发量很高时，其性能开销会很大。而乐观锁是基于冲突检验的，也就是每个线程都直接去进行操作，计算完成后检测是否与其他线程存在共享数据竞争，如果没有则直接进行修改，如果存在竞争则重复执行操作和检验，直至成功为止，CAS自旋等待。
CAS算法：Compare And Swap
- CAS算法设计三个操作数，内存值，预期值，新值。并且仅当预期值和内存值相等时才将内存值换成新值。这样处理的逻辑为，首先检查某块内存的值是否跟之前读取的一样，如果不一样则表示此内存值已经被别的线程更改过，舍弃本次操作，否则说明期间没有其他线程对此内存值进行操作，可以把新值设置给此块内存。
- CAS是原子性的，原子性由CPU硬件指令实现保证的。
- 乐观锁避免了悲观锁独占对象的现象，同时提高了并发性能。
- 乐观锁的缺点：
  - 乐观锁只能保证一个共享变量的原子操作。
  - 长时间自旋会造成开销大，如果CAS长时间不成功而一直自旋，会给CPU带来很大的开销
  - 存在ABA问题，CAS的核心思想是通过对比内存值与预期值是否一样而判断内存值是否被改过，但这个判断逻辑不严谨，比如内存原值为A，后来一条线程将其修改为B，最后被改为A，则CAS内存值并没有发生改变，但是实际上有被其他线程改过。这种情况对依赖过程值的运算结果影响很大。解决思路是引入版本号，每次变量更新都把版本号加一。

手写单例模式

懒汉
饿汉
双重校验
静态内部类
枚举

comparable与comparator的区别

Comparable是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现，compareTo方法也被称为自然比较方法。compareTo方法的返回值包括：
- 正数，比较者大
- 0，相等
- 负数，被比较者大
Comparetor是一个外比较器，两种情况下可以实现Comparator接口的方式：
- 一个对象不支持自己和自己比较，但是又想进行两个对象的比较。
- 一个对象实现了Comparable接口，但是开发者认为compareTo方法中的比较方式并不是自己想要的Comparator接口里面的compare方法，Comparator接口里面有一个compare方法，方法有两个参数T o1和T o2，是泛型的表示方式，分别表示待比较的两个对象，方法返回值和Comparable接口一样是int，有三种情况：
  - o1大于o2，返回正整数
  - o1等于o2，返回0
  - o1小于o3，返回负整数

Arrays和Collections对于sort的不同实现原理

Arrays.sort():该算法是一个经过调优的快速排序，此算法在很多数据集上提供N*log(N)的性能，这导致其他快速排序会降低二次型性能。
Collections.sort():该算法是一个经过修改的合并排序算法。此算法可提供保证的N*log(N)的性能，此实现将指定列表转储到一个数组中，然后再对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的n2log(n)性能。

Java中Object常用方法

clone()
equals()
hashCode()
finalize()
getClass()
notify()
notifyAll()
toString()

对Java中多态的理解

所谓多态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定，而是在程序运行期间才确定，即一个引用变量到底会指向哪个类的实例对象，该引用变量发出的方法调用到底是哪个类中实现的方法，必须在由程序运行期间才能决定。因为在程序运行时才确定具体的类，这样，不用修改源程序代码，就可以让引用变量绑定到各种不同的类实现上，从而导致该引用调用的具体方法随之改变，即不修改程序代码就可以改变程序运行时所绑定的具体代码，让程序可以选择多个运行状态，这就是多态性。

多态的定义：指允许不同类的对象对同一消息做出响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。（发送消息就是函数调用）

Java实现多态有三个必要条件：继承、重写、父类引用指向子类对象。

继承：在多态中必须存在有继承关系的子类和父类。

重写：子类对父类中某些方法进行重新定义，在调用这些方法时就会调用子类的方法。

父类引用指向子类对象：在多态中需要将子类的引用赋给父类对象，只有这样该引用才能够具备技能调用父类的方法和子类的方法。

实现多态的技术称为：动态绑定（dynamic binding），是指在执行期间判断所引用对象的实际类型，根据其实际的类型调用其相应的方法。

多态的作用：消除类型之间的耦合关系。

Session机制

垃圾收集器和内存分配策略

发表于 2019-04-21 | 分类于 Java ， JVM

垃圾收集器

垃圾收集器的历史要远早于Java，不过我们很多人都是通过Java才了解垃圾收集器的。学习垃圾收集器可以更好进行内存泄漏，内存溢出的排查，以及高并发场景下垃圾收集成为系统性能瓶颈。

垃圾收集器关注的问题很简单：

哪些垃圾需要回收？--who
什么时候回收？-- when
怎么回收？--how

程序计数器，虚拟机栈，本地方法栈是线程私有的，也就是和线程的生命周期一致，栈帧随着方法的执行进行进栈和出栈操作，内存分配和回收具有确定性，不需要考虑垃圾回收问题。方法区和Java堆则需要在运行时才确定需要的内存大小，从而需要我们动态的分配内存和垃圾收集。

那些垃圾需要回收？-who

已经“死掉”的对象需要回收，对象死掉的概念是指没有引用他的对象了。

引用计数法：给对象中添加一个引用计数器，当有一个地方引用他时，计数器+1，当引用失效时，计数器-1，当计数器为0时，对象死掉。java中并没有采用这种机制。

优点：实现简单，判定效率高

缺点：循环引用

public class ReferenceCountingGC {
	public Object instance = null;
	private static final int _1MB = 1024 * 1024;
	/**
	 * 这个成员属性的唯一意义就是占点内存，以便在能在GC日志中看清楚是否有回收过
	 */
	private byte[] bigSize = new byte[2 * _1MB];
	public static void testGC() {
		ReferenceCountingGC objA = new ReferenceCountingGC();
		ReferenceCountingGC objB = new ReferenceCountingGC();
		objA.instance = objB;
		objB.instance = objA;
		objA = null;
		objB = null;
		// 假设在这行发生GC，objA和objB是否能被回收？
		System.gc();
	}
}

0.137: [GC (System.gc()) [PSYoungGen: 9344K->808K(76288K)] 9344K->816K(251392K), 0.0029826 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
0.140: [Full GC (System.gc()) [PSYoungGen: 808K->0K(76288K)] [ParOldGen: 8K->662K(175104K)] 816K->662K(251392K), [Metaspace: 3464K->3464K(1056768K)], 0.0046314 secs] [Times: user=0.03 sys=0.00, real=0.02 secs]
Heap
 PSYoungGen      total 76288K, used 655K [0x000000076b380000, 0x0000000770880000, 0x00000007c0000000)
  eden space 65536K, 1% used [0x000000076b380000,0x000000076b423ee8,0x000000076f380000)
  from space 10752K, 0% used [0x000000076f380000,0x000000076f380000,0x000000076fe00000)
  to   space 10752K, 0% used [0x000000076fe00000,0x000000076fe00000,0x0000000770880000)
 ParOldGen       total 175104K, used 662K [0x00000006c1a00000, 0x00000006cc500000, 0x000000076b380000)
  object space 175104K, 0% used [0x00000006c1a00000,0x00000006c1aa5b78,0x00000006cc500000)
 Metaspace       used 3470K, capacity 4496K, committed 4864K, reserved 1056768K
  class space    used 381K, capacity 388K, committed 512K, reserved 1048576K

可达性分析算法：起始点为GC Root Set中的GC Roots对象，由GC Root向下的路径成为引用链，当一个对象和GC Roots没有引用链连接时，此对象死掉。

Java中可以作为GC Roots的对象包括：
- 虚拟机栈(栈帧中的本地变量表)中引用的对象
- 方法区中静态属性引用的对象
- 方法区中常亮引用的对象
- 本地方法栈中JNI（Native方法）引用的对象
引用的类型

Java1.2之前，reference类型的数据中存储的数值代表的是一个内存的起始地址，则称为一个引用。对象只存在被引用和不被引用两种状态。

强引用：程序代码中普遍存在的
软引用：描述一些还有用但不是必须的对象，系统内存溢出前会对其进行二次垃圾回收
弱引用：描述非必须的对象，垃圾回收时直接回收
虚引用：不影响其生存，回收时可以收到一个系统通知

对象死亡的过程

可达性分析后，对没有和GC Roots相连接的引用链的对象会被标记一次，同时对其进行一次筛选，筛选条件为此对象是否有必要执行finalize()方法，当对象没有重写finalize()方法或者finalize()方法被虚拟机调用过，则不执行finalize()方法。

有必要执行finalize()方法的对象会被放到F-Queue对象中，等待虚拟机的Finalizer线程去执行finalize()方法，GC会对F-Queue对象进行小范围标记，如果对象在finalize()方法中和引用链连接上，则会被移出队列，否则被真正回收。

/**
 * 对象可以在被GC时自我拯救
 * 这种自救机会只有一次，因为一个对象的finalize()方法最多只会被系统调用一遍
 */
public class FinalizeEscapeGC {
    public static FinalizeEscapeGC SAVE_HOOK = null;
    public void isAlive() {
        System.out.println(" I am alive !");
    }
    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("finalize method executed!");
        FinalizeEscapeGC.SAVE_HOOK = this;
    }
    public static void main(String[] args) throws InterruptedException {
        SAVE_HOOK = new FinalizeEscapeGC();
        //对象第一次拯救自己
        SAVE_HOOK = null;
        System.gc();
        //finalize()优先级很低，暂停0.5s等待
        Thread.sleep(500);
        if (SAVE_HOOK != null)
            SAVE_HOOK.isAlive();
        else
            System.out.println("no, I am dead!");
        //第二次自救失败
        SAVE_HOOK = null;
        System.gc();
        //finalize()优先级很低，暂停0.5s等待
        Thread.sleep(500);
        if (SAVE_HOOK != null)
            SAVE_HOOK.isAlive();
        else
            System.out.println("no, I am dead!");
    }
}

1
2
3

finalize method executed!
 I am alive !
no, I am dead!

回收方法区

虽然虚拟机规范中没有要求在方法区进行垃圾回收，但是方法区存在垃圾回收，回收效率很低。回收的内容为废弃常亮和无用的类。

回收废弃常亮：看和GC Roots之间是否存在引用链
回收无用类：
1. 该类的所有实例都已经被回收
2. 加载该类的ClassLoader已经被回收
3. 该类对应的Java.lang.Class对象没有在任何地方被引用，无法在任何地方通过反射访问该类的方法。

垃圾收集算法

标记-清除算法(Mark-Sweep):首先标记所有需要回收的对象，标记完成后统一回收被标记对象。
- 存在两个不足：
  1. 效率问题：标记和清除两个过程的效率都不高
  2. 空间问题：标记清除之后会产生大量不连续的内存碎片，会导致存放大对象时没有足够的空间而提前出发垃圾清楚

复制算法(Copint)：将内存分成一样的两块，每次只使用一块，当一块用完了就进行垃圾回收，并将还存活的对象复制到第二块硬盘上并整理顺序。每次回收针对的是一半内存空间，同时也没有了空间碎片的问题
- 存在的问题是内存空间变为一半。实际上，新生的对象98%是朝生夕死的，所以不需要1:1来划分内存空间。而是将新生代内存化为一块Eden空间和两块Survivor空间，比例为8:1:1。
- 每次使用Eden空间和其中一块Survivor空间，回收时将Eden和Survivor空间中还存活的对象复制到另一块Survivor中，然后清除Eden和Survivor空间。
- 如果空间不够的话，需要老年代进行分配担保
标记-整理算法(Mark-Compact)：标记过程和之前相同，整理过程将存活对象移动到一边，根据整理边界回收剩余空间内的对象，适用于老年代的垃圾收集
分代收集算法：将Java堆对象根据存货周期划分为新生代和老年代，新生代采用复制算法，老年代给新生代做分配担保，由于老年代的对象存活率高，所以老年代采用标记-整理或者标记-清除算法。

HotSpot的算法实现

枚举根节点：可作为根节点的主要在全局性的引用(常亮或者静态属性)与执行上下文(栈帧中的本地变量表)，可达性分析时需要停止一切的Java程序执行，Stop the world，在Oop中保存着对象引用的地址。
安全点：程序执行过程中并不是所有位置都可以停下来GC，让系统中的所有线程到安全点的方式有两种：
- 抢先式中断：所有线程中断，如果有线程不在安全点上，则恢复线程，让其跑到安全点上再中断
- 主动式中断：设置一个标志，各个线程执行时去轮询这个标志，发现中断标志位真时就自己中断挂起，轮询标志的地方和安全点是重合的。
安全区域：
- 解决线程处于休眠状态无法响应JVM的中断请求的情况。
- 安全区域指在一段代码中，引用关系不会发生变化
- 线程执行Safe Region中的代码时，会标识自己已经进入Safe Region，可以随时进行GC，如果线程离开安全区域时，会先检查枚举根节点或者GC是否完成，未完成则需要等待。

垃圾收集器

Java虚拟机规范中对垃圾收集器如何实现并没有规定，因此诞生了多种多样的垃圾收集器，适合各自的应用场景。HotSpot虚拟机中的垃圾收集器包括对新生代回收的Serial，ParNew，Parallel Scavenge，对老年代回收的CMS，Serial Old(MSC), Parallel Old及G1。

Serial收集器
- 最基本，历史最悠久的单线程收集器
- GC过程中必须停止整个程序的运行，Stop the World
- 优点:简单而高效，适用Client模式下工作的虚拟机
ParNew收集器
- Serial收集器的多线程版本
- 运行在Server模式的虚拟机中首选的新生代收集器—重要原因是，其是除了Serial外唯一能和CMS收集器配合工作。
Parallel Scavenge收集器
- 新生代收集器，复制算法，并行的多线程收集器
- 收集器的关注点不是尽可能缩短垃圾收集时用户线程的停顿时间，而是尽可能达到一个可控制的吞吐量(吞吐量=运行代码时间/(运行代码时间+GC时间))
- 吞吐量优先收集器，
- GC自适应调节策略
Serial Old收集器
- 单线程
- 老年代
- 标记-整理（Mark-Compact）算法
- 适用Client模式的虚拟机，如果要用在Server模式下，有两个用途，一个是与Parallel Scavenge搭配适用，一个是作为CMS收集器的后备预案，在并发收集失败时使用。

Parallel Old收集器
- Parallel Scavenge老年代版本
- 多线程+标记-整理算法
- 在注重吞吐量和CPU资源敏感的场合，可以优先考虑和Parallel Scavenge搭配使用。
CMS收集器：Concurrent Mark Sweep
- 以获取最短回收停顿时间为目标的收集器
- 标记-清除算法
- 运作过程：
  1. 初始标记(CMS initial mark) – stop the world, 标记GC Roots能直接关联到的对象，速度很快
  2. 并发标记(CMS concurrent mark) – stop the world，进行GC Roots Tracing，
  3. 重新标记(CMS remark)，修正标记期间因为用户线程运行而改变的对象的标记记录，时间长于初始标记但短于并发标记
  4. 并发清除(CMS concurrent sweep)，清除标记的对象
- 缺点：
  - CMS对CPU资源敏感，默认回收线程数是：（CPU数量+3）/4
  - CMS收集器无法处理浮动垃圾（Floating Garbage，并发清除阶段产生的垃圾,当前GC无法清除，需要下次GC才可以清除），会导致Concurrent Mode Failure而引发另一次Full GC。老年代需要保留足够的空间给用户线程使用，当CMS运行期间预留的内存空间不够时会发生Concurrent Mode Failure，这时候需要临时调用Serial Old来进行Full GC，停顿时间很长。
  - 产生内存碎片问题，解决方法，CMS进行Full GC时，先进行碎片整理，或者进行若干次不整理的GC时，进行一次碎片整理的GC。
G1收集器：Garbage First
- 并行与并发
- 分代收集
- 空间整合：marking-compact
- 可预测的停顿
- G1将整个堆划分为很多Region，新生代和老年代都是由很多Region组成，G1后台维护一个列表，列表中记录了各个Region里面的垃圾价值大小（回收获得的空间和回收需要时间），GC时，优先回收价值最大的Region，保证G1在有限的时间内获得最高的回收效率。RememberSet避免全堆扫描。
- 运作过程：
  1. initial marking
  2. concurrent marking
  3. final marking
  4. live data counting and evacuation

内存分配与回收策略

对象优先在Eden区生成
大对象直接进入老年代，如字符串和数组
长期存活的对象将进入老年代
动态对象年龄判定，如果Survivor中相同年龄所有对象大小的总和大于Survivor空间的一半，则大于或等于该年龄的对象将直接进入老年代。
空间分配担保：Minor GC之前检查老年代最大可用连续空间是否大于新生代所有对象总和或者大于新生代晋升老年代的历次平均大小，进行Minor GC,否则进行Full GC

Java内存区域

发表于 2019-04-21 | 分类于 Java ， JVM

运行时数据区域

Java和C++之间有一堵由内存动态分配和垃圾收集机制所围成的墙，墙外面的人想进来，墙里面的人想出去。深入理解Java虚拟机这本书的作者在介绍自动化内存管理时写到。个人认为内存动态分配和垃圾收集机制是Java的特点，不同于C++，一个对象从创建的内存分配，到销毁的内存回收都需要程序员来掌控，Java把这部分权限从程序员手中收回，限制了程序员的权限，但同时也减少了开发中存在的内存泄漏，内存溢出的频率。Java中不是没有内存泄漏和内存溢出，但是相对来说没有c++里面那么频繁，排查起来相对简单。了解虚拟机的相关知识对一个Java程序员是必不可少的技能。
Java虚拟机是Java实现跨平台的基础，也就是一直宣称的一次编译，到处执行，Java文件编译后生成的文件并不是调用操作系统的native方法，而是运行在JVM上，由JVM来调用操作系统的native方法。JVM在执行Java程序时，会将自身管理的内存划分为若干个数据区域：
1. 程序计数器：
  - 线程私有内存，
  - 不会产生OOM(唯一)
  - 一块较小的内存空间，可以看做是当前线程所执行的字节码的行号指示器。
  - 字节码解释器工作时就是通过改变计数器的值来选取下一条执行的字节码指令。
2. Java虚拟机栈
  - 线程私有
  - 声明周期和线程一样
  - 描述的是Java方法执行的内存模型(也就是说每个方法在执行过程中都会创建一个栈帧，栈帧中存储着局部变量表，操作数栈，动态链接，方法出口等信息，方法的执行过程对应着栈帧的入栈和出栈过程)
  - 平常说的栈指的是虚拟机栈或者说是其中局部变量表部分(局部变量表存放着编译期可知的各种基本数据类型8+reference，也就是说在编译完成之后其方法的局部变量表的大小就已经确定)
3. 本地方法栈
  - 线程私有
  - 服务Native方法
  - hotspot虚拟机将本地方法栈和Java虚拟机栈合二为一
4. Java堆
  - 所有线程共享
  - 原则上存放所有的对象实例(JIT和逃逸分析技术，栈上分配，标量替换优化等可能会在堆外创建实例)
  - GC堆，垃圾收集的主要区域
  - 新生代和老年代，Eden和Survivor
  - 可以划分多个Thread Local Allocation Buffer TLAB
5. 方法区
  - 所有线程共享
  - 存储已被虚拟机加载的类信息，常量，静态变量，即时编译器变异后的代码等数据
  - Non-Heap
  - hotspot将其称为永久代，不过已经取消
  - 运行时常亮池是方法区的一部分，存放字面量和符号引用
- 直接只存：Direct Memory，NIO类，可以在native函数库外直接分配堆外内存，可以通过在堆中存储的DirectByBuffer对象作为引用来操作

HotSpot

对象创建流程
- 虚拟机为新生对象分配内存时，对象所需的内存大小在类加载完毕之后就已经确定。分配方式有两种
  - Bump the Pointer，碰撞指针，此时内存空闲内存时连续规整的，Serial, ParNew等垃圾收集器采用
  - Free List 空闲列表，空闲内存时分散的，找一个足够大的空间，Mark-Sweep收集器
- 线程安全问题，也就是同时有两个对象申请同一块内存
  - 对分配内存空间的动作进行同步处理，CAS+失败重试
  - 将内存分配的动作按照线程划分在不同的空间中进行，TLAB，TLAB满了并且分配新的TLAB才需要同步
对象的内存布局
1. 对象头 Header
  - 存储对象自身运行时的数据
    - 哈希码
    - GC分代年龄
    - 锁状态标志
    - 线程持有的锁
    - 偏向线程ID
    - 偏向时间戳
  - 类型指针：指向类元数据的指针
2. 实例数据
  - 对象真正存储的有效信息，代码中定义的字段内容
3. 对齐填充
  - 非必须，对齐实例数据，使其为8的倍数。
对象的访问定位
- 句柄：Java堆中划分出一块内存来作为句柄池，reference中存储的是对象的句柄地址，句柄中包含了对象实例数据和类型数据各自的具体地址信息
- 直接指针：reference中存储的是对象地址，对象中存储着到对象类型指针的地址。

Java多线程基础

发表于 2019-04-21 | 分类于 Java ， Multi-Thread

进程与线程的区别

进程是资源分配的最小单位，线程是程序执行的最小单位
进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段，堆栈段和数据段。线程是共享进程中的数据的，使用相同的地址空间，CPU切换一个线程的花费远小于切换一个进程的花费，创建一个线程的开销也远小于进程。
线程之间通信更加方便，同一进程下的线程共享全局变量，静态变量等数据，而进程之间的通信需要以通信的方式进行。
多进程程序更加健壮，多线程只要一个线程死掉，整个进程挂掉。
一个程序至少有一个进程，一个进程至少有一个线程。

Java实现多线程

Java中可以通过三种方式实现多线程
- 继承Thread类
- 实现Runable接口
- 实现Callable接口

继承Thread类

实例:

/**
 * @program: 02_Basic
 * @author: cdx
 * @create: 2018-09-02 16:23
 **/
public class CreateThreadByExtendsThread extends Thread{
    private String name;
    public CreateThreadByExtendsThread(String name) {
        this.name = name;
    }
    @Override
    public void run() {
        for (int i = 0; i < 3; i++)
            System.out.println(this.name + " create thread by extends Thread!");
    }
    public static void main(String[] args) {
        Thread threadA = new CreateThreadByExtendsThread("A");
        Thread threadB = new CreateThreadByExtendsThread("B");
        threadA.start();
        threadB.start();
    }
}

运行结果:

B create thread by extends Thread!
A create thread by extends Thread!
B create thread by extends Thread!
A create thread by extends Thread!
A create thread by extends Thread!
B create thread by extends Thread!

实现Runable接口

实例

/**
 * @program: 02_Basic
 * @author: cdx
 * @create: 2018-09-02 16:39
 **/
public class CreateThreadByImplRunable implements Runnable{
    private String name;
    public CreateThreadByImplRunable(String name) {
        this.name = name;
    }
    @Override
    public void run() {
        for (int i = 0; i < 3; i++) {
            System.out.println(this.name + " create thread by implements Runable!");
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args) {
        Runnable threadA = new CreateThreadByImplRunable("A");
        Runnable threadB = new CreateThreadByImplRunable("B");
        threadA.run();
        threadB.run();
    }
}

运行结果

A create thread by implements Runable!
A create thread by implements Runable!
A create thread by implements Runable!
B create thread by implements Runable!
B create thread by implements Runable!
B create thread by implements Runable!

实现Callable接口

实例

import java.util.concurrent.Callable;
/**
 * @program: 02_Basic
 * @author: cdx
 * @create: 2018-09-02 16:45
 **/
public class CreateThreadByImplCallable implements Callable<String> {
    private String name;
    public CreateThreadByImplCallable(String name) {
        this.name = name;
    }
    @Override
    public String call() throws Exception {
        for (int i = 0; i < 3; i++) {
            System.out.println(this.name + " create thread by implements Calable!");
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return name;
    }
    public static void main(String[] args) {
        Callable<String> threadA = new CreateThreadByImplCallable("A");
        Callable<String> threadB = new CreateThreadByImplCallable("B");
        try {
            System.out.println("the result of threadA: " + threadA.call());
            System.out.println("the result of threadB: " + threadB.call());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

运行结果

A create thread by implements Calable!
A create thread by implements Calable!
the result of threadA: A
B create thread by implements Calable!
B create thread by implements Calable!
B create thread by implements Calable!
the result of threadB: B

Thread和Runnable的区别

Runable适合多个相同的程序代码的线程去处理同一个资源
Runnable可以避免Java中单继承的限制
Runable增加程序的健壮性，代码可以被多个线程共享，代码和数据独立
线程池只能放入实现Runable或Callable接口的类线程，不能直接放入继承Thread的类
- main方法本身是一个线程，Java中所有线程都是同时启动的，执行取决于对CPU资源的竞争
- Java中每个程序至少运行两个线程, main和jvm。

Runable和Callable的区别

Callable规定的方法为call，Runable规定的方法为run
call方法可以抛出异常，run方法不可以抛出异常
Callable的任务执行后可返回值，运行Callable任务可以拿到一个Future对象，而Runable是不能返回值的。
Callable缺点在于繁琐，实现Callable对象+实现call方法+ExecotorService获取Future对象
- Future表示异步计算的结果，提供了检查计算是否完成的方法，以等待计算的完成并检查结果。
- 通过Future对象可以了解任务的执行情况，可以取消任务的执行，可以获取任务的执行结果

线程状态切换

新建状态(New):使用new关键字新建一个线程对象
就绪状态(Runable):线程对象创建之后，其他线程调用了该对象的start()方法，该状态的线程位于可运行线程池中，变的可运行，需要竞争获取CPU时间片。
运行状态(Running):就绪状态的线程获取了CPU的时间片，执行程序代码。
阻塞状态(Blocking):阻塞状态是因为线程因为某种原因，暂时停止运行，知道线程进入就绪状态，才有机会转换到运行状态，。阻塞状态分为三种情况：
1. 等待阻塞:运行的线程执行wait()方法，JVM会把该线程放入等待池中，会释放持有的锁。
2. 同步阻塞:运行的线程在获取对象的同步锁时，若该同步锁被别的线程占用，则JVM会把该线程放入锁池中。
3. 其他阻塞:运行的线程执行sleep()或join()方法，或者发出了IO请求时，JVM会把该线程晋升为阻塞状态，当sleep状态超时，join等待线程终止或者超时时，或者IO处理完毕，线程重新转入就绪状态。sleep不会释放所持有的锁。
死亡状态(Dead):线程执行完毕或者因异常退出了run()方法，该线程结束生命周期。

线程调度

线程优先级

Java中线程存在优先级，优先级别高的线程会获得更多的运行机会。

Java中优先级取值范围为1-10，Thread类中的优先级

/**
 * The minimum priority that a thread can have.
 */
public final static int MIN_PRIORITY = 1;
/**
 * The default priority that is assigned to a thread.
 */
public final static int NORM_PRIORITY = 5;
/**
 * The maximum priority that a thread can have.
 */
public final static int MAX_PRIORITY = 10;

Thread类的setPriority和getPriority可以设置和获取线程的优先级

/**
 * Changes the priority of this thread.
 * <p>
 * First the <code>checkAccess</code> method of this thread is called
 * with no arguments. This may result in throwing a
 * <code>SecurityException</code>.
 * <p>
 * Otherwise, the priority of this thread is set to the smaller of
 * the specified <code>newPriority</code> and the maximum permitted
 * priority of the thread's thread group.
 *
 * @param newPriority priority to set this thread to
 * @exception  IllegalArgumentException  If the priority is not in the
 *               range <code>MIN_PRIORITY</code> to
 *               <code>MAX_PRIORITY</code>.
 * @exception  SecurityException  if the current thread cannot modify
 *               this thread.
 * @see        #getPriority
 * @see        #checkAccess()
 * @see        #getThreadGroup()
 * @see        #MAX_PRIORITY
 * @see        #MIN_PRIORITY
 * @see        ThreadGroup#getMaxPriority()
 */
public final void setPriority(int newPriority) {
    ThreadGroup g;
    checkAccess();
    if (newPriority > MAX_PRIORITY || newPriority < MIN_PRIORITY) {
        throw new IllegalArgumentException();
    }
    if((g = getThreadGroup()) != null) {
        if (newPriority > g.getMaxPriority()) {
            newPriority = g.getMaxPriority();
        }
        setPriority0(priority = newPriority);
    }
}
/**
 * Returns this thread's priority.
 *
 * @return  this thread's priority.
 * @see     #setPriority
 */
public final int getPriority() {
    return priority;
}

每个线程都有默认的优先级，主线程的默认的优先级为NORMAL
线程的优先级具有继承关系
一般使用三个静态常量作为优先级来完成与操作系统的线程优先级的映射

线程睡眠

/**
 * Causes the currently executing thread to sleep (temporarily cease
 * execution) for the specified number of milliseconds plus the specified
 * number of nanoseconds, subject to the precision and accuracy of system
 * timers and schedulers. The thread does not lose ownership of any
 * monitors.
 *
 * @param  millis
 *         the length of time to sleep in milliseconds
 *
 * @param  nanos
 *         {@code 0-999999} additional nanoseconds to sleep
 *
 * @throws  IllegalArgumentException
 *          if the value of {@code millis} is negative, or the value of
 *          {@code nanos} is not in the range {@code 0-999999}
 *
 * @throws  InterruptedException
 *          if any thread has interrupted the current thread. The
 *          <i>interrupted status</i> of the current thread is
 *          cleared when this exception is thrown.
 */
public static void sleep(long millis, int nanos)
throws InterruptedException {
    if (millis < 0) {
        throw new IllegalArgumentException("timeout value is negative");
    }
    if (nanos < 0 || nanos > 999999) {
        throw new IllegalArgumentException(
                            "nanosecond timeout value out of range");
    }
    if (nanos >= 500000 || (nanos != 0 && millis == 0)) {
        millis++;
    }
    sleep(millis);
}

sleep方法使线程转到阻塞状态，以毫秒为单位，当睡眠结束后，就转为Runnable状态，平台移植性比较好，睡眠过程中不会释放持有的锁。

线程等待

Object类的wait()方法，导致当前的线程等待，直到其他线程调用此对象的notify()方法或者notifyAll()唤醒方法。

/**
 * Causes the current thread to wait until another thread invokes the
 * This method should only be called by a thread that is the owner
 * of this object's monitor. See the {@code notify} method for a
 * description of the ways in which a thread can become the owner of
 * a monitor.
 *
 * @throws  IllegalMonitorStateException  if the current thread is not
 *               the owner of the object's monitor.
 * @throws  InterruptedException if any thread interrupted the
 *             current thread before or while the current thread
 *             was waiting for a notification.  The <i>interrupted
 *             status</i> of the current thread is cleared when
 *             this exception is thrown.
 * @see        java.lang.Object#notify()
 * @see        java.lang.Object#notifyAll()
 */
public final void wait() throws InterruptedException {
    wait(0);
}
/**
 * Wakes up a single thread that is waiting on this object's
 * @throws  IllegalMonitorStateException  if the current thread is not
 *               the owner of this object's monitor.
 * @see        java.lang.Object#notifyAll()
 * @see        java.lang.Object#wait()
 */
public final native void notify();
/**
 * Wakes up all threads that are waiting on this object's monitor
 * @throws  IllegalMonitorStateException  if the current thread is not
 *               the owner of this object's monitor.
 * @see        java.lang.Object#notify()
 * @see        java.lang.Object#wait()
 */
public final native void notifyAll();

Obj.wait()与Obj.notify()必须要与synchronized(Obj)一起使用，也就是wait,与notify是针对已经获取了Obj锁进行操作，从语法角度来说就是Obj.wait(),Obj.notify必须在synchronized(Obj){…}语句块内。从功能上来说wait就是说线程在获取对象锁后，主动释放对象锁，同时本线程休眠。直到有其它线程调用对象的notify()唤醒该线程，才能继续获取对象锁，并继续执行。

相应的notify()就是对对象锁的唤醒操作。但有一点需要注意的是notify()调用后，并不是马上就释放对象锁的，而是在相应的synchronized(){}语句块执行结束，自动释放锁后，JVM会在wait()对象锁的线程中随机选取一线程，赋予其对象锁，唤醒线程，继续执行。这样就提供了在线程间同步、唤醒的操作。

Thread.sleep()与Object.wait()二者都可以暂停当前线程，释放CPU控制权，主要的区别在于Object.wait()在释放CPU同时，释放了对象锁的控制

实例

public class SimpleWaitAndNotify {
    final static Object object = new Object();
    public static class T1 extends Thread {
        @Override
        public void run() {
            synchronized (object) {
                System.out.println(System.currentTimeMillis() + ":T1 start! ");
                try {
                    System.out.println(System.currentTimeMillis() + ":T1 wait for object");
                    object.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(System.currentTimeMillis() + ":T1 end!");
            }
        }
    }
    public static class T2 extends Thread {
        @Override
        public void run() {
            synchronized (object) {
                System.out.println(System.currentTimeMillis() + ":T2 start! notify ont thread");
                object.notify();
                System.out.println(System.currentTimeMillis() + ":T2 end!");
                try {
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    public static void main(String[] args) {
        Thread thread1 = new T1();
        Thread thread2 = new T2();
        thread1.start();
        thread2.start();
    }
}
/*
1535885737176:T1 start!
1535885737176:T1 wait for object
1535885737176:T2 start! notify ont thread
1535885737176:T2 end!
1535885739177:T1 end!
*/

wait()和sleep()区别
- 共同点
  1. 多线程环境中，都可以在程序中调用阻塞当前线程指定的毫秒数
  2. wait()和sleep()都可以通过interrupt()方法打断线程的暂停状态，从而使线程立刻抛出异常。
- 不同点
  1. sleep是Thread类的方法，wait是Object类的方法
  2. 每个对象都有一个锁来控制同步访问。synchronize关键字可以和对象的锁交互，实现线程的同步。sleep方法没有释放锁，wait方法释放了锁。
  3. wait，notify，notifyAll只能在同步控制方法或者同步控制块中使用，sleep可以在任意地方使用。

线程让步
- Thread.yield()方法，导致当前正在执行的线程对象，将执行机会让给相同或者更高优先级的线程。
- 使用目的为让相同优先级的线程之间进行适当的轮转执行，实际中yield让出时间片的线程有可能获得时间片继续执行。
- yield不会导致线程转入等待、睡眠、阻塞状态。大多数情况下，yield将导致线程从运行状态转入就绪状态，也可能没有效果。
- sleep和yield的区别
  1. sleep使得当前线程进入阻塞状态，执行sleep的线程在指定的时间内肯定不会被执行，yield只是使当前的线程进入就绪状态，执行yield之后该线程有可能竞争到时间片从而马上执行。
  2. 方法使当前运行中的线程休眠一段时间，进入阻塞状态，这段时间的长短是由程序设定的。yield方法使当前程序让出CPU占有权，让出时间无法控制。
  3. sleep允许较低优先级的线程获得运行机会，yield只会将执行机会让给同级的或者高级的线程。

线程加入

Thread.join()方法，等待其他线程终止。在当前的线程中调用另一个线程的join()方法，则当前线程转入阻塞状态，直到另一个线程运行结束，当前线程由阻塞状态转为就绪状态。

当主线程需要子线程的计算结果进行后续计算时，使用join，否则当子线程耗时较长时，主线程会先结束。

public class JoinMain {
    public volatile static int i = 0;
    public static class AddThread extends Thread {
        @Override
        public void run() {
            i = 0;
            while (i < 1000000) {
                i++;
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        AddThread addThread = new AddThread();
        addThread.start();
        addThread.join();
        System.out.println(i);
    }
}
// 1000000

线程唤醒
- notify():唤醒在此对象监视器上等待的单个线程，如果多个线程等待，则随机唤醒一个线程。
- 线程通过调用该对象的wait方法进入对象的监视器上处于等待状态
- notifyAll():唤醒所有等待线程

线程同步

synchronized关键字

对象锁
- 某个对象实例内，synchronized a method可以防止多个线程同时访问这个对象的synchronized方法。
- 如果一个对象有多个synchronized方法，只要一个线程访问了其中的一个synchronized方法，则其他线程就不能访问这个对象的任何一个synchronized方法
- 不同对象实例的synchronized方法是互不干扰的，其他线程可以统统是访问相同类的另一个对象中的synchronized方法。
- synchronized关键字在方法中的某个代码块上，同样表示对该对象加锁。
类锁
- synchronized static aMethod{} 防止多个线程同时访问这个类的synchronized static方法。其对类的所有对象实例起作用。
synchronized关键字是不能继承的，父类中的synchronized方法在继承类中不是自动创建为synchronized方法，需要显示指定。
synchronized关键字可有作用在instance变量，object引用，static函数和类名称字面常量上。

synchronized关键字加在方法上还是对象上，它取得的锁都是对象，而不是把一段代码或函数当做锁

每个对象只有一个锁与之相关

实现同步需要很大的系统开销作为代价，甚至可能造成死锁，尽量避免无谓的同步控制。

总结
- 线程同步的目的是为了保护多个线程反问一个资源时对资源的破坏。
- 线程同步方法是通过锁来实现，每个对象都有切仅有一个锁，这个锁与一个特定的对象关联，线程一旦获取了对象锁，其他访问该对象的线程就无法再访问该对象的其他非同步方法
- 对于静态同步方法，锁是针对这个类的，锁对象是该类的Class对象。静态和非静态方法的锁互不干预。一个线程获得锁，当在一个同步方法中访问另外对象上的同步方法时，会获取这两个对象锁。
- 对于同步，要时刻清醒在哪个对象上同步，这是关键。
- 编写线程安全的类，需要时刻注意对多个线程竞争访问资源的逻辑和安全做出正确的判断，对“原子”操作做出分析，并保证原子操作期间别的线程无法访问竞争资源。
- 当多个线程等待一个对象锁时，没有获取到锁的线程将发生阻塞。
- 死锁是线程间相互等待锁锁造成的，在实际中发生的概率非常的小，一旦程序发生死锁，程序将死掉。

线程数据传递

传统开发模式中，当我们调用一个函数时，通过这个函数的参数将数据传入，并通过这个函数的返回值来返回最终的计算结果。但是在多线程的异步开发模式下，数据的传递和返回和同步开发模式有很大区别。由于线程的运行和结束都是不可预料的，因此，在传递和返回函数时无法像函数一样通过函数参数和return语句来返回数据。线程之间的数据传递可以通过构造方法，变量和方法，回调函数来完成。

通过构造方法来传递数据

在线程的构建方法中传入数据，线程运行之前数据就已经确定，不会造成数据在线程运行之后才传入的线性。但是传递的数据比较多时，成本很高。同时由于Java没有默认参数，因此需要使用重载，使得构造方法本身很复杂，同时数量很多。

/**
 * @program: 02_Basic
 * @author: cdx
 * @create: 2018-09-02 16:23
 **/
public class CreateThreadByExtendsThread extends Thread{
    private String name;
    public CreateThreadByExtendsThread(String name) {
        this.name = name;
    }
    @Override
    public void run() {
        for (int i = 0; i < 3; i++)
            System.out.println(this.name + " create thread by extends Thread!");
    }
    public static void main(String[] args) {
        Thread threadA = new CreateThreadByExtendsThread("A");
        Thread threadB = new CreateThreadByExtendsThread("B");
        threadA.start();
        threadB.start();
    }
}

通过变量和方法

向对象中传入数据一般有两次机会，第一次是在建立对象时时通过构造方法将数据传入，第二次是在类中定义一些列的public的方法和变量。然后再建立完对象之后，通过对象实例逐个赋值。

/**
 * @program: 02_Basic
 * @author: cdx
 * @create: 2018-09-02 16:23
 **/
public class CreateThreadByExtendsThread extends Thread{
    private String name;
    public CreateThreadByExtendsThread(String name) {
        this.name = name;
    }
    public CreateThreadByExtendsThread() {
    }
    @Override
    public void run() {
        for (int i = 0; i < 3; i++)
            System.out.println(this.name + " create thread by extends Thread!");
    }
    public void writeName(String name) {
        this.name = name;
    }
    public static void main(String[] args) {
        Thread threadA = new CreateThreadByExtendsThread();
        Thread threadB = new CreateThreadByExtendsThread();
        ((CreateThreadByExtendsThread) threadA).writeName("A");
        ((CreateThreadByExtendsThread) threadB).writeName("B");
        threadA.start();
        threadB.start();
    }
}

通过回调函数传递数据

前两种都是main方法中向线程类中传递数据，实际中，有些数据需要从线程类传递到main函数中，如下：

import java.util.Arrays;
import java.util.Random;
/**
* @program: 02_Basic
* @author: cdx
* @create: 2018-09-02 21:26
**/
public class ThreadDataTransferByCallback implements Runnable{
   private Work work;
   public ThreadDataTransferByCallback(Work work) {
       this.work = work;
   }
   @Override
   public void run() {
       Random random = new Random();
       Data data = new Data();
       int n1 = random.nextInt(1000);
       int n2 = random.nextInt(1000);
       int n3 = random.nextInt(1000);
       work.process(data, new Integer[]{n1, n2, n3});
       System.out.printf("n1 is %d, n2 is %d, n3 is %d,sum is %d\n", n1, n2, n3, data.value);
   }
   public static void main(String[] args) {
       new ThreadDataTransferByCallback(new Work()).run();
   }
}
class Data {
   int value = 0;
}
class Work {
   public void process(Data data, Integer[] numbers) {
       for (Integer i : numbers)
           data.value += i;
   }
}
// n1 is 540, n2 is 982, n3 is 945,sum is 2467

Java网络编程

发表于 2019-04-21 | 分类于 Java

网络编程中的两个主要问题

如何准确的定位网络上的一台或者多台主机

TCP/IP协议中IP协议主要负责网络主机的定位，数据传输的路由，可以由IP地址唯一的确定Internet上的一台主机。

找到主机后如何进行可靠高效的数据传输

TCP层提供面向应用的可靠传输（TCP）或者非可靠的UDP数据传输机制。目前比较流行的网络编程模型为C/S架构，也就是通信一方作为服务器等待客户提出请求并给予相应，客户端在需要服务时向服务器提出申请。服务器一般作为守护进程始终执行，监听网络端口，一旦有客户请求，就会启动一个服务进程来响应客户，同时自己继续监听服务端口，使后来的客户也能及时得到服务。

TCP协议和UDP协议

TCP：Transfer Control Protocol的简称，是一种面向连接的可靠传输协议。通过TCP协议传输得到的是一个顺序的无差错的数据流，发送方和接收方的成对的连个socket必须建立连接，以便在TCP协议的基础上进行通信。

UDP：User Datagram Protocol的简称，是一种无连接的协议。每个数据报都是一个独立的消息，包括完整的源地址或目的地址，在网络上以任何可能的路径进行传送，能否到达目的地以及到达的时间都不确定。

	UDP	TCP
连接性	无连接	面向连接
传输数据大小	大小有限制，64KB以内	统一格式数据传输
可靠性	不可靠，不保证到达	可靠协议
应用	Telnet/FTP	视频会议

基于Socket的Java网络编程

网络上两个程序通过一个双向的通讯连接实现数据的交换，这个双向链路的一端成为一个Socket。Socket通常用来实现客户方和服务端的链接。一个Socket由一个IP和一个PROT唯一确定。Java环境下，Socket编程主要是指基于TCP/IP协议的网络编程。

Socket通信流程

Server端监听某个端口是否有连接请求
Client端相Server端发送Connect请求
Server端相Client端发送Accept消息，建立连接。
Server端和Client端都可以通过Send，Write等方式通信。
关闭Socket

创建一个Socket

Java中java.net包中提供了两个类，Socket，ServerSocket，分别表示双向连接的客户端和服务端。

客户端类的构造方法：

public Socket(String host, int port)
    throws UnknownHostException, IOException
{
    this(host != null ? new InetSocketAddress(host, port) :
         new InetSocketAddress(InetAddress.getByName(null), port),
         (SocketAddress) null, true);
}

服务端的构造方法：

1
2
3

public ServerSocket(int port) throws IOException {
    this(port, 50, null);
}

简单的Client/Server程序

未完