Java求集合的交集、并集、差集(必要时重写equals和hashCode方法)

Java求集合的交集、差集、并集,必要时需要重写equals或/且hashCode方法,本文给出应用实例,并自行编写函数将求得的交、差、并集存储在新的集合,不破坏原集合的内容。

1. 应用实例

1.1 Set接口

Java集合属于Java集合框架的一部分,Set接口无序并且不允许存在重复元素,详情参考博文《Java集合框架概述:Collection(List, Set, Queue)和Map》的Set部分。Set接口继承Collection接口,Collection接口定义了addAll、removeAll、retainAll,在AbstractSet.java实现了这些方法,用以求集合的交集、并集、差集。

//Collection.class
boolean    retainAll(Collection<? extends E> c)  //求交集 Adds all of the elements in the specified collection to this collection (optional operation).
boolean    addAll(Collection<? extends E> c)     //求并集 Adds all of the elements in the specified collection to this collection (optional operation).
boolean    removeAll(Collection<?> c)            //求差集 Removes all of this collection's elements that are also contained in the specified collection (optional operation).

1.2 实例

我在The ONE仿真器求两个节点buffer的交、并、差集。但结果有误,如下:

p43         [M2, M1]
p33         [M1]
p43 − p33   [M2, M1]    //正确结果应为[M1]
p43 ∪ p33  [M1, M2, M1] //正确结果应为[M1, M2]
p43 ∩ p33   [M1]

原因是集合使用HashMap存储hashes和elements以避免存在重复元素,并集和差集用到了hashCode,而交集没用到。而我只重写了equals,没有重写hashCode方法。修正该错误,需要重写hashCode。

1.3 equals和hashCode

关于hashCode的官方文档见这里Object as a Superclass更多实用地讲解了hashCode函数,如下:

The value returned by hashCode() is the object’s hash code, which is the object’s memory address in hexadecimal.

By definition, if two objects are equal, their hash code must also be equal. If you override the equals() method, you change the way two objects are equated and Object’s implementation of hashCode() is no longer valid. Therefore, if you override the equals() method, you must also override the hashCode() method as well.

默认的equals和hashCode源代码如下,

//Object.class
public boolean equals(Object obj) {
    return (this == obj);
}
public native int hashCode();  //存储对象的内存地址(16进制表示)

在Message.java重写equals和hashCode,源代码如下:

public boolean equals (Object other) {
    Message m = (Message)other;
    return this.id.equals(m.getId());  //String id; like M1, M2, M3, ...
}

public int hashCode () {
    String str = this.id.replaceAll("\\D+",""); //use regex and delete non-digits.
    return Integer.parseInt(str);
}

2. 相关源代码

AbstractSet.java实现的addAll、removeAll、retainAll只能在原集合操作,以下将求得的交、差、并集保存在另一个集合,不破坏原集合。源代码如下:

//return union of two collections
public <T> Collection<T> union(Collection<T> collection1, Collection<T> collection2) {
    Set<T> set = new HashSet<T>(collection1);
    set.addAll(collection2);
    return set;
}

//return intersection of two collections
public <T> Collection<T> intersection(Collection<T> collection1, Collection<T> collection2) {
    Set<T> set = new HashSet<T>(collection1);
    set.retainAll(collection2);
    return set;
}

//return set difference of two collections
public <T> Collection<T> setDifference(Collection<T> collection1, Collection<T> collection2) {
    Set<T> set = new HashSet<T>(collection1);
    set.removeAll(collection2);
    return set;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注