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 を返し、2 番目のテストは想定どおりに false を返します。map.containsKey() メソッドは、 equals() が呼び出される前に、最初にオブジェクトの hashcode メソッドを呼び出して比較しているようです。ハッシュが一致しない場合は、比較する必要さえありません。これは機能しますが、マップをだますためにこの方法で hashcode メソッドを実装する必要があるのは少し危険です。

これを行うためのより効率的な方法があるかどうか疑問に思っていました。毎秒かなりの数のトランザクションを処理しているため、マップ上でかなりの数のルックアップを行っています。

PS: これはブラインドでコーディングしたので、構文エラーがあると確信しています。それらは無視してください。一般的な考えを伝えようとしているだけです。

4

8 に答える 8

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 に答える
5

hashCode()メソッドが定数値を返す場合、すべてのキーが 内の同じバケットにハッシュされ、 (O(1) を概算する代わりに) アクセス時間が O(n) のリンク リストにHashMap効果的に削減されます。HashMap

考えられる解決策の 1 つ (スペース効率が悪い): 各文字列に対して、可能な文字列プレフィクスに対応する複数のキーを格納しますが、すべて同じ値を参照します。たとえば、「He​​llo」という単語の場合、キー「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 に答える
4

ハッシュテーブルは良い解決策ではないと思います。プレフィックス付きのハッシュテーブルをロードするという@Adamskisのアイデアは興味深いものですが、キーがプレフィックスを共有している場合や、エントリをその場で挿入/削除する必要がある場合は、面倒になると思います。

マップ/ルックアップテーブルのエントリが変更されない場合は、事前に並べ替えられた配列とArrays.binarySearch(...)（@Aaronが提案）を使用することをお勧めします。O（log（N））ルックアップが得られるはずです。

ただし、マップエントリをその場で挿入または削除する必要がある場合、これらの操作は、配列ベースのソリューションではO（N）になります。代わりに、TreeMapを使用し、'lowerKey（）,floorKey（）andhigherKey（）`などのNavigableMap APIのメソッドを使用して、テーブル内で「最も近い」一致を見つける必要があります。これにより、ルックアップ、挿入、および削除のためのO（log（N））が得られます。

于 2009-08-12T09:39:24.660 に答える
2

このオブジェクトは、 hashCode の一般的な規約にも従っていません:

  • equals(Object) メソッドに従って 2 つのオブジェクトが等しい場合、2 つのオブジェクトのそれぞれで hashCode メソッドを呼び出すと、同じ整数結果が生成される必要があります。

  • equals(java.lang.Object) メソッドに従って 2 つのオブジェクトが等しくない場合、2 つのオブジェクトのそれぞれで hashCode メソッドを呼び出すと、異なる整数結果が生成される必要はありません。

ただし、プログラマーは、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上する可能性があることに注意する必要があります。

実装 (常に定数を返すスタブ)ObjectとString. テストして、テストして、テストして、考えて、テストして、テストして、テストして…

于 2009-08-12T07:25:47.610 に答える
2

なぜ HashMap をこのような非効率な方法で使用するのですか。TreeMap を使用してはるかに高速にできるのと同じことです。また、ハッシュ コードの const は O(n) パフォーマンスを示しますが、TreeMap は ln(n) を提供します。

于 2009-08-12T07:24:50.547 に答える
1

入力仲間に感謝します。問題ステートメントの最大の要因の1つは、格納されているキーがほとんどの場合、比較よりも短いことです。そのために、誰かが将来同様の何かに遭遇した場合に参照が必要になった場合に備えて、問題の説明を解決する2つの異なるアプローチを考え出しました。

  1. 通常どおりマップを使用します。入力比較が入ったら、比較します。ヒットがない場合は、文字列をトリミングして、もう一度比較します。

  2. これは少し凝っています。Don KnuthのTrieについて読んだもの（ref 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コントラクトに危険な変更を加える必要はありません。

考慮事項：

保留中の行動分析を使用するものを決定していません。ほとんどの場合、比較値はマップに保存されている値とまったく同じになるため、単純なルックアップで十分です。それに対応する必要がある他の「特別な」ケースです。要約すると、特別な出来事が非常に低い頻度である傾向がある場合、私は最初のアプローチ（＃1）に行きたくなるでしょう。検索の大部分は迅速であり、特別なケースが発生した場合、私は文字列操作のオーバーヘッドの苦痛に耐えます。逆の場合は、＃2の方が魅力的かもしれません。

PS：コメントを歓迎します

于 2009-08-14T07:07:51.513 に答える
0

2 つの異なるオブジェクトに同じデータ構造を使用するように強制しているため、マップがそれほど効率的ではないと思います。

より良い解決策を提供するには、次のような詳細情報が必要になる場合があります。マップの ID は常に 6 桁ですか?

OK では、たとえば、このような 2 つのクラスを作成できます。

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.get(myId.getMyIdMap()) を使用するだけです

于 2009-08-12T07:21:10.443 に答える