七、容器/集合

1. 容器概念：Java API 所提供的一系列类的实例，用于在程序中存放对象。
2. 容器 API：J2SDK所提供的容器API位于 java.util 包内。
    Collection 接口－定义了存取一组对象的方法，其子接口Set和List分别定义了存储方式。
        Set 中的数据对象没有顺序且不可以重复。
        List 中的数据对象有顺序且可以重复。（即互相equals）
    Map 接口定义了存储“键（key）－ 值（value）映射对”的方法。


3.Collection 接口
    Collection 接口中所定义的方法：

int size();  
boolean isEmpty(); 
void clear();
boolean contains(Object element);  //equals
boolean add(Object element);
boolean remove(Object element);
Iterator iterator();
boolean containsAll(Collection c);
boolean addAll(Collection c);
boolean removeAll(Collection c);
boolean retainAll(Collection c);   //求交集
Object[] toArray(); 

    容器类对象在调用remove、contains 等方法时需要比较对象是否相等，这会涉及到对象类型的 equals 方法和hashCode(hash容器)方法；对于自定义的类型，需要要重写equals 和 hashCode 方法以实现自定义的对象相等规则。
    注意：相等的对象应该具有相等的 hash codes。
    增加Name类的equals和hashCode方法如下：

public boolean equals(Object obj) {
    if (obj instanceof Name) {
        Name name = (Name) obj;
        return (firstName.equals(name.firstName))
            && (lastName.equals(name.lastName));
    }
    return super.equals(obj);
}
public int hashCode() {
    return firstName.hashCode();
}

4. Map 接口
    实现Map接口的类用来存储键－值 对。
    Map 接口的实现类有HashMap和TreeMap等。
    Map类中存储的键－值对通过键来标识，所以键值不能重复。
    方法：

Object put(Object key, Object value);
Object get(Object key);
Object remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
void putAll(Map t); 
void clear(); 

5. hashCode
    hashCode重要结论：
    重写equals方法,通常需要重写hashCode方法.
    因为你的本意是想让两个不同的对象实现业务逻辑上的相等。但是hashMap等容器判断两个key是不是相等（重复）是靠hashCode和equals，除非hashCode也相等并且equals也相等，hashMap才会认为2个key是重复的。
    如果不重写,不同的对象就不会相等。因为2个对象虽然equals是相等的。但是默认的Object类继承过来的hashCode方法将返回不同的整数
    一个对象被当作HashMap里面的key的时候,hashCode和equals用来比较两个key是不是重复。即：判断key是否重复有两条件必须同时成立：第一，hash必须相等，第二，内存地址相等或者用equals判断是相等的。
    jdk1.6：e.hash == hash && ((k = e.key) == key || key.equals(k))
    jdk1.5：e.hash == hash && eq(k, e.key)
    hashCode用来在HashMap等容器里面计算索引。目的是为了提高搜索效率。甚至比数组遍历还要快很多。

6. Set 接口
    Set 接口是Collection的子接口，Set接口没有提供额外的方法，但实现 Set 接口的容器类中的元素是没有有顺序的，而且不可以重复。
    Set 容器可以与数学中“集合”的概念相对应。
    J2SDK API中 所提供的 Set 容器类有 HashSet，TreeSet 等。
    HashSet底层靠HashMap实现的。
7. List 接口
    List接口是Collection的子接口，实现List接口的容器类中的元素是有顺序的，而且可以重复。
    List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
    J2SDK 所提供的 List 容器类有 ArrayList，LinkedList 等。
    List 常用算法：

void sort(List)  对List容器内的元素排序
void shuffle(List) 对List容器内的对象进行随机排列
void reverse(List) 对List容器内的对象进行逆续排列 
void fill(List, Object)  
用一个特定的对象重写整个List容器
void copy(List dest,List src) 
将src List容器内容拷贝到dest List容器
int binarySearch(List, Object)
对于顺序的List容器，采用折半查找的方法查找特定对象

8. Comparable 接口
    问题：上面的算法根据什么确定容器中对象的“大小”顺序？
    所有可以“排序”的类都实现了java.lang.Comparable 接口，Comparable接口中只有一个方法  public int compareTo(Object obj)；该方法: 返回   0   表示 this == obj    返回正数表示 this  >  obj     返回负数表示 this  <  obj
    实现了Comparable 接口的类通过实现 comparaTo 方法从而确定该类对象的排序方式。

9. Iterator 接口
    所有实现了Collection接口的容器类都有一个iterator方法用以返回一个实现了Iterator接口的对象。
    Iterator对象称作迭代器，用以方便的实现对容器内元素的遍历操作。
    Iterator接口定义了如下方法：
    boolean hasNext();  //判断游标右边是否有元素
    Object next();      //返回游标右边的元素并将游标移动到下一个位置
    void remove();      //删除游标左面的元素，在执行完next之后该操作只能执行一次

import java.util.*;
public class Test {
    public static void main(String[] args) {
        Collection c = new HashSet();
        c.add(new Name("f1","l1"));
        c.add(new Name("f2","l2"));
        c.add(new Name("f3","l3"));
        Iterator i = c.iterator();
        while(i.hasNext()) {
        //next()的返回值为Object类型，需要转换为相应类型
            Name n = (Name)i.next();
            System.out.print(n.getFirstName()+" ");
        }
    }
}

    Enumeration/ Iterator/ ListIterator区别：

	Enumeration		Iterator		ListIterator
	不能		删除元素		删除元素
	不能		不能		增加元素
	不能		不能		反向迭代
	不支持fail-fast		支持fail-fast		支持fail-fast

