10

在尝试对多项式建模时，特别是它们的乘法，我遇到了以下问题。在乘法过程中，两个多项式的单个单项式相乘，当然，我有 (3x^2 y + 5x y^2) * (x + y)。结果包含 3x^2 y^2 和 5 x^2 y^2，我想立即通过加法组合它们。

自然，我想使用单项式的 x^2 y^2 部分作为（散列）映射中的键来添加不同的系数（示例中为 3 和 5）。但是我设想的单项式对象自然也应该包含系数，它不应该是映射键的一部分。

当然，我可以编写单项式对象的等于/哈希码，这样它们就忽略了系数。但这感觉非常错误，因为从数学上讲，一个单项式显然只有在系数也相等的情况下才等于另一个。

为中间操作引入无系数单项式对象看起来也不对。

除了使用地图，我可以使用列表并使用带有忽略系数的专用比较器的二进制搜索。

没有实现一个不使用键的等于/哈希码而是专用的映射，关于如何融合单项式有更好的想法吗？

4

4 回答 4

5

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

  • 像这样的包装对象：

      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));

    好吧，有更多的吸气剂/构造器。

    这可能很烦人，并且可能存在一些库（如 Guava），它允许给出一个 equals/hashCode 方法，就像你可以给出一个Comparatorto一样TreeMap。

    您将在下面找到一个示例实现，它指出了如何装饰现有地图。

  • 将 aTreeMap与特定的Comparator. 另一个答案指向它，但我会说你需要正确定义 aComparator因为这可能会导致问题：如果你compareTo的方法在达到相等时返回 0 ，而在其他情况下返回 1 ，这意味着没有自然排序。您应该尝试找到一个，或使用包装器对象。

如果您想接受挑战，您可以使用委托/装饰创建一个基本实现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);
    }
  }
}

以及使用地图的代码：

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直接使用处理程序而不是包装器。

于 2014-09-10T20:00:05.047 回答
3

您可以将 aTreeMap与自定义比较器一起使用：

TreeMap(Comparator<? super K> comparator)

构造一个新的空树映射，根据给定的比较器排序。

（来源）

于 2014-09-10T20:02:01.930 回答
3

考虑使用 a TreeMap，它是 a SortedMap，因此也是 a Map。您可以Comparator向其构造函数提供 a 。排序后的地图将使用Comparator它对地图键进行排序。但重要的是，对于您的情况，如果返回 0，它将认为键是相等的Comparator。在您的情况下，这将需要一个Comparator与 equals 不一致的值，如果您不小心，这可能会给您带来问题。

另一种选择是引入另一个类，它充当 a 的适配器Mononomial并且可以用作具有您应得的属性的映射键。

于 2014-09-10T20:05:04.707 回答
1

我认为将单项式分成两部分可能会更好：系数和变量。这样，您可以将地图中的变量部分用作键，将系数用作值（然后可以向上更新）。

所有这些代码都应该是Polynomial对象内部的实现细节

我不确定您为什么认为无系数单项式看起来不正确。如果您不想，您不必将对象暴露在外面。但这可能是让您Polynomial获得每个单项式的系数的好方法。

于 2014-09-10T20:02:49.600 回答