黑马程序员技术交流社区

标题: 关于TreeSet的问题 [打印本页]
作者: 途遥子若    时间: 2013-12-22 19:23
标题: 关于TreeSet的问题
为什么说“对于存储到这个集合中的对象；是需要进行自然顺序的排序”的呢？TreeSet里没有自带自然排序方法吗？如果构造排序方法，那么汉字是按什么排序的？
作者: 天天学习    时间: 2013-12-22 20:39
TreeSet集合本身具有自动排序的功能，但是排序要按一定条件进行排序，因此存入TreeSet集合的对象必须具有比较性，如果没有比较性，TreeSet集合不知道按什么条件排序，因此当对象不具备比较性时，存入多个对象时。会抛出异常。因此我们将对象存入集合中，集合会自动排序，而我们所要做的就是给对象指定比较条件，即使对象具有比较性。
1，第一种方式：自然排序，实现Comparable接口，java中如String类等已经实现了这个接口，本身具备了比较性，因此我们在存入字符串对象进集合时，可以直接存入，而对于自定义的对象如Student对象时，我们必须要让Student类实现Comparable接口，并重新复写compareTo()方法，来确定自己的比较条件
  1. class Student implements Comparable
  2. {
  3.         private String name;
  4.         private int age;

  6.         Student(String name,int age)
  7.         {
  8.                 this.name = name;
  9.                 this.age = age;
  10.         }
  11.         public String getName()
  12.         {
  13.                 return name;
  14.         }
  15.         public int getAge()
  16.         {
  17.                 return age;
  18.         }
  19.         public int compareTo(Object obj)
  20.         {
  21.                                
  22.                 if(!(obj instanceof Student))
  23.                         throw new RuntimeException("一个错误对象类型");
  24.                 Student st = (Student)obj;
  25.                 if(this.age>st.age)
  26.                         return 1;
  27.                 else if(this.age==st.age)
  28.                 {
  29.                         return this.name.compareTo(st.name);
  30.                 }else
  31.                         return -1;
  32.                
  33.         }

  35. }
复制代码

2，第二种方式：实现Comparator接口方式，当元素自身不具备比较性或具备的比较性不满足需要时，需要让集合自身具备比较性，第一步：定义一个比较器类实现Comparator接口并重写compare()方法。第二步：将比较器对象作为参数传递给TreeSet集合的构造函数。
  1. class MyComparator implements Comparator    //建立比较器类
  2. {
  3.         public int compare(Object o1,Object o2)
  4.         {
  5.                 if(!(o1 instanceof Student && o2 instanceof Student))
  6.                         throw new RuntimeException("错误对象类型");
  7.                 Student st1 = (Student)o1;
  8.                 Student st2 = (Student)o2;
  9.                
  10.                 int num = st1.getName().compareTo(st2.getName());
  11.                 if(num==0)
  12.                 {
  13.                         if(st1.getAge()>st2.getAge())
  14.                                 return 1;
  15.                         if(st1.getAge()==st2.getAge())
  16.                                 return 0;
  17.                         return -1;
  18.                 }
  19.                 return num;

  21.         }
  22. }
复制代码
  1. TreeSet ts = new TreeSet(new MyComparator());//传入比较器
  2.                 ts.add(new Student("lisi01",11));
  3.                 ts.add(new Student("lisi02",12));
复制代码

3，汉字，按什么排序，个人观点：
      3.1，对于单个汉字可以转换成字符对象，而字符对象对应的包装类Character本身具备比较性，直接存入即可按自然排序方式排序，即根据数字比较两个 Character 对象。
      3.2，多个汉字，可以按字符串对象进行存储，字符串对象与Character一样具备比较性都可按自然排序方法排序即 按字典顺序比较两个字符串。
作者: 途遥子若    时间: 2013-12-22 20:51
天天学习 发表于 2013-12-22 20:39
TreeSet集合本身具有自动排序的功能，但是排序要按一定条件进行排序，因此存入TreeSet集合的对象必须具有比 ...

