public interface Collection<E> extends Iterable<E>{
  int size();
  boolean isEmpty();
  void clear();
  boolean contains();
  boolean add();
  boolean remove();
  Iterator<E> iterator();
}

实现一个Collection，在ArrayList中实现了List接口,而List接口继承了Collection接口，所以可以用下面方式来实现一个Collection集合，然后可以用上述方法。
Collection<String> c = new ArrayList<String>();

List接口是Collection的子接口，用于定义线性表数据结构。可以将List理解为存放对象的动态数组，只不过其元素个数可以动态的增加或者减少。List接口两个常见的实现类是ArrayList和LinkedList。分别用动态数组和链表的方式实现了List接口。（这两种实现方式在文末附上）

public interface List<E> extends Collection<E> {
Anytype get(int idx);
  Anytype set(int idx, Anytype newVal);
  void add(int idx, Anytype x);
  void remove(int idx);
  Iterator<Integer> listIterator(int pos);
}

重要方法：

List<E> list = new ArrayList<>();
E get(int idx) 获取集合中指定下标对应的元素
E set(int idx,E element) 给定下标上的元素，并将原来的元素返回
E add(int idx,E element) 在给定下标出添加元素，原位置及以后的元素都后移
E remove(int idx) 删除给定位置的元素，并将被删除的元素返回
List<E> sublist(int formIdx,int toIdx)获得List中的子序列（前包括，后不包括）

Object[] toArray()
<T> [] t  =  toArray(T[] a) 
String [] strArr = list.toArray(new String []()); 将List转成数组，第二种比较常用

static List<T> list = asList<T[]a>
String [] strArr = {"a","b","c"};
  List<String> list = Arrays.asList(strArr);将数组转换成list。

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

迭代器用于遍历集合元素。获取迭代器，可以使用Collection中的方法，Iterator iterator()。具体用法如下代码。：

Set<String> set = new HashSet<String>();
  set.add("a");
  set.add("b")；
  //建立一个指向set的迭代器
  Iterator<String> it = set.iterator();
  while(it.hasNext()){ 
   String str = it.next();
   System.out.println(str);
   //删除元素
   it.remove();
  }
 System.out.println(set);

注意：迭代器在遍历元素时，不能通过集合的remove方法来删除元素，否则会抛出异常。但是可以通过迭代器自身提供的方法的remove方法来删除，具体实现方式在LinkedList的实现代码中有。 

Collections操作集是为collection及其子接口、类提供操作方法的一个操作集。（几乎用不到）但是有sort()方法比较重要。
void sort(List<T> list);
直接使用该方法是自然排序，也可以使用Comparable 和Comparator。
Collection中的sort()能够排序的主要原因是，传入的集合元素都是Comparable接口的实现类，该接口表示子类是可以比较的，因为实现该接口重写抽象方法 int compareTo(T t);
该方法用于当前对象与给定对象进行比较：
 若当前对象大于给定对象，则返回值应为大于0的整数
 若当前对象小于给定对象，则返回值应为小于0的整数
 若两个对象相等，则返回值等于0

一旦java类实现了comparable接口，其比较规则就已经确定。如果想要在排序中临时指定规则，可以采用Comparator接口回调的方式，具体使用如下：

list.sort(new Comparator<String>(){
   //比较规则写在这
   //如果返回值>0，那么就会将o2排在o1之前
   //如果返回值<0，那么就会将o1排在o2之前
   public int compare(String o1,String o2){
    //return o1.compareTo(o2);
    return o1.charAt(0) - o2.charAt(0);
   }
  });

不包含重复元素的集合(唯一)
Set的具体用法跟list差不多，这里代码不再重复写。
Set<String> set = new HashSet<String>();
HashSet
底层基于hashMap来进行存储，不保证迭代顺序，并且不保证循序不变。
HashMap
是基于数组+链表来进行存储。底层数组初始容量为16.数组中的每一个位置称之为是一个桶-bucket
O1---先计算o1的hash码--哈希码是int类型的整数--针对哈希码进行二次运算，使运算结果落在桶的编号之中。
每一个桶中维系了一个链表。添加新元素时，先比较与桶中的元素是否相等，不相等，加入到链表，有相等就舍弃。放的越晚的元素，比较就越低，增删改效率都会降低。所以想要缩短链的长度，就得增加桶的个数。扩容，每次都是一倍。
如果已经使用的桶的数量/桶的总数量>加载因子，那么就认为需要扩容。默认加载因子是0.75。扩容之后，会对桶中的元素进行重新的计算和分布，是元素散列在新找的桶中--rehash。
Rehash---元素越多，效率越低。当你进行rehash的时候，是不能往里面放元素的。
加载因子：影响扩容，越小会扩容越频繁。同时会导致内存的浪费。效率变低。加载因子越大，会导致每一个桶汇中的链表会变长而导致查找变慢。
public HashSet(int initialCapacity)，允许指定初始容量和加载因子。
总的效率，一开始是高的，然后慢慢变慢。在JDK1.8中，如果链的长度>8,那么会将这个链扭转成红黑树，自平衡二叉树。红黑树，比节点小，往左放，比节点大，往右放，类似二分查找。如果红黑红树的节点个数<=6，会扭回链表。

一组自变量按照某种规则变成另外一组因变量，就叫做映射。
K -key-键，V-value-值。一个键对应一个值 - 键值对。也就意味着，一个映射实际上是由多个键值对组成。在映射中，键是唯一的。一个键最多只能对应一个值。
实现类HashMap与HashTab

