集合java.util.*

一个对象，容纳多个对象，用于维护一系列相似对象。数组是一种简单集合。

程序中，如何管理数据，需要一种数据结构。（数组是一种线形结构）。

Java的集合框架是通过一系列接口和一些层级类形成的一套体系。

通过接口来查看整个集合框架，并分类来进行学习和研究。

概述：

Collection接口的一个对象会把数据按照一维线形组织。里面都是对象。

List代表，会按照元素的相应顺序来组织，元素的顺序有关系有意义。元素可重复。

Set是数学中集合的概念，顺序无关不可重复。

SortedSet特殊按照元素数值把元素进行排序，添加元素自动排序。

Map是由键对象和值对象组成的键-值对儿的集合。

用不可重复的键值，去对应一个value值的集合。

SortedMap 如果可以根据key值排序，可以是一个SortedMap

============================================

常用实现类
List接口实现类
java.util.ArrayList

长度可变数组，内部采用数组实现（一种组合关系，内部有一个object[]），有一个增长因子来控制增幅。

ArrayList遍历时，并不丢失顺序信息，就是添加顺序。

两种遍历方式，
非通用方式，通过size()方法，for循环。
  ArrayList al = new ArrayList();
  al.add(new Integer(10000));
  al.add(new Integer(200000));
  al.add(new Integer(1000000));
  for(int i = 0; i < al.size(); i++)
  {
   System.out.println(al.get(i));
  }

通用方式，迭代器。

printCollection(Collection c){
      Iterator it = c.iterator();
      while(it.hasNext())
      {
         it.next();
      }
}

记住iterator()方式是在Collection接口中定义的，也就是说所有Collection接口的实现类都要实现这个方法。都可以通过它来遍历，Set也一样。

java.util.Collections是一个工具类，里面有很多静态方法。

有一个给List排序的方法sort，static sort(List list)，另外一种重载形式static sort(List list,Comparator c)。记住可是对List接口的对象排序。

一个ArrayList内部是字符串的话，调用Collections.sort(al);   元素按照字母升序规则进行排序。如果是数字，从大到小。

排序这件事，由两个部分组成，1，排序规则，2，算法。
算法，数据结构学过的几种常见排序算法，冒泡，二叉树，等，在Java中封装了很多算法，不需要自己实现。

而规则，绝对需要自己来定义，尤其对于自定义类的对象的排序规则，也就是对象大小的依据。

两种方式：

1自定义类实现java.lang.Comparable接口。覆盖其public int compareTo(Object o)方法。

public int compareTo(Object o)
{
 Student s = (Student)o;
 if(this.age > s.age) return 1;
 else if(this.age == s.age) return 0;
 else return -1;
}

或者对String 类型属性，可以：

return this.name.compareTo(((Student)o).name);

2再写一个类实现java.util.Comparator，比较器接口，实现自己的比较器。

实现public int compare(Object o1,Object o2)方法。

o1 > o2 返回正数
o1 = o2 返回0
o1 < o2 返回负数

还有一个boolean equals(Object obj)，用自己写么？不用！从Object继承就有了。

class MyComparator1 implements Comparator{
    public int compare(Object o1, Object o2)
    {
        Student s1 = (Student)o1;
        Student s2 = (Student)o2;
        return s1.age - s2.age;
    }
}

Collections.sort(List list, Comparator c)

这种方式可以定义多个排序规则，分别按照对象不同属性排序。

第一种方式，在更改排序规则时，需要更改代码，而第二种是一种扩展的方式。

使用比较器的方式，开发中很常见。

注意MyComparator1与Student类联系很紧密，可以采用内部类的方式来实现。

import java.util.Comparator;

public class Employee {

    public Employee() {
        super();
    }
    
    public Employee(String name, int id, double salary)
    {
        this.name = name;
        this.id = id;
        this.salary = salary;
    }
    
    @Override
    public boolean equals(Object o)
    {
        if(this == o)
            return true;
        if(o == null)
            return false;
        if(!(o instanceof Employee))
            return false;
        Employee e = (Employee)o;
        if(this.name.equals(e.name)&& this.id == e.id && this.salary == e.salary)
            return true;
        else return false;
    }
    
    @Override
    public String toString(){
        return "Name: " + this.name + " ID: " + this.id; 
    }
    
    public Comparator getNameCmp()
    {
        return new NameSorter();
    }
    
    public Comparator getIdCmp()
    {
        return new IdSorter();
    }
    
    private class NameSorter implements Comparator{
        
        NameSorter(){}
        
        public int compare(Object o1, Object o2) {
            return ((Employee)o1).name.compareTo(((Employee)o2).name);
        }
        
    }
    
    private class IdSorter implements Comparator{
        IdSorter(){}
        
        public int compare(Object o1, Object o2)
        {
            return ((Employee)o1).id - ((Employee)o2).id;
        }
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getSalary() {
        return salary;
    }

    public void setSalary(double salary) {
        this.salary = salary;
    }

    private String name;

    private int id;

    private double salary;

}

import java.util.*;

public class TestSortEmployee {

    public TestSortEmployee() {
        super();
        // TODO Auto-generated constructor stub
    }
    
