複合キー: 複合キーの処理方法に関するガイド

複合キーは、マップまたはキャッシュ ルックアップの「キー」を定義するためにデータの組み合わせが必要な場合です。この例としては、顧客名とユーザーのロールに基づいて値をキャッシュする必要がある場合が考えられます。このような場合、キャッシュはこれら 2 つ (またはそれ以上) の基準のそれぞれに基づいて一意の値を保存できる必要があります。

コードで複合キーを処理できる方法はいくつかあります。

条件を文字列に結合する

最も多くの人が最初に飛びつくのは、条件を文字列に結合してキーとして使用することです。それは簡単で、多くの労力はかかりません:

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

これは問題を処理するためのかなり基本的な方法です。文字列キーを使用すると、キャッシュ キーが人間が読める形式であるため、デバッグと調査が容易になります。ただし、このアプローチには注意すべき問題がいくつかあります。

1. マップを操作するたびに新しい文字列を作成する必要があります。この文字列の割り当ては一般に小さいですが、マップが頻繁にアクセスされると、時間がかかり、ガベージ コレクションが必要になる大量の割り当てが発生する可能性があります。キーのコンポーネントの大きさやキーの数に応じて、文字列割り当てのサイズが大きくなる場合もあります。

   
   

2. 作成した複合キーが別のキー値に偽装されないようにする必要があります。

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

上記では、groupId = 1 および accessType = 23 の場合、それは groupId = 12 および accessType = 3 と同じキャッシュ キーになります。文字列の間に区切り文字を追加することで、この種の重複を防ぐことができます。ただし、キーのオプション部分には注意してください。

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

上の例では、extensionName はキーのオプションの部分です。 extensionName がオプションの場合、userProvidedString には区切り文字と有効な extensionName が含まれ、アクセスすべきでないキャッシュ データにアクセスできる可能性があります。

文字列を使用する場合は、キーの衝突を避けるためにデータをどのように組み合わせるかを検討する必要があります。特にユーザーが生成したキーの入力周り。

ネストされたマップ/キャッシュを使用する

別のオプションは、キーをまったく結合せず、代わりにデータ構造をネストすることです (マップのマップのマップ)。

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

これには、キーに渡された値がすでに割り当てられているため、マップを操作するときに新しいメモリを割り当てる必要がないという利点があります。最終的な値を得るには複数の検索を行う必要がありますが、マップは小さくなります。

ただし、このアプローチの欠点は、ネストが深くなるほど複雑になることです。レベルが 2 つしかない場合でも、マップの初期化は複雑に見える場合があります。 3 つ以上のデータを扱い始めると、コードが非常に冗長になる可能性があります。さらに、各レベルでは null ポインターを回避するために null チェックが必要です。

一部の「キーパーツ」もマップキーとして適切に機能しない可能性があります。配列またはコレクションには、その内容を比較するデフォルトの等しいメソッドがありません。したがって、それらを実装するか、別の代替手段を使用する必要があります。

ネストされたマップを使用すると、キーの各レベルが一意であるかどうかによっては、スペース効率が低下する可能性もあります。

複合キーオブジェクトの作成

最後のオプションは、キー値を文字列に結合する代わりに、キーのカスタム オブジェクトを作成することです。

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

ただし、すべての対話では、新しいオブジェクトに対する新しいメモリ割り当てが必要になります。オブジェクト キーの割り当ては、複合文字列に必要な割り当てよりも大幅に小さくなります。その理由は、キーを構成する部分を文字列として再割り当てする必要がないためです。代わりに、ラッピング オブジェクト キーのみが新しいメモリを必要とします。

複合キー オブジェクトでは、キーの等価性とハッシュコードの実装をカスタマイズすることもできます。文字列内の大文字の区別を無視したり、配列やコレクションをキーの一部として使用したりするなどです。

ただし、ここでも欠点は、複合文字列よりも多くのコードが必要になることです。また、マップのキー クラスに有効な等しいコントラクトとハッシュコード コントラクトがあることを確認する必要があります。

では、どれを選べばいいのでしょうか？

一般的に言えば、複合文字列キーを使用することをお勧めします。シンプルで理解しやすく、必要なコードが最小限で、後でデバッグするのが最も簡単です。これはパフォーマンスが最も遅いと考えられますが、一般に、他の 2 つのオプションのいずれかを使用して得られる利点よりも、シンプルで読みやすいコードを作成することの方が重要です。覚えて：

「時期尚早な最適化は諸悪の根源である」ドナルド・クヌース

マップ/キャッシュの検索がパフォーマンスのボトルネックになると信じる証拠や理由がない場合は、可読性を重視してください。

ただし、マップまたはキャッシュへのスループットが非常に高いシナリオにいる場合は、他の 2 つのオプションのいずれかに切り替えるとよいでしょう。 3 つすべてのパフォーマンスとメモリ割り当てサイズを比較してみましょう。

上記の 3 つのシナリオをテストするために、複合キーに対する 3 つのシナリオすべての同じ実装を複製するコードを作成しました。キー自体は、整数値、文字列値、long 値で構成されます。 3 つの実装はすべて、実行ごとに同じテスト データを使用してキーを構築しました。

