hashCode() 和 HashSet, compareTo() 和 TreeSet
Java 中的 Set 我们经常使用, 但是笔者前几天遇到了一点问题, 如何将自己写的类存入 Set 中??
平时在做力扣的过程中 Set 之后的泛型参数使用的都是包装类, 但是自己写的类由于某些东西不够完善, 导致 Set 的功能无法实现, 经过笔者的努力总算是搞明白了一点, 下面我们展开说说.
目录
hashCode() 和 HashSet, compareTo() 和 TreeSet
所以重写 hashCode() 和 equals() 方法的原则
问题发现
看下面一段代码:
import java.util.HashSet;
import java.util.Set;
class AA {
public int a;
public double b;
public AA(int a, double b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "a = " + a + " b = " + b;
}
}
public class Test1 {
public static void main(String[] args) {
AA aa1 = new AA(1, 20.4);
AA aa2 = new AA(1, 20.4);
System.out.println("aa1 的信息为" + aa1.toString());
System.out.println("aa2 的信息为" + aa2.toString());
Set<AA> set = new HashSet<>();
set.add(aa1);
set.add(aa2);
System.out.println("set 中存放元素的个数为" + set.size());
}
}根据上面代码, 可以看出 aa1 和 aa2 的信息完全相同, Set 具有去重的功能, 我们的想法是将 aa1 和 aa2 全部存放在 Set 中, 根据其去重的功能 Set 中应当只存放一个元素, 可是它的运行结果如下:
可见即使 aa1 和 aa2 的信息完全一致 set 去重的功能也无法实现.
这可怎么办?? 经过查阅资源我发现, 想实现 Set 的功能必须重写某些方法.
hashCode() 和 equals() 方法
java 中 HashSet 采用链地址法, 底层的结构是哈希桶, 所以根据 hash 码确定该对象在哪一个桶中(并不是直接确定, 还需要一些手段确定它在数组的具体位置).
所以 HashSet 中想要存放自己写的类必须实现 hashCode() 方法, 得到一个 hash 码, 如果这个码相同代表它存放在 HashSet 的位置相同, 之后在根据 equals() 方法判断这个元素是不是已经在该桶中存在, 从而达到去重的目的.
两个函数的目的是:
HashCode() : 确定该对象在 HashSet 中的位置.
equals() : 确定两个对象是否相等.
上面的例子中, 我们并没有重写 hashCode() 方法, 打印 aa1 和 aa2 两个对象的 hash码看看:
public static void main(String[] args) {
AA aa1 = new AA(1, 20.4);
AA aa2 = new AA(1, 20.4);
System.out.println(aa1.hashCode());
System.out.println(aa2.hashCode());
}结果为:
可见这两个对象的 hash 码并不相同, HashSet 功能无法实现的问题找到了.
所以重写 hashCode() 和 equals() 方法的原则是:
如果 equals() 为 true 则这两个对象的 hashCode() 的结果也是相同的.
如果两个对象的 HashCode() 的结果相同, 不代表两个对象就相同, 只能说明这两个对象在散列存储结构中, 存放于同一个位置.
所以, 如果对象的equals() 方法被重写, 那么对象的HashCode() 方法也尽量重写.
重写 hashCode() 的一种方法:
我们知道, 每一种包装类都重写了 hashCode() 方法, 我们可以根据类的各个属性的 hash 码之和来生成全新的 hash 码.
例如:
class AA {
public int a;
public double b;
public AA(int a, double b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "a = " + a + " b = " + b;
}
@Override
public int hashCode() {
Integer aInt = a;
Double bDou = b;
return aInt.hashCode() + bDou.hashCode();
}
@Override
public boolean equals(Object obj) {
AA aa = (AA)obj;
if (aa.a == a && aa.b == b) {
return true;
}
return false;
}
}上面的例子中, 我们根据属性 a 和 b 的hash码之和生成了新的 hash码.
同时我们重写了 equals() 方法(注意参数是 Object 对象).
此时我们再看看结果:
public static void main(String[] args) {
AA aa1 = new AA(1, 20.4);
AA aa2 = new AA(1, 20.4);
System.out.println("aa1 的信息为" + aa1.toString());
System.out.println("aa2 的信息为" + aa2.toString());
System.out.println("aa1 的hash码为 " + aa1.hashCode());
System.out.println("aa2 的hash码为 " + aa2.hashCode());
System.out.println("aa1 和 aa2 是否相等 " + aa1.equals(aa2));
Set<AA> set = new HashSet<>();
set.add(aa1);
set.add(aa2);
System.out.println("set 中存放元素的个数为" + set.size());
}结果为:
很好, HashSet 的功能实现了.
需要注意的一点, 如果有对象作为该类的属性, 必须该属性对应的类中重写了 HashCode() 方法:
class BB {
public int a;
public AA aa;
@Override
public int hashCode() {
Integer aInt = a;
return aInt.hashCode() + aa.hashCode();
}
@Override
public boolean equals(Object obj) {
BB bb = (BB)obj;
if (a == bb.a && aa.equals(bb.aa)) {
return true;
}
return false;
}
}如果没有重写 AA 中的 HashCode() 方法, aa.hashCode() 得到的就是一个无效值, aa.equals() 同理.
compareTo() 方法
compareTo() 是一个提供比较原则的方法, 该方法在需要排序的地方(如 PriorityQueue, Collections.sort, TreeSet, TreeMap 等)提供了一种比较规则.
该方法来自 Compareable 接口, 自定义类需要实现该接口才能在 TreeSet 等场景中使用.
这和这些容器或者排序的底层实现有关, 比如 TreeSet 和 TreeMap 的底层是一个红黑树, PriorityQueue 的底层是堆, Collections.sort 方法是归并排序, 这些都需要指定比较规则.
我们先给出测试:
class BB {
public int a;
public double b;
public BB(int a, double b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "a= " + a + " b= " + b;
}
}
public class Test1 {
public static void main(String[] args) {
BB bb1 = new BB(1, 23.4);
BB bb2 = new BB(6, 25.6);
BB bb3 = new BB(1, 23.4);
Set<BB> set = new TreeSet<>();
set.add(bb1);
set.add(bb2);
set.add(bb3);
}
}结果如下:
这段代码抛出了 ClassCastException ,代表着 BB 类没有实现 Comparable 接口, 无法比较大小.
所以就要实现这个接口提供一种比较规则.
下面请看具体实现:
class BB implements Comparable<BB> {
public int a;
public double b;
public BB(int a, double b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "a= " + a + " b= " + b;
}
@Override
public int compareTo(BB o) {
if (a == o.a) {
if (b == o.b) {
return 0;
}else if (b > o.b){
return 1;
}else {
return -1;
}
}else {
return a - o.a;
}
}
}
public class Test1 {
public static void main(String[] args) {
BB bb1 = new BB(1, 23.4);
BB bb2 = new BB(6, 25.6);
BB bb3 = new BB(1, 23.4);
Set<BB> set = new TreeSet<>();
set.add(bb1);
set.add(bb2);
set.add(bb3);
System.out.println(set.size());
}
}运行结果如下:
下面基于上面的 BB 类来测试优先级队列和排序:
public static void main(String[] args) {
BB bb1 = new BB(1, 23.4);
BB bb2 = new BB(6, 25.6);
BB bb3 = new BB(1, 23.4);
PriorityQueue<BB> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(bb1);
priorityQueue.offer(bb2);
priorityQueue.offer(bb3);
System.out.println("优先级队列测试");
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
List<BB> list = new ArrayList<>();
list.add(bb1);
list.add(bb2);
list.add(bb3);
Collections.sort(list);
System.out.println("排序测试");
for (BB x : list) {
System.out.println(x);
}
}结果如下:
compare() 方法
我们可以使用匿名内部类, 在传入参数的时候存入一个比较器对象, 从而指定比较规则, 代码如下:
这里的 BB 类没有实现 Comparable 接口
public static void main(String[] args) {
BB bb1 = new BB(1, 23.4);
BB bb2 = new BB(6, 25.6);
BB bb3 = new BB(1, 23.4);
Set<BB> set = new TreeSet<>(new Comparator<BB>(
) {
@Override
public int compare(BB o1, BB o2) {
if (o1.a == o2.a) {
if (o1.b == o1.b) {
return 0;
}else if (o1.b > o2.b) {
return 1;
}else {
return -1;
}
}else {
return o1.a - o2.a;
}
}
});
set.add(bb1);
set.add(bb2);
set.add(bb3);
System.out.println("TreeSet 测试");
System.out.println(set.size());
PriorityQueue<BB> priorityQueue = new PriorityQueue<>(new Comparator<BB>(
) {
@Override
public int compare(BB o1, BB o2) {
if (o1.a == o2.a) {
if (o1.b == o1.b) {
return 0;
}else if (o1.b > o2.b) {
return 1;
}else {
return -1;
}
}else {
return o1.a - o2.a;
}
}
});
priorityQueue.offer(bb1);
priorityQueue.offer(bb2);
priorityQueue.offer(bb3);
System.out.println("优先级队列测试");
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
List<BB> list = new ArrayList<>();
list.add(bb1);
list.add(bb2);
list.add(bb3);
Collections.sort(list, new Comparator<BB>(
) {
@Override
public int compare(BB o1, BB o2) {
if (o1.a == o2.a) {
if (o1.b == o1.b) {
return 0;
}else if (o1.b > o2.b) {
return 1;
}else {
return -1;
}
}else {
return o1.a - o2.a;
}
}
});
System.out.println("排序测试");
for (BB x : list) {
System.out.println(x);
}
}运行的结果为:
今天就分享到这里, 希望大家一起提高.