常见数据结构浅析

2023-12-22 17:33:12

常见数据结构浅析

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

文章来源:https://blog.csdn.net/m0_37635053/article/details/135155748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。