为什么不允许外部接口为HashMap提供hashCode / equals？
https://stackoverflow.com/questions/214136
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
使用 TreeMap ，提供自定义 Comparator 是微不足道的，因此会覆盖添加到地图中的 Comparable 对象提供的语义。然而， HashMap 不能以这种方式控制;提供哈希值和相等性检查的函数不能“侧载”。
我怀疑设计界面并将其改进为 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
Trove4j 具有我所追求的功能，他们称之为散列策略。
他们的地图具有不同限制的实现，因此具有不同的先决条件，因此这并不暗示Java的“本机”实现。 HashMap是可行的。
其他提示
对你来说有点晚了，但对于未来的访问者，可能值得知道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有自己的。
这不像提供外部“ Hasharator ”那样强大。到 Map 实例。您必须为每个散列策略实现一个新的映射类（组合与继承反击......）。但要知道它仍然很好。
.NET通过IEqualityComparer（对于可以比较两个对象的类型）和IEquatable（对于可以将自己与另一个实例进行比较的类型）来实现这一点。
事实上，我认为在java.lang.Object或System.Object中定义相等和哈希码是错误的。特别是平等很难用继承有意义的方式来定义。我对博客有意义......
但是，基本上这个想法是合理的。
HashingStrategy 是您正在寻找的概念。它是一个策略接口，允许您定义equals和hashcode的自定义实现。
public interface HashingStrategy<E>
{
int computeHashCode(E object);
boolean equals(E object1, E object2);
}
您不能将 HashingStrategy 与内置的 HashSet 或 HashMap 一起使用。 GS Collections 包含一个名为 UnifiedSetWithHashingStrategy 的java.util.Set和一个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)));
为什么不使用 Map ？ UnifiedSetWithHashingStrategy 使用 UnifiedMap 的一半内存，以及 HashMap 的四分之一内存。有时你没有方便的密钥，必须创建一个合成的密钥，就像一个元组。这会浪费更多的记忆。
我们如何执行查找？请记住，集合具有 contains（），但不包含 get（）。除了 Set 之外， UnifiedSetWithHashingStrategy 实现 Pool ，因此它还实现了 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系列的开发人员。
注意：正如所有其他答案中所述，HashMaps没有明确的排序。他们只承认“平等”。从基于散列的数据结构中获取订单是没有意义的，因为每个对象都变成了一个哈希 - 实质上是一个随机数。
您可以随时为类（通常必须）编写哈希函数，只要您仔细执行即可。这是一件很难做的事情，因为基于散列的数据结构依赖于散列值的随机均匀分布。在Effective Java中，有大量文本专门用于正确实现具有良好行为的哈希方法。
尽管如此，如果你只想让你的哈希忽略 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;
}
好问题，请问josh bloch。我在java 7中将该概念作为RFE提交，但它已被删除，我相信其原因与性能有关。但我同意应该这样做。
我怀疑这还没有完成，因为它会阻止hashCode缓存？
我尝试创建一个通用的Map解决方案，其中所有键都以静默方式包装。事实证明，包装器必须保存包装对象，缓存的hashCode以及对负责相等检查的回调接口的引用。这显然不如使用包装类那样高效，在这里你只需要缓存原始键和另外一个对象（参见hazzens的答案）。
（我还遇到了与泛型有关的问题; get-method接受Object作为输入，因此负责散列的回调接口必须执行额外的instanceof-check。要么是这样，要么是map类必须知道它的钥匙类。）
这是一个有趣的想法，但它对性能来说绝对是可怕的。其原因对哈希表的概念非常重要：不能依赖订购。 Hashtables非常快（常量时间），因为它们在表格中对元素进行索引的方式：通过计算该元素的伪唯一整数散列并访问该数组中的该位置。它实际上是在内存中计算一个位置并直接存储元素。
这与平衡的二叉搜索树（ TreeMap ）形成对比，后者必须从根开始，并在每次需要查找时向下运行到所需的节点。维基百科有一些更深入的分析。总而言之，树图的效率取决于一致的排序，因此元素的顺序是可预测和合理的。但是，由于“遍历到目的地”所造成的性能损失。方法，BST只能提供 O（log（n））性能。对于大型地图，这可能是一个重大的性能影响。
可以在哈希表上强加一致的排序，但这样做涉及使用类似 LinkedHashMap 的技术并手动维护排序。或者，可以在内部维护两个单独的数据结构：哈希表和树。该表可用于查找，而树可用于迭代。问题当然是这使用了所需内存的两倍以上。此外，插入仅与树一样快：O（log（n））。并发技巧可以降低这一点，但这不是一个可靠的性能优化。
简而言之，您的想法听起来非常好，但如果您真的尝试实现它，您会发现这样做会带来巨大的性能限制。最终的判决是（并且已经持续了数十年）：如果您需要性能，请使用哈希表;如果您需要订购并且可以使用性能下降，请使用平衡的二叉搜索树。我担心在没有失去其中一种保证的情况下，实际上没有有效地结合这两种结构。
