Java中的TreeMap、Comparable、Comparator

现在的位置: 首页 > 综合 > 正文

Java中的TreeMap、Comparable、Comparator

2019年05月09日 ⁄ 综合 ⁄ 共 12400字 ⁄ 字号小中大 ⁄ 评论关闭

写的非常到位

转载：http://www.it165.net/pro/html/201407/18366.html

我们知道HashMap的存储位置是按照key这个对象的hashCode来存放的，而TreeMap则是不是按照hashCode来存放，他是按照实现的Comparable接口的compareTo这个方法来存储的，只要compareTo的返回结果为0就表示两个对象相等，那么就存不进去两个对象，后put的就把前面的覆盖掉，甚至我们都不用重写equasls和hashCode方法，而只需要实现Comparable接口来重写comparareTo方法就行了，但是我们不能保证在应用中不会用到HashMap，所以保持良好的习惯，当我们定义了一个对象之后习惯性的重写equals和hashCode方法。本文比较详细的解释了TreeMap、Comparable、Comparator这三者的关联。

　　测试Comparable接口：

　　第一次比较：定义一个User类，实现Comparable接口，按照年龄排序，我们让equals为true，而hashCode也始终相等。

01.public class User implements Comparable<User>

 {

02.private String

 id;

03.private String

 name;

04.private Integer

 age;

05. 

06.public User()

 {

07.}

08. 

09.public User(String

 id, String name, Integer age) {

10.super();

11.this.id

 = id;

12.this.name

 = name;

13.this.age

 = age;

14.}

15. 

16.public String

 getId() {

17.return id;

18.}

19. 

20.public void setId(String

 id) {

21.this.id

 = id;

22.}

23. 

24.public String

 getName() {

25.return name;

26.}

27. 

28.public void setName(String

 name) {

29.this.name

 = name;

30.}

31. 

32.public Integer

 getAge() {

33.return age;

34.}

35. 

36.public void setAge(Integer

 age) {

37.this.age

 = age;

38.}

39. 

40.@Override

41.public String

 toString() {

42.return "User

 [name=" + name + ",

 age=" + age + "]";

43.}

44. 

45.@Override

46.public boolean equals(Object

 obj) {

47.return true;

48.}

49. 

50.@Override

51.public int hashCode()

 {

52.return 0;

53.}

54.public int compareTo(User

 o) {

55.return this.age

 > o.getAge() ? 1 : this.age

 == o.getAge() ? 0 :

 -1;

56.}

57.}

　　测试代码：

