JAVA 数据结构接口-对比分析

JAVA 推荐面向接口编程，这样在代码重构时，只需替换掉具体的实现类而不影响现有的代码，因此，当我们在考虑数据结构时，第一步就是要选出一个合适的接口

JAVA 集合框架接口（继承体系）

哈希接口（散列表结构）

集合接口

Map 介绍

• Map

  • 散列表（哈希表），通过 Key 对象的哈希值来决定 Value 存储位置，但判断 Key 时需要同时保证 hashCode() 和 equals()
    
    • 插入和查找效率极高
    • 虽然可以使用 keySet()、values()、entrySet() 进行数据遍历，但由于哈希表结构较复杂（底层采用数组+链表，且表元素为Key-Value类型），因此遍历的效率比不上 List、Queue

• SortedMap

  • 在 Map 的基础上进一步提供了 Key 自动排序的特性（是 Key 不是 Value）
    
    • 用于范围查询和升序遍历，建议使用其子接口 NavigableMap，提供了更细致的操作
    • （SortedMap 是 JDK1.2 的产物，而且只提供了内部实现类，一般不用于直接编程，而 JDK1.6 的 NavigableMap 完美继承了 SortedMap，且提供了实现类 TreeMap 用于应用开发）

• NavigableMap

  • 扩展自 SortedMap，新增了许多更细致更强大的方法
    
    • 提供了许多方法用于数据定位，而非遍历，例如：floorKey(key) 返回小于等于给定key的最大key
    • descendingMap() 和 descendingKeySet() 可实现降序遍历
    • subMap()、headMap()、tailMap() 等范围查询可指定”是否包含边界值”
    • firstEntry() 返回第一个元素，pollFirstEntry() 弹出第一个元素（类似出栈）

• ConcurrentMap

  • 高性能的线程安全的 Map，保证原子操作
    
    • ConcurrentMap 接口实现的类是新设计的类（大量采用了 CAS 原语），比旧版的 Map 接口实现的线程安全类 HashTable（采用锁）拥有更高的性能

• ConcurrentNavigableMap

  • 扩展自 ConcurrentMap 和 NavigableMap（高性能并发安全 + Key自动排序）

Set 介绍

• Set

  • 集合结构，不包含重复元素，最多包含一个 null 元素
    
    • 计算交集、差集、并集等（接受Collection接口类型，即允许与List、Queue等进行计算）

• SortedSet

  • 在 Set 的基础上进一步提供了集合元素自动排序的特性，不建议插入 null 元素
    
    • 用于范围查询和升序遍历，建议使用其子接口 NavigableSet，理由与 SortedMap 类似

• NavigableSet

  • 扩展自 SortedSet，新增了许多更细致更强大的方法
    
    • 提供了许多方法用于数据定位，而非遍历，例如：floor(e) 返回小于等于给定元素的最大元素
    • descendingSet() 和 descendingIterator() 可实现降序遍历
    • subSet()、headSet()、tailSet() 等范围查询可指定”是否包含边界值”
    • first() 返回第一个元素，pollFirst() 弹出第一个元素（类似出栈）

List 介绍

• List
  
  • 列表，支持下标的随机访问，底层一般基于数组（顺序存储结构）或链表（链式存储结构）
    
    • 非常基础的线性结构，可以灵活地实现各种功能

Queue 介绍

JAVA 中，队列的操作方法一般分为两类：①在失败时抛出异常，②在失败时返回特殊值，例如 null、false（因此推荐不要插入 null 元素）

• Queue

  • 队列，基于先进先出（FIFO）的处理方式
    
    • offer() 和 add() 从队列尾部插入元素
    • peek() 和 element() 从队列头部取出元素
    • poll() 和 remove() 从队列头部弹出元素（类似出栈）

• Deque

  • 扩展自 Queue 的双向队列，不仅提供了队列的先进先出（FIFO），还整合了栈的后进先出（LIFO）
    
    • 比 Queue 更为灵活，允许两端插入和弹出元素
    • 替代了传统的 Stack 类（提供了入栈、出栈操作），如果需要线程安全的栈类，请使用其派生接口 BlockingDeque
    • removeFirstOccurrence(e) 删除第一个出现的目标元素，removeLastOccurrence(e) 删除最后一个出现的

• BlockingQueue

  • 高性能的线程安全的队列（使用内部锁或其他方式实现高效率的并发控制），同时支持阻塞操作，主要用于生产者/消费者队列
    
    • 在原有两种类型的基础上又添加了两种新类型操作：①在失败时抛出异常，②在失败时返回特殊值，例如 null、false，③当前线程挂起（阻塞）等待，直至操作成功，④当前线程只挂起一段时间，超时后退出
      
      • add()、offer()、put()、offer() 插入一个元素，其中 put() 阻塞等待，offer() 最多等待一段时间
      • take()、poll() 弹出一个元素，其中 take() 阻塞等待，poll() 计时等待
    • 不接受 null 元素
    • 虽然支持集合操作，例如 remove(x)，但效率不高

• BlockingDeque

  • 扩展自 Deque 和 BlockingQueue（高性能并发安全 + 双端队列）

• TransferQueue

  • 扩展自 BlockingQueue，不仅支持生产者的货物阻塞等待入队，还允许支持后续阶段的阻塞等待消费，新增五个新操作
    
    • tryTransfer(e)，如果存在消费者在阻塞等待，返回 true；否则 false 且货物不入队
    • transfer()，阻塞等待，直至该元素被消费掉（两阶段：阻塞等待货物入队 + 阻塞等待货物被消费）
    • tryTransfer(E e, long timeout, TimeUnit unit)，如果存在消费者在阻塞等待，返回 true；否则计时等待该元素被消费掉，超时后 false，同时移除该元素
    • hasWaitingConsumer() 检测是否存在阻塞等待的消费者
    • getWaitingConsumerCount() 检测阻塞等待的消费者的数量