常见数据结构浅析

常见数据结构浅析

1.ArrayList和CopyOnWriteArrayList

ArrayList

特点

1. 线程不安全
2. 底层数据结构是数组（查询快，增删慢，支持快速随机访问）
3. 内存占用会存在部分浪费，末尾会预留一部分容量空间

容量

当创建一个ArrayList对象时，它会分配一定的初始容量，通常为10
private static final int DEFAULT_CAPACITY = 10;

添加元素：

1.判断需要的容量是不是大于数组长度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
2.扩容 扩为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

3.复制原数据到新数组
elementData = Arrays.copyOf(elementData, newCapacity);

4.把新元素添加到数组末尾
elementData[size++] = e;

移除元素：

1.计算一个元素得位置
int numMoved = size - index - 1;
2.复制
把原数组的第index+1后面的数据复制到原数组的index位置复制长度为size - index - 1
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
3.把数组最后一个元素置空
elementData[–size] = null;

解决ArraryList线程不安全

1.vector
2.Collections.synchronizedList(new ArrayList<>());
3.CopyOnWriteArrayList

CopyOnWriteArrayList

写时复制： CopyOnWrite 容器即写时复制容器。往一个容器添加元素时，不直接往Object[]添加，而是先将当前容器Object[]进行copy 复制出一个新得容器，Object[] newElements，然后往新的容器newElements里添加元素，添加完元素后再将原容器的引用指向新得容器setArray(newElements)。这样做的好处是可以对CopyOnWrite容器进行并发读，而不需要加锁，因为当前容器不添加任何元素。所以CopyOnWrite是一种读写分离思想，即读和写用的不同容器

写的时候使用了ReentrantLock枷锁

 public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

数组array本身使用了volatile，保证多线程可见性

private transient volatile Object[] array;

2.HashSet和CopyOnWriteArraySet

HashSet线程不安全其底层就是一个HashMap<E,Object> HashSet的add方法

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

PRESENT是（常量）：

 private static final Object PRESENT = new Object();

CopyOnWriteArraySet

底层依然是CopyOnWriteArrayList，线程安全

3.HashMap与ConcurrentHashMap