灰常感谢
作者: 不愿一人    时间: 2013-12-22 21:29
对于这个问题,我想分三点进行分析:
首先是“对于存储到这个集合中的对象；是需要进行自然顺序的排序”,对于这句话
你可以查一下JDKSE的TreeSet的帮助文档,这是我摘抄的部分:
基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，
或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法.
如果还不懂,那就只能看TreeSet底层的源码了,当你在调用HashSet的add方法时,他底层实际
会调用map中的put方法,在put方法中会调用hashCode和equals方法,同时还在put方法里面
进行元素的比较,这是源代码:
  1. public boolean add(E e) {
  2. return map.put(e, PRESENT)==null;
  3. }
  4. public V put(K key, V value) {
  5.      if (key == null)
  6.          return putForNullKey(value);
  7.      int hash = hash(key.hashCode());
  8.      int i = indexFor(hash, table.length);
  9.      for (Entry<K,V> e = table; e != null; e = e.next) {
  10.          Object k;
  11.          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  12.             V oldValue = e.value;
  13.              e.value = value;
  14.              e.recordAccess(this);
  15.              return oldValue;
  16.          }
  17.      }
  18.      modCount++;
  19.      addEntry(hash, key, value, i);
  20.      return null;
  21. }
复制代码

当你调用TreeSet中的add方法时，add方法则调用map中的put方法，在put方法里则根据来比较，源代码如下
  1. public V put(K key, V value) {
  2.      Entry<K,V> t = root;
  3.      if (t == null) {
  4.          root = new Entry<K,V>(key, value, null);
  5.          size = 1;
  6.          modCount++;
  7.          return null;
  8.      }
  9.      int cmp;
  10.      Entry<K,V> parent;
  11.      [color=Red]Comparator<? super K> cpr = comparator;[/color]
  12.     if (cpr != null) {
  13.          do {
  14.              parent = t;
  15.              cmp = cpr.compare(key, t.key);
  16.             if (cmp < 0)
  17.                  t = t.left;
  18.              else if (cmp > 0)
  19.                  t = t.right;
  20.              else
  21.                  return t.setValue(value);
  22.          } while (t != null);
  23.      }
  24.      else {
  25.          if (key == null)
  26.              throw new NullPointerException();
  27.          Comparable<? super K> k = (Comparable<? super K>) key;//比较
  28.         do {
  29.              parent = t;
  30.              [color=Red]cmp = k.compareTo(t.key);[/color]
  31.             if (cmp < 0)
  32.                  t = t.left;
  33.              else if (cmp > 0)
  34.                  t = t.right;
  35.              else
  36.                  return t.setValue(value);
  37.          } while (t != null);
  38.      }
  39.      Entry<K,V> e = new Entry<K,V>(key, value, parent);
  40.      if (cmp < 0)
  41.          parent.left = e;
  42.      else
  43.          parent.right = e;
  44.      fixAfterInsertion(e);
  45.      size++;
  46.      modCount++;
  47.      return null;
  48. }
复制代码


还有就是TreeSet集合的底层的数据机构是二叉树,在二叉树存储数据时,会对元素进行
排序,所以放入的元素要有比较性,自定义对象实现Comparable接口,
所以每次往TreeSet里面存入一个对象时会与前面对象进行比较（调用compareTo()方法),
从而实现元素的排序功能.(楼主最好自己跟踪一下源代码)
第二点:就是TreeSet里没有自带的自然排序算法,他所用到的排序规则,要么是存储对象
实现Comparable接口时,实现的compareTo方法时定义的规则,要么就是在创建TreeSet对象时
,也就是TreeSet的这个构造方法:
{TreeSet(Comparator<? super E> comparator)
构造一个新的空 TreeSet，它根据指定比较器进行排序。}
所定义的规则,当然如果楼主存储了String类型的对象到TreeSet集合中,就不用做这两项
工作中的其中一个,因为String类默认实现了Compareble的接口.
最后一点是,汉字是怎么排序的,这个完全可以有由楼主自己定,让该类实现Comparable的接口,
在实现compareTo()的方法时,根据需要自己定义规则



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2