線形検索

線形検索（Linear Search）は最も基本的な検索アルゴリズムで、目的のデータを探す為に集合から要素を１つづつ取り出し比較していく手順を踏みます。

線形検索は非常に解りやすく単純です。
しかし、データがたまたま１つ目にあったならば１回で目的のデータを検索できますが、最後にあった場合は最後まで処理を繰り返さなければなりません。
ｎ件のデータがあったとすれば、最小で１回、最大でｎ回の比較処理が行われるという事になります。

java.util.HashSet

線形検索のアルゴリズムを実装する前に集合を扱うクラスを用意する必要があります。
ArrayListを使っても実装できますが、ここではjava.util.HashSetクラスを使用しましょう。
HashSetはArrayListと同じようにCollections Frameworkに属するクラスで、順序を持たず重複を許可しない集合を定義します。

HashSetの主なコンストラクタを以下に示します。

コンストラクタ	概要
HashSet()	新しい空のセットを作成します。
HashSet(int initialCapacity)	新しい空のセットを作成します。

ArrayListと同様に通常はデフォルトのコンストラクタを使用しますが、容量が解っている場合には初期容量を指定することが可能です。。

HashSetクラスの主要なメソッドを以下に示します。

戻り値	メソッド	概要
boolean	add(Object o)	指定された要素がセットの要素として存在しない場合に、その要素をセットに追加します。
int	size()	セット内の要素数 (そのカーディナリティ) を返します。
boolean	isEmpty()	セットが要素を 1 つも保持していない場合に true を返します。
void	clear()	すべての要素をセットから削除します。
boolean	contains(Object elem)	contains(Object o)セットが、指定された要素を保持している場合に true を返します。
Iterator	iterator()	セットの要素の反復子を返します。
boolean	remove(Object o)	指定された要素があればセットから削除します。

このようにHashSetに定義されたメソッドはArrayListのメソッドとほとんど変わりません。
順序を持たない為、get(int index)がない以外はほとんど同じと言えます。
ただし、addがArrayListは重複していてもリストの最後に追加するのに対して、HashSetでは存在すれば追加と動きが異なることに注意します。
しかし、このようにメソッドを同じように使えるのがオブジェクト指向プログラミングの特徴です。

LinearSearch

それでは線形検索クラスを見ていきましょう。

package example06;

import java.util.HashSet;
import java.util.Iterator;

public class LinearSearch {
    
    // 要素を格納する集合
    private HashSet bookSet = new HashSet();
    // コンストラクタ
    public LinearSearch() {}
    // 本を追加
    public void add(Book book)
    {
        bookSet.add(book);
    }
    // 線形検索（存在しない場合はnullを返す）
    public Book search(String title)
    {
        for (Iterator iter = bookSet.iterator(); iter.hasNext();)
        {
            Book book = (Book) iter.next();
            if(title.equals(book.getTitle()) == true)
            {
                return book;
            }
        }
        return null;
    }
}

線形検索クラスはHashSetクラスを使い、本（要素）を保持しています。
本はaddメソッドを使い線形検索クラスに登録されます。
検索を行う場合は本のタイトルを引数としたメソッドを呼び出します。

add

add()メソッドは集合に本を追加するメソッドですが、重要な機能も兼ねています。
それはHashSetのadd()メソッドは引数がObject型である為、どのようなクラスをも要素として追加できてしまうのです。
そこで、LinerSearchクラスのadd()メソッドではBook型に限定し、間違ったクラスを追加できないように制御しています。

また、HashSetにはremove()メソッドなど多彩な機能が実装されています。
しかし、直接HashSetにアクセスさせるのではなく、LinerSearchクラスのメソッドを介する事で制限できているのです。

search

searchは線形検索を使い、検索処理を行うメソッドです。
この線形検索のアルゴリズムは一目瞭然でしょう。

    for (Iterator iter = bookSet.iterator(); iter.hasNext();)
    {
        Book book = (Book) iter.next();
        if(title.equals(book.getTitle()) == true)
        {
            return book;
        }
    }
    return null;

bookSetから反復子（Iterator）を取り出して順次処理を行います。
HashSetでは順序は定められているわけではないので、addで登録した順番に処理されるとは限りませんが、Iteratorの約束により順番に１つづつ処理されます。
後は要素をBookクラスにキャストしてタイトルを比較するだけです。
比較の結果等しければ、戻り値として返され、最後まで一致するタイトルがなければnullを返します。
このように日本語で説明すると長くなりますが、コードは処理を簡潔に記述しています。

確認用のコードは次のようになるでしょう（main()メソッドを持つクラスを作って試してください）。

    LinearSearch search = new LinearSearch();
    search.add(new Book("Java入門", 1980));
    search.add(new Book("Java入門(2)", 1980));
    search.add(new Book("C言語入門", 2100));
    search.add(new Book("C#入門", 2500));
    search.add(new Book("易しいJava", 1500));
    search.add(new Book("基礎から学ぶJava", 1500));
    search.add(new Book("Servlet/JSP入門", 31000));
    search.add(new Book("デザインパターン", 3400));
        
    Book book = search.search("基礎から学ぶJava");
    System.out.println(book);