Java Collection

下图是Java Collection的框架图。

Java Collection面试常见考点总结

ArrayList 和 Vector的区别是什么?

Vector是线程安全的； ArrayList是非线程安全的.
- 可以通过调用 Colections.synchronizedList 将 ArrayList 变为线程安全的。

扩大容量。ArrayList 和 Vector 底部都是用数组来存储数据，因此长度是固定的。当存储的数据达到了固定的长度后，需要扩充容量。

ArrayList 是直接在原有容量上再扩充一半。源码为：

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);
}

Vector 默认是在原有容量的基础上再扩充1倍。 Vector 也可以通过构造函数自定义扩充容量的大小。源码为：

public Vector(int initialCapacity, int capacityIncrement) {
  super();
  if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal Capacity: "+
                                         initialCapacity);
  this.elementData = new Object[initialCapacity];
  this.capacityIncrement = capacityIncrement;
}

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);
}

LinkedList 和 ArrayList的区别

ArrayList 接口继承了 AbstractList 抽象类; 而 LinkedList 继承了 AbstractSequentialList(PS: AbstractSequentialList 抽象类 AbstractList) 抽象类；
ArrayList 底部实现为容量可扩充的数组；而 LinkedList 的底部实现为双向链表；
For LinkedList :
- get(int index) worst case is O(n/2)
- add(E element) is O(1)
- add(int index, E element) worst case is O(n/2) when index = 0 is O(1) main benefit of LinkedList< E >
- remove(index) is O(n/2)
- Iterator.remove() is O(1) main benefit of LinkedList< E >
- ListIterator.add(E element) is O(1) main benefit of LinkedList< E >
For ArrayList :
- get(int index) is O(1) main benefit of LinkedList< E >
- add(E elements) worst case is O(n)
- remove(int index) worst case is O(n)
- Iterator.remove() worst case is O(n)
- ListIterator.add(E element) worst case is O(n)

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don’t have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

Comparable 和 Comparator 的区别

Comparable 是定义在 java.lang 中的接口； Comparator 是定义在 java.util 中的接口。
Comparable 可以说是内部比较器。如果一个类实现了 Comparable 接口，则意味着该类支持排序。该类的对象可以用作有序映射或有序集合，无需指定比较器。
1
2
3
public int compareTo(E o) {
return this.attr == o.attr;
}
Comparator 可以说是外部比较器。如果需要控制某个类的次序，但是该类本身不支持排序。我们可以新建一个类，实现Comparator接口，作为比较器来进行排序。
1
2
3
public int compare(E o1, E o2) {
return o1.attr == o2.attr;
}

参考资料

HashMap 和 HashTable

相同点 :
- HashMap 和 HashTable 都是以 key-value的形式进行存储。
不同点 :
- HashMap 继承自抽象类 AbstractMap；而 HashTable 继承自抽象类 java.util.Dictionary 并实现了接口 Map 。
- HashTable 是 synchronize 的，所以是线程安全的。而 HashMap 是非线程安全的；
- HashMap 的 key 和 value 都可以为 null 。HashTable 的 key 和 value 都不能为 null 。
  原因是：HashTable 的 key 必须实现了 hashCode 和 equal 函数。 HashMap 是对 HashTable 的一个提高版。

Enumeration 和 Iterator

相同点 :
- Enumeration 和 Iterator 都是 java.util 中的接口；用来遍历 Collection 对象中的元素。
不同点 :
- Enumeration 只能遍历 Collection 对象中的元素，没法删除；而，Iterator 提供了 remove() 函数；
- Enumeration 是遗留接口，用来遍历 Vector (PS : Vector也提供了用Iterator来遍历的函数), HashTable (PS : 只提供了Enumeration来进行遍历), Stack ； Interator 用来遍历 collection 框架中的大部分类，比如：ArrayList , LinkedList , HashSet , TreeSet 等等。
- Iterator 接口是 Fail-Fast 的；而， Enumeration 是 Fail-Safe 的。
  Fail-Fast 是当遍历 collection 时，如果也试图改变 collection 的结构 (新增 add() 或删除 delete())，则会马上抛出ConcurrentModificationException。比如，以下代码就可能抛出异常：
  1
  2
  3
  4
  5
  Iterator<Integer> it = list.iterator();
  while (it.hasNext()) {
  Integer integer = (Integer) it.next();
  list.add(8457);
  }
Fail-Safe 通过 clone collection 再遍历，所以即使进行了修改，也不会改动原始数据，则不会抛出错误。

Iterable 和 Iterator 的区别

Iterator 是定义在 java.util 中的接口；Iterable 是定义在 java.lang 中的接口。
Iterable 定义了函数 iterator() 和 foreach() 。因此，实现了Iterable 的类可以用 “foreach” 循环。Iterator 是用来管理 iteration 。它包含了迭代状态，包括当前元素、判断是否有下一个元素，以及如何获取下一个元素。
Iterable 可以通过 iterator() 函数重复的遍历 collection 。

HashMap 和 LinkedHashMap 和 TreeMap 之间的区别

HashMap O(1) 复杂度的查找、插入、删除
LinkedHashMap O(1) 复杂度的查找、插入、删除。LinkedHashMap 内部采用的结构是 HashTable 和双向的 LinkedList。双向的 LinkedList 用来维护插入顺序。
TreeMap O(log(n)) 复杂度的查找、插入、删除。TreeMap 内部采用的结构是红黑树。TreeMap 会按照 key 的排序存储。key 需要实现 Comparable 接口，或者通过构造函数指定 Comparator 。
HashMap 和 LinkedHashMap 的 key 和 value 都可以为 null ，但至多只允许有一条记录的 key 为 null；而 TreeMap 的 key 不能为空，因为 TreeMap 要按 key 进行排序。

未完待续