允许单独提供equals比较器和哈希函数的映射表

Question

允许单独提供equals比较器和哈希函数的映射表

javahashmapsymbolic-mathpolynomials

10

在尝试建模多项式，特别是它们的乘法时，我遇到了以下问题。在乘法过程中，两个多项式的各个单项式相乘，当然可能会出现（3x^2y+5xy^2）*（x+y）的情况。结果包含3x^2y^2和5x^2y^2，我想立即通过加法将它们组合起来。

自然地，我想使用单项式中 x^2y^2 部分作为 (哈希)映射中的键，以添加不同系数（例如示例中的3和5）。但是，正如我所设想的那样，单项式对象也应该包含系数，而这些系数不应该是映射键的一部分。

当然，我可以编写单项式对象的 equals/hashcode 方法，使其忽略系数。但是这感觉就是错的，因为从数学上讲，只有系数也相等时单项式才相等。

引入一个没有系数的单项式对象进行中间操作也不太对。

除了实现不使用键的equals/hashcode而使用专用的映射之外，还有更好的方法来融合这些单项式吗？

可使用列表，使用忽略系数的专用比较器进行二进制搜索。

- Harald

4个回答

3

您可以使用具有自定义比较器的TreeMap：

TreeMap(Comparator<? super K> comparator)
Constructs a new, empty tree map, ordered according to the given comparator.

(源码)

- Alexander Langer

3

考虑使用TreeMap，它是SortedMap，也是Map。您可以向其构造函数提供一个Comparator。排序的映射将使用该比较器对映射键进行排序。但重要的是，在您的情况下，如果比较器返回0，则会将键视为相等。在您的情况下，这将需要一个不符合equals的比较器，这可能会给您带来问题，如果您不小心的话。

另一个选择是引入另一个类，它充当Mononomial的适配器，并可用作具有所需属性的映射键。

- Raedwald

TreeMap 依赖于对 Monomial 进行二进制排序。虽然我可以提供所需的比较器，但我宁愿使用一个只是有序的二进制数组。我认为开销更小，而且性能应该是可比较的。 - Harald

1

我认为将单项式分为两部分：系数和变量，可能更好。这样你可以将变量部分用作键来进行映射，而将系数作为值（然后可以更新）。

所有这些代码应该是一个"Polynomial"对象内的实现细节。

我不确定为什么你认为没有系数的单项式看起来不对。如果你不想让对象暴露给外界，那没关系。但是，对于每个单项式，使用 "Polynomial" 中的getter来获取系数可能是一个很好的方法。

- dkatzel

嗯，如果没有系数，单项式看起来就不对了，因为没有系数，它在数学意义上不再是单项式。 - Harald

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NoDataFound · Accepted Answer

由于JDK实现的[Linked]HashMap不允许您重写equals/hashCode实现，因此唯一的其他方法是：

a wrapping object like this:

  class A {
    private final String fieldA; // equals/hashCode based on that field.
    private final String fieldB; // equals/hashCode based on that field.
  }

  class B {
    private A a;
    public int hashCode() {return a.fieldA.hashCode();} 
    public boolean equals(Object o) {... the same ... }
  }

  Map<B, Value> map = new HashMap<B, Value>();
  map.put(new B(new A("fieldA", "fieldB")), new Value(0));

Well, with more getters/constructors.

This can be annoying, and perhaps there exists some library (like Guava) that allows an equals/hashCode method to be given like you can give a Comparator to TreeMap.

You'll find below a sample implementation that point out what to do to decorate an existing map.

use a TreeMap with a specific Comparator. The other answer point it, but I'd say you'll need to correctly define a Comparator because this could lead to problems: if you compareTo method returns 0 when equality is reached, and 1 in other case, this means there is no natural ordering. You should try to find one, or use the wrapper object.

如果您想接受挑战，您可以使用委托/装饰器在另一个HashMap（这可以是另一种地图，如LinkedHashMap）上创建基本实现：

public class DelegatingHashMap<K,V> implements Map<K,V> {
  private final BiPredicate<K,Object> equalsHandler;
  private final IntFunction<K> hashCodeHandler;
  private final Map<Wrapper<K>,V> impl = new HashMap<>();

  public DelegatingHashMap(
    BiPredicate<K,Object> equalsHandler,
    IntFunction<K> hashCodeHandler
  ) {
    this.equalsHandler = requireNonNull(equalsHandler, "equalsHandler");
    this.hashCodeHandler= requireNonNull(hashCodeHandler, "hashCodeHandler");
  }

  public Object get(K key) {
    Wrapper<K> wrap = new Wrapper<>(key);
    return impl.get(wrap);
  }  

  ...

  static class Wrapper<K2> {
    private final K2 key;
    private final BiPredicate<K> equalsHandler;
    private final IntFunction<K> hashCodeHandler;
    public int hashCode() {return hashCodeHandler.apply(key);}
    public boolean equals(Object o) {
      return equalsHandler.test(key, o);
    }
  }
}

使用map的代码：

DelegatingHashMap<String, Integer> map = new DelegatingHashMap<>(
  (key, old) -> key.equalsIgnoreCase(Objects.toString(o, "")),
  key -> key.toLowerCase().hashCode()
);
map.put("Foobar", 1);
map.put("foobar", 2);

System.out.println(map); // print {foobar: 2}

但也许最好的记忆方法是重写 HashMap，直接使用处理程序而不是包装器。