1

我正在写一些每秒会收到很多交易的东西。对于传入的每个事务，都会引用一个映射，其中键值为 id 和一个 bean，这将有助于处理该特定事务。基本上每个事务都带有一个 id，将对映射进行查找以检索相应的 bean 进行处理。棘手的部分是每个事务的 id 并不意味着与映射中的 id 精确匹配。更多的是从操作开始。为此，我没有使用字符串作为 id，而是创建了一个名为 MyId 的简单 pojo。以下代码：

public class MyId
{

    private static final int HASHCODE_CONSTANT = 1;
    private String value;

    public MyId(String value)
    {
        this.value = value;
    }

    @Override
    public int hashCode()
    {
        //Returns the same hashcode value for all instances of this pojo
        return HASHCODE_CONSTANT;
    }

    @Override
    public boolean equals(Object obj)
    {
        //Checks for object type, forcibly casts and then compares the starts with
        if(obj instanceof MyId)
        {
            if(!(obj == null || "".equals(obj)))
            {
                return this.value.startsWith(((MyId)obj).getValue());
            }
        }
        return false;
    }

    public String getValue()
    {
        return value;
    }

    public void setValue(String value)
    {
        this.value = value;
    }

    //Test
    public static void main(String[] args)
    {
         Map map = new HashMap();
         map.put(new MyId("123456"), "");

         System.out.println("Result: " + map.containsKey(new MyId("12345677")));
         System.out.println("Result: " + map.containsKey(new MyId("11234567")));
    }
}

第一个测试返回 true，第二个测试返回 false，就像它应该的那样。似乎 map.containsKey() 方法在调用 equals() 之前首先调用并比较了对象的 hashcode 方法。如果您的哈希不匹配，它甚至不会费心比较。虽然这可行，但必须以这种方式实现 hashcode 方法来欺骗地图，感觉有点狡猾。

想知道是否有更有效的方法来做到这一点。我们每秒处理相当多的事务，因此在地图上进行了相当多的查找。

PS：我对此进行了盲编码，因此我确定存在语法错误。请忽略那些。只是试图传达总体思路。

4

8 回答 8

5

如果您的hashCode()方法返回一个常量值，您的所有键都将散列到 中的同一个桶中HashMap，从而有效地将您减少HashMap为一个链表，访问时间为 O(n)（而不是近似为 O(1)）。

一种可能的解决方案（不节省空间）：为每个字符串存储与可能的字符串前缀对应的多个键，但都引用相同的值。例如，对于单词“Hello”，您将存储键“H”、“He”、“Hel”、“Hell”、“Hello”。这显然会占用更多空间，但查找时间会非常快，并且您不需要破坏类的equals()方法来执行“模糊”比较。您可以通过编写自定义类来提高空间效率；例如

/**
 * Class representing String prefix.
 * Storage overhead == original string + two ints.
 */
public class Prefix {
  private final String str;
  private final int len;
  private final int hc;

  public Prefix(String str, int len) {
    this.str = str;
    this.len = len;
    this.hc = toString().hashCode(); // Precompute and store hash code.
  }

  public String toString() {
    return str.substring(0, len);
  }

  public int hashCode() {
    return hc;
  }

  public boolean equals(Object o) {
    boolean ret;

    if (this == o) {
      ret = true;
    } else if (o instanceof Prefix) {
      ret = toString().equals(((Prefix)o).toString());
    } else {
      ret = false;
    }

    return ret;
  }
}
于 2009-08-12T07:20:41.897 回答
5

如果您的比较器正在使用startsWith()，则哈希映射是错误的数据结构。您需要一些可以通过首字母快速找到键的东西：您需要树状图。

与哈希图不同，树图是有序的。因此，与其盲目地潜入奇数分布的数学空间，不如从根开始搜索，性能将是 O(log(n))。Java 实现的主要问题：它是关闭和锁定的。您不能真正将其扩展为使用startsWith().

在您的情况下，事务处理器的数量似乎是稳定的（这意味着您不会一直创建新的）。如果不是这种情况，那么处理器的数量应该相对较少（例如，< 1000）。

我的建议是使用一个数组并将所有处理器放在该数组中。按 ID 对它们进行排序。

现在，您可以使用比较器中Arrays.binarySearch(T[] a, T key, Comparator<? super T> c)的代码有效地查找元素。equals()

于 2009-08-12T07:35:35.190 回答
4

我不认为哈希表是一个好的解决方案。@Adamskis 加载带有前缀的哈希表的想法很有趣，但我认为如果键共享前缀或者您需要即时插入/删除条目，它会变得混乱。

如果您的地图/查找表条目没有更改，那么使用预排序数组和Arrays.binarySearch(...)（由@Aaron 建议）是一个很好的解决方案。它应该为您提供 O(log(N)) 查找。

但是，如果您需要即时插入或删除映射条目，对于基于数组的解决方案，这些操作将是 O(N)。相反，您应该使用 TreeMap，并使用 NavigableMap API 中的方法（例如 'lowerKey() ,floorKey( ) highKey( and)`）在表中查找“最接近”的匹配项。这应该给你 O(log(N)) 用于查找、插入和删除。

于 2009-08-12T09:39:24.660 回答
2

你为什么以如此低效的方式使用HashMap。使用 TreeMap 可以更快地完成同样的事情 - 它完全按照您的意愿完成。哈希码中的 const 也将显示 O(n) 性能，而 TreeMap 为您提供 ln(n)。

于 2009-08-12T07:24:50.547 回答
2

