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

f:id:Naotsugu:20200201162139p:plain


はじめに

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

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


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 を実装して自然順序付けが適切に処理されるようにする必要があります。


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を含まない)

それぞれのメソッドには境界値を含む/含まないを指定するオーバーロードメソッドが存在します。

これらを使うことで、(部分一致はできませんが)前方一致検索を簡単に実現することができます。



Effective Java 第3版

Effective Java 第3版

ドリル形式で楽しく学ぶ Processing-Java (Future Coders(NextPublishing))

ドリル形式で楽しく学ぶ Processing-Java (Future Coders(NextPublishing))

  • 作者:田中 賢一郎
  • 出版社/メーカー: インプレスR&D
  • 発売日: 2018/11/23
  • メディア: Kindle版