集合总结

Collection 层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。

List：一个有序的序列，是有顺序的



集合中存放的依然是对象的引用而不是对象本身。

集合当中只能放置对象的引用，无法放置原生数据类型，我们需要使用原生数据类型的包装类才能加入到集合当中。

集合当中放置的都是Object类型，因此取出来的也是Object类型，那么必须要使用强制类型转换将其转换为真正的类型（放置进去的类型）。

下面讲解ArrayList：
ArrayList底层采用数组实现，当使用不带参数的构造方法生成ArrayList对象时，实际上会在底层生成一个长度为10的Object类型数组。

如果增加的元素个数超过了10个，那么ArrayList底层会新生成一个数组，长度为原数组的1.5倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组中。当新数组无法容纳增加的元素时，重复该过程。

对于ArrayList元素的删除操作，需要将被删除元素的后续元素向前移动，代价比较高。

ArrayList(数组的列表)：底层是采用数组实现的，使用Add方法往里面添加东西。取出来的时候是和放进去的顺序一致的，先放进去的先取出来，后放进去的后取出来，元素的下标也是从0开始，和数组类似，里面允许存放相同的元素。
Remove方法的原理：比如清除了下标为0的元素，那么后面的元素就往前挪，第二个元素的下标又变成了0。放进去的什么类型的，取出来的时候向下类型转换就转换成什么类型的。
集合里面只能放置对象，不能放置原生数据类型的数据，例如需要把原生数据类型转换成包装类。
ArrayList里面有一个方法toArray()，这个方法是将这个集合转换成一个数组。
Object{}类型的无法强制类型转换成Integer[]类型的，因为Object[]类型里面可以存放很多类型的数据，比如String 、Integer等，而String类型的没法转换成Integer类型的，所以会报错。
集合里面存放的还是对象的引用，
ArrayList重写了Object的toString()方法，以一个[开头，一个]结束，中间包含调用list里面包含的每一个对象(每一个元素)的toString()方法的结果……

其实ArrayList底层就是一个数组而已，没什么神秘的，定义数组的时候底层首先给他初始化一个长度为10的数组而已。

集合大总结需要把圣思源笔记Java SE Lession5.pdf里面关于集合的笔记也加进去。

ArrayList里面的remove方法的代价比较高，是把index参数索引后面的所有元素都向前移动一位，索引值都减一，涉及到大量元素的移动，因此ArrayList里面的删除操作代价相当高。

ArrayList里面有两个添加方法，其中public boolean add(E e)不太耗费资源，操作时需要的资源比较少，只是追加到底层数组的末尾。另一种是public void add(int index,E element)，这种添加方法代价就比较高了，和上面的remove方法消耗的资源差不多，这种方法是将元素添加到底层数组的指定位置。

下面讲解LinkedList(链接的列表)：

LinkedList里面有getFirst()、getLast()、addFirst(E e)、addLast(E e)、add(int index, E element)、peek()、poll()、pop()等方法。而这些方法在ArrayList里面却没有，这也是由这两种集合底层实现方式的不同而引起的。

LinkedList里面的元素在内存里存放的位置不是在一起的，每个元素分散的存放在内存中，散乱的，只是通过每个元素里面的前驱引用和后继引用将每个元素穿起来组成一个链表，组成一个集合，每个元素都知道它的下一个元素和上一个元素在哪里。


关于ArrayList与LinkedList的比较分析
a)  ArrayList底层采用数组实现，LinkedList底层采用双向链表实现。
b)  当执行插入或者删除操作时，采用LinkedList比较好（使用LinkedList实现插入或删除时改变的只是元素的引用而已，不需要发生移动。而如果使用ArrayList实现的话，从插入或删除位置后面的所有元素都需要移动，消耗的资源就非常大。）。
c)  当执行搜索操作时，采用ArrayList比较好（比如100个元素，我想要找到第50个元素，如果采用LinkedList实现，我需要从第一个元素，一个一个往后找，一直找到第50个元素，才能找到。而如果采用ArrayList实现的话，它里面是连续的存放的，通过第一个元素的首地址再加上每个元素所占据的字节，一下子就找到第50个元素了。）。
d)  ArrayList里面存放的直接就是存放对象的引用。而LinkedList里面却不是直接存放对象的引用，而是存放的是Entry类型对象的元素(LinkedList里面的一个内部类)，每个Entry类型的对象里面包含了三个元素，第一个是向前的引用，第二个是需要存放的数据本身对象的引用，第三个是向后的引用。
e)  当向ArrayList添加一个对象时，实际上就是将该对象放置到了ArrayList底层所维护
的数组当中；当向LinkedList中添加一个对象时，实际上LinkedList内部会生成一个
Entry对象，该Entry对象的结构为：
Entry
{
  Entry previous;
  Object element;
  Entry next;
}
其中的Object类型的元素element就是我们向LinkedList 中所添加的元素，然后Entry
又构造好了向前与向后的引用previous、next，最后将生成的这个Entry对象加入到了链
表当中。换句话说，LinkedList中所维护的是一个个的Entry对象。


