我们应该从JAVA集合中学到什么

公众号_松华说

修改于 2019-07-30 13:17:50

2530

修改于 2019-07-30 13:17:50

本文不讲解各种集合间的区别，适用场景是什么，增删改查的时间复杂度和时间复杂度是多少，是否线程安全，是否有序，是否支持随机访问，是否是快速失败的，也不关心底层结构是数组、哈希表、链表、红黑树的哪一个。如果你阅读过我blog(www.liangsonghua.me)大部分文章就会发现基本上是总结性、技巧性、细节性的，送一句话与你共勉：看懂然后模仿再创造，加油！！

一、空接口

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