Map
HashMap
HashMap 的初始容量为 16. 扩容因子 默认 0.75 , 可以改. 扩容时是当前容量翻倍即: capacity*2. 查询效率 jdk 1.7 为 O(N), jdk 1.8 为 O(lgN)
HashTable
初始容量为 11. 扩容因子 默认 0.75 , 可以改. 扩容时是容量翻倍 + 1 即: capacity*2+1.
ConcurrentHashMap
初始容量为 16. 扩容因子 默认 0.75 , 不可以改. 扩容时是当前容量翻倍即: capacity*2
List
Arraylist
线程不安全. 初始容量是 10. 扩容倍数是 1.5 + 1, 即初始为 10, 扩容后为 16.
Vector
线程安全. 初始容量为 10, 一次扩容后容量为 20
Set
HashSet
线程不安全, 存取速度快. 初始容量为 16, 加载因子为 0.75
TreeSet
线程不安全, 底层是红黑树
EnumSet
线程不安全
HashSet 的性能总是比 TreeSet 好 (特别是最常用的添加, 查询元素等操作), 因为 TreeSet 需要额外的红黑树算法来维护集合元素的次序. 只有当需要一个保持排序的 Set 时, 使用 TreeSet, 其他情况都应该使用 HashSet.
ArrayList 和 LinkedList 时间复杂度
注: 1, 在 add(index, E) 中, ArrayList 和 LinkedList 的 查询时间复杂性 和 插入时间复杂度的区别
2, 在 remove(index, E) 中, ArrayList 和 LinkedList 的 查询时间复杂性 和 插入时间复杂度的区别
3,get(index), ArrayList 和 LinkedList 的 查询时间复杂性
ArrayList 是线性表 (数组)
get() 直接读取第几个下标, 复杂度 O(1)
add(E) 添加元素, 直接在后面添加, 复杂度 O(1)
add(index, E) 添加元素, 在第几个元素后面插入, 后面的元素需要向后移动, 复杂度 O(n)
remove() 删除元素, 后面的元素需要逐个移动, 复杂度 O(n)
LinkedList 是链表的操作
get() 获取第几个元素, 依次遍历, 复杂度 O(n)
add(E) 添加到末尾, 复杂度 O(1)
add(index, E) 添加第几个元素后, 需要先查找到第几个元素, 直接指针指向操作, 复杂度 O(n)
remove() 删除元素, 直接指针指向操作, 复杂度 O(1)
集合扩容
来源: http://www.bubuko.com/infodetail-3683771.html