10. 补充：JDK1.5增强的for循环
    增强的for循环对于遍历array 或 Collection的时候相当简便；
    缺陷：
        数组：不能方便的访问下标值；
        集合：与使用Iterator相比，不能方便的删除集合中的内容。
    总结：除了简单遍历并读出其中的内容外，不建议使用增强for。

import java.util.*;

class Test {
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5};
		for(int a : arr) {
			System.out.println(a);
		}
		
		Collection c = new ArrayList();
		c.add(new String("aaa"));
		c.add(new String("bbb"));
		c.add(new String("ccc"));
		for(Object o : c) {
			//c.remove(o);
			System.out.println(o);
		}
	}
}

11. Auto-boxing/unboxing
    在合适的时机自动打包、解包
    自动将基础类型转换为对象
    自动将对象转换为基础类型

//注意i1和i2都是Integer类型，事实上只要这个值的范围在“-128—127”之间，输出结果都是“Equal!”。

//当i1和i2值为128时，在进行 “==”时，它们被装进两个不同的Integer Objects，
//由于这是两个不同的instances，它们引用不同的内存地址，所以结果是“Not equal!”。

//对于值从-128到127之间的值，它们被装箱为Integer对象后，会存在内存之中被重用
//这样进行“==”时，JVM仍然使用的是相同的object instance，所以输出结果为“Equal!”了。

//如果超过了从-128到127之间的值，被装箱后的Integer对象并不会被重用，
//即相当于每次都新建一个Integer对象，所以当值在 200，使用'=='进行比较时，i1与i2参考的是不同的对象。


class Test {
	public static void main(String[] args) {
		Integer i1 = 127;
		
		Integer i2 = 127;
		
		i1 = 126;
		
		if (i1 == i2)
			System.out.println("Equal!");
		else
			System.out.println("Not equal!");
	}
}

12. 补充：JDK1.5泛型

//等号左边可以不写泛型,
	//如果方法返回值是泛型，那么返回值是Object，
	//方法参数如果是泛型javac不再做类型检查
	//-->索引这样写代码不可取
//等号右边可以不写泛型，默认是调用方法时候，靠左边的泛型来限制，而且取出来的是泛型的类型
	//因为等号右边可能是以前定义的类
	//不要这样写代码
//如果都写泛型，左右必
import java.util.*;
class Test{
	public static void main(String [] args){
		Collection<String> a = new ArrayList<String>();
		a.add("aaa");
		a.add("bbb");
		a.add("ccc");
		a.add("ddd");
		//a.add(new Name("sss"));	
		System.out.println(a);
		System.out.println("------------------------------");
	
		Myclass<String> my = new Myclass<String>();
		my.setName("sdf");
		Myclass<A> my1 = new Myclass<A>();
		//Myclass<A> my1 = new Myclass<AA>();		X
		//Myclass<AA> my1 = new Myclass<A>();		X
		//Myclass<A> my1 = new Myclass<B>();		X
		my1.setName(new A());
	}
}
class Name{
	String name;
	Name(String name){
		this.name = name;	
	}	
	public String toString(){
		return name;	
	}
}
class Myclass<T> {
	T name;
	public void setName(T name){
		this.name = name;	
	}
}
class A{
}
class AA extends A{
}
class B{
}

13.如何选择数据结构

引用

Array读快改慢
Linked改快读慢
Hash搜索极快，遍历极慢
Tree插入/搜索都比较快，适合做索引

14. Vector & ArrayList的区别
    Vector被ArrayList代替了
    因为Vector中的方法是同步的，一般不常用，但有时在多线程中可以用。
15. hashMap和HashTable区别

	Hashtable		HashMap
	实现了Map接口		实现了Map接口
	java.lang.Object   java.util.Dictionary<K,V>       java.util.Hashtable<K,V>		java.lang.Objectjava.util.AbstractMap<K,V>java.util.HashMap<K,V>
	Hashtable中的方法是同步的，		HashMap是Hashtable的轻量级实现（非线程安全的实现）。在多线程应用程序中，需要额外的同步机制。
			但HashMap的同步问题可通过Collections的一个静态方法得到解决：Map Collections.synchronizedMap(Map m) 这个方法返回一个同步的Map，这个Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
	Hashtable不允许。 		在HashMap中，null可以作为键，这样的键只有一个； 可以有一个或多个键所对应的值为null。 当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
	HashTable使用Enumeration，		HashMap使用Iterator。
	HashTable中hash数组默认大小是11，增加的方式是 old*2+1。		HashMap中hash数组的默认大小是16，而且一定是2的指数。
	哈希值的使用不同，HashTable直接使用对象的hashCode，		而HashMap重新计算hash值，而且用与代替求模：
			由于非线程安全，效率上可能高于Hashtable。
			HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。

16. HashMap 和TreeMap区别

			HashMap		TreeMap
	key有无顺序		HashMap通过hashcode对其内容进行快速查找（HashMap中元素的排列顺序是不固定的）。		而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap
	判断key是否重复逻辑不同		判断key是否重复有两条件必须同时成立：第一，hash必须相等，第二，内存地址相等或者用equals判断是相等的。		compareTo方法比较是0
	对key类的要求不同		key类重写equals有必要重写hashCode方法		Key类必须实现了Comparable接口。