List, Set, Queue, Map 四者的区别

集合是否顺序是否重复
List有序可
Set无序不可
Queue有序(按特定规则实现顺序)可
Mapkey无序不可重复
Mapvalue无序可

集合框架底层数据结构总结

+++ 点击展开/隐藏

List

  • ArrayList: Object[] 数组
  • Vector: Object数组
  • LinkedList: 双向链表(Jdk1.6之前循环链表,Jdk1.7取消了循环)

Set

  • HashSet(无序,唯一): 基于HashMap实现,底层采用HashMap保存元素
  • LinkedHashSet(有序,唯一): 是HashSet的子类,内部通过LinkedHashMap实现
  • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树)

Queue

  • PriorityQueue: Objecet实现二叉堆
  • ArrayQueue: Object数组 + 双指针

Map

  • HashMap:
    • Jdk1.8之前: 数组+链表, 数组是主体,链表是为了解决哈希冲突(拉链法)
    • Jdk1.8以后: 链表长度大于阈值(默认8),将链表转换红黑树以减少搜索时间
  • LinkedHashMap: 继承HashMap,在基础结构之上增加双向链表,保持键值对的插入顺序
  • HashTable: 数组+链表, 数组是主体,链表是为了解决哈希冲突
  • TreeMap: 红黑树(自平衡的二叉树)

+++

ArrayList 和 Vector 的区别

  • ArrayList是List的主要实现类,底层使用Object[]数组,适用于频繁的查找工作,线程不安全.
  • Vector是List的古老实现类,底层使用Object[]数组,线程安全的.

ArrayList 与 LinkedList 区别

+++ 点击展开/隐藏

  • 线程是否安全: ArrayList和LinkedList都是不同步的,不保证线程安全.
  • 底层数据结构: ArrayList底层是Object[]数组,LinkedList底层使用的是双向链表(Jdk1.6为循环链表,Jdk1.7之后取消了循环)
  • 插入\删除是否受元素位置影响:
    • ArrayList采用数组储存,插入和删除元素的时间复杂度受元素位置的影响.
      • 追加列表末尾: 时间复杂度O(1)
      • 指定位置i插入/删除元素: 时间复杂度 O(n-1)
    • LinkedList 采用链表储存
      • 头尾插入/删除: 不受元素位置影响
      • 指定位置i插入/删除元素: 时间复杂度 O(n)
  • 快速随机访问 (通过序号快速获取元素对象get( int index ) ):
    • ArrayList 支持
    • LinkedList 不支持
  • 内存占用:
    • ArrayList: 内存占用主要体现在list列表的结尾会预留一定的空间
    • LinkedList: 每一个元素都要消耗比ArrayList更多的空间

补充内容:

双向链表

双向循环链表

+++

ArrayList 的扩容机制

⽐较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

接口实现类集合顺序元素重复线程安全数据结构应用场景
SetHashSet无序元素唯一不安全哈希表（基于 HashMap 实现）不需要保证元素插⼊和取出顺序的场景
LinkedHashSet有序链表和哈希表( 满足FIFO)于保证元素的插⼊和取出顺序满⾜ FIFO 的场景
TreeSet有序(支持⾃然排序和定制排序)红黑树⽤于⽀持对元素⾃定义排序规则的场景

Queue 与 Deque 的区别

略过

HashMap和HashTable区别

HashMap和Hashtable的区别？HashMap和HashSet区别？HashMap和TreeMap区别？

// todo