Java集合教程之Collection实例详解

public class Vector<E>
 extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 /**
  * The array buffer into which the components of the vector are
  * stored.
  */
 protected Object[] elementData;

 /**
  * The number of valid components in this {@code Vector} object.
  */
 protected int elementCount;

 /**
  * The amount by which the capacity of the vector is automatically
  * incremented when its size becomes greater than its capacity. If
  * the capacity increment is less than or equal to zero, the capacity
  * of the vector is doubled each time it needs to grow.
  */
 protected int capacityIncrement;

 public Vector() {
  this(10);
 }

 // 添加元素
 public synchronized boolean add(E e) {
  modCount++;
  ensureCapacityHelper(elementCount + 1);
  elementData[elementCount++] = e;
  return true;
 }

 // 删除元素
 public synchronized E remove(int index) {
  modCount++;
  if (index >= elementCount)
   throw new ArrayIndexOutOfBoundsException(index);
  E oldValue = elementData(index);

  int numMoved = elementCount - index - 1;
  if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
  elementData[--elementCount] = null; // Let gc do its work

  return oldValue;
 }

 // 修改元素
 public synchronized E set(int index, E element) {
  if (index >= elementCount)
   throw new ArrayIndexOutOfBoundsException(index);

  E oldValue = elementData(index);
  elementData[index] = element;
  return oldValue;
 }
 // 查找元素
 public synchronized E get(int index) {
  if (index >= elementCount)
   throw new ArrayIndexOutOfBoundsException(index);

  return elementData(index);
 }
...

public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 private static final long serialVersionUID = 8683452581122892189L;

 /**
  * Default initial capacity.
  */
 private static final int DEFAULT_CAPACITY = 10;

 /**
  * Shared empty array instance used for empty instances.
  */
 private static final Object[] EMPTY_ELEMENTDATA = {};

 /**
  * The array buffer into which the elements of the ArrayList are stored.
  * DEFAULT_CAPACITY when the first element is added.
  */
 private transient Object[] elementData;

 /**
  * Constructs an empty list with an initial capacity of ten.
  */
 public ArrayList() {
  super();
  this.elementData = EMPTY_ELEMENTDATA;
 }

 // 添加元素
 public boolean add(E e) {
  ensureCapacityInternal(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
 }

 // 增加数组的长度
 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);
 }
...

public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 transient int size = 0;

 /**
  * Pointer to first node.
  */
 transient Node<E> first;

 /**
  * Pointer to last node.
  */
 transient Node<E> last;

 /**
  * Constructs an empty list.
  */
 public LinkedList() {
 }

 // 每一个元素即为一个节点，节点的结构如下（这是一个内部类啊）
 private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;

  Node(Node<E> prev, E element, Node<E> next) {
   this.item = element;
   this.next = next;
   this.prev = prev;
  }
 }

 // 添加元素
 public boolean add(E e) {
  linkLast(e);
  return true;
 }

 void linkLast(E e) {
  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  if (l == null)
   first = newNode;
  else
   l.next = newNode;
  size++;
  modCount++;
 }

 // 删除某个节点的逻辑
 E unlink(Node<E> x) {
  // assert x != null;
  final E element = x.item;
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;

  if (prev == null) {
   first = next;
  } else {
   prev.next = next;
   x.prev = null;
  }

  if (next == null) {
   last = prev;
  } else {
   next.prev = prev;
   x.next = null;
  }

  x.item = null;
  size--;
  modCount++;
  return element;
 }
...

