Set や Map のキーを前方一致の Like 検索する

f:id:Naotsugu:20200201162139p:plain

はじめに
NavigableSet
NavigableMap
まとめ

はじめに

入力項目の自動補完(auto complete)などで、前方一致の Like 検索を行いたい場合があります。

Set や Map は、key または key-value のデータ構造なので、これらの用途には向いたものではありませんが、NavigableSet や NavigableMap を使うことで実現できます(java 6 で追加されたインターフェース)。

NavigableSet

NavigableSet の実装クラスである TreeSet を用意します。

NavigableSet<String> names = new TreeSet<>(
  Arrays.asList(
        "赤坂ミッドタウン・タワー",
        "新宿野村ビル",
        "新宿住友ビル",
        "虎ノ門城山トラストタワー",
        "虎ノ門ヒルズビジネスタワー",
        "虎ノ門ヒルズ森タワー"));

NavigableSet.tailSet() で、指定値と等しいかそれよりも大きい要素を持つ部分ビューを得ることができます。

このビューを使うことで以下のように前方一致での抽出を実現できます。

String query = "虎ノ門";

for (String name : names.tailSet(query)) {
    if (name.startsWith(query)) {
        System.out.println(name);
    } else {
        break;
    }
}

以下のような出力が得られます。

虎ノ門ヒルズビジネスタワー
虎ノ門ヒルズ森タワー
虎ノ門城山トラストタワー

もちろん String query = "虎ノ門ヒルズ"; とすれば

虎ノ門ヒルズビジネスタワー
虎ノ門ヒルズ森タワー

のように絞り込みができます。

なお、ここでは String を要素としていますが、自身のオブジェクトを要素とする場合には、Comparable を実装して自然順序付けが適切に処理されるようにする必要があります。

NavigableMap

Map の場合は NavigableMap とその実装である TreeMap を利用します。

NavigableMap<String, String> names = new TreeMap<>();
// ...

for (Map.Entry<String, String> name : names.tailMap(query).entrySet()) {
    if (name.getKey().startsWith(query)) {
        System.out.println(name);
    } else {
        break;
    }
}

使い方は NavigableSet と同様です。

まとめ

Navigable 系の部分ビュー系メソッドには以下のようなものが用意されています。

NavigableSet	NavigableMap	説明
headMap(E to)	headMap(K to)	指定値よりも小さい要素を持つ部分ビューを取得
tailMap(E from)	tailMap(K from)	指定値に等しいかそれよりも大きい要素を持つ部分ビューを取得
subMap(E from, E to)	subMap(K from, K to)	指定の範囲を持つ部分ビューを取得(fromを含む、toを含まない)