Java常用的一些集合类

参考了Core Java卷一的第十三章 - 集合

一些常用的集合接口和类

Collection

　　集合类的基本接口就是Collection接口，有两个基本方法

public interface Collection<E> {
  boolean add(E element);
  Iterator<E> iterator();
  .....
}

　　iterator接口返回一个实现Iteator接口的对象，也就是一个迭代器，Iterator接口，注意没有add方法

public interface Iterator<E> {
  E next();
  boolean hasNext();
  void remove();
}

　　for each循环可以与任何实现Iterable接口的对象一起工作，Iterable接口：

1
2
3

public interface Iterable<E> {
  Iterator<E> iterator();
}

　　因此Collection接口拓展了Iterable接口，关于Iterator和Iterable的区别可以看看 stackoverflow上的一个回答

　　Iterator的remove方法将删除上次调用next方法返回的元素，例如：

1
2
3

Iterator<String> it = c.iterator();
String element = it.next();
it.remove();//删除了element

　　remove方法调用之前没有next方法调用被认为是不合法的。

Queue

　　队列接口指的是可以高效地实现在尾部添加元素，头部删除元素，遵循先进先出的规则，并能查找队列元素个数。Queue接口实现了Collection接口

interface Queue<E> {
  void add(E element);
  E remove();
  int size();
}

　　队列接口可以由数组实现，也可以由链表实现，在java中实现的数组实现的类为ArrayDeque，链表实现的类为LinkedList，这两个类都是实现了Deque接口，也就是说是双端队列

LinkedList

　　在Java中，所有链表实际上都是双向链接的double linked，链表是一个有序集合ordered collection，因此LinkedList的add方法将元素插到链表的最后。LinkedList的listIterator方法可以从前后两个方向便利链表中的元素，并可以添加或删除元素

ArrayList

　　ArrayList和Vector区别是：Vector的所有方法是同步的，线程安全的。ArrayList的所有方法是异步的。因此单线程从效率上推荐使用ArrayList

HashSet

　　自定义类需要负责实现这个类的hashCode方法。注意自己实现的hashCode方法，如果a.equals(b)为true，a与b必须有相同的散列码。

　　在Java中散列表用链表数组实现，每个链表称为bucket，想查找表中对象的位置，要先计算它的散列码。散列码的值对桶的数量取余，得到的就是桶的编号，如果要放入元素的桶已满，就会发生散列碰撞hash collision那么就需要将要放入的对象和已有的对象比较，看是否存在。如果散列表装的太满，就需要重新散列，装填因子load factor决定了什么时候散列表需要重新进行散列。例如load factor为0.75，当超过0.75时，buckets就要扩容1倍。在Java中的实现类为HashSet。

TreeSet

　　还有另外一种Set是TreeSet，这种Set内部会对字段排好序，实现机制是红黑树，因此向TreeSet中插入元素会比HashSet慢。但是插入元素重复性的判断还是要在数组或链表中判断快，因为基于树结构比较次数是logn的。

但是如果使用TreeSet，元素必须要实现Comparable接口或者是在构造TreeSet时，传入一个Comparator。从源码实现上，TreeSet实现了NavigableSet接口，NavigableSet接口继承了SortedSet接口，SortedSet接口继承了Set接口。

PriorityQueue

　　优先级队列的概念就不多解释了，使用优先级队列，同样，元素必须要实现Comparable接口或者在构造的时候传入一个Comparator

Map

　　Map提供了三种视图

1
2
3

Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K, V>> entrySet()

　　keySet()返回的Set既不是HashSet，也不是TreeSet，返回的是实现了Set接口的其它类，Set接口也是继承了Collection接口的。entrySet()视图是能同时返回key和value的，例如：

for (Map.Entry<String, Employee> entry : staff.entrySet())
{
   String k = entry.getKey();
   Employee v = entry.getValue();
   //do something with k, v
}

　　注意，如果在keySet视图上使用了remove方法，那么同时会将key和对应的value从map中移除，而且不能从keySet视图上增加元素，entrySet视图上也不允许添加。