数据结构的相关知识查看圣思源笔记Java SE Lesson 5里面的collection.pdf(比如链表、线性结构等，就是这里讲到的集合底层实现方式的一些相关的数据结构的知识，非常重要)。

LinkedList底层采用的就是双向链表的方式实现的，它里面对元素的添加、删除、存储方式和链表的方式一模一样(关于链表的详细讲解见圣思源笔记Java SE Lesson 5里面的collection.pdf)。一定要重点查看这个pdf文档。



下面讲解HashSet(数学上的集合)：
Set(里面存放对象引用)是没有顺序的而且不能包含重复元素

调用Set集合的add(E e)方法执行添加时判断集合里面是否已经存在此对象的方式比较特殊，具体如下：先讲解此问题涉及到的相关知识：
1.  关于Object类的equals方法的特点(前提是x和y都不为空，不为null)
a)  自反性：x.equals(x)应该返回true
b)  对称性：x.equals(y)为true，那么y.equals(x)也为true。
c)  传递性：x.equals(y)为  true并且y.equals(z)为true，那么x.equals(z)也应该为true。
d)  一致性：x.equals(y)的第一次调用为true，那么x.equals(y)的第二次、第三次、第n次调用也应该为true，前提条件是在比较之间没有修改x也没有修改y。
e)  对于非空引用x，x.equals(null)返回false。
2.  关于Object类的hashCode()方法的特点(一般情况下，当我们重写Object类里面的equals()方法的时候，也需要重写hashCode()方法。以保证相等的对象也具有相同的hashCode)：
a)  在Java 应用的一次执行过程当中，对于同一个对象的hashCode方法的多次调用，
他们应该返回同样的值（前提是该对象的信息没有发生变化）【比如说你第一次启动一个java虚拟机去加载这个应用程序去执行，返回的hash code是123，在这一次执行过程当中，后面又去调用并返回hash code值也一定是123，但是如果这时候你的这个应用执行完了，再去重新的执行一次应用，结果不一定就是123了，有可能变成234了，这就是所谓的在一次java应用的执行过程当中。】。
b)  对于两个对象来说，如果使用equals方法比较返回true，那么这两个对象的hashCode
值一定是相同的。
c)  对于两个对象来说，如果使用equals方法比较返回false，那么这两个对象的hashCode值不要求一定不同（可以相同，可以不同），但是如果不同则可以提高应用的性能。
d)  对于Object类来说，不同的Object对象的hashCode值是不同的（Object类的hashCode值表示的是对象的地址）。

调用Set集合的add(E e)方法执行添加时判断集合里面是否已经存在此对象的方式比较特殊，具体如下：
当使用HashSet时，hashCode()方法就会得到调用，判断已经存储在集合中的对象的hash  code值是否与增加的对象的hash  code值一致；如果不一致，直接加进去；如果一致，再进行equals方法的比较，equals方法如果返回true，表示对象已经加进去了，就不会再增加新的对象，否则加进去。

下面通过实例验证上面说的添加验证方法：

package com.shengsiyuan2;

import java.util.HashSet;

public class SetTest2 {
	public static void main(String[] args) {
		HashSet set1 = new HashSet();

		set1.add(new People("zhangsan"));
		set1.add(new People("lisi"));
		set1.add(new People("zhangsan"));//People类继承Object类，继承里面的hashCode()方法，且没有重写，而对于Object类来说，不同的Object对象的hashCode值是不同的（Object类的hashCode值表示的是对象的地址），所以这个对象能添加进去
		System.out.println(set1);
		
		System.out.println("==================================");
		
		HashSet set2 = new HashSet();
		People p1 = new People("zhangsan");
		set2.add(p1);
		set2.add(p1);//People类继承Object类，继承里面的hashCode()方法，而Object类的hashCode值表示的是对象的地址，p1和p1指向同一个对象，因此地址信息相同，hashcode值也相同，不能添加。然后再用equals()方法比较p1和p2,返回true,也不能添加，所以不能添加此对象
		System.out.println(set2);
		
		System.out.println("===================================");
		
		HashSet set3 = new HashSet();
		String s1 = new String("a");
		String s2 = new String("a");
		set3.add(s1);
		set3.add(s2);//首先判断s1和s2的hashcode值是否相同，String类继承Object类，重写里面的hashCode()方法，而String类里面的hashCode()方法大概比较的是字符串每个位置的字符一样，因此比较结果为两者的hashcode值相同。然后再用equals()方法比较s1和s2，返回true,因此就不会再添加此对象了。
		System.out.println(set3);
		
		System.out.println("====================================");
	}
}

