您的位置: 首页  >  文章  >  集合之间的关系

集合之间的关系

分类: 文章 • 2024-07-12 11:49:22

集合

  • List，Set,Map都是接口，前两个继承Collection接口，Map为独立的接口
  • Set下HashSet，LinkedHashSet，TreeSet
  • List下有ArrayList，Vector，LinkedList，Stack
  • Map下有LinkedHashMap，HashMap，TreeMap
  • Hashtable继承于dictionary
  • 有PriorityQueue类
  • Collection接口下还有个Queue接口
  • Queue接口与list,Set同一级别，都是继承了Collection接口。
  • SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。

关系图：

集合之间的关系

集合之间的关系

Connection接口：

  1. List 有序，可重复
  • ArrayList
    • 优点:底层数据结构是数组，查询快，增删慢，效率高。
    • 缺点：线程不安全
  • Vector
    • 优点：底层数据结构是数组，查询快，增删慢，线程安全
    • 缺点：效率低
  • LinkedList
    • 优点：底层数据结构是链表，查询慢，删除快，效率高
    • 缺点：线程不安全
  • Stack
    • 特性：先进后出，是数组实现的，是继承于Vector
      • 常用API：
        boolean empty()
        synchronized E peek() 执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
        synchronized E pop()执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。
        E push(E object) 执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。
        synchronized int search(Object o)
        因为继承与Vector所以Vector有的方法他也有。
  1. Set 无序，唯一
  • HashSet
    • 底层数据结构是哈希表。(无序，唯一)
    • 如何来保证元素唯一性
    • 依赖两个方法：hashCode()和equals()
  • LinkedhashSet
    • 底层数据结构是链表和哈希表。(FIFO插入有序，唯一)
      1. 链表保证了元素的有序
      2. 哈希表保证了元素的唯一
  • TreeSet
    • 底层数据结构是红黑树。(唯一，有序)
    • 如何保证元素排序的
      1. 自然排序
      2. 比较器排序
    • 如何保证元素的唯一性
      1. 根据比较的返回值是否为0来决定

Map接口：

Map接口有三个比较重要的实现类，分别是HashMap，TreeMap和HashTable。

  1. TreeMap是有序的，HashMap和HashTable是无序的。

    • HashTable和HashMap二者的区别
      1. HashTable的方法是同步的，HashMap的方法不是同步的
      2. HashTable是线程安全的，HashMa不是线程安全的。
      3. HashMap的效率较高，HashTable的效率较低
      4. 对同步性和代码兼容性没有要求，使用HashMap。
      5. HashTable的所有public方法都是被synchronized关键字修饰的
      6. HashTable不准许null值，HashMap准许null值
      7. HashTable的父类是Dictionary，HashMap的父类是AbstractMap

  2. 线程安全

    • ConcurrentHashMap 和 HashTable

    ConcurrentHashMap和HashTable都是线程安全的集合，它们的不同主要是加锁粒度上的不同。HashTable的加锁方法是给每个方法加上synchronized关键字，这样锁住的是整个Table对象。而ConcurrentHashMap是更细粒度的加锁
    在JDK1.8之前，ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响
    JDK1.8对此做了进一步的改进，它取消了Segment字段，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率

Collection集合的灵活运用

  • 元素唯一

    • Set

      • 有序

        • TreeSet/LinkedHashSet
        • 无序
          • HashSet
        • 如果要用Set但是不知道用那个Set就用HashSet

    • 元素不唯一

      • List

        • 线程安全
          • Vector
        • 线程不安全
          • ArrayList或者LinkedList
        • 查询多
          • ArrayList
        • 增删多
          • LinkedList
        • 如果List不知道用那个List，就用ArrayList线程安全就用Vector

    • TreeSet, LinkedHashSet and HashSet 的区别

      • 介绍
        • TreeSet, LinkedHashSet and HashSet 在java中都是实现Set的数据结构
        • TreeSet的主要功能用于排序
        • LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
        • HashSet只是通用的存储数据的集合
      • 相同点
        • 三者都不是线程安全的，如果要使用线程安全可以Collections.synchronizedSet()
        • 因为三者都实现Set interface，所以三者都不包含duplicate elements
      • 不相同
        • HashSet插入数据最快，其次LinkHashSet，最慢的是TreeSet因为内部实现排序
        • HashSet不保证有序，LinkHashSet保证FIFO即按插入顺序排序，TreeSet安装内部实现排序，也可以自定义排序规则
        • HashSet和LinkHashSet允许存在null数据，但是TreeSet中插入null数据时会报NullPointerException

* 注意：

  1. 排序可以是实现Comparable接口重写Compareto方法
  2. 单独创建一个比较类，继承Comparator接口重写Comparator接口中的Compare方法

Queue的实现

  1. 没有实现的阻塞接口的LinkedList： 实现了java.util.Queue接口和java.util.AbstractQueue接口内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue

    1. PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定。
    2. ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大 小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

  2. 实现阻塞接口的：

    1. java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。
    2. 五个队列所提供的各有不同：
      1. ArrayBlockingQueue ：一个由数组支持的有界队列。
      2. LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
      3. PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
      4. DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
      5. SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

    下表显示了jdk1.5中的阻塞队列的操作：
    　　add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
    　　remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    　　element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
    　　offer 添加一个元素并返回true 如果队列已满，则返回false
    　　poll 移除并返问队列头部的元素 如果队列为空，则返回null
    　　peek 返回队列头部的元素 如果队列为空，则返回null
    　　put 添加一个元素 如果队列满，则阻塞
    　　take 移除并返回队列头部的元素 如果队列为空，则阻塞
    remove、element、offer 、poll、peek 其实是属于Queue接口。

​

相关推荐