Java学习笔记8

2017-12-28

day9

开始对容器的完整学习，几个常用容器是重点，无论是写算法题还是项目开发必备。

1.容器分类表

首先，对JAVA中的容器进行总体上的把握，按照继承关系可看下图：

容器家族

根据Oracle公司的官方文档：

Collection是对Iterable接口的拓展。故所有的Collection对象都可以使用foreach方式，对元素进行方便的遍历。

由于Iterable接口中定义了的唯一方法为：返回一个Iterator对象，故所有的Collection都可以用对象名.iterator()的方式获取该collection的迭代器iterator对象（结合工厂方法和内部类的思想来理解，其作用十分大）

Map中提供了产生Collection的方法，以支持方便的对键值对的值域进行操作。

Collection<V> values() // Returns:a collection view of the values contained in this map.

从JAVA提供的数据容器来看，可以清晰的认识到面向对象的思想在类的架构设计中的重要性。

灵活的使用好各类容器类，以最大限度的提升程序的性能。由于类型过多，大多的基础操作都被抽象到了Collection中，熟练并利用好Collection提供的接口，已经可以解决大量的问题（即使是Map，其也提供了产生Collection对象的机制）。

Collection接口


boolean add(Object o)//添加对象到集合
boolean remove(Object o)//删除指定的对象
int size()//返回当前集合中元素的数量
boolean contains(Object o)//查找集合中是否有指定的对象
boolean isEmpty()//判断集合是否为空
Iterator iterator()//返回一个迭代器
boolean containsAll(Collection c)//查找集合中是否有集合c中的元素
boolean addAll(Collection c)//将集合c中所有的元素添加给该集合
void clear()//删除集合中所有元素
void removeAll(Collection c)//从集合中删除c集合中也有的元素
void retainAll(Collection c)//从集合中删除集合c中不包含的元素

List

List主要将元素在特定的序列中，基本上在Collection的基础上加入了大量的方法，可以在List中间进行插入和删除

LinkedList

　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

ArrayList

类似于C++中的vector,随机访问元素快，中间插入删除慢，ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。和LinkedList一样，ArrayList也是非同步的（unsynchronized）。一般情况下使用这两个就可以了，因为非同步，所以效率比较高。如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

Set接口

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。 Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。Set容器类主要有HashSet和TreeSet等。

Java.util.HashSet类实现了Java.util.Set接口。

HashSet

它不允许出现重复元素；
不保证和政集合中元素的顺序
允许包含值为null的元素，但最多只能有一个null元素。


public static void main(String [] args)
    {
       HashSet h=new HashSet();
       h.add(1st);
       h.add(2nd);
       h.add(new Integer(3));
       h.add(new Double(4.0));
       h.add(2nd);            //重复元素，未被添加
       h.add(new Integer(3));      //重复元素，未被添加,对象的重复判定规则是.equals().
       h.add(new Date());
       Iterator it=h.iterator();
       while(it.hasNext())
       {
           Object o=it.next();
           System.out.println(o);
       }
       h.remove(2nd);
       System.out.println(h);

TreeSet

TreeSet描述的是Set的一种变体——可以实现排序等功能的集合，它在讲对象元素添加到集合中时会自动按照某种比较规则将其插入到有序的对象序列中，并保证该集合元素按照“升序”排列。

Map

HashMap

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value null key，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。　　

－JDK1.0引入了第一个关联的集合类HashTable，它是线程安全的。 HashTable的所有方法都是同步的。

－JDK2.0引入了HashMap，它提供了一个不同步的基类和一个同步的包装器synchronizedMap。synchronizedMap被称为有条件的线程安全类。

－JDK5.0util.concurrent包中引入对Map线程安全的实现ConcurrentHashMap，比起synchronizedMap，它提供了更高的灵活性。同时进行的读和写操作都可以并发地进行。

Iterator

我们在使用Iterator时一般可以这样用：


List<Apple> apples=new ArrayList<Apple>();
//...
//遍历
Iterator<Apple> it=apples.iterator();
while(it.hasNext()){
 System.out.println(it.next());
}
//删除
while(it.hasNext()){
	it.next();
	it.remove();
}

接下来看一下源码：


private class Itr implements Iterator<E> {
       int cursor = 0; //   下一个next元素的位置
       int lastRet = -1; //最后访问的位置
       int expectedModCount = modCount; //fast-failed机制，可以在多线程中防止其他线程在这个迭代器使用过程中修改容器结构。
       public boolean hasNext() {
           return cursor != size();
       }
       public E next() {
           checkForComodification();
           try {
               int i = cursor;
               E next = get(i);
               lastRet = i;
               cursor = i + 1;
               return next;
           } catch (IndexOutOfBoundsException e) {
               checkForComodification();
               throw new NoSuchElementException();
           }
       }
       public void remove() {
           if (lastRet < 0)
               throw new IllegalStateException();
           checkForComodification();
           try {
               AbstractList.this.remove(lastRet);
               if (lastRet < cursor)
                   cursor--;
               lastRet = -1;
               expectedModCount = modCount;
           } catch (IndexOutOfBoundsException e) {
               throw new ConcurrentModificationException();
           }
       }
       final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }
   }