class People {
	String name;

	public People(String name) {
		this.name = name;
	}
}

下面是一个额外知识点：
自定义的一个类如果我们重写equals方法，那么也要重写hashCode方法，反之亦然。比如我们自定义的一个类，我们要向让它内容一样，比如两个人，我们认为两个人名字一样，他们内容就一样，这种情况就不让他们增加到一个集合里面，这种功能的实现就要求我们重写hashCode()方法，重写equals()方法，因为这两个方法都是object类定义的两个方法，这两个方法又都是密切相关的，所以在多数情况下，我们只要重写了hashCode()方法，我们就要同时重写equals()方法，反之亦然。

结论：对于自定义的类如果重写了equals()、hashCode()方法中的一个，就最好把另一个也重写了，因为你自己也不确定此自定义的类是否需要添加到集合里面去，而把此类添加到类似HashSet这样不能重复的集合里面的时候，这两个方法同时会用到。(MyEcplse也能帮助我们完成这件事，快捷键：光标放到此类里-点击Source-Generate hashCode() and equals()...)
通过下面的例子来证实上面的结论：

package com.shengsiyuan2;

import java.util.HashSet;

/**
 * 想要实现的效果：两个学生如果名字相同，那么在Set里面要作为相同的元素来对待，不能重复添加。
 * 类: SetTest3 <br>
 * 描述: TODO <br>
 * 作者: 
 * 时间: Sep 11, 2013 5:03:02 PM
 */
public class SetTest3 {
	public static void main(String[] args) {
		HashSet set = new HashSet();

		Student s1 = new Student("zhangsan");
		Student s2 = new Student("zhangsan");

		set.add(s1);
		set.add(s2);
		System.out.println(set);
	}
}

class Student {
	String name;

	public Student(String name) {
		this.name = name;
	}

	public int hashCode() {
		return this.name.hashCode();
	}

	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}

		if (null != obj && obj instanceof Student) {
			Student s = (Student) obj;
			if (this.name.equals(s.name)) {
				return true;
			}
		}
		return false;
	}
}

开始遍历HashSet（使用迭代器方式），遍历HashSet使用里面的iterator()方法，此方法返回对此Set中元素进行迭代的迭代器，返回元素顺序不确定，迭代器的工作原理查看圣思园课程笔记Java SE Lesson 5里面的collection.pdf文档(在里面找到迭代器的工作原理)。

下面代码演示了采用迭代器方式遍历HashSet:

package com.shengsiyuan2;

import java.util.HashSet;
import java.util.Iterator;

public class InteratorTest {
	public static void main(String[] args) {
		HashSet set = new HashSet();

		set.add("a");
		set.add("b");
		set.add("c");
		set.add("d");
		set.add("e");

		for (Iterator iterator = set.iterator(); iterator.hasNext();) {
			System.out.println(iterator.next());
		}
	}
}

下面讲解接口SortedSet：

SortedSet是具有对元素进行排序功能的集合。排序方式可以是自然(默认)的，也可以是自定义的(通过Comporator指定)。

接口SortedSet的实现类里面用的最多的是TreeSet。

下面讲解TreeSet：