すべての実行は、マップ内の 100 万レコードを使用して実行されました (Java のハッシュマップが使用されました)。キー サイズの異なる組み合わせでキーを構築する 3 回の実行が完了しました。

• 100 int、100 string、100 long — 100 万個の一意のキー

• 1 int、1 string、1,000,000 long — 100 万個の一意のキー

• 1,000,000 ints、1 string、1 long — 100 万個の一意のキー

  
  

まず、各マップがヒープ内でどのくらいのスペースを占めるかを見てみましょう。これは、アプリケーションの実行に必要なメモリ量に影響するため、重要です。

ここで明らかにすべき興味深い点が 1 つあります。最後のシナリオ (1,000,000 int) では、ネストされたマップのサイズが他のものよりも大幅に大きいです。これは、このシナリオでは、ネストされたマップにより、100 万のエントリを含む 1 つの第 1 レベルのマップが作成されるためです。次に、2 番目と 3 番目のレベルでは、エントリが 1 つだけ含まれる 100 万個のマップが作成されます。

これらのネストされたマップはすべて余分なオーバーヘッドを格納しており、ほとんどが空です。これは明らかに特殊なケースですが、強調するために示したかったのです。ネスト マップの実装を使用する場合、一意性 (およびその一意性の順序) が非常に重要になります。

この順序を 1、1、100 万と逆にすると、実際には最小のストレージ要件が得られます。

他の 2 つのシナリオでは、カスタム キー オブジェクトが 2 番目に来て、文字列キーが最後に来て、ネストされたマッピングが最も効率的です。

次に、これらの各マップを最初から作成するのにかかる時間を見てみましょう。

繰り返しますが、ネストされたマップは、メモリ割り当ての 100 万 -1-1 シナリオで最もパフォーマンスが悪くなりますが、それでも CPU 時間では他のマップよりも優れています。上記では、カスタム キー オブジェクトを使用すると、ネストされたキーよりもわずかに遅く、より多くのメモリ割り当てが必要になる一方で、String キーのパフォーマンスがすべてのケースで最も悪くなる様子もわかります。

最後に、最高のスループットのシナリオと、それがどの程度効率的に読み取るかを見てみましょう。 100 万回の読み取り操作 (作成されたキーごとに 1 回) を実行しました。存在しないキーは含めていません。

ここで、文字列ベースのキー検索がいかに遅いかがわかります。これは 3 つのオプションの中で最も遅く、最も多くのメモリを割り当てます。カスタム キー オブジェクトは、ネストされたマップの実装に「近い」動作をしますが、依然としてわずかな差で一貫して遅くなります。

ただし、ルックアップ メモリ割り当てでは、ネストされたマップがいかに優れているかに注目してください。いいえ、それはグラフの不具合ではありません。ネストされたマップ内の値を検索する場合、検索を行うために追加のメモリを割り当てる必要はありません。そんなことがあるものか？

さて、複合オブジェクトを文字列キーに結合するときは、毎回新しい文字列オブジェクトにメモリを割り当てる必要があります。

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

複合キーを使用する場合でも、新しいキー オブジェクトにメモリを割り当てる必要があります。ただし、そのオブジェクトのメンバーはすでに作成され参照されているため、新しい文字列よりもはるかに少ない量しか割り当てられません。

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

ただし、ネストされたマップの実装では、ルックアップ時に新しいメモリを割り当てる必要はありません。指定された部分を、ネストされた各マップのキーとして再利用します。

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

さて、上記に基づいて、最もパフォーマンスが高いのはどれでしょうか?

ほとんどすべてのシナリオで、ネストされたマップが最優先であることが簡単にわかります。ほとんどのユースケースで生のパフォーマンスを求めている場合は、これがおそらく最良のオプションです。ただし、ユースケースを確認するには独自のテストを実行する必要があります。

キー オブジェクトは、ネストされたマップが実用的でないか実装で使用できない場合に、非常に優れた汎用オプションになります。また、複合文字列キーは実装が簡単ですが、ほとんどの場合最も遅くなります。

複合キーの実装を検討する際に考慮すべき最後の点は、上記のものを組み合わせられるかどうかです。たとえば、最初のレベルまたは 2 つのレベルにネストされたマップを使用し、その後、より深いレベルを簡略化するために複合キー オブジェクトを使用できます。

これにより、ストレージと検索のパフォーマンスを最適化しながら、高速検索のためにデータをパーティション化したままにすることができます。コードも読みやすい状態に保ちます。

TLDR;

ほとんどの場合、シンプルにしておいてください。それが最も簡単なオプションであり、パフォーマンスが大きな問題ではない場合は、複合キーを文字列キーに結合してマップまたはキャッシュに保存します。

パフォーマンスが重要なシナリオでは、必ず独自のテストを行ってください。ただし、ほとんどの場合、ネストされたマップを使用すると最もパフォーマンスが高くなります。また、ストレージ要件も最小限になる可能性があります。また、ネストされたマッピングが現実的でなくなった場合でも、複合キーは依然としてパフォーマンスの高い代替手段となります。

ここでも公開されています