这个对象甚至不遵循hashCode 的一般合同：

  • 如果两个对象根据 equals(Object) 方法相等，则对两个对象中的每一个调用 hashCode 方法必须产生相同的整数结果。

  • 如果根据 equals(java.lang.Object) 方法，如果两个对象不相等，则不需要对两个对象中的每一个调用 hashCode 方法都必须产生不同的整数结果。

但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

你可能想测试你的实现（一个总是返回一个常量的存根）和一个“正常” Object，比如String. 请测试，测试，测试，思考，测试，测试，测试，...

于 2009-08-12T07:25:47.610 回答
1

好的，感谢您的输入。认为问题陈述中最大的因素之一是存储的密钥几乎总是比比较短。为此，提出了两种不同的方法来解决问题陈述，以防万一有人在将来遇到类似的事情时需要参考：

  1. 照常使用地图。当输入比较进来时，比较。如果没有命中，则修剪字符串并再次比较。

  2. 这个有点花哨。非常喜欢我读到的关于 Don Knuth 的 Trie 的内容（感谢参考 Avi），并提出了一个非常简单的实现。（仅供参考，ID 的格式类似于 1.1.1.2。需要记住这一点，这样示例代码看起来不会太奇怪）。

public class Trie { private HashMap map = new HashMap();

public Trie()
{
}

public Object get(String key)
{
    return recurse(key.split("\\."), map, 0);
}

protected Object recurse(String[] key, Map map, int location)
{
    Object value = map.get(key[location]);
    if(value instanceof Map)
        return recurse(key, (Map)value, location+1);
    else
        return value;
}

public void addKey(String key, Object value)
{
    String[] keys = key.split("\\.");
    addKey(keys, map, 0, value);
}

protected void addKey(String[] key, Map map, int location, Object value)
{
    if((location+1) == key.length)
    {
        //end of the road. value insertion
        map.put(key[location], value);
    }
    else
    {
        Map hashMap = (Map) map.get(key[location]);
        if(!(map.containsKey(key[location])))
        {
            hashMap = new HashMap();
            map.put(key[location], hashMap);
        }
        addKey(key, hashMap, location+1, value);
    }
}

public static void main(String[] args)
{
    Trie trie = new Trie();
    trie.addKey("1.1.2.1", "1.1.2.1");
    trie.addKey("1.1.2.2", "1.1.2.2");
    trie.addKey("1.1.2.3.1", "1.1.2.3.1");
    trie.addKey("1.1.2.3.2", "1.1.2.3.2");
    trie.addKey("1.1.2.4", "1.1.2.4");

    System.out.println(trie.get("1.1.2.1.0")); //returns 1.1.2.1
    System.out.println(trie.get("1.1.2.3.1.0")); //returns 1.1.2.3.1
    System.out.println(trie.get("1.1.2.4.1.0")); //returns 1.1.2.4
}

}

在我的用例中，我预计 Trie 的深度不会增长超过 2-3 级，因此如果您的树结构变得非常复杂，您可能需要分析性能问题并查看额外的查找是否会导致过多的开销。哦，这两种方法都不需要对 hashCode 或 equals 合约进行任何狡猾的更改，因为我们只处理 String 对象。

注意事项：

尚未决定使用哪一个待定行为分析。大多数情况下，比较值将与存储在地图中的值完全相同，因此简单的查找就足够了。它只是需要照顾的其他“特殊”情况。总而言之，如果特殊事件的频率非常低，我很想采用最初的方法（＃1）。绝大多数搜索都会很快，当出现特殊情况时，我将忍受字符串操作开销的痛苦。如果反过来，#2 可能更有吸引力。

PS：欢迎评论

于 2009-08-14T07:07:51.513 回答
1

您的 equals() 方法不遵守Object.equals()的合同- 它不是可传递的。它会让 "a".equals("ab") 返回 true，并且 "a".equals("ac") 返回 true，但 "ab".equals("ac") 返回 false。

如果您尝试基于字符串前缀存储与字符串相关的对象，您可能需要考虑使用某种trie。

于 2009-08-12T09:23:56.750 回答
0

我认为您正在强制两个不同的对象使用相同的数据结构，这会使您的地图效率不高。

为了提供更好的解决方案，我可能需要更多信息，例如：地图中的 id 是否总是 6 位数字？

好的，那么您可以例如创建两个这样的类。

public class MyIdMap {

   private String value;

   public MyIdMap(String value) {
      this.value = value;
   }

   public String getValue() {
      return value;
   }

   public void setValue(String value) {
      this.value = value;
   }

   @Override
   public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ((value == null) ? 0 : value.hashCode());
      return result;
   }

   @Override
   public boolean equals(Object obj) {
      if (this == obj)
         return true;
      if (obj == null)
         return false;
      if (getClass() != obj.getClass())
         return false;
      MyIdMap other = (MyIdMap) obj;
      if (value == null) {
         if (other.value != null)
            return false;
      } else if (!value.equals(other.value))
         return false;
      return true;
   }
}


public class MyId {

   private String value;

   public MyId(String value) {
      this.value = value;
   }

   public String getValue() {
      return value;
   }

   public void setValue(String value) {
      this.value = value;
   }

   public MyIdMap getMyIDMap() {
      return new MyIdMap(value.substring(0, 6));
   }
}

将 MyIdMap 放在 Map 中，然后在查找时，只需使用 map.get(myId.getMyIdMap())

于 2009-08-12T07:21:10.443 回答