Java----Collection总结
集合，存储多个元素的容器----大小不定。
在集合这块主要的内容有：
接口：Collection Iterator List Set Map
类：ArrayList LinkedList stack queue
hashMap hashTable
本篇为Collection的总结，才开始学习Java,在集合这块看资料总是感觉一团乱麻。所以写这个总结，一方面把自己知道的东西梳理一下，另一方面初学水平有限，如果有错误还请各位大神能够指点，还有就是刚开始玩社区，希望能够获取一点积分，嘿嘿。希望有一天，能够学习JAVA，加入Ali。
Collection接口
Collection是集合层次的根接口。由于泛型的限制，集合中只能存储对象。泛型只能表示引用类型。
Collection定义中的主要方法,就是说当要实现一个Collection的时候，要先实现以下方法（不全，可以查看API稳定）:
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>();
Collection<String> c = new ArrayList<String>();
List接口
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。
Iterator接口
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 操作集
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接口--散列集合
不包含重复元素的集合(唯一)
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，会扭回链表。
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，会扭回链表。
Map接口
一组自变量按照某种规则变成另外一组因变量，就叫做映射。
K -key-键，V-value-值。一个键对应一个值 - 键值对。也就意味着，一个映射实际上是由多个键值对组成。在映射中，键是唯一的。一个键最多只能对应一个值。
实现类HashMap与HashTab
K -key-键，V-value-值。一个键对应一个值 - 键值对。也就意味着，一个映射实际上是由多个键值对组成。在映射中，键是唯一的。一个键最多只能对应一个值。
实现类HashMap与HashTab
HashMap<K,V>
底层是基于数组+链表的结构。允许键或者值为null。默认初始容量是16，加载因子是0.75.。这个类不保证数据的顺序map是计算key的哈希码，可以针对哈希码来进行二次运算，决定存到哪个桶中。尤其是不保证这个顺序恒久不变。默认rehash扩容，每次会增加大约两倍空间。如果是一个比较高的加载因子，
hashMap允许指定初始容量。指定的初始容量在[2^x , 2^x+1]之间，那么容量算出来的一定是为2^x+1。指定这么大是为了扩容的时候，直接左移一位。本身是一个异步式线程不安全的映射。
异步式：如果一个对象在同一个时刻内允许多人操作
同步式：如果一个对象在一个时刻内允许一个人操作
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);
HashTbale
不允许键或者值为null.底层也是基于数组+链表。底层的默认初始容量是11.加载因子为0.75F,默认扩容增加一倍，然后再+1。(官方没有解释为什么这样)
这个映射本身是一个同步式线程安全的映射。
指定初始容量，指定多少，就是多少。
基本上没有用，效率比较低，只会出现在面试的时候。
这个映射本身是一个同步式线程安全的映射。
指定初始容量，指定多少，就是多少。
基本上没有用，效率比较低，只会出现在面试的时候。
List接口 自己写的LinkedList的实现
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;
}
