随笔-159  评论-114  文章-7  trackbacks-0

集合java.util.*

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

程序中,如何管理数据,需要一种数据结构。(数组是一种线形结构)。

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

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


Collection.jpg

概述:

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

底层为双向循环链表

22.gif

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

特点:查寻效率低(从头节点遍历),插入删除效率高。

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方法,因为取数据,也需要这两个方法。




 



posted on 2005-12-06 23:13 北国狼人的BloG 阅读(907) 评论(1)  编辑  收藏 所属分类: 达内学习总结

评论:
# re: 达内第十五天,第十六天 Core Java 之 集合框架 2005-12-14 19:19 | DJ
看了你的文章感觉受益非浅!!希望赶快更新!  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: