3

我们必须根据三个输入数据字段查找一些数据。查找必须很快。只有大约 20 种可能的查找组合。我们使用静态 HashMap 实例实现了这一点，在该实例中，我们通过连接三个数据字段来创建一个键。有没有更好的方法来做到这一点，或者这是要走的路？代码如下。

更新：我并不是说这段代码很慢。只是好奇是否有更好的方法来做到这一点。我认为可能有一个更优雅的解决方案，但如果没有令人信服的替代方案，我很乐意保持这一点！

创建类级静态 HashMap 实例：

private static HashMap map = new HashMap();

我们如何将数据加载到内存中：

private void load(Iterator iterator) {        
    while (iterator.next()) {  
      Object o = it.next();
      key = o.getField1() + "-" + o.getField2() + "-" o.getField3();
      map.put(key, o.getData());
    }
}

以及我们如何根据三个字段查找数据：

private Stirng getData(String f1, String f2, String f3) {
   String key = f1 + "-" + f2 + "-" f3;
   return map.get(key);
}
4

7 回答 7

7

好吧，要问自己的问题当然是“速度够快吗？” 因为除非您的应用程序需要更快并且这是瓶颈，否则这真的无关紧要。你所拥有的已经相当有效了。

话虽如此，如果您想从这个例程中尽可能地提高速度（而不用汇编语言重写它;-)，您可能会考虑使用数组而不是 a HashMap，因为只有少量有限数量的键。您必须开发某种散列函数，将每个对象散列为 0 到 19 之间的唯一数字（或者您实际拥有的许多元素）。您也许还可以优化该哈希函数的实现，尽管在不知道您正在使用的对象的详细信息的情况下，我无法告诉您如何准确地做到这一点。

于 2009-10-04T13:22:27.537 回答
3

您可以创建一个具有三个 String 字段的特殊键对象，以避免构建键字符串：

class MapKey {
  public final String k1;
  public final String k2;
  public final String k3;

  public MapKey(String k1, String k2, String k3) {
    this.k1 = k1; this.k2 = k2; this.k3 = k3;
  }

  public MapKey(Object o) {
    this.k1 = o.getField1(); this.k2 = o.getField2(); this.k3 = o.getField3();
  }

  public int hashCode() {
    return k1.hashCode();  // if k1 is likely to be the same, also add hashes from k2 and k3
  }
}
于 2009-10-04T13:39:27.833 回答
1

在您的情况下，我将继续使用您概述的实现。对于映射到常量数据的大量常量键列表，您可以使用Minimal Perfect Hashing。由于编写此代码并非易事，而且我不确定现有库，因此您必须在使用此代码之前考虑实施成本。

于 2009-10-04T13:50:28.320 回答
1

我认为您的方法非常快。通过实现自己的散列算法获得的任何收益都将非常小，尤其是与所需的努力相比。

关于您的密钥格式的评论。您最好确保您的分隔符不能出现在 toString() 值字段中，否则您可能会遇到键冲突：

field1="a-", field2="b-", field3="c" -> key="a--b--c"
field1="a", field2="-b", field3="-c" -> key="a--b--c"
于 2009-10-04T15:32:51.803 回答
1

连接字符串对于创建密钥来说是个坏主意。我的主要目的是不清楚。但在实践中，很大一部分实现存在错误，特别是分隔符实际上可能出现在字符串中。在性能方面，我看到一个程序只需将字符串破解的键更改为有意义的键对象即可将速度提高 10%。（如果你真的对代码很懒惰，你可以用它Arrays.asList来制作密钥 - 请参阅List.equalsAPI doc。）

于 2009-10-04T15:45:14.023 回答
0

完成此操作的另一种方法是创建一个Object来处理您的密钥，您可以使用它覆盖equals()(and hashCode()) 来对传入的密钥进行测试field1，field2然后field3依次进行测试。

编辑（回应评论）：

由于您的 Map 使用返回的值hashCode()将您的键放入存储桶（然后它将从中测试equals），因此理论上所有键的值可能相同。但是，我不建议这样做，因为您不会获得 HashMaps 性能的好处。您基本上将遍历存储桶中的所有项目并进行测试equals()。

您可以采取的一种方法是将调用委托给hashCode()您的密钥容器中的一个值。例如，您总是可以从 中返回 hashCode field3。在这种情况下，您将把密钥分发到可能与field3. 找到HashMap存储桶后，它仍然需要遍历存储桶中的项目以测试结果， equals()直到找到匹配项。

您可以创建的将是hashCode()您所有字段返回的值的总和。正如刚才所讨论的，这个值不需要是唯一的。此外，碰撞的可能性以及因此更大的铲斗要小得多。考虑到这一点，您对 的查找HashMap应该更快。

编辑2：

此密钥的良好哈希码问题已在此处的单独问题中得到解答

于 2009-10-04T13:39:40.737 回答
0

由于您只有 20 个组合，因此在了解每个组合的特征的基础上，手工制作“给我这个组合的索引 1..20”可能是可行的。

您是否能够列出确切的组合列表？

于 2009-10-04T17:44:55.403 回答