Java容器中如何高效处理不同类型数据结构？

结合一些文章阅读源码后整理的Java容器常见知识点。对于一些代码细节，本文不展开来讲，有兴趣可以自行阅读参考文献。 1. 思维导图 各个容器的知识点比较分散，没有在思维导图上体现，因此看上去右半部分很像类的继承关系。 2. 容器对比 类名 底层实现 特征 线程安全性 默认迭代器实现(Itr) ArrayList Object数组 查询快，增删慢 不安全 数组下标 LinkedList 双向链表 查询慢，增删快 不安全 当前遍历的节点 Vector Object数组 查询快，增删慢 方法使用synchronized确保安全（注1）；有modCount 数组下标 Stack Vector 同Vector 同Vector 同Vector HashSet HashMap (使用带特殊参数的构造方法则为LinkedHashMap) 和HashMap一致 和HashMap一致 和HashMap一致 LinkedHashSet LinkedHashMap 和LinkedHashMap一致 和LinkedHashMap一致 和LinkedHashMap一致 TreeSet TreeMap 和TreeMap一致 和TreeMap一致 和TreeMap一致 TreeMap 红黑树和Comparator（注2） key和value可以为null（注2），key必须实现Comparable接口 非线程安全，有modCount 当前节点在中序遍历的后继 HashMap 见第3节 key和value可以为null 非线程安全 HashIterator按数组索引遍历，在此基础上按Node遍历 LinkedHashMap extends HashMap 可以按照插入顺序或访问顺序遍历（注4） 非线程安全 同HashMap ConcurrentHashMap 见第3节 key和value不能为null 线程安全（注1） 基于Traverser （注5） Hashtable Entry数组 + Object.hashCode() + 同key的Entry形成链表 key和value不允许为null 线程安全 枚举类或通过KeySet/EntrySet 操作的时间复杂度 ArrayList下标查找O(1)，插入O(n) 涉及到树，查找和插入都可以看做log(n) 链表查找O(n)，插入O(1) Hash直接查找hash值为 O(1) 注1：关于容器的线程安全 复合操作 无论是Vetcor还是SynchronizedCollection甚至是ConcurrentHashMap，复合操作都不是线程安全的。如下面的代码[1]在并发环境中可能会不符合预期： if (!vector.contains(element)) vector.add(element); ... } ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap(); map.put("key", 1); // 多线程环境下执行 Integer currentVal = map.get("key"); map.put("key", currentVal + 1); 在复合操作的场景下，通用解法是对容器加锁，但这样会大幅降低性能。根据具体的场景来解决效果更好，如第二段代码的场景，可以改写为[1] ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap(); // 多线程环境下执行 map.get("key").incrementAndGet(); modCount和迭代器Iterator问题 modCount是大多数容器（比如ConcurrentHashMap就没有）用来检测是否发生了并发操作，从而判断是否需要抛出异常通知程序员去处理的一个简单的变量，也被称为fast-fail。 一开始我注意到，Vector也有modCount这个属性，这个字段用来检测对于容器的操作期间是否并发地进行了其他操作，如果有会抛出并发异常。既然Vector是线程安全的，为什么还会有modCount？顺藤摸瓜，我发现虽然Vector的Iterator()方法是synchronized的，但是迭代器本身的方法并不是synchronized的。这就意味着在使用迭代器操作时，对Vector的增删等操作可能导致并发异常。 为了避免这个问题，应该在使用Iterator时对Vector加锁。