比如我在一个TreeSet里面调用add(E e)放入“a”、“d”、“c”、“b”、“e”五个字符串，那么TreeSet就会将放进去的这些元素默认按升序排列存放，打印出来的结果就是[a,b,c,d,e]；如果我们在一个TreeSet里面调用add(E e)放入“3”、“5”、“1”、“4”、“2”五个字符串，那么TreeSet同样的就会将放进去的这些元素默认按升序排列存放，打印出来的结果就是[1,2,3,4,5]。但是假如我们调用TreeSet的add(E e)方法往里面放入我们自己自定义的类(比如Person类)的几个对象，那么在添加的过程中，TreeSet希望能将添加进来的每一个元素按照一些可能存在的规则(比如上面的数字的大小了、字母的先后顺序等等……)进行默认的排序，于是TreeSet就会用当前需要添加的这个Person对象和TreeSet里面已有的Person对象进行比较，看谁应该放在前面谁应该放在后面，但是他发现这些对象之间根本没法做比较，于是就报错了ClassCastException。这问题怎么解决呢？所以我们要想往TreeSet里面能放置对象并且让对象之间可以进行比较，我们必须要自己指定好自己的一套排序规则，前提是这些被放置进去的对象本身没有一种所谓的自然的顺序(比如不是像上面的数字或字母等等)。我们可以通过TreeSet的构造方法来指定这种排序规则，TreeSet(Comparator<? super E> comparator)，这个构造方法里面接收的Comparator类型的参数comparator就可以是我们自己指定的排序规则。Comparator是一个接口，我们只要定义一个类实现这个接口，并重写里面的compare(T o1, T o2)方法，并在此方法里面定义排序规则，然后把此类的对象作为参数传递到TreeSet的构造方法里即可。compare(T o1, T o2)方法的使用方法参见API文档。

下面通过两个例子验证上面的知识点（TreeSet存放元素时自定义的排序函数）：

package com.shengsiyuan2;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * TreeSet里面如果不添加自定义的排序规则，默认的排序规则是升序的。这个类让存放在TreeSet里面的字母按照降序排列
 * 类: TreeTest3 <br>
 * 描述: TODO <br>
 * 作者: fangguanhong [e-mail] <br>
 * 时间: Sep 13, 2013 5:04:31 PM
 */
public class TreeTest3 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet(new MyComparator());

		set.add("C");
		set.add("A");
		set.add("B");
		set.add("E");
		set.add("F");
		set.add("D");

		for (Iterator iter = set.iterator(); iter.hasNext();) {
			System.out.println(iter.next());// 这个默认是按照升序排列的
		}
	}
}

class MyComparator implements Comparator {
	/**
	 * 继承Comparator这个接口必须要实现这个方法(我们自定义的比较规则)
	 * 如果方法返回-1表示o1 < o2，o1在o2的前面
	 * 如果方法返回0表示o1 = o2
	 * 如果方法返回1表示o1 > o2，o1在o2的后面
	 * 方法: compare <br>
	 * 描述: TODO
	 * @param o1
	 * @param o2
	 * @return 
	 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
	 */
	public int compare(Object o1, Object o2) {
		String s1 = (String) o1;
		String s2 = (String) o2;

		// String类里面的compareTo(String
		// str)方法是按照字典的顺序来比较这两个字符串，比如s1在s2的前面，那就叫字典的顺序。返回值有几种0、负数、正数。分别表示一个字符串在另一个的相同位置、前面、后面。
		return s2.compareTo(s1);
	}
}

package com.shengsiyuan2;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * 让存放在TreeSet里面的Person对象按照他们分数score的升序排列
 * 类: TreeSetTest2 <br>
 * 描述: TODO <br>
 * 作者: fangguanhong [e-mail] <br>
 * 时间: Sep 13, 2013 5:05:39 PM
 */
public class TreeSetTest2 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet(new PersonComparator());

		Person p1 = new Person(10);
		Person p2 = new Person(20);
		Person p3 = new Person(30);
		Person p4 = new Person(40);
		set.add(p1);
		set.add(p2);
		set.add(p3);
		set.add(p4);

		for (Iterator iter = set.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}
	}
}

class Person {
	int score;

	public Person(int score) {
		this.score = score;
	}

	public String toString() {
		return String.valueOf(this.score);
	}
}

class PersonComparator implements Comparator {
	public int compare(Object o1, Object o2) {
		Person p1 = (Person) o1;
		Person p2 = (Person) o2;

		// p1.score大于p1.score返回正数
		// p1.score小于p1.score返回负数
		// p1.score等于p1.score返回0
		return p1.score - p2.score;
	}
}

List集合也是有迭代器的，也可以使用迭代器对其进行迭代打印，打印出来的结果是有序的，因为list里面的元素存放的就是有序的。而Set用迭代器迭代打印出来的结果是无序的，因为Set里面的元素存放的就是无序的。

