松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有JAVA技術和業內最佳實踐,大部分都是務實的、能看懂的、可復現的

掃一掃
關注公眾號

我們應該從JAVA集合中學到什么

博客首頁文章列表 松花皮蛋me 2019-06-05 22:44

本文不講解各種集合間的區別,適用場景是什么,增刪改查的時間復雜度和時間復雜度是多少,是否線程安全,是否有序,是否支持隨機訪問,是否是快速失敗的,也不關心底層結構是數組、哈希表、鏈表、紅黑樹的哪一個。如果你閱讀過我blog(www.znvxfuqt.icu)大部分文章就會發現基本上是總結性、技巧性、細節性的,送一句話與你共勉:看懂然后模仿再創造,加油!!

一、空接口

public interface RandomAccess {
}

聲明的是一個標簽,接口繼承者應該自覺遵守標簽規則,比如支持隨機訪問。現實生活中,經常會貼上各種標簽,比如有個打折活動,自動識別用戶的標簽,如果是活動送的VIP就打9折,正常購買的VIP打7折

二、ArrayList序列化和反序列化

ArrayList的數組是動態擴增的,并不是所有被分配的內存空間都存儲了數據,所以使用transient修飾數組防止被其他外部方法序列化,避免沒有數據的內存空間被序列化,內部提供兩個私有方法writeObject以及readObject來自我完成序列化和反序列化。序列化和反序列化時在java.io.ObjectStreamClass#getPrivateMethod()方法中通過反射獲取到writeObject、readObject方法

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

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

三、降低哈希碰撞

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果簡單使用(n-1) & key.hashCode(),二進制運算時會有很多0參與運算。如果通過將hashCode值無符號右移16位后,也就是取int類型的一半,剛好可以將該二進制對半切開,并且使用位異或運算,這樣就會盡量打亂真正參與運算的低16位

另外設置初始容量時,一般是2的整數次冪,如果不是,HashMap也會做出相應的調整

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

實際上2的冪次方減1后每一位都是1,這樣在&hash值時使得數組每個位置都是可以添加元素的,有效降低哈希沖突

四、有界阻塞隊列ArrayBlockingQueue

下面代碼中的ReentrantLock鎖默認是非公平的。公平鎖就是在獲取鎖之前會先判斷等待隊列是否為空或者自己是否位于隊列頭部,該條件通過才能獲得鎖,否則添加到隊列尾部

非公平鎖嘗試獲取鎖時,鎖釋放如果剛好發生,它往往會直接獲得鎖,因為就緒隊列喚醒有開銷的。非公平鎖減少了鎖掛起的開銷,鎖掛起需要從用戶態轉到內核態

public E poll(long timeout, TimeUnit unit) throws InterruptedException {
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0) {
            if (nanos <= 0)
                return null;
            nanos = notEmpty.awaitNanos(nanos);
        }
        return dequeue();
    } finally {
        lock.unlock();
    }
}

interrupt()并不能使一個在等待鎖的線程真正”中斷”,它只會設置線程的中斷標志,并不會使它從鎖等待隊列中出來。synchronized關鍵字和Lock.lock()獲取鎖的過程中不響應中斷請求,可以改用Lock.lockInterruptibly(),它可以向上拋出中斷異常

五、鎖分離,CopyOnWriteArrayList中讀寫分離、ConcurrentHashMap中的分段鎖

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加鎖
    lock.lock();
    try {
        // 獲取舊數組
        Object[] elements = getArray();
        int len = elements.length;
        // 檢查是否越界, 可以等于len
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // 如果插入的位置是最后一位
            // 那么拷貝一個n+1的數組, 其前n個元素與舊數組一致
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 如果插入的位置不是最后一位
            // 那么新建一個n+1的數組
            newElements = new Object[len + 1];
            // 拷貝舊數組前index的元素到新數組中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 將index及其之后的元素往后挪一位拷貝到新數組中
            // 這樣正好index位置是空出來的
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 將元素放置在index處
        newElements[index] = element;
        setArray(newElements);
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

六、LinkedHashMap實現LRU緩存淘汰策略

class LRU<K,V> extends LinkedHashMap<K,V> {
    private int capacity;
    public LRU(int capacity,float loadFactor) {
        //第三個參數表示是否有序
        super(capacity,loadFactor,true);
        this.capacity = capacity;
    }
    /** 
    * @Description: 默認的LinkedHashMap并不會移除舊元素,如果需要移除舊元素,則需要重寫removeEldestEntry()方法設定移除策略
    * @Param: [eldest] 
    * @return: boolean 
    * @Author: Pidan
    */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        //當元素個數大于緩存的容量時,就移除元素
        return size()>this.capacity;
    }
}

開閉原則的味道有某有?!!

七、CAS+自旋+ABA校驗

ConcurrentHashMap的方法代碼太長,不好演示,這里摘取原子類AtomicInteger#getAndIncrement進行說明。輕量級鎖-自旋鎖是指當一個線程在獲取鎖的時候,如果鎖已經被其它線程獲取,那么該線程將循環等待,然后不斷的判斷鎖是否能夠被成功獲取,直到獲取到鎖才會退出循環,這樣不會進入休眠狀態-內核調度狀態

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

// Unsafe中的方法
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

八、升級

ConcurrentHashMap鏈表結點數達到TREEIFY_THRESHOLD后轉換為紅黑樹、Java并發中的鎖升級(偏向鎖、輕量級鎖、重量級鎖)

黑龙江6+1开奖结果查询