常见数据结构浅析
常见数据结构浅析
1.ArrayList和CopyOnWriteArrayList
ArrayList
特点
- 线程不安全
- 底层数据结构是数组(查询快,增删慢,支持快速随机访问)
- 内存占用会存在部分浪费,末尾会预留一部分容量空间
容量
当创建一个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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!