一般而言，迭代器是实现了Iterator接口，有三个方法：

Next()
hasNext()
remove()

2.填充容器

Collections.fill()可以填充List对象，只能复制同一对象。

Collections.nCopy()可以复制对一个对象的多个引用。

Set

Set(interface) 存入Set的每个元素是不同的，也就是.equals()要返回false，Set与Collection有相同的接口
HashSet,存放的元素必须有hashCode()方法。
TreeSet,存放元素有序。
LinkedHashSet,具有HashSet的查询速度，按照插入的次序排序。


package wangliang;
import java.security.cert.TrustAnchor;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;
class SetType{
	int i;
	public SetType(int n){
		i=n;
	}
	public boolean equals(Object o){
		return o instanceof SetType &&(i==((SetType)o).i);
	}
	public String toString(){
		return Integer.toString(i);
	}
}
class HashType extends SetType{
	public HashType(int n){
		super(n);
	}
	public int hashCode(){return i;}
}
class TreeType extends SetType
implements Comparable<TreeType>{
	public TreeType(int n){super(n);}
	public int compareTo(TreeType o){
		return (this.i<o.i)?-1:((this.i==o.i)?0:1);
	}
}
public class TypesForSets {
	static <T> Set<T> fill(Set<T> set,Class<T> type){
		try{
			for(int i=0;i<10;i++){
				set.add(type.getConstructor(int.class).newInstance(i));
			}
		}catch (Exception e) {
			throw new RuntimeException(e);// TODO: handle exception
		}
		return set;
	}
	static <T> void test(Set<T> set,Class<T> type){
		for(int i=0;i<3;i++)
			fill(set, type);
		System.out.println(set);
	}
	public static void main(String[] args){
		test(new HashSet<HashType>(),HashType.class);
		test(new LinkedHashSet<HashType>(),HashType.class);
		test(new TreeSet<TreeType>(),TreeType.class);
		test(new HashSet<SetType>(), SetType.class);
		try{
			test(new TreeSet<SetType>(),SetType.class );
		}catch (Exception e) {
			System.out.println(e.getMessage());// TODO: handle exception
		}
	}
}//output
/*
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[5, 8, 1, 7, 3, 7, 9, 1, 9, 6, 7, 8, 4, 0, 3, 4, 9, 3, 2, 0, 5, 2, 1, 6, 6, 5, 4, 2, 8, 0]
java.lang.ClassCastException: wangliang.SetType cannot be cast to java.lang.Comparable
*/

可以看到，如果没有实现hashCode()方法的类放入HashSet中，会出现无法估计的结果。