Java容器类

Publish: 2018/7/25   

• Java

Java容器类

基本概念

Java容器类类库的用途是”保存对象”，并将其划分为两个不同的概念。

• Collection。一个独立元素的序列，这些元素都服从一条或多条规则。所有的Collection都可以用foreach语法遍历

  • List必须按照插入的顺序保持元素。
  • Set不能有重复元素。
  • Queue按照排队规则来确定对象产生的顺序(通常与它被插入的顺序相同)。

• Map。一组成对的”键值对”对象，允许你使用键来查找值。

Collection

Collection是描述所有序列容器的共性的根接口。java.util.AbstractCollection类提供了Collection的默认实现。包括List、Set和Queue。

List

List承诺可以将元素维护在特定的序列中。

有两种基本类型的List：

• ArrayList,查询快，增删慢。容量的增长策略为1.5倍。
  

  private void grow(int minCapacity) {
     int oldCapacity = elementData.length;
     // >>是右移运算符，它将数字减少到一半
     int newCapacity = oldCapacity + (oldCapacity >> 1);
     ...
     elementData = Arrays.copyOf(elementData, newCapacity);
  }
  

• LinkedList,查询慢，增删快。还添加了可以使其用作栈、队列或双端队列的方法。

  • getFirst()和element()完全一样，它们都返回列表的头(第一个元素)，而不是移除它，如果List为空，则抛出NoSuchElementException。peek()在列表为空时返回null。
  • removeFirst()与remove()完全一样，它们移除并返回列表的头，如果List为空，则抛出NoSuchElementException。poll()在列表为空时返回null。
  • addFirst()与add()和addLast()相同，都是讲某个元素插入到列表的尾(端)部。
  • removeLast()移除并返回列表的最后一个元素。

Set

Set不保存重复的元素。

• HashSet使用了散列。最快的查询速度。
• TreeSet保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口。
  
  如果要按照字母序排序，那么可以向TreeSet的构造器传入String.CASE_INSENTIVE_ORDER比较器。
• LinkedHashSet使用了散列和链表(链表用来维护元素的插入顺序)。以插入顺序保存元素。

Queue

队列是一个典型的先进先出(FIFO)的容器。Deque双端队列接口继承Queue接口。

• LinkedList实现了Deque接口。
• PriorityQueue非并发的优先队列。
• ConcurrentLinkedQueue先进先出队列。
• BlockingQueue扩展了Queue，增加了可阻塞的插入和获取等操作。
  • LinkedBlockQueue
  • ArrayBlockingQueue
  • PriorityBlockingQueue按优先级排序的队列(元素实现Comparable)。
  • SynchronousQueue维护一组线程，这些线程在等待着把元素加入或移出队列，从而降低了将数据从生产者移动到消费者的延迟。

Map

• HashMap基于散列表的实现。插入和查询”键值对”的开销是固定的。key、value值均可为null。
• TreeSet基于红-黑树的实现。次序由Comparable或Comparator决定，没有HashMap快。
• LinkedHashMap保持元素插入的顺序，但也通过散列提供了快速访问能力。只比HashMap慢一点；而在迭代访问时反而更快，因为使用了链表维护内部次序。
• ConcurrentHashMap一种线程安全的Map。