public class HashSet<E>
 extends AbstractSet<E>
 implements Set<E>, Cloneable, java.io.Serializable
{
 private transient HashMap<E,Object> map;

 // Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();

 /**
  * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  * default initial capacity (16) and load factor (0.75).
  */
 public HashSet() {
  map = new HashMap<>();
 }

 // 添加元素，其实就是像 Map 中添加主键，所以添加的元素不能重复
 public boolean add(E e) {
  return map.put(e, PRESENT)==null;
 }

 // 实现 Iterable 接口中的 Iterator 方法。
 public Iterator<E> iterator() {
  return map.keySet().iterator();
 }
...

public class TreeSet<E> extends AbstractSet<E>
 implements NavigableSet<E>, Cloneable, java.io.Serializable
{
 /**
  * The backing map.
  */
 private transient NavigableMap<E,Object> m;

 // Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();

 /**
  * Constructs a set backed by the specified navigable map.
  */
 TreeSet(NavigableMap<E,Object> m) {
  this.m = m;
 }

 /**
  * Constructs a new, empty tree set, sorted according to the
  * natural ordering of its elements. All elements inserted into
  * the set must implement the Comparable interface.
  */
 public TreeSet() {
  this(new TreeMap<E,Object>());
 }

 /**
  * Constructs a new, empty tree set, sorted according to the specified
  * comparator. All elements inserted into the set must be mutually
  * comparable by the specified comparator
  * If the Comparable natural ordering of the elements will be used.
  */
 public TreeSet(Comparator<? super E> comparator) {
  this(new TreeMap<>(comparator));
 }
 
 // 添加元素方法
 public boolean add(E e) {
  return m.put(e, PRESENT)==null;
 } 
...

... // 这是 TreeMap 的 put 方法的节选，为了看到比较的过程。
 public V put(K key, V value) {
 ...
  // split comparator and comparable paths
  Comparator<? super K> cpr = comparator;
  if (cpr != null) {
   do {
    parent = t;
    cmp = cpr.compare(key, t.key);
    if (cmp < 0)
     t = t.left;
    else if (cmp > 0)
     t = t.right;
    else
     return t.setValue(value);
   } while (t != null);
  }
  else {
   if (key == null)
    throw new NullPointerException();
   Comparable<? super K> k = (Comparable<? super K>) key;
   do {
    parent = t;
    cmp = k.compareTo(t.key);
    if (cmp < 0)
     t = t.left;
    else if (cmp > 0)
     t = t.right;
    else
     return t.setValue(value);
   } while (t != null);
  }
 ...
 }

public class Person implements Comparable<Person>{

 public String name;
 public Integer age;

 public Person(String name,Integer age) {
  this.name = name;
  this.age = age;
 }
 /* 自定义的比较的逻辑：
  *  首先按照对象的 name 属性排序
  *  其次按照 age 属性排序
  * 方法的返回值为 0 ，大于 0，小于 0 ，分别对应于 相等，大于，和小于
  */
 @Override
 public int compareTo(Person o) {
  int i = this.name.compareTo(o.name);
  if(i == 0){
   return this.age.compareTo(o.age);
  }else {
   return i;
  }
 }
 @Override
 public String toString() {
  return "[Person] name:"+this.name+" age:"+this.age;
 }
}

 // 以下是测试代码
 public static void main(String[] args) {
  TreeSet<Person> set = new TreeSet<>();
  set.add(new Person("AJK923",20));
  set.add(new Person("BJK923",20));
  set.add(new Person("AJK923",21));
  set.add(new Person("BJK923",21));

  for (Person person : set) {
   System.out.println(person.toString());
  }
  /*
  [Person] name:AJK923 age:20
  [Person] name:AJK923 age:21
  [Person] name:BJK923 age:20
  [Person] name:BJK923 age:21
  */
    
  ----以下为定制排序的部分----匿名内部类实现 Comparator 接口----  
  TreeSet<Person> set2 = new TreeSet<>(new Comparator<Person>() {
   @Override
   public int compare(Person o1, Person o2) {
    int i = o1.age.compareTo(o2.age);
    if(i == 0){
     return o1.name.compareTo(o2.name);
    }else {
     return i;
    }
   }
  });

  set2.add(new Person("AJK923",20));
  set2.add(new Person("BJK923",20));
  set2.add(new Person("AJK923",21));
  set2.add(new Person("BJK923",21));

  for (Person person : set2) {
   System.out.println(person.toString());
  }
  /*
   [Person] name:AJK923 age:20
   [Person] name:BJK923 age:20
   [Person] name:AJK923 age:21
   [Person] name:BJK923 age:21
   */
 }

private class Itr implements Iterator<E> {
  int cursor;  // index of next element to return
  int lastRet = -1; // index of last element returned; -1 if no such
  int expectedModCount = modCount;

  public boolean hasNext() {
   return cursor != size;
  }

  @SuppressWarnings("unchecked")
  public E next() {
   checkForComodification();
   int i = cursor;
   if (i >= size)
    throw new NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
    throw new ConcurrentModificationException();
   cursor = i + 1;
   return (E) elementData[lastRet = i];
  }

  public void remove() {
   if (lastRet < 0)
    throw new IllegalStateException();
   checkForComodification();

   try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
   }
  }

  final void checkForComodification() {
   if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  }
 }

  public static void main(String[] args) {

  List<Integer> list = new ArrayList<>(); 
  list.add(1);
  list.add(2);
  list.add(3);

  Iterator<Integer> it = list.iterator();
  while (it.hasNext()) {
   Integer i = it.next();
   System.out.println(i);
  }
 }