部分的なプロパティを見つける

Question

私はマップを持っています。キーは、6文字の文字列とPropertiesクラスは、おおよそ以下のように見える含まれています

public class Properties { 
    private String propertyOne; 
    private String propertyTwo; 
    private String propertyThree; 
    private String propertyFour; 
    ... 
    ... 
} 

今度は、私は以下のようにマップ内のいくつかのエントリを持っているとしましょう：

41111 - > {1,2,3,4 、5}

41112 - > {1,2,3,4,6-}

41234 - > {1,2,345,87,65}

51123 - > {100,200,30000,345,123 }

51122 - > {} 100,200,30000,556,989

私はmap.get("12567")をすれば今、私は、所望の特性オブジェクトを取得します。

私が持っている課題は、部分データを保存できるデータ構造を作成する必要があることです。部分データによって私はmap.get("4111")をすれば、私は交差点のを取得する必要があります意味{1,2,3,4,5}（プロパティ41111用）

{1,2,3,4,null}.は同様map.get("41")が{1,2,null,null,null}を生成する必要がある（41112のプロパティ）と{1,2,3,4,6}。

Map<String, Property>`` keyValuesForOneCharがキーとそれに対応する値として、すべての可能な単一の文字が含まれています

私は今、私のようなすべての可能な部分キーとそれに対応する値を含む複数のハッシュマップを作成しているソリューションを持っています。

Map<String, Property> keyValuesForTwoCharsには、可能なすべての2文字がキーとその対応する値として含まれています。

私はこのソリューションが好きではありませんでした。これはかなり単純ですし、複数のハッシュマップを維持することは良い考えではないと思います。もう1つの問題は、私の生データ数が約200000であり、すべての順列の組み合わせで膨大な部分データが作成され、その膨大な数のハッシュマップのパフォーマンスが低下すると思います。この問題のより良い解決策を提案してください。私は次のような制約があります。

1. 解決策は厳密にメモリ内でなければなりません。
2. ルックアップが速くなければなりません。そのため、生データの処理とデータ構造の準備に余分な時間とメモリが必要で、それが問題ではない場合は、その理由があります。

Answer 1

HashMapは、問題に最も適したデータ構造ではありません。キーが文字列なので、トライ（プレフィックスツリーとも呼ばれます）を実装できます。

これは、文字列キーを小さな文字列または文字に分割することによって機能します。この方法で、キーの値を保存することができますが、共通の接頭辞も保存できます。つまり、共通接頭辞「4111」に「41111」と「41112」の交点を格納することができます。4111を検索すると、キーの長さをmとすると、O（m）ステップがかかり、{1,2,3,4,5}と{1,2,3 、4,6}。交差点を更新すると、トライに項目を挿入します。

はトライを構築しながら、あなたは部分的な特性を更新することができ、部分的性質

を取得します。カップル（41111、{1,2,3,4,5}）を挿入したとしましょう。試行は特定の樹木で、このように見えます。 k,vという表記は、これがキーkと値vのノードであることを意味します。

4,{1,2,3,4,5} 
     | 
1,{1,2,3,4,5} 
     | 
1,{1,2,3,4,5} 
     | 
1,{1,2,3,4,5} 
     | 
1,{1,2,3,4,5} 

パスに沿った各ノードに、部分プロパティを格納します。あなたは41234を挿入した場合、{、、

 4,{1,2,3,4,null} 
      | 
     1,{1,2,3,4,null} 
      | 
     1,{1,2,3,4,null} 
      | 
     1,{1,2,3,4,null} 
    /    \ 
1,{1,2,3,4,5}  2,{1,2,3,4,6} 

そして再び1,2,345,87,65：カップル（41112、{1,2,3,4,6}を）挿入するときに今、あなたはトライを更新します}、それは次のようになります。これを行う

が

   4,{1,2,null,null,null} 
         | 
       1,{1,2,null,null,null} 
      /     \ 
     1,{1,2,3,4,null}   2,{1,2,345,87,65} 
      |       | 
     1,{1,2,3,4,null}   3,{1,2,345,87,65} 
    /    \     | 
1,{1,2,3,4,5}  2,{1,2,3,4,6} 4,{1,2,345,87,65} 

、あなただけ既に挿入されている項目の共通接頭辞のための部分的なプロパティを格納、あなたはすべての組み合わせを作成する必要はありません。また、部分的なプロパティの取得は、値を取得するのと同じアルゴリズムを使用して行われます。