处理map,equals()和hashCodes().这有多高效？

Question

我正在写一些每秒会收到大量交易的东西.对于每个进入的事务,都会引用一个映射,其中键值是id,bean是一个有助于处理该特定事务的bean.基本上每个事务都带有一个id,一个查找将对map执行检索相应的bean进行处理.粘性部分带有这样的事实:每个事务的id并不意味着精确匹配地图中的id.更多的是从操作开始.为此,我创建了一个名为MyId的简单pojo,而不是使用字符串作为id.代码如下:

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方法.如果你的哈希值不匹配,它甚至都不愿意比较.虽然这有效,但是以这种方式实现哈希码方法来欺骗地图感觉有点狡猾.

想知道是否有更有效的方法来做到这一点.我们正在处理相当多的交易/秒,因此在地图上查找了很多.

PS:我对此进行了编码,因此我确信存在语法错误.请忽略这些.只是想传达一般的想法.

Answer 1

如果你的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;
  }
}

Answer 2

如果你的比较器正在使用startsWith(),那么哈希映射是错误的数据结构.你需要一些东西,你可以通过他们的第一个字母快速找到键:你需要一张树图.

与哈希映射不同,树映射是有序的.因此,而不是盲目地潜入奇怪的分布式数字的数学空间,可以从根开始搜索和性能将是O(日志(N)).Java实现的主要问题:它已关闭并锁定.你不能真正扩展它来搜索startsWith().

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

我的建议是使用一个数组并将所有处理器放在该数组中.按ID分类.

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