我们以前讲过Arrays这个类，它主要提供了数组的一些辅助方法，里面的所有方法都是一些静态的，比如binarySearch(……)是进行二分查找，copyOf(…….)是数组的拷贝，copyOfRange(….)根据范围进行拷贝，equals(…….)判断数组是否相同，fill(…….)用某一个值填充到某个数组里卖弄去，sort(……)对数组进行自定义规则的排序，toString(……)将数组转换成字符串。针对数组Array有Arrays这么一个类来为它提供这么多辅助性的方法。同样的，针对集合Collection也有这样一个类为它提供一些辅助性的功能方法，这个类就是Collections。Collection是一个接口，而Collections是一个类，Collections里面的方法也全都是静态的，这个类包含了静态方法用于操纵或是返回集合，它对集合Collection的作用类似于Arrays这个类对数组Arry的作用。

下面通过一个例子演示Collections类的少量常用方法：

package com.shengsiyuan2;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * Collections类使用示例(仅仅演示其中的少部分方法)
 * 类: CollectionsTest <br>
 * 描述: TODO <br>
 * 作者: fangguanhong [e-mail] <br>
 * 时间: Sep 13, 2013 5:51:53 PM
 */
public class CollectionsTest {
	public static void main(String[] args) {
		LinkedList list = new LinkedList();

		list.add(new Integer(-8));
		list.add(new Integer(20));
		list.add(new Integer(8));
		list.add(new Integer(-20));

		for (Iterator iter = list.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}
		System.out.println("=================================");

		// 返回针对目标集合的比较器，这个比较器会对目标集合的自然顺序执行相反的操作，如果目标集合自然顺序是升序，那么调用这个方法之后就是降序了。
		Comparator r = Collections.reverseOrder();
		// 按照r指定的比较器对list进行排序
		Collections.sort(list, r);
		for (Iterator iter = list.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}

		System.out.println("==================================");

		// 调用这个方法意思是把集合里面的元素的顺序打乱，和播放器上面的随机播放的意思差不多，第一首播放完了你不知道跳到第几首，其实就是把元素的顺序搞乱了。每次调用完之后元素的顺序都不同。
		Collections.shuffle(list);
		for (Iterator iter = list.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}

		// 获得集合里面元素的最小值和最大值
		System.out.println("minimum value:" + Collections.min(list));
		System.out.println("maximum value:" + Collections.max(list));
	}
}

下面讲解Map的两种迭代方式：
1、通过map.keySet()方式得到map里面键的集合keyset，然后遍历keyset，
For(Iterator iter = keyset.iterator();iter.hasNext()){String value = map.get(iter.next())}获取每个键对应的值。
2、通过Map的entrySet()方法获取元素的键值对映射集合set，然后遍历Set，set里面存放的元素是内部类Map.Ectry类型的，向下类型转换之后调用getKey()和getValue()方法获得键和值。
Set set = map.entrySet();
for(Iterator iter = set.iterator(); iter.hasNext();) {
Map.Entry entry = (Map.Entry)iter.next();
String key = (String)entry.getKey();
String value = (String)entry.getValue();
}



Map.Enty，指的是Enty是Map类里面的一个内部类(类里面定义的类)。Map.Enty本身就表示Enty这个内部类。

对于Map底层会生成Entry对象，Entry里面有一个key的信息，有一个value的信息，key和value封装到一个Entry这样一个对象里面，所以获得了一个Entry对象，就即能获得键的信息，又能获得一个值的信息，Map底层比较复杂，先简单讲这么多。



TreeMap还没讲呢，TreeMap和TreeSet很类似，只不过TreeSet是就一个key的信息比较没有value，而TreeMap即有key，又有value，但它也是对key的信息进行的一个比较。它里面也同样的有接收Comparator接口实现类(定义自己的比较器)的构造方法。


下面是HashSet和HashMap相关的一些知识，比较复杂，了解下即可(不用太深究)：
1. HashSet底层是使用HashMap实现的。当使用add方法将对象添加到Set当中时，实际上是将该对象作为底层所维护的Map对象的key，而value则都是同一个Object对象（该对象我们用不上）；
2. HashMap底层维护一个数组，我们向HashMap中所放置的对象实际上是存储在该数组当中；
3. 当向HashMap中put一对键值时，它会根据key的hashCode值计算出一个位置，该位置就是此对象准备往数组中存放的位置。
4. 如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找（Entry类有一个Entry类型的next成员变量，指向了该对象的下一个对象），如果此链上有对象的话，再去使用equals方法进行比较，如果对此链上的某个对象的equals方法比较为false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。
5. HashMap的内存实现布局： 如附件“内部内布局.jpg”