允许分别提供等值比较器和散列函数的映射

Question

在尝试对多项式进行建模时，特别是它们的乘法运算时，我遇到了以下问题。在乘法运算期间，两个多项式的单个单项式相乘，当然可能发生我有（3x^2 y + 5x y^2）*（x + y）。结果包含3x^2 y^2和5 x^2 y^2，我想通过加法立即合并。

当然，我希望使用单项部分x^2 y^2作为（散列）映射中的一个键来合并不同的系数（示例中的3和5）。但是我设想它的单项对象当然也应该包含系数，它应该是而不是是地图关键字的一部分。

当然，我可以写出单项对象的equals/hashcode，以使它们忽略系数。但是这种感觉真的太错了，因为在数学上，如果系数是相等的，那么单项式显然只与另一个相等。

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

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

实现一个不使用键'等号/哈希码，但专用的地图的缺点，有没有更好的想法如何融合单项式？

Answer 1

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

  好，与更多的getter /构造函数。

  这可能很烦人，也许存在一些库（如Guava），允许给出equals/hashCode方法，就像您可以给Comparator至TreeMap。

  您会在下面找到一个示例实现，指出如何修饰现有地图。

• 使用TreeMap与特定的Comparator。另一个答案指出，但我会说你需要正确定义一个Comparator，因为这可能会产生问题：如果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); 
    } 
    } 
} 

使用地图的代码：

但也许最好的（fo内存）将重写HashMap直接使用处理程序而不是包装。

Answer 2

你可以使用一个TreeMap使用自定义比较：

TreeMap(Comparator<? super K> comparator) 

构造一个新的，空的树图，根据给定的比较器进行排序。

（Source）

Answer 3

我认为这可能是更好的单项式分离成2个部分：系数和变量。这样，您可以将地图中的变量部分用作关键字，将系数用作值（然后可以更新）。

所有这些代码应该是一个Polynomial对象

我不知道里面的实现细节，为什么你认为一个免费的系数，单项不看的权利。如果你不需要，你不必将对象暴露在外面。但是这可能是一个很好的方式让你的获得者在你的Polynomial上得到每个单项式的系数。

Answer 4

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

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

Answer 5

+1也是所有的答案，因为每个帮助我稍微从稍微不同的角度看问题来梳理一下。在阅读时，我意识到答案比我想象的要简单。也许我应该在我的问题上强调，每个单项式当然包含变量的权力列表，例如[x^5，y^7，z]。这正是我必须在地图中用作键的单项部分。我有它随时可用，不需要围绕单项包装，不需要调整单项式的equals或hashCode。我只需要确保

a）这些列表是规范化的，例如通过保持它们的排序和b）“变量的权力”对象具有适当的hashCode和等于。

鉴于此，我假定每个这样的列表（我保持它们不变）使得一个适当的映射关键。然后很容易添加像乘法到多项式的单项式。