0 
class Expression{
   private final String expression; //can be 00* or 01* or 0101*

   public int hashCode(){
       //what should I put here
       //tried to use String hashCode but not useful
   }

   public boolean equals(Object obj){
       //Logic for testing of equality
       //Check if the obj is String check if expression matches
   }
}

//This is how map is initialized
map.put("00*",someObject);
map,put("0101*", someOtherObject);

为什么 String hashCode 实现没有用？

因为String在Expression课堂上是00*，而String我试图查找的将是00112233。所以hashCode()那些字符串不会相同。

客户端代码尝试从HashMap使用String键中查找

map.get("0011"); //should get someObject as `0011` matches expression `00*`

有没有办法做到这一点？

我知道它hashCode()应该包含不可变的值以及关于hashCode()和equals()合同的值。

但我怀疑是否有任何方法可以实现这一目标。

4

3 回答 3

0

我同意 RocketBoy .. 这不适用于Map. 我建议查看Trie数据类型。它不在标准 Java API 中，因此您需要编写自己的实现或在线查找。

另一种选择是List<Expression>在您的Map. 你可以遍历列表做类似的事情

for (final Expression e : myExpressions) {
    if (myLookup.startsWith(e)) {
        return myMap.get(e);
    }
}
于 2013-09-03T12:02:19.003 回答
0

让我重申你的问题：

您在 L={0,1}^* 上有 n 个正则表达式

re_1
re_2
..
re_n

并且您已将对象存储在哈希映射中，其中正则表达式（或数字）的字符串作为键。

map.put(re_1, obj_1)
map.put(re_2, obj_2)
..
map.put(re_n, obj_n)

现在你有一个给定的字符串匹配（最多）一个正则表达式，你想要一个快速的

map.get(s) -> s matching regexp re_k -> map.get(re_k) -> obj_k

这将需要一种方法来识别您给定的字符串匹配哪个正则表达式。

最简单的方法是对所有 n 个正则表达式的集合进行循环，如果您的字符串匹配它，则一个接一个地尝试。

任何更聪明的方案都需要分析给定的正则表达式，很可能是它们等效的有限自动机的图。

我不知道这样的方案。

这也取决于你的正则表达式，也许它们有一些简单的形状，可以被利用。

于 2013-09-03T13:22:29.757 回答
0

没有实现这种数据结构是有原因的。让我们对其进行逆向工程：

要求：

keyA = Expression.getInstance("00*");
keyB = Expression.getInstance("0011");

map.get(keyA) == map.get(keyB)

现在 hashmap() 是如何工作的？

  • 首先计算key的hash值，用于定位hash桶。
  • 现在使用存储桶键的 equals() 来查找 Entry 对象，然后返回 Entry.value()。

分析

这意味着，keyA并且keyB应该具有相同的hashCode并且也应该相等。

所以keyA.equals(keyB) == true

关于什么，keyC = Expression.getInstance("0010");

按照你的逻辑keyC.equals(keyA) = true。但是因为 equals 是传递性的，这意味着keyB.equals(keyC) == true。

这意味着在您的地图中，0010并0011映射到相同的值！？事实上，以“00”开头的任何东西都将具有相同的值。因此，它与用作00该值的键相同。你看到我要去哪里了吗？

简而言之，我认为它不适用于现有的 HashMap() 实现。

于 2013-09-03T11:44:59.127 回答