01.public class TestUser

 {

02.public static void main(String[]

 args) {

03.Map<User,

 Integer> userHashMap = new HashMap<User,

 Integer>();

04.User

 user1 = new User("1", "Jay", 30);

05.User

 user2 = new User("2", "Jolin", 21);

06.User

 user3 = new User("3", "Jack

 Cheng", 22);

07.User

 user4 = new User("4", "Bruce

 Lee", 22);

08.userHashMap.put(user1, 100);

09.userHashMap.put(user2, 200);

10.userHashMap.put(user3, 300);

11.userHashMap.put(user4, 400);

12. 

13.System.out.println(userHashMap);

14. 

15.Map<User,

 Integer>  userTreeMap = new TreeMap<User,

 Integer>();

16.userTreeMap.put(user1, 100);

17.userTreeMap.put(user2, 200);

18.userTreeMap.put(user3, 300);

19.userTreeMap.put(user4, 400);

20. 

21.System.out.println(userTreeMap);

22.}

23.}

　　结果：

1.

{User

 [name=Jay, age=

30]=400}

2.

{User

 [name=Jolin, age=

21]=200

,

 User [name=Jack Cheng, age=

22]=400

,

 User [name=Jay, age=

30]=100}

　　结论：对于HashMap而言，只要key的equals相等就表示两个元素相等，HashMap就存不进去；而TreeMap是不管equals和hashCode的，只要compareTo相等就表示两个元素相同，就存不进去。

　　2.第二次比较：现在我们按照id来重写hashCode和equals方法，如下：

01.@Override

02.public int hashCode()

 {

03.final int prime

 = 31;

04.int result

 = 1;

05.result

 = prime * result + ((id == null)

 ? 0 :

 id.hashCode());

06.return result;

07.}

08. 

09.@Override

10.public boolean equals(Object

 obj) {

11.if (this ==

 obj)

12.return true;

13.if (obj

 == null)

14.return false;

15.if (getClass()

 != obj.getClass())

16.return false;

17.User

 other = (User) obj;

18.if (id

 == null)

 {

19.if (other.id

 != null)

20.return false;

21.} else if (!id.equals(other.id))

22.return false;

23.return true;

24.}

测试代码不变，还是上面的测试代码，结果：

1.

{User

 [name=Jolin, age=

21]=200

,

 User [name=Jay, age=

30]=100

,

 User [name=Bruce Lee, age=

22]=400

,

 User [name=Jack Cheng, age=

22]=300}

2.

{User

 [name=Jolin, age=

21]=200

,

 User [name=Jack Cheng, age=

22]=400

,

 User [name=Jay, age=

30]=100}

说明：HashMap只要equals不等那就表示不等，而对于TreeMap如果compareTo相等，那么2个元素就相等，并且排序是按照compareTo方法定义的排序规则。

接下来再在测试代码里面添加List测试：

List<User>

 userList = new ArrayList<User>();

userList.add(user1);

userList.add(user2);

userList.add(user3);

userList.add(user4);

 

System.out.println(userList);

 

Collections.sort(userList);

System.out.println(userList);

结果：

1.{User

 [name=Jolin, age=21]=200,

 User [name=Jay, age=30]=100,

 User [name=Bruce Lee, age=22]=400,

 User [name=Jack Cheng, age=22]=300}

2.{User

 [name=Jolin, age=21]=200,

 User [name=Jack Cheng, age=22]=400,

 User [name=Jay, age=30]=100}

3.[User

 [name=Jay, age=30],

 User [name=Jolin, age=21],

 User [name=Jack Cheng, age=22],

 User [name=Bruce Lee, age=22]]

4.[User

 [name=Jolin, age=21],

 User [name=Jack Cheng, age=22],

 User [name=Bruce Lee, age=22],

 User [name=Jay, age=30]]

当调用sort方法之后List里面的元素就按照age排序了。

对于Comparator，一种叫做策略模式的设计模式，我们在User中实现Comparable接口，重写里面的方法，可以实现对User按age排序，这个排序算法是存在于User内部的，换句话说User和排序算法是相互依存的，User只能用compareTo这个算法，而compareTo算法也只能为User服务，那么如果我们其他地方也有同样的需求，就只能再实现一次Comparable，来为另外一个对象服务，这就有点重复的感觉，而且代码没有得到复用，样子对象和算法混在一起耦合性很强，于是希望把算法和模型分离出来，让算法单独存在，不同的对象可以使用同一个算法，并且二者是分离的，没有混为一体。当然可以分开那必然还是可以放在一起的。用一句比较专业点的话来讲就是策略模式有两个特点：1.封装变化。2.变成中使用接口而不实现接口。如果我再说得直白一点，策略模式就是一种面向接口编程的思想。这点在多线程里面也有所体现，就是为什么我们在开启新线程的时候要new
Thread(Runnable接口)，参数传接口而不推荐去继承Thread，虽然也可以继承，这也是体现面向对象的封装特性，将run的算法和线程分离，可以实现run所在类的复用，虽然一般都不会去复用，当然这里还有一点就是Java只能单继承，如果继承了Thread就不能在继承其他的类。此时我们的User是按照age排序，那如果想按照名字排序呢，那就没办法了，但是如果将算法分离出来，需要用名字排序我们就传用名字排序的算法进去，需要用age排序就传age排序算法进去。环境持有接口引用，通过set方法将接口实现传入到环境，在环境中来调用接口方法，这完完全全是面向接口的特点。下面的第一个例子就是存放在一起的，因为TreeMap的构造方法其中就有一个是待Comparator接口参数的构造方法，该参数只要实现了Comparator接口就行，如下：

1.public TreeMap(Comparator<? super K>

 comparator) {

2.this.comparator

 = comparator;

3.}

举例：

有一个Person类，实现了Comparator接口，并且按照岁数排序：

01.public class Person implements Comparator<Person>

 {

02.private String

 id;

03.private String

 name;

04.private Integer

 age;

05. 

06.public Person()

 {

07.}

08. 

09.public Person(String

 id, String name, Integer age) {

10.this.id

 = id;

11.this.name

 = name;

12.this.age

 = age;

13.}

14. 

15.public String

 getId() {

16.return id;

17.}

18. 

19.public void setId(String

 id) {

20.this.id

 = id;

21.}

22. 

23.public String

 getName() {

24.return name;

25.}

26. 

27.public void setName(String

 name) {

28.this.name

 = name;

29.}

30. 

31.public Integer

 getAge() {

32.return age;

33.}

34. 

35.public void setAge(Integer

 age) {

36.this.age

 = age;

37.}

38. 

39.@Override

40.public String

 toString() {

41.return "Person

 [name=" + name + ",

 age=" + age + "]";

42.}

43. 

44.@Override

45.public int hashCode()

 {

46.final int prime

 = 31;

47.int result

 = 1;

48.result

 = prime * result + ((id == null)

 ? 0 :

 id.hashCode());

49.return result;

50.}

51. 

52.@Override

53.public boolean equals(Object

 obj) {

54.if (this ==

 obj)

55.return true;

56.if (obj

 == null)

57.return false;

58.if (getClass()

 != obj.getClass())

59.return false;

60.Person

 other = (Person) obj;

61.if (id

 == null)

 {

62.if (other.id

 != null)

63.return false;

64.} else if (!id.equals(other.id))

65.return false;

66.return true;

67.}

68. 

69.public int compare(Person

 o1, Person o2) {

70.return o1.getAge()

 > o2.getAge() ? 1 :

 o1.getAge() == o2.getAge() ? 0 :

 -1;

71.}

72. 

73. 

74.}

测试：

01.public class TestPerson

 {

02.public static void main(String[]

 args) {

03.Map<Person,

 Integer> personHashMap = new HashMap<Person,

 Integer>();

04.Person

 person1 = new Person("1", "Jay", 30);

05.Person

 person2 = new Person("2", "Jolin", 21);

06.Person

 person3 = new Person("3", "Jack

 Cheng", 22);

07.Person

 person4 = new Person("4", "Bruce

 Lee", 22);

08.personHashMap.put(person1, 100);

09.personHashMap.put(person2, 200);

10.personHashMap.put(person3, 300);

11.personHashMap.put(person4, 400);

12. 

13.System.out.println(personHashMap);

14. 

15.Map<Person,

 Integer>  personTreeMap = new TreeMap<Person,

 Integer>(new Person());

16.personTreeMap.put(person1, 100);

17.personTreeMap.put(person2, 200);

18.personTreeMap.put(person3, 300);

19.personTreeMap.put(person4, 400);

20. 

21.System.out.println(personTreeMap);

22. 

23.}

24.}

结果：

1.

{Person

 [name=Jolin, age=

21]=200

,

 Person [name=Jay, age=

30]=100

,

 Person [name=Bruce Lee, age=

22]=400

,

 Person [name=Jack Cheng, age=

22]=300}

2.

{Person

 [name=Jolin, age=

21]=200

,

 Person [name=Jack Cheng, age=

22]=400

,

 Person [name=Jay, age=

30]=100}

依然是compara方法相等的元素表示相同，只能存放一个进去，并且是按照age排序的。

在List中的结果：

public class TestPerson

 {

public static void main(String[]

 args) {

Map<Person,

 Integer> personHashMap = new HashMap<Person,

 Integer>();

Person

 person1 = new Person("1", "Jay", 30);

Person

 person2 = new Person("2", "Jolin", 21);

Person

 person3 = new Person("3", "Jack

 Cheng", 22);

Person

 person4 = new Person("4", "Bruce

 Lee", 22);

personHashMap.put(person1, 100);

personHashMap.put(person2, 200);

personHashMap.put(person3, 300);

personHashMap.put(person4, 400);

 

System.out.println(personHashMap);

 

Map<Person,

 Integer>  personTreeMap = new TreeMap<Person,

 Integer>(new Person());

personTreeMap.put(person1, 100);

personTreeMap.put(person2, 200);

personTreeMap.put(person3, 300);

personTreeMap.put(person4, 400);

 

System.out.println(personTreeMap);

 

List<Person>

 personList = new ArrayList<Person>();

 

personList.add(person1);

personList.add(person2);

personList.add(person3);

personList.add(person4);

 

System.out.println(personList);

 

Collections.sort(personList, new Person());

 

System.out.println(personList);

 

}

}

结果：

1.{Person

 [name=Jolin, age=21]=200,

 Person [name=Jay, age=30]=100,

 Person [name=Bruce Lee, age=22]=400,

 Person [name=Jack Cheng, age=22]=300}

2.{Person

 [name=Jolin, age=21]=200,

 Person [name=Jack Cheng, age=22]=400,

 Person [name=Jay, age=30]=100}

3.[Person

 [name=Jay, age=30],

 Person [name=Jolin, age=21],

 Person [name=Jack Cheng, age=22],

 Person [name=Bruce Lee, age=22]]

4.[Person

 [name=Jolin, age=21],

 Person [name=Jack Cheng, age=22],

 Person [name=Bruce Lee, age=22],

 Person [name=Jay, age=30]]

调用sort方法前没排序，而调用之后按照age排序了。

其实将算法和模型分离也非常类似，只需要将实现Comparator接口的类单独拿出去就ok了。现在定义Person类，不实现Comparator接口，而将SortPerson类来实现该接口，其实就是用SortPerson类代替之前TreeMap中的参数，之前的参数是实现了Comparator接口的Person对象。

01.Person类：<br>public class Person

 {

02.private String

 id;

03.private String

 name;

04.private Integer

 age;

05. 

06.public Person()

 {

07.}

08. 

09.public Person(String

 id, String name, Integer age) {

10.this.id

 = id;

11.this.name

 = name;

12.this.age

 = age;

13.}

14. 

15.public String

 getId() {

16.return id;

17.}

18. 

19.public void setId(String

 id) {

20.this.id

 = id;

21.}

22. 

23.public String

 getName() {

24.return name;

25.}

26. 

27.public void setName(String

 name) {

28.this.name

 = name;

29.}

30. 

31.public Integer

 getAge() {

32.return age;

33.}

34. 

35.public void setAge(Integer

 age) {

36.this.age

 = age;

37.}

38. 

39.@Override

40.public String

 toString() {

41.return "Person

 [name=" + name + ",

 age=" + age + "]";

42.}

43. 

44.@Override

45.public int hashCode()

 {

46.final int prime

 = 31;

47.int result

 = 1;

48.result

 = prime * result + ((id == null)

 ? 0 :

 id.hashCode());

49.return result;

50.}

51. 

52.@Override

53.public boolean equals(Object

 obj) {

54.if (this ==

 obj)

55.return true;

56.if (obj

 == null)

57.return false;

58.if (getClass()

 != obj.getClass())

59.return false;

60.Person

 other = (Person) obj;

61.if (id

 == null)

 {

62.if (other.id

 != null)

63.return false;

64.} else if (!id.equals(other.id))

65.return false;

66.return true;

67.}

68.}

1.SortPerson类：

2.public class SortPerson implements Comparator<Person>

 {

3. 

4.public int compare(Person

 o1, Person o2) {

5.return o1.getAge()

 > o2.getAge() ? 1 :

 o1.getAge() == o2.getAge() ? 0 :

 -1;

6.}

7. 

8.}

测试：

public class TestPerson

 {

public static void main(String[]

 args) {

Map<Person,

 Integer> personHashMap = new HashMap<Person,

 Integer>();

Person

 person1 = new Person("1", "Jay", 30);

Person

 person2 = new Person("2", "Jolin", 21);

Person

 person3 = new Person("3", "Jack

 Cheng", 22);

Person

 person4 = new Person("4", "Bruce

 Lee", 22);

personHashMap.put(person1, 100);

personHashMap.put(person2, 200);

personHashMap.put(person3, 300);

personHashMap.put(person4, 400);

 

System.out.println(personHashMap);

 

Map<Person,

 Integer>  personTreeMap = new TreeMap<Person,

 Integer>(new SortPerson());

personTreeMap.put(person1, 100);

personTreeMap.put(person2, 200);

personTreeMap.put(person3, 300);

personTreeMap.put(person4, 400);

 

System.out.println(personTreeMap);

 

List<Person>

 personList = new ArrayList<Person>();

 

personList.add(person1);

personList.add(person2);

personList.add(person3);

personList.add(person4);

 

System.out.println(personList);

 

Collections.sort(personList, new SortPerson());

 

System.out.println(personList);

 

}

}

结果：

1.{Person

 [name=Jolin, age=21]=200,

 Person [name=Jay, age=30]=100,

 Person [name=Bruce Lee, age=22]=400,

 Person [name=Jack Cheng, age=22]=300}

2.{Person

 [name=Jolin, age=21]=200,

 Person [name=Jack Cheng, age=22]=400,

 Person [name=Jay, age=30]=100}

3.[Person

 [name=Jay, age=30],

 Person [name=Jolin, age=21],

 Person [name=Jack Cheng, age=22],

 Person [name=Bruce Lee, age=22]]

4.[Person

 [name=Jolin, age=21],

 Person [name=Jack Cheng, age=22],

 Person [name=Bruce Lee, age=22],

 Person [name=Jay, age=30]]

很明显：结果与之前的将算法实现在Person类里面的结果一致的。

写的太多了，就不从JDK源码的角度来看问题了，如果有兴趣可以看看JDK源码，大致思路是才用红黑树来存数据，通过比较器的比较结果来判断当前需要保存的元素位于什么地方，还是那句话，既然底层用到了比较排序，那么性能肯定是比较差的，可以说是牺牲性能来做到排序功能，这个很容易理解，因为Java里面或者说计算机语言里面都是这个思路，要获得某种特定的能力，必然是需要牺牲性能，当然有时候为了获得良好的性能，那就必须要牺牲内存或者硬盘空间。比如HashMap为了获得非常强大的根据key来读取数据的性能，采用hash算法来牺牲一定的内存空间，再比如，数据库里面为了获得查询性能，给某些列添加索引，牺牲硬盘存储空间来达到效果，当然像数据库的为了获得查询和统计等性能为某些列添加聚簇索引，这种对硬盘空间的牺牲那是相当的惊人。索引占用空间比表里面的数据还大，但是获得的性能也是非常优秀的，所以，从某种意义上说，为了获取某种特性来牺牲另外一些资源那也是值得的。

【上篇】Spring配置连接池
【下篇】MySQL左连接、右连接和内连接详解

作者: felder

该日志由 felder 于5年前发表在综合分类下，最后更新于 2019年05月09日.
转载请注明: Java中的TreeMap、Comparable、Comparator | 学步园 +复制链接

抱歉!评论已关闭.

学步园

Java中的TreeMap、Comparable、Comparator

作者: felder

书签

最新文章New

本站推荐

返回首页