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