Java数据结构与排序

一、引子:想要给ArrayList排序却发现没有排序方法?你有两种选择:

          1、换用TreeSet;

        2、使用Collection.sort(List<T> list) / Collection.sort(List<T> list, Comparator<? super T> c)方法。

二、展开分析Java的几种主要数据结构及其排序方法:

LinkedList 高效操作元素
TreeSet  不重复,有序
HashSet 不重复,快速查找
HashMap  NVP(key不能重复),按Hash算法来存储,取出与存入顺序常常不一致
LinkedHashMap  NVP(key不能重复),可记住元素插入的顺序,取出与存入顺序一致

     PS:  HashSet<T>.addAll(ArrayList<T>) 可以这样将所有的元素加进去

三、类型参数与泛型

  在API中常常看见的
                public class ArrayList<E> extends AbstractList<E> {...}
      这里的E会被实际传入的真正类型所取代,这个真正类型也称为类型参数。类ArrayList<E>被称为泛型的类
      同样的,泛型的方法代表着方法声明用到类型参数。有两种运用方式:
      (1)在使用了该类型参数的类中使用     
1  public class ArrayList<E> extends AbstractList<E>{
2         public boolean add( E o){
3         ......
4         }
5 }
      (2)在未使用该类型参数的类中使用,但不能将任何东西加入到集合中,只能读及调用方法:
                (在返回类型前加上声明)        
1  public <T extends Animal> void takeThing(ArrayList<T> list){
2         .....
3 }
             或者使用?              
1 public void takeThing(ArrayList<? extends Animal> animals){
2        .....
3 }
             需要注意:这和以下代码代表的意思是不一样的:
1  public void takeThing(ArrayList<Animal> list){
2         .....
3 }
             前者是表示类型参数只要是Animal或其子类就可以而后者只能是Animal
               如果说对后者有了不正确的操作,比如加入了Animal的子类,也只会在运行期间才会被发现。
               在泛型中,extend代表extend或implement

四、使用Collections.sort(List<T> list)方法

      (一)对存放String的ArrayList排序
                
1 ArrayList<String> songList = new ArrayList<String>();
2 Collections.sort(songList);

 

      (二)对存放对象的ArrayList排序
                (1)对象需要实现Comparable<E>接口(重写compareTo方法,在里面写上比较逻辑),例:
                      
1 public int compareTo( Song s ){
2        return title.compareTo( s.getTitle() );
3 }
                (2)步骤与对String排序相同。
 
五、使用Collections.sort(List<T> list, Comparator<? super T> c)方法
      该方法是使用自制的Comparator来帮助排序,以实现更加灵活的排序。
      代码:
     
1  //内部类
2 class ArtistCompare implements Comparator<Song>{
3       public int compare(Song one, Song two){
4              return one.getArtist() . compareTo( two. getArtist());  
5       }
6 }
7 ArtistCompare artistCompare = new ArtsitCompare();
8 Collections.sort(songList, artistCompare);

 

六、想一想,拿着两个对象,有那么多可以比较的方面,你比那个?所以:你以为对象的比较那么简单?

     hashCode()的默认行为是对堆上的对象产生独特的值。
      equals()的默认行为是执行==的比较。也就是对象字节组合间的比较。
      所以如果你没有重写过以上两个方法,两个对象无论如何都会被认为是不同的。
      下面:引用的相等性和对象的相等性
      1、引用的相等性:引用的是同一个对象,则引用是相等的。
                                    调用hashCode()可以得到相同的结果,hashCode()会根据对象在内存上的位置返回一个专属的序号,该序号是不重复的。
                                    可以用==来判断引用变量是否相等(对象的字节组合);
      2、对象的相等性:如果你想把两个不同的对象视为相等的,必须覆盖从Object继承下来的hashCode()方法与equals()方法。使前者相等,后者返回true(之前提过原因)                但两个对象如果有相同的hashCode也不一定是相等的(存在杂凑算法的碰撞值)。
 
      覆盖的例子:以一首歌的标题来比较歌曲是否是相同:
 1 class Song implements Comparable<Song>{
 2       private String title;
 3       public boolean equals(Object o){
 4             Song s = (Song) o;
 5             return getTitle().equals(s.getTitle);
 6       }
 7       public int hashCode(){
 8             return getTitle().hashCode();
 9       }
10       public String getTitle(){
11             return this.title;
12       }
13 }

 

七、在介绍了上面对象之间如何比较后,还记得开头提到可以提到ArrayList的Treeset么?
  TreeSet的元素必须是(实现了)Comparable 或者 使用重载、取用了Comparator参数的构造函数
       第二种举例:
  
1 TreeSet<Book> tree = new TreeSet<Book>(bCompare);  //bCompare是实现了Comparator接口类的一个对象

八、Map键值对的取得方式

       1、传统方法1(转成set后取得)

 

        2、传统方法2(转成set后取得)

   3、增强for循环(推荐, jdk1.5以后可使用)

 
             不用iterater,直接迭代以上两种方法取得的set即可。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。