2015-10-27

Java-集合

Java是面向对象的语言，实际操作中经常会遇到对多个对象进行操作的情况。但StringBuffer类存在只能操作字符串、数组类存在必须定义长度的问题，Java语言为我们提供了集合来操作动态的一组对象。同时Java中的集合类库也将常用的基本数据结构封装起来供开发者使用。

一、集合类的总体结构

Collection 是 Java 中所有单例集合根接口，下面 List 和 Set实现了 Collection 接口同时有不同的特点。

—-| Collection 单例集合的根接口

——-| List 如果是实现了 List 接口的集合类，该集合类具备的特点：有序、可重复。

————| ArrayList ArrayList 底层是维护了一个Object数组实现的。特点：查询速度快，增删慢。
————| LinkedList LinkedList 底层是使用了链表数据结构实现的，特点：查询速度慢，增删快。
————| Vector底层也是维护了一个Object的数组实现的，实现与ArrayList是一样的，但是Vector是线程安全的，操作效率低。

——-| Set 如果是实现了 Set 接口的集合类，该集合具备的特点：无序，不可重复。

———–| HashSet 底层是使用了一个哈希表支持的，特点：存取速度快。
———–| TreeSet 底层是使用了二叉树实现的，特点：会对元素进行排序存储。

—-| Map 双例集合接口（没有实现collection）

———–| HashMap 底层是使用了一个哈希表支持的
———–| TreeMap 底层是使用了二叉树实现的，特点：会对元素进行排序存储。
———–| Hashtable 类似 Vector 线程安全但效率比较低，不推荐使用。

二、Collection 极其方法总结

1.基本的增删查改

增加
boolean add(Object obj):添加一个元素
boolean addAll(Collection c):添加一个集合的元素

删除

void clear():移除所有元素
boolean remove(Object o):移除一个元素    （boolean返回值都是成功与否）
boolean removeAll(Collection c):移除一个集合的元素

判断

boolean contains(Object o)：判断集合中是否包含指定的元素
boolean containsAll(Collection c)：判断集合中是否包含指定的集合元素
boolean isEmpty()：判断集合是否为空

长度

int size(Collection C):元素的个数 （数组、String都有 length() 方法,集合类只有size方法）

交集

boolean retainAll(Collection c): 仅保留此 collection 中那些也包含在指定 collection 的元素(保留两个集合的交集)，如果此集合发生更改，则返回true。

把集合转换为数组

Object[] toArray(Collection c)

2.集合的遍历

集合的遍历通常有两种方式，传统的迭代器方式以及JDK1.5后新加入的for-each语句的方式（增强for循环）

2.1 迭代器 Iterator iterator()
iterator()方法是java.lang.Iterable接口,被Collection继承。
Java 中的迭代器对象类似于C类语言中的指针概念，但迭代器在抓取集合元素的过程中只允许单向移动。（ListIterator 可以对List实现类的集合进行双向遍历）

需要注意的是，迭代器的“指针”指向的实际上是元素之前的位置，而不是元素上。

常用的方法有

iterator() 要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。
next() 获得序列中的下一个元素。
hasNext() 检查序列中是否还有元素。
remove() 将迭代器新返回的元素删除。

iterator 中没有 add 方法，当获取到某个集合的迭代器对象时，迭代器就已经知道集合中所有元素的引用，当再次添加元素时，迭代器是不知道的，这就造成了两者的不一致，JVM会抛出ConcurrentModificationException异常。

一个简单的例子：


