14

使用 aTreeMap提供 custom 是微不足道的Comparator，从而覆盖Comparable添加到地图的对象提供的语义。HashMap但是不能以这种方式控制 s；提供散列值和相等性检查的函数不能被“侧载”。

我怀疑设计一个界面并将其改造成HashMap（或一个新类）既容易又有用？像这样的东西，除了更好的名字：

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);
  }

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }
  }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }
  }

不区分大小写Map的问题得到了一个简单的解决方案：

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

这是否可行，或者你能看到这种方法的任何基本问题吗？

是否在任何现有（非 JRE）库中使用了该方法？（试过谷歌，没有运气。）

编辑：hazzen 提出了很好的解决方法，但恐怕这是我试图避免的解决方法...... ;)

编辑：将标题更改为不再提及“比较器”；我怀疑这有点令人困惑。

编辑：接受与性能相关的答案；会喜欢更具体的答案！

编辑：有一个实现；请参阅下面接受的答案。

编辑：改写第一句以更清楚地表明这是我所追求的侧载（而不是排序；排序不属于 HashMap）。

4

9 回答 9

9

.NET 通过 IEqualityComparer（对于可以比较两个对象的类型）和 IEquatable（对于可以将自身与另一个实例进行比较的类型）来实现这一点。

事实上，我认为在 java.lang.Object 或 System.Object 中定义相等和哈希码是一个错误。尤其是平等很难以一种对继承有意义的方式来定义。我一直想写关于这个的博客……

但是，是的，基本上这个想法是合理的。

于 2008-10-17T23:40:48.160 回答
9

对你来说有点晚了，但对于未来的访问者来说，可能值得知道 commons-collections 有一个AbstractHashedMap（在3.2.2和4.0中的泛型）。您可以覆盖这些受保护的方法来实现您想要的行为：

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

这种替代方案的示例实现HashedMap是 commons-collections 自己的IdentityMap（仅高达3.2.2，因为 Java自 1.4 以来就有自己的）。

这不如为实例提供外部“ Hasharator”强大。Map您必须为每个散列策略（组合与继承反击......）实现一个新的映射类。但还是很高兴知道。

于 2013-11-17T12:43:03.600 回答
6

HashingStrategy是您正在寻找的概念。它是一个策略接口，允许您定义 equals 和 hashcode 的自定义实现。

public interface HashingStrategy<E>
{
    int computeHashCode(E object);
    boolean equals(E object1, E object2);
}

您不能将 aHashingStrategy与内置的HashSetor一起使用HashMap。GS Collections包括一个名为 java.util.SetUnifiedSetWithHashingStrategy和一个名为 的 java.util.Map UnifiedMapWithHashingStrategy。

让我们看一个例子。

public class Data
{
    private final int id;

    public Data(int id)
    {
        this.id = id;
    }

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

这是您如何设置UnifiedSetWithHashingStrategy和使用它的方法。

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

为什么不只使用 a Map？UnifiedSetWithHashingStrategy使用 a 的一半内存和 a 的UnifiedMap四分之一内存HashMap。有时您没有方便的键，必须创建一个合成键，例如元组。那会浪费更多的内存。

我们如何执行查找？请记住，集合有contains()，但没有get()。UnifiedSetWithHashingStrategy除了实现Pool之外Set，它还实现了get().

这是处理不区分大小写字符串的简单方法。

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));

这展示了 API，但它不适合生产。问题是 HashingStrategy 不断委托给String.toLowerCase()它创建一堆垃圾字符串。下面介绍如何为不区分大小写的字符串创建有效的散列策略。

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
  {
    @Override
    public int computeHashCode(String string)
    {
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
      {
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      }
      return hashCode;
    }

    @Override
    public boolean equals(String string1, String string2)
    {
      return string1.equalsIgnoreCase(string2);
    }
  };

注意：我是 GS 收藏的开发人员。

于 2014-12-31T23:31:46.447 回答
4

