Listjava.util包提供了两种ArrayListLinkedListArrayList比LinkedList常用很多，原因是:ArrayList查找更容易ArrayListArrayList封装了一个数组Object[]数组的初始化ArrayList array = new ArrayList();封装一个空数组, {}ArrayList array = new ArrayList(10);封装一个大小为10的数组 new Object[10];数组如何实现扩容ArrayList.add/addAll都需要先进行扩容检查，类似， 对象调用方法，要进行对象判空， UI操作之前要进行，线程检查 扩容检查: size+增加的大小 与 数组.length 比较计算数组扩容的数组长度： 首先，扩容至原数组大小的一倍，size+增加的大 小与其比较： 如果大于，扩容至原数组大小的一倍 如果小于，扩容至size+增加的大小;private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }扩容使用的是: Array.copyof(array, newLen)removeAll如何实现与remove()不同，remove使用System.copy完成数组的 部分移动 而removeAll,使用的算法：ArrayList array1 = new ArrayList();array1.addAll({0,3,5,7,3,6});int[] array2 = {3,5,4};array1.removeAll(array2);首先，遍历array1中每个元素，若元素 不在array2内，将计数位置的值设置为元素的值并将计 数+1; 遍历完成后，计数为数组剩余元素的个 数，将计数之后的元素清空. 算法详细:   0,3,5,7,3,6 ;<br>   遍历之后，计数为2，数组为0,7,6,7,3,6;<br>   清空之后，0,7,6,null,null,null;trimToSize()数组扩容后即使删除元素，数组的length也不会该改变，意味着即使删除了某些元素数组占用的内存大小不会改变;数组只会不断的增大,且出现大量null的元素.trimToSize()方法用于改变数组的length,将为null的元素释放掉，等待GC这也是防止内存浪费的一种方式，当ArrayList经历了多次删除操作之后，使用trimToSize(),避免内存浪费.trimToSize()使用Array.copyof()来改变数组的length总结ArrayList本质上维护了一个数组，也就意味者它具有数组的优缺点：增删难，查找易LinkedListNode的数据结构Node<E> { E element; Node<E> prev; Node<E> next;}基本结构 Node<E> first, lastLinked是双向链表,first,last指向表头，表尾总结LinkedList是一个Deque,双向链表， 增删易，查找难，造成在编码中很少使用Mapjava.util包提供了两种Map:1.HashMap2.TreeMapAndroid为了性能优化，提供了HashMap的替代品:1.ArrayMap2.SparseMap它俩可以在数据量都在千级以内的情况下， 如果key的类型为int，使用SparseMap, 如果key的类型为其它类型，使用ArrayMapHashMap相比TreeMap更常用HashMap数据结构 Node的数据结构:Node<K,V> { int hash; K key; V value; Node<K,V> next;}基本数据结构:Node<K,V>[] table;float loadFoctor;//默认值0.75fint threshold;可以看出HashMap的数据结构是数组+链表扩容什么时候扩容当调用put/putAll时,实际上都是调用putVal方法 先创建Node,再查看新的Node放入数组，还是链表; 当++size>threshold，则需要扩容table如何扩容它的扩容包含两个步骤:1. 确定扩容的大小;2. 如何移动元素，包含数组中的元素与链表中的元素;<br> 确定扩容的大小: threshold默认值 = 16*0.75f=12 每次扩容， 先创建一个threadhold大小的数组，赋给tble,也就是扩容至threadhold 再，threadhold = threadhold <<1，扩大一倍 如何移动元素，包含数组中的元素与链表中的元素: 1.如果元素只在数组里，而没有链表: 新的位置是 e.hash&(newCap-1) 2.元素在链表上: 根据(e.hash & oldCap) == 0 决定是在原位置还是在原位置+oldCap上 链表可能会分为两部分TreeMap数据结构TreeMapEntry的数据结构TreeMapEntry<K, V> { K key; V value; TreeMapEntry<K, V> left; TreeMapEntry<K, V> right; TreeMapEntry<K, V> parent;}TreeMap的数据结构：TreeMapEntry<K, V> root;Comparator<? super K> comparator;TreeMap实际上是红黑二叉树SparseArray数据结构int[] mKeys;Object[] mValues;总结 官方推荐去使用SparseArray<E>去替换HashMap<Integer,E>, 牺牲了部分效率换来内存ArrayMapLinkedHashMap可以看作HashMap+LinkedList，用于保证插入顺序一般用于作为缓存Java中的线程安全的容器同步容器Vector HashTable 并发容器用于读写分离，实现读并发，写同步并发的不同策略: 1.Blocking容器 2.CopyOnWrite容器 3.Concurrent容器Blocking容器并发策略: 用于解决限制容量的容器的存取问题 类似生产者-消费者 容器为空时，阻塞取线程 容器满时，阻塞存线程CopyOnWrite容器并发策略: 写时赋值，即添加元素时，先复制整个容器，添加到复制的容器中, 再将容器引用指向复制的容器，达到读的最大并发; 适用于读多写少的情况;Concurrent容器并发策略: 使用分段锁，首先将容器分成多段，每段使用不同的锁，对不同段达到读写并发,相同段读并发，写同步