Java集合概述（上） (2)

通过链表，可以有效地将零散的内存单元通过引用的方式串联起来，形成按链路顺序查找的线性结构，内存利用率较高（引用自《码出高效》）

Vector

Vector本质与ArrayList没太大区别，底层同样是Object数组，默认大小依旧为10（不过Vector采用的是不推荐的魔法数字）。

唯一的区别，就是Vector在关键方法上添加了Sychronized关键字，来确保线程安全。

但是，由于处理得较为粗糙，以及其特点，所以性能很差，基本已经被抛弃。

这里就不再赘述了。

CopyOnWriteArrayList

CopyOnWriteArrayList，作为COW容器的一员，其思想就是空间换时间，主要针对读多写少的场景。当有元素写入时，会新建一个数组，将原有数组的元素复制过来，然后进行写操作（此时数组的读操作，还是针对原数组）。在写操作完成后，会将读操作针对的数组引用，从原数组指向新数组。这样就可以在写操作进行时，不影响读操作的进行。

数据组织方式 /** The array, accessed only via getArray/setArray. */ // 一方面通过transient避免序列化，另一方面通过volatile确保可见性，从而确保单个属性（这里是引用变量）的线程安全 private transient volatile Object[] array; 数据处理方式 add public void add(int index, E element) { final ReentrantLock lock = this.lock; // 进行加锁，同时只能有一个写操作 // 另外，加锁操作放在try块外，一方面是try规范（lock操作并不会发生异常，并且可以减少try块大小），另一方面是避免加锁失败，finally的释放锁出现IllegalMonitorStateException异常 lock.lock(); try { // 获取原有数组，并赋值给elements（引用变量） Object[] elements = getArray(); int len = elements.length; // 数据校验 if (index > len || index < 0) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+len); // 下面的操作，就是对原有数组进行复制，并赋值给newElements（并且留出index位置） Object[] newElements; int numMoved = len - index; if (numMoved == 0) newElements = Arrays.copyOf(elements, len + 1); else { newElements = new Object[len + 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + 1, numMoved); } // 设置新数组index位置的值为element，完成赋值操作 newElements[index] = element; // 将数组引用（读操作正在读的数组引用）改为newElements setArray(newElements); } finally { // 无论是否异常，都需要释放锁， lock.unlock(); } }

最大的特色，就是这部分了。至于remove操作，都是类似的。故不再赘述。

小结

由于CopyOnWriteArrayList的数据组织方式与ArrayList一致，也是采用的数组，故：

CopyOnWriteArrayList随机查询快

CopyOnWriteArrayList插入与读写慢

CopyOnWriteArrayList是容量可变的（每次进行增删的写操作，都会新建一个数组，进而进行替换）

补充：

CopyOnWriteArrayList是线程安全的（读写操作隔离，写操作通过ReentrantLock确保线程安全）

CopyOnWriteArrayList的写操作不直接影响读操作（两者在内存上针对的不是同一个数组）

CopyOnWriteArrayList只适用于读多写少场景（毕竟写操作是需要复制数组）

CopyOnWriteArrayList占据双倍内存（因为写操作的时候需要复制数组）

CopyOnWriteArrayList的性能会随着写入频次与数组大小上升，而快速下降（写入频次m x 数组大小n）

推荐：高并发请求下，可以攒一下要进行的写操作（如添加，或删除，可以分开保存），然后进行addAll或removeAll操作。这样可以有效减低资源消耗。但是这个攒的度需要好好把握，就和请求合并一样，需要好好权衡。

二，Map TreeMap 数据组织方式 数据处理方式 小结 HashMap

HashMap一方面是工作中用的非常多的集合，另一方面是面试的高频（我每次面试几乎都会被人问这个）。