Java集合

List

  • ArrayList
    • ArrayList是List接口的主要实现类，底层使用Object数组实现。
    • ArrayList中的数据是按顺序存储的，可以通过索引快速访问，时间复杂度为O(1)。
    • ArrayList插入或删除元素的开销为O(n)，因为要移动后面的元素，无论是否使用Iterator。
    • ArrayList是线程不安全的，即多线程访问时需要使用同步锁。
    • ArrayList的初始容量为10，每当容量不足时，容量会自动扩充为原来的1.5倍，扩容性能差。
    • 适用场景：元素个数相对固定，需要快速随机访问元素，并且不需要频繁的插入和删除元素时。
  • LinkedList
    • LinkedList是List接口的主要实现类，底层使用双向链表实现。
    • LinkedList随机访问元素开销是O(n)。
    • LinkedList使用下标插入和删除元素的性能是O(n)，使用Iterator插入和删除元素性能是O(1)。
    • 适用场景：只顺序访问元素，并使用迭代器进行插入或删除。

Map

  • HashTable
    • 线程安全，所有方法都是synchronized，性能低下
    • 访问元素的时间复杂度是O(1)，不允许null值或null键
  • HashMap
    • HashMap访问元素的时间复杂度是O(1)，允许null值和null键。
    • HashMap对迭代顺序绝对没有保证。当添加新元素时，顺序会完全改变。
    • 非线程安全
  • TreeMap
    • TreeMap使用红黑树（Red-black Truee）实现，访问，插入和删除元素开销都是O(log(n))，不允许null键，只允许null值。
    • TreeMap将根据键的“自然顺序”基于它们的compareTo方法（或外部提供的Comparator）进行迭代。
  • LinkedHashMap
    • LinkedHashMap访问元素的时间复杂度是O(1)，允许null值和null键。
    • LinkedHashMap迭代顺序和插入顺序一致。
  • ConcurrentHashMap
    • ConcurrentHashMap是线程安全的，不允许null值和null键。
    • ConcurrentHashMap实现原理：分段锁，分段加锁，分段CAS，并使用volatile来提高内部字段的可见性。默认使用16个分段，即其Concurrency Level是16。可以通过构造函数更改这个值。
    • ConcurrentHashMap访问元素性能比HashMap低。
  • ConcurrentSkipListMap
    • ConcurrentSkipListMap是线程安全
    • ConcurrentSkipListMap使用跳表（SkipList）实现，是sorted的，查询，插入和删除的时间复杂度都是O(log(n))。
    • ConcurrentSkipListMap性能比ConcurrentHashMap低。

Set

和Map相仿。

参考资料