list l = new ArrayList();
l.add("aa");
l.add("bb");
l.add("cc");
/*迭代器用于while循环
Iterator iter = l.iterator();
while(iter.hasNext()){
 String str = (String) iter.next();
 System.out.println(str);
}

2.2 for-each 语句（增强for循环）

for-each 循环能以一种非常简洁的方式对集合中的元素进行遍历（数组等也可以），如下所示：

for (Object o : collection)
System.out.println(o);

三、List 集合

List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList，具有元素排列有序、元素可重复的特征。可以将仸何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，实际上它在底层维护了一个Object数组，在内存中进行连续存储，因此它的随机访问速度极快（利用索引值），但不适合对其中的元素进行增删。而 LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作，而随机访问需要遍历链表因此效率较低。

1.List集合的基本方法

List 集合类实现了 Collection 接口的全部方法，同时还添加了一些新的方法：

addAll()和inserts()两个方法进行元素的批量插入操作。

E get(int index)
E set(int index, E element)
void add(int index, E element)
E remove(int index) //这些方法可以通过传入索引值与集合两个参数使用。

subList(int fromIndex, int toIndex) 方法根据索引值返回一个子集合，[romIndex, toIndex) 前闭后开。

boolean Contains(Object obj)这个方法用来判断一个集合中是否包含特定对象，其底层依赖的是equals()方法，即通过对象的地址值比较两个对象是否相等。(可以进行重写以满足特定需求)

2.List迭代器

List 集合实现了功能更加强大的迭代器 ListIterator 。

比起 Iterator 迭代器，ListIterator只能用于实现List接口的集合类中，但它的功能也更为强大：

2.1 两种迭代器都能实现遍历查看、删除操作，但ListIterator迭代器可以实现集合元素的添加、修改工作，对应的方法分别是

add(E e): 将指定的元素插入列表，插入位置为迭代器当前位置之前

set(E e)：从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e

2.2 ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。

2.3 ListIterator 可以定位当前索引的位置，nextIndex()和previousIndex()两个方法可以实现。Iterator没有此功能。

2.4 remove()方法从列表中删除next()或previous()返回的最后一个元素（有点拗口，意思就是对迭代器使用hasNext()方法时，删除ListIterator指向位置后面的元素；当对迭代器使用hasPrevious()方法时，删除ListIterator指向位置前面的元素）

一个简单的程序实例：

mport java.util.LinkedList;  
import java.util.List;  
import java.util.ListIterator;  
  
public class ListIteratorTest {  
  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        List<String> staff = new LinkedList<>();  
        staff.add("AAA");  
        staff.add("BBB");  
        staff.add("CCC");  
        ListIterator<String> iter = staff.listIterator();  
        String first = iter.next();  
          
        //删除AAA
        //iter.remove();  
          
        //把AAA改为DDD  (在上一个语句的基础上)
        //iter.set("DDD");  

        //添加EEE元素
        //iter.add("EEE");
              
        //遍历List元素    
        iter = staff.listIterator();            //listIterator方法返回一个 ListIterator 迭代器
        System.out.println("遍历List中元素，方法二：");  
        while(iter.hasNext())  
        {  
            System.out.println(iter.next());  
        }  
    }  
  
}

四、set集合

实现了Set接口的集合具有的特点是无序、不可重复，无序是指元素在存储时不会依据存入时的顺序排列，而是根据Comparable接口中的比较规则进行排列，不可重复性则依靠底层的HashCode()、equals()两个方法来进行判断”是否重复”。

1.HashSet 集合

HashSet集合的底层是使用了哈希表来支持的，特点：存取速度快.

hashSet的add()方法比较特殊，会返回false值，因为往Haset添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。

因此，可以通过重写自定义类的 HashCode()(改变返回值即可)、与equals()两个方法来实现一些特定的功能(比如用HashSet集合存储居民信息，HashCode返回ID、equals方法返回ID之差可以避免添加ID相同的居民)。

一个简单的例子：

import java.util.HashSet;
import java.util.Scanner;

/*
 需求： 接受键盘录入用户名与密码，如果用户名与密码已经存在集合中，那么就是视为重复元素，不允许添加到HashSet中。
  */
class User{
	String userName;
	String password;
    public User(String userName, String password) {
		super();
		this.userName = userName;
		this.password = password;
	}
	
	@Override
	public String toString() {
		return "{ 用户名："+this.userName+" 密码："+ this.password+"}";
	}

	@Override
	public boolean equals(Object obj) {
		User user = (User)obj;
		return this.userName.equals(user.userName)&&this.password.equals(user.password);
	}
	
	@Override
	public int hashCode() { //  abc 123   ， 123 abc
		return userName.hashCode()+password.hashCode();
	}
	
}

public class Demo3 {
    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		HashSet set = new HashSet();
		
		
		while(true){
			System.out.println("请输入用户名:");
			String userName = scanner.next();
			System.out.println("请输入密码：");
			String password = scanner.next();
			//创建一个对象
			User user = new User(userName, password);
			if(set.add(user)){
				System.out.println("注册成功...");
				System.out.println("当前的用户有："+ set);
			}else{
				System.out.println("注册失败...");
			}
		}
			
	}

}

2.TreeSet 集合

TreeSet 实质上是将二叉树的数据结构进行封装，根据自然顺序或者比较器的定义来判断元素的先后顺序。

2.1 treeSet添加自定义元素的一些注意事项

a. 往TreeSet添加元素的时候，如果元素本身具备了自然顺序的特性，那么就按照元素自然顺序的特性进行排序存储。
b. 如果元素本身不具备自然顺序的特性，那么该元素所属的类必须要实现Comparable接口，把元素的比较规则定义在compareTo(T o)方法上。
c. 如果比较元素的时候，compareTo方法返回的是0，那么该元素就被视为重复元素，不允许添加。(注意：TreeSet与HashCode、equals方法没有任何关系)
d. 往TreeSet添加元素的时候, 如果元素本身没有具备自然顺序的特性，而元素所属的类也没有实现Comparable接口，那么必须要在创建TreeSet的时候传入一个比较器。
e. 往TreeSet添加元素的时候，如果元素本身不具备自然顺序的特性，而元素所属的类已经实现了Comparable接口，在创建TreeSet对象的时候也传入了比较器，以比较器的比较规则优先使用。(推荐使用比较器，使得定义的比较规则可以重复利用)

<注意> 所谓的“本身具备自然顺序”实际上是Java平台让一些常用的具有自然顺序的对象所属的类实现了Comparable接口，包括数字类、字符串类、日期类、文件类等等。

2.2 Comparable接口与比较器

a.Comparable 接口的使用

集合中需要排序的自定义元素类来实现Comparable接口，并实现comparaTo方法定义比较规则。compareTo方法返回的应该是关键元素（差值有意义）的差值，CompareTo方法只传入一个形参，形参与对象

一个例子：

   class  Emp implements Comparable<Emp>{

      int id;
      String name;
      int salary;

public Emp(int id, String name, int salary) {
	super();
	this.id = id;
	this.name = name;
	this.salary = salary;
}

@Override
public String toString() {
	return "{ 编号："+  this.id+" 姓名："+ this.name+" 薪水："+ this.salary+"}";
}

//@Override //元素与元素之间的比较规则。
// 负整数、零或正整数，根据此对象是小于、等于还是大于指定对象。 
public int compareTo(Emp o) {
   //		System.out.println(this.name+"compare"+ e.name);
    	return this.salary- o.salary;
     }	
     }

b.比较器

自定义比较器需要实现Comparator接口（可以使用泛型），实现其中的 int compare(Object o1, Object o2) 方法，最后在创建TreeSet集合时传入比较器对象。

一个简单的示例：

    //自定义一个比较器
class MyComparator implements Comparator<Emp>{  //泛型实现方法

	@Override
	public int compare(Emp o1, Emp o2) {        //需要传入两个形参
		return o1.id-o2.id;
	}
	
	/*@Override
	public int compare(Object o1, Object o2) {   //普通方法，需要强制类型转换
		Emp e1 = (Emp) o1;
		Emp e2 = (Emp) o2;
		return e1.id - e2.id;
	}*/
	
	
}


public class Demo6 {
	
	public static void main(String[] args) {
		//创建一个比较器对象
		MyComparator comparator = new MyComparator();
		//创建TreeSet的时候传入比较器
		TreeSet tree = new TreeSet(comparator);
		
		tree.add(new Emp(110, "AA", 100));
		tree.add(new Emp(113, "BB", 200));
		tree.add(new Emp(220, "CC", 300));
		tree.add(new Emp(120, "DD", 500));
		System.out.println("集合的元素："+tree);
		
	}
}

五、Map 双例集合

1.Map集合的基本方法

Map集合是包含键值对的元M素的集合，键、值都可以是任意的对象，不能包含重复的键，并可通过键实现对值的快速访问。Map集合的一些基本的增删查改方法：

put(K key, V value)
putAll(Map<? extends K,? extends V> m)

remove(Object key)
clear()

get(Object key)
size()

containsKey(Object key)
containsValue(Object value)
isEmpty()

keySet()
values()
entrySet() //迭代遍历

几个简单的示例说明这些方法：
a.

public class Demo1 {
	