Trove4j具有我所追求的功能，他们称之为散列策略。

他们的 map 具有不同限制的实现，因此具有不同的先决条件，因此这并不隐含地意味着 Java 的“本机”HashMap 的实现是可行的。

于 2009-12-09T20:42:35.497 回答
3

注意：正如所有其他答案中所述，HashMaps 没有明确的顺序。他们只承认“平等”。从基于散列的数据结构中获取顺序是没有意义的，因为每个对象都变成了散列——本质上是一个随机数。

你总是可以为一个类编写一个散列函数（而且通常是必须的），只要你仔细地去做。这是一件很难正确完成的事情，因为基于散列的数据结构依赖于散列值的随机、均匀分布。在 Effective Java 中，有大量文本专门用于正确实现具有良好行为的哈希方法。

话虽如此，如果您只是希望散列忽略 a 的大小写，则可以为此目的String编写一个包装类并将其插入数据结构中。String

一个简单的实现：

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();
    }

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);
        }
    }

    private String s;
    private String lowerString;
}
于 2008-10-17T23:09:31.810 回答
0

好问题，问乔希布洛赫。我在 java 7 中将该概念作为 RFE 提交，但它被丢弃了，我相信原因与性能有关。不过，我同意，应该这样做。

于 2008-10-18T01:35:09.833 回答
0

我怀疑这还没有完成，因为它会阻止 hashCode 缓存？

我尝试创建一个通用 Map 解决方案，其中所有键都被静默包装。事实证明，包装器必须保存被包装的对象、缓存的 hashCode 和对负责相等检查的回调接口的引用。这显然不如使用包装类有效，在这种包装类中，您只需要缓存原始密钥加上一个对象（请参阅 hazzens 答案）。

（我还遇到了一个与泛型相关的问题；get 方法接受 Object 作为输入，因此负责散列的回调接口必须执行额外的 instanceof-check。要么这样，要么映射类必须知道 Class它的钥匙。）

于 2008-10-18T15:43:56.700 回答
0

这是一个有趣的想法，但对于性能来说绝对是可怕的。这样做的原因对于哈希表的概念来说是非常基本的：不能依赖排序。哈希表非常快（恒定时间），因为它们索引表中元素的方式：通过计算该元素的伪唯一整数哈希并访问数组中的该位置。它实际上是计算内存中的位置并直接存储元素。

这与平衡二叉搜索树TreeMap（维基百科有一些更深入的分析。总而言之，树状图的效率取决于一致的顺序，因此元素的顺序是可预测且合理的。但是，由于“遍历到目的地”方法对性能的影响，BST 只能提供O(log(n))性能。对于大型地图，这可能会对性能造成重大影响。

可以在哈希表上施加一致的排序，但这样做涉及使用LinkedHashMap与手动维护排序类似的技术。或者，可以在内部维护两个单独的数据结构：哈希表和树。该表可用于查找，而树可用于迭代。问题当然是这使用了两倍以上的所需内存。此外，插入的速度仅与树一样快：O(log(n))。并发技巧可以稍微降低这一点，但这不是可靠的性能优化。

简而言之，您的想法听起来确实不错，但如果您真的尝试实现它，您会发现这样做会带来巨大的性能限制。最终的结论是（并且已经持续了几十年）：如果您需要性能，请使用哈希表；如果您需要排序并且可以忍受性能下降，请使用平衡二叉搜索树。恐怕真的没有有效地结合这两种结构而不会失去其中一种或另一种的一些保证。

于 2008-10-18T16:26:48.203 回答
0

中有这样的功能com.google.common.collect.CustomConcurrentHashMap，不幸的是，目前还没有公开的方式来设置Equivalence（他们的Hasharator）。也许他们还没有完成它，也许他们认为该功能还不够有用。在番石榴邮件列表中询问。

我想知道为什么它还没有发生，正如两年多前的演讲中提到的那样。

于 2011-04-18T10:54:45.037 回答