Java Collections

Java集合类如图所示

1. Iterator

迭代器接口，是一种设计模式，用来遍历序列对象。

1.1 ListIterotr

可双向遍历。

2. Collection

• 最基本的集合接口，继承于Iterator，自身不被直接继承，两个子接口List和Set

​

2.1 List

• 有序Collection
• 提供基于索引的随机访问，内容可重复。
• 实现了ListIterator接口，可向前遍历

2.1.1 ArrayList

• 可变数组，允许随机访问
• 允许含null，只能存对象
• 非同步，线程不安全

• 有容量Capacity，每次扩充原来的一半。创建ArrayList时最好指定Capacity，提高插入效率。存在空间浪费。

  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

​

2.1.2 LinkedList

• 可变链表，允许随机访问
• 允许含null
• 可双向遍历，头尾操作快，可以用作Stack、Queue、双向Queue
• 非同步，线程不安全
• 比ArrayList更占空间，每个节点存储两个引用，分别指向前后元素

2.1.3 Vector

• 与ArrayList类似。

• Vector很多方法由synchronized修饰，是同步的，线程安全。

  • 如果遍历Vector过程中，另一个线程改变了Vector，则会报错。

• 扩充容量为原来的一倍，并且可以自己设置扩充因子

  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                       capacityIncrement : oldCapacity);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      elementData = Arrays.copyOf(elementData, newCapacity);
  }

2.1.4 Stack

• 继承于Vector，Vector的堆栈实现，包括empty、peek、pop、push、search等方法。

2.2 Set

• 成员不可重复
• 可以有序

2.2.1 HashSet

• 基于HashMap，key存值，value存系统默认的Object对象，可快速查找
• 不保证有序，非同步
• 成员为Object子类对象
• 可以放一个null

2.2.2 TreeSet

• 基于TreeMap，默认有序
• 自定义对象要实现Comparable接口才能放入TreeSet

2.2.3 LinkedHashSet

• 在HashSet基础上，维护一个链表来记录插入顺序。这使得它访问顺序比HashSet好，但插入顺序相比稍差。

3. Map

键值对，键不能重复，快速查找

3.1 HashMap

• 可含有一个key为null的键值对
• 非同步，若让HashMap同步，使用Collections.synchorniezMap()，
• 去除了contains方法
• 扩容为2的幂

3.2 TreeMap

• 基于红黑树，有序
• 遍历value时尽量使用entrySet遍历，这样防止二次查找（keySet找value极慢）
• 可以返回一个子树

3.3 LinkedHashMap

• HashMap子类，于LinkedHashSet类似，额外添加双向链表来保证顺序