集合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方法,因为取数据,也需要这两个方法。
posted on 2005-12-06 23:13
北国狼人的BloG 阅读(907)
评论(1) 编辑 收藏 所属分类:
达内学习总结