    public static void main(String[] args)
    {
        List<Employee> l = new ArrayList<Employee>();
        l.add(new Employee("HAC",6,2323.0));
        l.add(new Employee("ABC",3,3244.0));
        l.add(new Employee("FSA",7,5633.0));
        Iterator<Employee> it = l.iterator();
        System.out.println("before sort");
        while(it.hasNext()){
            Employee e = it.next();
            System.out.println(e);
        }
        Collections.sort(l,new Employee().getNameCmp());
        System.out.println("after sort");
        for(Employee e : l)
        {
            System.out.println(e);
        }        
    }
}

构建装入固定类型的ArrayList。
public class MyArrayList extends ArrayList{
      public boolean add(Object o){
         if(o instanceof String)
            return super.add(o);
         else ruturn false;
      }
}

JDK 5.0以后，可以使用范型来解决这个问题。很清楚，很方便，很安全。

LinkedList

底层为双向循环链表

可以双向找到前后的节点，最后头尾链接，形成一个环状。

特点：查寻效率低（从头节点遍历），插入删除效率高。

ArrayList

底层为数组，删除插入效率低，查询效率高。



LinkedList，可用于构建堆栈，或者队列。

import java.util.*;
class MyStack
{
    private LinkedList ll=new LinkedList();
    public void push(Object o)
    {
        ll.addFirst(o);
    }
    public Object pop()
    {
        return ll.removeFirst();
    }
    public boolean empty()
    {
        return ll.isEmpty();
    }
    public static void main(String[] args)
    {
        MyStack ms=new MyStack();
        ms.push("one");
        ms.push("two");
        ms.push("three");
        
        System.out.println(ms.pop());
        System.out.println(ms.pop());
        System.out.println(ms.empty());
    }
}

只使用LinkedList的一端。

注意：java.util.Stack，这个现成的类，不要用，因为其父类是java.util.Vector，效率较低下。

import java.util.*;
class MyQueue
{
    private LinkedList ll=new LinkedList();
    public void put(Object o)
    {
        ll.addLast(o);
    }
    public Object get()
    {
        return ll.removeFirst();
    }
    public boolean empty()
    {
        return ll.isEmpty();
    }
    public static void main(String[] args)
    {
        MyQueue mq=new MyQueue();
        mq.put("one");
        mq.put("two");
        mq.put("three");
        
        System.out.println(mq.get());
        System.out.println(mq.get());
        System.out.println(mq.get());
        System.out.println(mq.empty());
    }
}

注意JDK 5.0中，已经提供现成的队列类，无需自己实现。



Set接口有一个实现类，HashSet。

可以使用迭代器进行遍历。

对于其中元素：
1.无序，增加的顺序与遍历结果顺序无关。（实际有序，后面说）
2.元素不可重复。

HashSet，底层也是数组，它是如何插入数据的呢？

数组有一个长度，假设为6，hs.add(Object obj)操作进行时，先获得obj的哈希码，然后%6，也就是hashcode模数组长度，来决定该obj对象放入数组哪个位置。

如果恰巧两个对象的hashcode模长度得到相同的值，那么就会先判断这两个对象是否相等，也就是调用对象的equals方法。如果真的不同，通过某种算法将后面的对象找一个新的位置放置。

所以对于自定义类，需要同时覆盖hashCode()方法和equals方法。

两个原则，1，保证相同对象的hashCode一定相同,(保证肯定要真正调用equals比较，否则直接就放入了)
                     2,   不同对象的hashCode尽可能不同。(hashCode相同情况出现，会使得HashSet效率急剧下降)

public int hashCode(){
      return name.hashCode() + age;
}

public boolean equals(Object o)
{
      ...
}

HashSet特点，查询效率高，插入效率高，删除效率高。抱着这些的是牺牲了空间，因为那个底层的数组为保证不冲突，可能初始开辟一个极其大的长度。

问题：1无序（遍历出来的顺序是那个底层数组存放的顺序）
            2.明显用空间换时间。

hashCode和equals覆盖，缺一不可。



SortedSet子接口有一个实现类TreeSet，自动对元素排序。

可用迭代器遍历。

不允许元素重复。

增加元素自动排序。

注意，不再需要hashCode+equals方法来判断对象重复了，而是使用比较器，或者实现Comparable接口的compareTo()方法。

Map接口 与Collection接口无关系，它表示的集合，内部每个元素是一个键-值对。

把一系列对象通过一个关键字来存放，key不能重复，value可重复。

Map m = new HashMap();

put(Object key, Object value)存放键和值,返回值为Object。

遍历方法，通过Map接口提供的keySet()方法，会返回一个Set类型无序集合，存放着key对象（KEY不重复阿，所以是一个Set）。

Set s = m.keySet();
Iterator it = s.iterator();
while(it.hasNext()){
    Object key = it.next();
    Object value = m.get(key);
}

如果key值被认定重复，后面添加的key重复的纪录会覆盖前面的纪录，不报错，并把替换掉的value对象作为返回值返回，key不重复时，返回为null。

那么又会有一问题，Map是如何判断key对象是否重复的呢？尤其对于自定义类的对象。

HashMap底层也是数组。

说到这，得先回过去，说说HashSet，因为实际上察看源码发现，它的内部实际上有一个HashMap作为支持，实现元素的不可重复。只不过它使用key部分，value部分为一个final的Object()。（TreeSet与TreeMap也是这样）。

所以，如果key对象为自定义类对象，那么它需要覆盖equals()和hashCode()。

一个接口，有很多实现类，如何选择，在于人的编程经验。

List（有序）vs Set(无序) vs Map(键值)

对于TreeMap和TreeSet，只在需要排序时，使用一下，因为他们每次插入新元素，都会重新排序。

Hashtable，1.3以前使用，使用Enumeration遍历，线程安全，重量级组建。




TreeMap对于元素排序，是需要该类实现Comparable接口，实现compareTo方法的。它可以通过该方法判断俩个自定义类对象是否相同，并且进行排序。

=========================================

开发经验，一旦程序中使用，HashMap，Key放入的自定义类的对象，一定要覆盖hashCode和equals方法，因为取数据，也需要这两个方法。