底层是基于数组+链表的结构。允许键或者值为null。默认初始容量是16，加载因子是0.75.。这个类不保证数据的顺序map是计算key的哈希码，可以针对哈希码来进行二次运算，决定存到哪个桶中。尤其是不保证这个顺序恒久不变。默认rehash扩容，每次会增加大约两倍空间。如果是一个比较高的加载因子，
hashMap允许指定初始容量。指定的初始容量在[2^x , 2^x+1]之间，那么容量算出来的一定是为2^x+1。指定这么大是为了扩容的时候，直接左移一位。本身是一个异步式线程不安全的映射。
异步式：如果一个对象在同一个时刻内允许多人操作
同步式：如果一个对象在一个时刻内允许一个人操作

Map<String, Integer> map = new HashMap<>();
  map.put("d",6);
  map.put("e",4);
  map.put("s",3);
  map.put("f",9);
map.put("i",4);
  //如果键值相同，对应的值覆盖
  map.put("i", 3);
  
  //判断是否包含这个键
  System.out.println(map.containsKey("a"));
  System.out.println(map.containsValue(7));
  //移除键值对
  map.remove("i");
  //如果键相同，那么对应的值覆盖
  
  //清空映射
  map.clear();
  
  //获取指定的键所对应的值
  System.out.println(map.get("r"));
  
  //将映射中所有的值放入一个集合返回
  Collection<Integer> c = map.values();
 System.out.println(c);

不允许键或者值为null.底层也是基于数组+链表。底层的默认初始容量是11.加载因子为0.75F,默认扩容增加一倍，然后再+1。(官方没有解释为什么这样)
这个映射本身是一个同步式线程安全的映射。
指定初始容量，指定多少，就是多少。
基本上没有用，效率比较低，只会出现在面试的时候。

package ADT;

import java.security.NoSuchAlgorithmException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.String;

public class myLinkedList<String> implements Iterable<String> {

	private static class Node<String> {
		public Node(String d, Node<String> p, Node<String> n) {
			data = d;
			prev = p;
			next = n;
		}

		public String data;
		public Node<String> prev;
		public Node<String> next;

	}

	public myLinkedList() {
		doclear();
	}

	public void clear() {
		doclear();
	}

	public void doclear() {
		beginMarker = new Node<String>(null, null, null);
		endMarker = new Node<String>(null, beginMarker, null);
		beginMarker.next = endMarker;

		theSize = 0;
		modCount++;
	}

	public int size() {
		return theSize;
	}

	public boolean isEmpty() {
		return size() == 0;
	}

	public boolean add(String x) {
		add(size(), x);
		return true;
	}

	public void add(int idx, String x) {
		addBefore(getNode(idx, 0, size()), x);
	}

	public String get(int idx) {
		return getNode(idx).data;
	}

	public String set(int idx, String val) {
		Node<String> p = getNode(idx);
		String oldval = p.data;
		p.data = val;
		return oldval;
	}

	public String remove(int idx) {
		return remove(getNode(idx));
	}

	private void addBefore(Node<String> p, String x) {
		Node<String> newnode = new Node<>(x, p.prev, p);
		newnode.prev.next = newnode;
		p.prev = newnode;
		theSize++;
		modCount++;
	}

	private String remove(Node<String> p) {
		p.prev.next = p.next;
		p.next.prev = p.prev;
		theSize--;
		modCount++;
		return p.data;
	}

	private Node<String> getNode(int idx) {
		return getNode(idx, 0, size() - 1);
	}

	private Node<String> getNode(int idx, int low, int up) {
		Node<String> p;
		if (idx < low || idx > up) {
			throw new IndexOutOfBoundsException();
		}
		if (idx < size() / 2) {
			p = beginMarker;
			for (int i = 0; i < idx; i++)
				p = p.next;
		} else {
			p = endMarker;
			for (int i = size(); i > idx; i--)
				p = p.prev;
		}
		return p;
	}

	@Override
	public Iterator<String> iterator() {
		// TODO Auto-generated method stub
		return new LinkedIterator();
	}

	private class LinkedIterator implements Iterator<String> {
		private Node<String> current = beginMarker.next;
		private int exceptedModecount = modCount;
		private boolean okToRemove = false;

		@Override
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return current != endMarker;
		}

		@Override
		public String next() {
			// TODO Auto-generated method stub
			if (modCount != exceptedModecount)
				throw new ConcurrentModificationException();
			if (!hasNext())
				throw new NoSuchElementException();
			String nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}

		public void remove() {
			if (modCount != exceptedModecount)
				throw new ConcurrentModificationException();
			if (!okToRemove)
				throw new IllegalStateException();
			myLinkedList.this.remove(current.prev);
			exceptedModecount++;
			okToRemove = false;
		}

	}

	@Override
	public java.lang.String toString() {

		StringBuilder sb = new StringBuilder("[");

		Node node = this.beginMarker;
		while (node != null) {

			sb.append(node.data).append(", ");
			node = node.next;

		}

		java.lang.String str = sb.toString();
		if (size() != 0)
			str = str.substring(0, str.length() - 2);

		return str += "]";
	}

	private Node<String> beginMarker;
	private Node<String> endMarker;
	private int theSize;
	private int modCount = 0;
}