Java容器如果要分类的话，大体上可以按照实现接口分为两类：Collections，Map下面我就按照这个分类来做一个笔记

Collections

List

ArrayList

  1. 随机访问元素的时候很快，但是在List的中间插入和移除元素的时候较慢
  2. 底层实现是数组，有一个默认的容量，也可以指定一个容量，当容量不够用的时候，自动扩容（为原先容量的1.5倍，Vector扩容为原先容量的2倍）

    LinkedList

  3. 插入删除操作代价较低，随机访问的时候较慢，但是它的特性集较ArrayList更大
  4. 底层实现是一个双向的链表，没有容量的概念

    Arrays.asList()产生的List

  5. Arrays.asList()的底层实现是一个数组，因此无法修改尺寸，使用add，delete操作的时候会抛出异常
  6. Arrays.asList()返回固定尺寸的List，而Collections.unmodifiableList()产生不可以修改的List（Map，Set都有这样的方法），修改Arrays.asList()返回的List的元素是可以的，因为没有违反该List“尺寸固定”这一个特性，而unmodifiable()的结果在任何情况下都是不可以修改的

    其他

  7. 除了iterator之外，还可以使用ListIterator来遍历List，ListIterator可以双向遍历，增加元素，替换元素

    Set

    HashSet

  8. 底层维护了一个HashMap，通过HashMap实现Set的行为
  9. HashSet存储的顺序和插入顺序没有关系，因为HashSet的存储是基于散列的
  10. 存入HashSet的元素必须定义hashCode方法

    TreeSet

  11. 底层维护了一个NavigableMap，通过NavigableMap实现Set行为
  12. 最终将元素存放在红黑树中，根据给定的规则进行排序的

    LinkedHashSet

  13. 继承HashSet实现，通过源码可以看出，其实是调用了父类的构造方法，该方法new了一个LinkedHashMap，说白了就是通过LinkedHashMap实现
  14. 查询速度和HashSet一样快，但是维护了一个链表存储插入的顺序
  15. 元素必须定义hashcode方法

    Queue

  16. LinkedList提供了方法支持队列的行为，并且它实现了Deque（双向队列）接口，Deque接口集成Queue，因此LinkedList可以用作Queue的一种实现，通过LinkedList向上转型为Queue
  17. 使用较多的是PriorityQueue，支持插入元素按照规则排序

    其他的数据结构

    Vector

  18. 线程安全
  19. 已经过时，不应该使用

    Stack

  20. 原先的Stack通过集成Vector来实现，但这样是不合适的。如果你只需要Stack的行为，这里使用继承就不合适的了，因为这样会成导致其具有Vector行为，最完美的实现是让Stack类维护一个LinkedList，通过LinkedList来实现Stack的所有行为，就像HashSet的行为一样。

    Map

    HashMap

  21. 非线程安全，是Hashtable的一个轻量级实现
  22. 负载因子：尺寸／容量，空表的负载因子是0，半满表的负载因子是0.5，以此类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是理想的（但是会减慢使用迭代器进行遍历的过程）HashMap和HashSet都具有允许你置顶负载因子的构造器，表示党负载情况达到负载因子的水平的时候，容器将自动增加其容量（桶位），实现方式是使容量加倍，并重新将现有对象分布到新的桶位中（这被称为再散列），默认情况下，负载因子是0.75

    HashTable

  23. 线程安全的
  24. 已经过时了，不应该使用

    TreeMap

  25. 底层实现了一个红黑树，用于维护一个有序的结构

    LinkedHashMap

  26. 继承HashMap实现

    IdentityMap

  27. 其中保存同一对象的多个实例，使用==代替equals方法对“键”进行比较，所以根据存放地址来判断是否是重复的

    WeakHashMap

  28. 弱键映射，允许释放映射所指向的对象。如果映射之外没有引用只想某个键，则此键可以被垃圾回收

    Collections的一些方法使用

    常用操作

    |方法名称 |解释 | |———————————————- |—————————————————–| |sort(List) | 使用List中的自然排序 | |sort(List,Comparator<?Super T> c) | 允许使用提供用于排序的的Comparator | |fill(List<?super T>, T x) | 用对象x替换list中所有的元素 | |nCopies(int n,T x) | 返回大小为n的List，此List不可以改变，其中的引用都指向x | |disjoint(Collection, Collection) | 当两个集合没有任何相同的元素的时候，返回true | |frequency(Collection, Object x) | 返回Collection中等于x的元素的个数 | |copy(List<?super T>dest,List<?extends T> src) | 将src中的元素复制到dest |

多线程下使用

1.一般的容器都是非线程安全的，但是可以使用Collections.synchronizedMap等来封装容器来达到多线程使用的目的 # 小结 1. **ArrayList和LinkedList的选择**：通常情况下选择ArrayList作为默认的容器，其实两者性能上差距不大，观察ArrayList的底层代码实现的时候，ArrayList操作最为耗时的操作时扩容操作，当程序涉及频繁扩容的时候使用LinkedList更佳。相对好的习惯是初始化ArrayList的时候给定一个合理的size，且一般程序访问数据的次数多于插入数据的次数。 2. **迭代器**：要善于使用迭代器，建议所有对容器访问的时候都使用迭代器，一来迭代器轻量级，方法简单，二来迭代器中修改容器不会抛出异常，而且更合乎逻辑 3. **关于hashCode方法**：
- 使用HashSet等实现散列的容器的时候，必须定义hashCode。
- 重写euqals方法的时候一定要重写hashCode方法
- hashCode不应该依赖于一个易变的数据，当数据变化的时候，会重新计算hashCode，此时就不能取回原先容器中的对象了，会造成内存泄露 4. Collection保存单一的元素，而Map保存关联的键值对。有了Java的泛型，就可以指定容器中存放的对象类型，因此你就不会将错误类型的对象放入容器中，并且在容器中获得元素，不必进行类型转换，各种Collection和Map都可以在向其添加更多的元素的时候，自动调整其尺寸，容器不能持有基本类型，但是自动装箱机制会仔细的执行基本类型到容器中所持有的包装器类型之间的双向转换 5. 新程序中不该使用过时的Vector，Hashtable，Stack 6. **关于modCount**:所有容器都有modCount这个变量，这个是做什么用的呢，它是用来记录容器被修改的次数的。这是一个很重要的东西。当使用多个线程使用迭代器迭代访问该容器的时候，迭代器内部会保存一个expectedModCount来保存容器的modCount，在访问的时候实时检查expectedModCount==modCount，如果返回时一个false，抛出一个ConcurrentModificationException。简单来说在使用迭代器遍历的时候，用来检查列表中的元素是否发生结构性变化（列表元素数量发生改变）了，主要在多线程环境下需要使用，防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构。所以modCount的作用是迭代器在遍历时做线程安全检查的。具体可以看[这篇博客](http://www.cnblogs.com/dolphin0520/p/3933551.html)