----------- android培训、java培训、java博客、java学习型技术博客、期待与您交流！ --------------
本章主要的知识点总结：1、集合类的分类： Collection 和MAP中的常见类及区别
2、Set常用实现类、List常用的实现类、Map常用的实现类的说明。
3、掌握集合的迭代器的使用以及MAP集合获取元素的方法
4、掌握实现对象比较的两种方式
5、集合、数组相互转换：使用Collection中的toArray()方法 和 Arrays.asList(T... a)
6、集合泛型的使用以及ArrayList与HashSet的比较
一、分类
集合类中的接口主要有：
Collection -----> Set (不能包含重复的元素，无序)Collection -----> Set (不能包含重复的元素，无序)
------ HashSet: 使用散列函数,数据结构是哈希表，线程是非同步的。
-----TreeSet:使用红黑树，可以对Set集合中元素进行排序
---- LinkedHashSet: 使用链表结合散列函数
-----> List (可以包含重复的元素，是一个有序集合，可以存放空元素)
------ArrayList: 访问元素很快，插入、删除、移动较慢，线程是非同步的。
----- LinkedList: 插入、删除、移动方便，访问慢，非同步
------- Vector: 类似ArrayList，线程是同步的。
------- Stack: 继承Vector，实现一个后进先出的堆栈。
Map-----> (包含了Key-Value对，不能有重复的Key)
-- HashTable: 实现 Key-Value映射的哈希表，不允许空键，空值，线程是同步的
--- HashMap:与HashTable类似，允许空键，空值，线程是非同步的
-----TreeMap: 底层是二叉树结构，线程不同步，可用于给map集合中的键排序。
二、Set常用的实现类
HashSet: 此集合是基于哈希算法实现的，用数组保存数据。其中元素不能重复，查找效率相当高，缺省负载因子是0.75，负载因子通常不需要修改；依靠HaspMap来实现。性能比TreeSet要好，存放到此集合中的对象应该重写hashCode()和equals()。保证元素唯一性的原理：判断元素的hashCode值是否相同，如果相同，进一步判断equals方法是否为true。
我们通常应该使用HashSet，除非我们需要对存放的元素进行排序，那就用TreeSet。
TreeSet: 实现了SortedSet接口，依靠TreeMap来实现。是一个有序集合，其中元素按照升序排列，缺省是按照自然顺序排列，这就意味着存放到此集合中 的元素需要实现Comparable接口，覆盖compareTo方法。
另外，在元素自身不具备比较性，或者具备的比较性不是所需要的，需要按集合自身具备比较性，可以在构造TreeSet对象的时候指定一个实现了Comparator（比较器）接口的比较器对象，覆盖compare方法。
注意：当两者都存在，以比较器为主。
LinkedHashSet: 用链表保存数据。具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之外在于后者维护着一个运行于所有条目的双重链接列表。 此链接列表定义了迭代顺序，即按照将元素插入到set中的顺序（插入顺序）进行迭代。
注意，插入顺序不受在set中重新插入的元素的影响。
三、List常用的实现类
ArrayList: 是一种可增长数组的实现，底层采用数组实现。使用ArrayList的优点在于对get和set的调用花费常数时间。 其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在ArrayList的末端进行。 我们通常应该使用此集合替代Vector，除非确实需要同步列表。但是我们也可以使用Collections中的静态方法 synchronizedList(List<T> list)来得到一个线程安全的ArrayList对象。
Collections还提供了相应的方法来得到线程安全的Collection、 List、Set、 Map对象。
LinkedList: 底层采用一般的双向链表(double-linked list)完成，其中每个对象元素除了数据本身以外，还有两个分别指向前一个元素和后一个元素的引用。
如果我们需要经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用此集合。否则使用ArrayList性能会好一些。 其优点是新项的插入和现有项的删除均开销很小(这里假设变动项的位置是已知的)。其缺点是它不容易作索引，因此对get的调用是昂贵的，除非调用非常接近表的端点(如果对get的调用是接近表后部的项进行，那么搜索的进行可以从表的后部开始)。
Vector: 线程安全，底层采用数组实现，此类中的所有方法都是同步的，效率较低。但是比synchronizedList(List<T> list)方法来得到的List对象性能稍微要好一些，但是Vector有一些继承的操作使用起来要格外小心。如果不用考虑线程安全，我们应该用ArrayList集合。
Stack(栈): 此类从Vector继承而来，所以有了一些栈不应该有的特性，比如从Vector继承而来的ElementAt()方法等， 如果需要使用栈，我们可以自己去编写，可由LinkedList去实现一个栈。
四、Map常用的实现类
HashMap: 用数组保存数据。对Key进行散列，其中不能有重复的键，方法keySet()返回Set存放着Key中的元素，方法values()返回Collection存放着Value中的元素，方法entrySet()返回Set存放Map.Entry类型的元素，一个Map.Entry对象表示一个Key-Value对。Map.Entry接口中主要提供了方法getKey()和getValue()。此集合性能比TreeMap性能要好。我们通常应该使用HashMap，除非我们需要对存放的元素进行排序，那就用TreeMap。
Hashtable: 线程安全，此类中的所有方法都是同步的，效率较低。如果不用考虑线程安全，我们应该用HaspMap。 其中不能有重复的键，如果试图添加的键对象与原来的键对象重复，那么就将此键原来所对应的值替换为后来添加的值。
用作HashMap和Hashtable键对象的类，都应该覆盖Object.hashCode()和Object.equals()。
Map集合的常用方法：
1、添加 put(K key, V value) putAll (Map<? extends K,? extends V> m)
2、删除 clear() remove(Object key)
3、判断 containsValue(Object value) containsKey(Object key)
4、获取 get(Object key) size() values() entrySet() keySet()
方法注意：put方法添加元素时，如果出现添加相同的键，则后添加的值会覆盖掉原来的值，并且put方法会返回原来的值。get方法可以取出键所对应的值。
TreeMap: 实现了SortedMap接口，按照Key进行升序排列，缺省是按照自然顺序排列，这就意味着用作Key的元素需要实现Comparable接口，另外与TreeSet一样， 我们可以在构造TreeMap对象的时候指定一个实现了Comparator接口的比较器对象。
Map集合的常用两种取值方式：
1、keySet，将map集合中所有的键存入Set集合，因为Set具有迭代器，所以可以根据迭代方式取出所有的键，然后用get方法取出对应的值。
2、entrySet ，将map集合中的映射关系取出，存入到set集合中，返回Set<Map.Entry<k，v>>，再根据迭代方式取出所有的映射关系，然后使用Map.Entry的getKey()、getValue()方法获取关系中的键和值。
下面是一个使用Map集合查找字符串中字符出现的个数的例子
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class MapTest3 {
public static void main(String[] args) {
String str=get("aaabbcdfgshsb");
System.out.println(str);
}
public static String get(String str){
int count=0;
char[] ch=str.toCharArray();
TreeMap<Character,Integer> tm=new TreeMap<Character,Integer>();
for(int x=0;x<ch.length;x++){
if(!(ch[x]>='a'&&ch[x]<='z'||ch[x]>='A'&&ch[x]<='Z'))
continue;
Integer value=tm.get(ch[x]);
if(value!=null)
count=value;
count++;
tm.put(ch[x], count);
count=0;
}
StringBuilder sb=new StringBuilder();
Set<Map.Entry<Character,Integer>> entrySet=tm.entrySet();
Iterator<Map.Entry<Character,Integer>> it=entrySet.iterator();
while(it.hasNext()){
Map.Entry<Character, Integer> me=it.next();
Character ch1=me.getKey();
Integer value=me.getValue();
sb.append(ch1+"("+value+")");
}
return sb.toString();
}
}
LinkedHashMap: 用链表保存数据。Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。 此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。 注意，如果在映射中重新插入键，则插入顺序不受影响（如果在调用m.put(k, v)前m.containsKey(k)返回了true，则调用时会将键 k 重新插入到映射m中。）
Properties: 从Hashtable继承而来，表示了一个持久的属性集。也是存储Key-Value对，只是此类可以从输入流填充Key-Value对。 属性列表中每个键及其对应值都是一个字符串。链表有单向链表，循环链表，双向链表和双向循环链表。我们可以用LinkedList实现栈数据结构。
集合、数组相互转换
Collection中的toArray()方法可以将集合转换成Object数组，<T> T[ ] toArray(T[ ] a)可以将集合转换成相应类型的数组。注意，toArray(new Object[0]) 和 toArray() 在功能上是相同的。
Arrays.asList(T... a)可以将数组转换为集合类List。返回的List集合是个固定尺寸大小的集合，不能往里面添加元素和删除元素，只能修改元素的内容。
Arrays.asList(T... a)方法和Collection.toArray()方法一起，充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。
Collection接口提供了一个方法iterator()，返回一个可迭代的Iterator对象。Iterator迭代器给我们提供了一种通用的方法来访问集合中的元素，Iterator接口中只有三个方法：hasNext()、 next()、 remove()。
Collections 类可以对集合类进行很多的操作，里面的方法全部是静态方法，其中的一个方法是sort(List<T> list) 可以对List类型的集合进行排序。但是在List中的元素类型要实现了Comparable接口。
五、集合泛型的使用
JDK1.5为了保证安全问题，使用了泛型，是一种安全机制。可以用来明确集合内元素的类型，好处是将运行时期出现的问题ClassCastException，转移到了编译时期，方便程序员解决问题，让程序运行更加安全。而且还避免了从集合取元素时，避免了强制转换的麻烦。
泛型格式：通过<>来定义要操作的引用数据类型，集合中十分常用。
泛型可以定义在类上，称为泛型类，当类中要操作的引用数据类型不确定时，早期使用Object来完成扩展，现在可以定义泛型完成扩展。泛型类定义的泛型，在整个类中有效，如果方法被使用，泛型类对象明确操作的类型后，类型会固定，方法上的类型不能改变。
Class Demo<T> ｛public void show(T t){ p("show" +t) }
为了让方法可以操作不同类型，泛型也可以定义在方法上。方法的泛型是放在返回值前面，修饰符后面。
Class Demo ｛public <T>void show(T t){ p("show" +t) }
注意，泛型类和泛型方法可以同时使用。静态方法不可以访问类上的定义的泛型，但可以定义在方法上。泛型可以使用<?>通配符，
下面是个小例子，
class MyComparator implements Comparator<Student>{
public int compare(Student st1,Student st2){
int num= st1.getName().compareTo(st2.getName());
if(num==0){
return new Integer(st1.getAge()).compareTo(new Integer(st2.getAge()));
}
return num;
｝
六、 ArrayList与HashSet的比较
ArrayList里面存储的元素是按照我们添加元素的顺序有序的排列，其中的元素可以是重复的对象。HashSet里面存储的元素并不是按照我们添加元素的顺序进行排列的，而是按照哈希值分别存储到不同的区域，其中的元素不能是重复的对象。
有一种用哈希算法来提高从集合中查找元素的效率的方式，这种方式将集合分成若干个存储区域，每一个要存进来的对象可以算出一个值（哈希码值），然后将哈希码分组，每组分别对应某一个存储区域，然后根据一个对象的哈希码就可以确定该对象应该存储在哪个区域。
HashSet就是采用哈希算法来存取对象的集合，它内部采用对某个数字n进行取余的方式对哈希码进行分组和划分对象的存储区域，Object类中定义了一个hashCode()方法，来返回每个java对象的哈希码，当从HashSet中查找某个对象时，java系统首先调用对象的hashCode()方法，获得该对象的哈希码，然后根据哈希码找到相应的存储区域，最后取出该存储区域内的每个元素与该对象进行equals()方法比较，这样不用遍历集合中的所有元素就可以得到结论。
总的来说hashCode()的返回值是用来确定存取对象所在的区域，而真正比较两个对象在业务逻辑上是否等同的方法还是equals()方法。
可见HashSet集合具有很好的对象检索性能，但是HashSet存储对象的效率相对要低些。
所以说为什么存储在采用哈希算法来存取对象的集合里面的对象要同时重写equals()方法和hashCode()方法，因为如果两个对象采用equals()方法比较是否等同，但是如果他们返回的哈希值不同，就很有可能分别存储在不同的存储区域，那么这种情况下两个相同的对象就被存储到这个集合里面了。所以只有同时重写equals()方法和hashcode()方法，让用equals()方法比较是等同的两个对象返回相同的哈希值，才能保证HashSet集合里面存储对象的唯一性。
hashCode()方法返回一个哈希值，一般对象的哈希值是用内存地址算出来的，除非我们重写了hashCode()方法，注意：hashCode()方法只有在采用哈希算法来存取对象的集合中才有价值。
有一个问题得注意： 当一个对象被存储进HashSet集合之后，就不能修改这个对象中那些参与哈希值计算的字段，否则，对象修改后的哈希值与最初存储进HashSet时的哈希值就不同了，在这种情况下，即使在contains方法使用该对象的当前引用作为参数去HashSet集合中检索对象也将找不到对象，因为参与哈希值计算的字段被修改了，那么这个对象就有可能存储在另外的区域，这时还在原来的哪个区域找这个对象，肯定就无法找到了，这将导致无法从HashSet集合中单独删除当前对象，从而造成内存泄漏。
下面是关于hashCode()和equals()方法重写的例子：
public class PointHashCode {
private int x;
private int y;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
PointHashCode other = (PointHashCode) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
}