	public static void main(String[] args) {
		Map<String,String> map = new HashMap<String, String>();
		//添加方法
		map.put("汪峰", "章子怡");
		map.put("文章", "马伊琍");
		map.put("谢霆锋","张柏芝");
		
		System.out.println("返回值："+map.put("谢霆锋","黄菲"));  
		// 如果之前没有存在该键，那么返回的是null，如果之前就已经存在该键了，那么就返回该键之前对应的值。
		Map<String,String> map2 = new HashMap<String, String>();
		map2.put("杨振宁", "翁帆");
		map2.put("习总", "彭丽媛");
		map.putAll(map2); // 把map2的元素添加到map集合中。
		
		//删除方法
		System.out.println("删除的数据是:"+map.remove("汪峰")) ;  //根据键删除一条map中的数据，返回的是该键对应的值。
		map.clear(); //清空集合中的所有数据。
		
		//获取方法
		System.out.println("根据指定的键获取对应的值:"+ map.get("文章"));
		System.out.println("获取map集合键值对个数："+map.size());
		
		//判断方法
		System.out.println("判断map集合是否包含指定的键："+ map.containsKey("文章"));
		System.out.println("判断map集合中是否包含指定的值："+ map.containsValue("张柏芝"));
		map.clear();
		System.out.println("判断map集合是否为空元素："+ map.isEmpty());
		*/
		System.out.println("集合的元素："+ map);
		}
	}

public class Demo2 {

	public static void main(String[] args) {
		Map<String,String> map = new HashMap<String, String>();
		//添加方法
		map.put("汪峰", "章子怡");
		map.put("文章", "马伊琍");
		map.put("谢霆锋","张柏芝");
		
		//map集合中遍历方式一： 使用keySet方法进行遍历,返回Map中的所有键，没有值。 
		Set<String> keys = map.keySet();  //keySet() 把Map集合中的所有键都保存到一个Set类型的集合对象中返回。
		Iterator<String> it = keys.iterator();  //使用迭代器遍历Set集合显示输出
		while(it.hasNext()){
			String key = it.next();
			System.out.println("键："+ key+" 值："+ map.get(key));
		}
		
		
		
		//map集合的遍历方式二： 使用values方法进行遍历，返回所有的值，没有键。
		Collection<String>  c = map.values(); //values() 把所有的值存储到一个Collection集合中返回。
		Iterator<String> it = c.iterator();
		while(it.hasNext()){
			System.out.println("值："+ it.next());
		}
		*/
		
		//map集合的遍历方式三： entrySet方法遍历，同时获得Map中的键和值
		Set<Map.Entry<String,String>>  entrys = map.entrySet(); 
		Iterator<Map.Entry<String,String>> it = entrys.iterator();
		while(it.hasNext()){
			Map.Entry<String,String> entry = it.next();
			System.out.println("键："+ entry.getKey()+" 值："+ entry.getValue());
		}
		}
}

2.HashMap和TreeMap

2.1 HashMap

HashMap和HashSet集合类似，往HashMap添加元素的时候，首先会调用键的hashCode方法得到元素的哈希码值，然后经过运算就可以算出该元素在哈希表中的存储位置。如果算出的位置目前没有任何元素存储，那么该元素可以直接添加到哈希表中。如果算出的位置目前已经存在其他的元素，那么还会调用该元素的equals方法与这个位置上的元素进行比较，如果equals方法返回的是false，那么该元素允许被存储，如果equals方法返回的是true，那么该元素被视为重复元素，不允许存储。唯一的区别是，当使用put方法时集合中有相同的键，那么后添加的数据的值会取代之前的值。

2.2 TreeMap

TreeMap也与单列集合中的TreeSet集合相类似。需要键所属的类实现Comparable接口，或者在创建TreeMap对象的时候传入比较器（也是键对象之间的比较规则）。

一个简单的例子：

class Emp {      

	String name;
	int salary;

	public Emp(String name, int salary) {
		super();
		this.name = name;
		this.salary = salary;
	}
	@Override
	public String toString() {
		return "[姓名："+this.name+" 薪水："+ this.salary+"]";
	}
	
}
//自定义一个比较器,按salary排序
class MyComparator implements Comparator<Emp>{

	@Override
	public int compare(Emp o1, Emp o2) {
		return o1.salary - o2.salary;
	}
	
}
public class Demo6 {
	public static void main(String[] args) {
	    //创建一个自定义比较器
		MyComparator comparator = new MyComparator();
		TreeMap<Emp, String> tree = new TreeMap<Emp, String>(comparator);
		tree.put(new Emp("家宝", 1000),"002");
		tree.put(new Emp("习总", 3000),"003");
		tree.put(new Emp("克强", 5000),"005");
		tree.put(new Emp("财厚", 5000),"008");
		System.out.println(tree);
		}
}