(57)【要約】【課題】ハッシュ法の原空間が大きい場合であってもハッシュ衝突の発生を低減する。【解決手段】検索装置は、テーブルへの登録対象のデータ群の入力を受け付ける入力部と、入力されたデータ群それぞれを複数の区間に分割することにより所定のbit数の分割データを生成する分割部と、データ群の登録時に、所定のbit数のハッシュ値とポインタとしてNULLを対応付けたハッシュテーブルを作成し、作成したハッシュテーブルにおける分割データのハッシュ値に対応付けられるポインタをNULLから、当該分割データの分割元のデータにおいて当該分割データに続く分割データのハッシュテーブルへのポインタに更新し、ハッシュテーブルそれぞれをノードとするツリーを構築することにより、ハッシュテーブルそれぞれの使用メモリの総量を低減し、ハッシュテーブルにおけるハッシュ衝突を低減するテーブル作成部とを備える。【選択図】図１
2020119363.tif 000002
【特許請求の範囲】
【請求項１】
テーブルへの登録対象のデータ群の入力を受け付ける入力部と、
入力されたデータ群それぞれを複数の区間に分割することにより所定のbit数の分割データを生成する分割部と、
前記データ群の登録時に、前記所定のbit数のハッシュ値とポインタとしてNULLとを対応付けたハッシュテーブルを作成し、作成したハッシュテーブルにおける前記分割データのハッシュ値に対応付けられるポインタをNULLから、当該分割データの分割元のデータにおいて当該分割データに続く分割データのハッシュテーブルへのポインタに更新し、前記ハッシュテーブルそれぞれをノードとするツリーを構築することにより、前記ハッシュテーブルそれぞれの使用メモリの総量を低減し、前記ハッシュテーブルにおけるハッシュ衝突を低減するテーブル作成部と、
を備えることを特徴とする検索装置。
【請求項２】
前記テーブル作成部は、
前記区間ごとに、当該区間に属する前記分割データの種類を集計し、前記集計した分割データの種類が少ない区間の分割データのハッシュテーブルほど、前記ツリーのルート側に配置し、前記集計した分割データの種類が多い区間の分割データのハッシュテーブルほど、前記ツリーの末端側に配置した前記ツリーを構築することにより、登録可能なデータの数を増加させる
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記テーブル作成部は、
前記ハッシュテーブルに用いられるハッシュ関数として恒等関数を用いることにより、前記ハッシュテーブルにおけるハッシュ衝突を発生させない
ことを特徴とする請求項１に記載の検索装置。
【請求項４】
前記ツリーの使用メモリの総量が所定値を超える場合、前記分割区間の数を所定値よりも増加させる分割制御部をさらに備える
ことを特徴とする請求項１に記載の検索装置。
【請求項５】
前記テーブル作成部は、
前記ツリーの使用メモリの総量が所定値を超える場合、前記ハッシュテーブルに用いられるハッシュ関数の縮尺度を所定値よりも高める
ことを特徴とする請求項１に記載の検索装置。
【請求項６】
前記ツリーの使用メモリの総量が所定値を超える場合、記憶部に記憶された設定情報に従い、前記分割制御部に前記分割区間の数を所定値よりも増加させる指示、または、前記テーブル作成部に、前記ハッシュテーブルに用いられるハッシュ関数の縮尺度を所定値よりも高める指示を行う指示部をさらに備える
ことを特徴とする請求項４に記載の検索装置。
【請求項７】
検索装置により実行されるハッシュテーブルの作成方法であって、
テーブルへの登録対象のデータ群の入力を受け付けるステップと、
入力されたデータ群それぞれを複数の区間に分割することにより所定のbit数の分割データを生成するステップと、
前記データ群の登録時に、前記所定のbit数のハッシュ値とポインタとしてNULLとを対応付けたハッシュテーブルを作成し、作成したハッシュテーブルにおける前記分割データのハッシュ値に対応付けられるポインタをNULLから、当該分割データの分割元のデータにおいて当該分割データに続く分割データのハッシュテーブルへのポインタに更新し、前記ハッシュテーブルそれぞれをノードとするツリーを構築することにより、前記ハッシュテーブルそれぞれの使用メモリの総量を低減し、前記ハッシュテーブルにおけるハッシュ衝突を低減するステップと、
を含むことを特徴とするハッシュテーブルの作成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、および、ハッシュテーブルの作成方法に関する。
【背景技術】
【０００２】
従来、パケットの転送等において、どのパケットにどのruleを適用するかの検索にハッシュ法が用いられていた。このハッシュ法は高速な検索を実現する技術である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】ALAXALA、［平成31年1月13日検索］、インターネット＜URL：https://www.nic.ad.jp/ja/materials/iw/2012/proceedings/d1/＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ここで、ハッシュ法の原空間が大きい場合、メモリ等のリソース上の問題から、ハッシュ空間の縮尺度を高めなければならず、その縮尺度に応じてハッシュ衝突のリスクが生じる。
【０００５】
例えば、検索に用いられるハッシュ空間をＮbitとし、ハッシュ関数として恒等関数（y=x）を使用し、64bitマシンを用いる場合、ハッシュテーブルには、2N×64(bit)のメモリリソースが必要である。ここで、ハッシュテーブルのメモリリソースを16GByte以内に抑えたい場合、ハッシュ空間は31bit以下である必要がある。よって、ハッシュ法の原空間が64bitの場合、縮尺度が1/（233）のハッシュ関数を選択しなければならない。その結果、登録対象のrule（データ）の数が10億以下であれば、すべてのデータが同じハッシュ値にマッピングされる場合もあり、その場合、すべての登録データを線形検索しなければならない。例えば、非特許文献１に記載の技術においても、ハッシュ空間を縮尺するため、複数のデータが１つのハッシュ値にマッピングされ、固定化されず、再度検索する必要が出てくる。
【０００６】
そこで、本発明は、前記した問題を解決し、ハッシュ法の原空間が大きい場合であってもハッシュ衝突の発生を低減することを課題とする。
【課題を解決するための手段】
【０００７】
前記した課題を解決するため、本発明は、テーブルへの登録対象のデータ群の入力を受け付ける入力部と、入力されたデータ群それぞれを複数の区間に分割することにより所定のbit数の分割データを生成する分割部と、前記データ群の登録時に、前記所定のbit数のハッシュ値とポインタとしてNULLとを対応付けたハッシュテーブルを作成し、作成したハッシュテーブルにおいて前記分割データのハッシュ値に対応付けられるポインタをNULLから、当該分割データの分割元のデータにおいて当該分割データに続く分割データのハッシュテーブルへのポインタに更新し、前記ハッシュテーブルそれぞれをノードとするツリーを構築することにより、前記ハッシュテーブルそれぞれの使用メモリの総量を低減し、前記ハッシュテーブルにおけるハッシュ衝突を低減するテーブル作成部と、を備えることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、ハッシュ法の原空間が大きい場合であってもハッシュ衝突の発生を低減することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、第１の実施形態の検索装置が構築するハッシュテーブルのツリーの一例を示す図である。
【図２】図２は、各実施形態の検索装置の構成例を示す図である。
【図３】図３は、第２の実施形態の検索装置の効果を説明するための図である。
【図４】図４は、第３の実施形態の検索装置の効果を説明するための図である。
【図５】図５は、第４の実施形態の検索装置が作成するハッシュテーブルのツリーの使用メモリ量の最大値を説明するための図である。
【図６】図６は、各実施形態の検索装置の機能を実現するプログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照しながら、本発明を実施するための形態（実施形態）を第１の実施形態から第４の実施形態に分けて説明する。本発明は、各実施形態に限定されない。
【００１１】
［第１の実施形態］
［ハッシュテーブルのツリーの例］
まず、図１を用いて、第１の実施形態におけるハッシュテーブルのツリーの構築例を説明する。ここではデータの検索に用いられるハッシュ空間（原空間）が64bitである場合を例に説明する。本実施形態の検索装置は、例えば、検索に用いられる64bitのハッシュ空間を４つに分割し、16bitのハッシュ空間を示すハッシュテーブルをノードとするツリーを構築する。
【００１２】
この検索装置は、ハッシュテーブルへの登録対象のデータ（以下、適宜「rule」と称す）群の入力を受け付けると、登録に必要なハッシュテーブルを新規に作成する。ここでは、ハッシュテーブルに用いるハッシュ関数として、恒等関数（y=x）を用いる場合を例に説明する。
【００１３】
また、本実施形態におけるハッシュテーブルは、ハッシュ値とポインタとを対応付けたテーブルである。なお、図１に示すハッシュテーブル１０４，１０６，１０９，１１０のハッシュ値には、bool（false/true）が対応付けられているが、ポインタを対応付けてもよい。
【００１４】
例えば、検索装置が、図１に示す（１）〜（４）のデータを４つの区間（区間１１１〜１１４）に分割し、分割されたデータ（分割データ）を16bitのハッシュテーブル１０１〜１１０に登録する。具体的には、検索装置は、ハッシュテーブル１０１において（１）〜（４）のデータに登場する分割データ（＝ハッシュ値）に対応するポインタを「NULL」から「NP（ネクストポインタ）」に更新する。そして、このNPに対応するハッシュテーブル（例えば、ハッシュテーブル１０２）のハッシュ値のうち、上記の分割データに続く分割データに対応するポインタを「NULL」から「NP」に更新する。
【００１５】
例えば、検索装置は、ハッシュテーブル１０１を作成し、このハッシュテーブル１０１における分割データ「２００」および「３００」のポインタを「NULL」から「NP」に更新する。次に、検索装置は、ハッシュテーブル１０２を作成すると、このハッシュテーブル１０２において、上記の分割データ「２００」に続く分割データ「３００」および「６００」のポインタを「NULL」から「NP」に更新する。検索装置は、上記の処理を（１）〜（４）のデータそれぞれについて実行することにより、（１）〜（４）のデータをハッシュテーブル１０１〜１１０に登録する。その結果、ハッシュテーブル１０１〜１１０をノードとし、ノード同士がNPにより接続されたハッシュテーブルのツリーが構築される。
【００１６】
検索装置が、上記のハッシュテーブルのツリーを構築した後、例えば、（１）のデータの検索要求を受け付けた場合、図１に示すハッシュテーブルのツリーを辿ることにより、（１）のデータを検索する。検索の結果、（１）のデータを発見すると、検索装置はtrueを返し、（１）のデータを発見できなかった場合、検索装置はfalseを返す。
【００１７】
上記のように、検索装置は、例えば、検索対象となるハッシュ空間を分割し、分割したハッシュ空間を示すハッシュテーブルのツリーを構築する。また、検索装置は、データの登録時に必要なハッシュテーブルを作成する。その結果、検索対象となるハッシュ空間が比較的大きい場合であっても、ハッシュテーブルの使用メモリ量を大幅に低減することができる。これにより、検索装置は、ハッシュテーブルに用いるハッシュ値を縮尺しないでよい、あるいは、ハッシュ値を縮尺する場合であっても縮尺度を小さくすることができるので、ハッシュ衝突の発生を低減することができる。また、例えば、検索装置において、各ハッシュテーブルに使用することができるメモリ量の総量（つまり、rule登録に使用することができるメモリ量の総量）が所定値（例えば、16GByte）以内に限られている場合であっても、使用メモリ量を上記の所定値以内に収めることができる。
【００１８】
［構成］
次に、図２を用いて第１の実施形態の検索装置１０の構成例を説明する。検索装置１０は、入力部１１、制御部１２、記憶部１３、出力部１４を備える。
【００１９】
入力部１１および出力部１４は、例えば、検索装置１０の備える入出力インタフェースにより、実現される。制御部１２は、例えば、検索装置１０の備えるＣＰＵによるプログラム実行処理により実現される。記憶部１３は、例えば、検索装置１０の備えるメインメモリおよびハードディスク装置により実現される。
【００２０】
入力部１１は、各種データの入力を受け付ける。例えば、入力部１１は、ハッシュテーブルへの登録対象となるデータ群の入力を受け付ける。制御部１２は、検索装置１０全体の制御を司り、例えば、分割部１２１と、テーブル作成部１２２と、検索部１２３とを備える。破線で示す分割制御部１２４および指示部１２５は装備される場合と装備されない場合とがあり、装備される場合については、後記する。
【００２１】
分割部１２１は、入力されたデータ群それぞれを複数の区間に分割することにより所定のbit数の分割データを生成する。
【００２２】
テーブル作成部１２２は、登録対象のデータの登録先となるハッシュテーブルを作成し、作成したハッシュテーブルにデータを登録する。具体的には、テーブル作成部１２２は、上記の所定のbit数のハッシュ値とポインタとを対応付けたハッシュテーブルを作成する。そして、テーブル作成部１２２は、作成したハッシュテーブルに、分割部１２１により生成された分割データを登録する。例えば、テーブル作成部１２２は、作成したハッシュテーブルにおいて、当該分割データのハッシュ値に対応付けられるポインタを、当該分割データの分割元のデータにおいて当該分割データに続く分割データのハッシュテーブルへのポインタ（上記のNP）に更新する。テーブル作成部１２２は、このような処理を、登録対象となるデータの末尾の区間の分割データまで繰り返す。これにより、検索対象となるハッシュテーブルがポインタ（上記のNP）により接続された、ハッシュテーブルのツリーが構築される。
【００２３】
検索部１２３は、テーブル作成部１２２により作成されたハッシュテーブルのツリーを用いて、検索対象のデータを検索し、出力部１４経由で検索結果を出力する。
【００２４】
記憶部１３は、制御部１２が動作するために必要な各種データを記憶する。例えば、記憶部１３は、ハッシュ空間の分割数等を記憶する。この分割数は、例えば、入力部１１からの指示入力に基づき適宜変更可能である。また、記憶部１３は、テーブル作成部１２２により作成されたハッシュテーブルを記憶する。
【００２５】
出力部１４は、制御部１２による処理結果を出力する。例えば、出力部１４は、検索部１２３による検索結果を出力する。
【００２６】
このような検索装置１０によれば、例えば、64bitのハッシュ空間を４分割し、10000ruleを登録した場合でも、メモリ使用量は最大で15.7GByte程度である。つまり、上記の場合、ハッシュテーブルの数は最大で1＋10000+10000+10000=30001であるので、メモリ使用量を、30001（テーブル数）×65536（1テーブルあたりのindex数）×8Byte（1indexあたりの容量）≒15.7GByte以内に収めることができる。
【００２７】
このように検索装置１０は、登録対象のruleに関するハッシュテーブルのみを新規に作成するので、ハッシュテーブルに必要なメモリ領域を低減できる。その結果、ハッシュ関数として恒等関数（y=x）を用いやすくなる。また、従来技術のようにハッシュ空間を分割せずに上記の10000ruleを登録する場合、ハッシュ空間の縮尺度を高める必要がある。よって、ruleの検索時に最大で10000回のハッシュ衝突が発生するので、検索時間が長くなってしまうおそれがある。一方、検索装置１０の場合、ruleの検索時に、（ハッシュ空間の分割数−1）回のNULL判定が発生するものの、ハッシュ空間の縮尺度を高める必要がなくなる。その結果、ハッシュ衝突の発生を低減することができるので、検索時間が長くなることを防止することができる。
【００２８】
［第２の実施形態］
次に、第２の実施形態の検索装置１０を説明する。第１の実施形態と同じ構成は同じ符号を付して説明を省略する。
【００２９】
第２の実施形態の検索装置１０のテーブル作成部１２２は、分割部１２１において、登録対象のrule群それぞれを所定のbit数の区間に区切った分割データを生成した後、区間ごとに、当該区間に属する分割データ群の種類を集計する。そして、テーブル作成部１２２は、ハッシュテーブルのツリーを構築する際、集計した分割データの種類が少ない区間の分割データのハッシュテーブルほど、ツリーのルート側に配置し、集計した分割データの種類が多い区間の分割データのハッシュテーブルほど、ツリーの末端側に配置する。このようにすることで、検索装置１０は、ハッシュテーブルのツリーの使用メモリ量を低減することができる。その結果、検索装置１０は、ハッシュテーブルのツリーに登録可能なrule数を増加させることができる。例えば、検索装置１０においてrule登録に使用することができるメモリ量の総量が所定値（例えば、16GByte）以内に限られている場合あっても、より多くのruleを登録することができる。
【００３０】
例えば、図１の（１）〜（４）に示すruleを４つの区間（区間１１１，１１２，１１３，１１４）に区切った場合、分割データの種類が最も少ないのは区間１１１であり（２種類）、２番目に分割データの種類が少ないのは区間１１２，１１４であり（３種類）、最も分割データの種類が多いのは区間１１３である（４種類）。
【００３１】
よって、テーブル作成部１２２は、テーブル作成部１２２は区間１１１の分割データのハッシュテーブルをツリーのルート側に配置し、区間１１３の分割データのハッシュテーブルをツリーの末端側に配置し、区間１１２，１１４の分割データのハッシュテーブルをツリーのルートと末端との間に配置する。
【００３２】
また、検索装置１０は64bitのデータを４分割した際の区間ごとの分割データの種類数がそれぞれ1、10、1000、50000である10万ruleを登録する場合の使用メモリ量の計算例を、図３を参照しながら説明する。
【００３３】
例えば、分割データの種類数が「50000」の区間における分割データ群のハッシュテーブルをツリーのルート側に配置し、ツリーの末端方向に向かって、種類数の昇順に、種類数が「1000」の区間における分割データのハッシュテーブル→種類数が「10」の区間における分割データのハッシュテーブル→種類数が「1」の区間における分割データのハッシュテーブルという順に配置した場合を考える。この場合、各区間におけるテーブル数の最大値は、図３（ａ）に示すように1、50000、100000、100000なので、ハッシュテーブルの数の合計は最大で1+50000+100000+100000=250001である。よって、ハッシュテーブルのツリーの使用メモリ量は最大で約131.1GByteで、16GByte以内に収まらない可能性がある。
【００３４】
一方、検索装置１０のテーブル作成部１２２は、分割データの種類数が「1」の区間における分割データのハッシュテーブルをツリーのルート側に配置し、ツリーの末端方向に向かって、種類数の昇順に、種類数が「10」の区間における分割データのハッシュテーブル→種類数が「1000」の区間における分割データのハッシュテーブル→種類数が「50000」の区間における分割データのハッシュテーブルという順に配置する。この場合、各区間におけるテーブル数の最大値は、図３（ｂ）に示すように1、1、10、10000なので、ハッシュテーブルの数の合計は最大で1+1+10+10000=10011である。よって、ハッシュテーブルのツリーの使用メモリ量は最大で約5.2GByteで、16GByte以内に収まる。
【００３５】
［第３の実施形態］
次に、第３の実施形態の検索装置１０を説明する。前記した実施形態と同じ構成は同じ符号を付して説明を省略する。
【００３６】
第１の実施形態で述べたとおり、ハッシュ空間の分割数（例えば、第１の実施形態においては４分割）を増やすほど、ハッシュテーブルのツリーが使用するメモリ領域を節約することができる。そこで、予めハッシュテーブルのツリーが使用する最大メモリ領域（閾値）をコンフィグ等で検索装置１０に指定しておき、ハッシュテーブルのツリーが使用するメモリ領域の総量（使用メモリ量）が上記の閾値を超える場合、検索装置１０は、上記の分割数を増加させてもよい。
【００３７】
例えば、第３の実施形態において、検索装置１０は、破線で示す分割制御部１２４をさらに備える。分割制御部１２４は、ハッシュテーブルのツリーの使用メモリの総量が所定の閾値を超える場合、ハッシュ空間の分割数を所定数より増加させる。
【００３８】
例えば、分割制御部１２４は、ハッシュテーブルのツリーの使用メモリの総量が所定の閾値を超えると判断した場合、分割部１２１およびテーブル作成部１２２の用いる分割数が当初「4」であったところ、「8」に増加させる。例えば、分割制御部１２４は、分割部１２１に登録対象のruleそれぞれを8bitずつに分割した分割データを生成するよう指示し、また、テーブル作成部１２２に8bitのハッシュ値とポインタとを対応付けたハッシュテーブルを作成するよう指示する。
【００３９】
これにより検索装置１０は、例えば、登録対象のrule数が多い場合でも、ハッシュテーブルのツリーの使用メモリの総量を所定の閾値以内に収めることができる。その結果、例えば、検索装置１０においてrule登録に使用することができるメモリ量の総量が所定の閾値（例えば、16GByte）以内に限られている場合において、登録対象のrule数が増加したときでも、これに対応することができる。
【００４０】
例えば、rule登録に使用することができるメモリ量の総量が16GByte以内に限られている場合において、検索装置１０が、10万ruleをハッシュテーブルのツリーに登録するときを考える。この場合、検索装置１０が、ハッシュ空間の分割数を「4」とすると、例えば、図４（ａ）に示すように、ハッシュテーブルのテーブル数は最大で1+65536+100000+100000=265537である。よって、ハッシュテーブルのツリーに使用メモリ量は、最大で約139.2GByteで、16GByte以内に収まらず、その結果、検索装置１０は、登録対象のruleを登録できない可能性がある。
【００４１】
一方、第３の実施形態の検索装置１０のように、ハッシュ空間の分割数を「8」とする（つまり、8bitずつに分割する）と、例えば、図４（ｂ）に示すように、ハッシュテーブルのテーブル数は最大で1+256+65536+100000+…+100000=565793である。よって、ハッシュテーブルのツリーの使用メモリ量は、最大でも約1.2GByteで、16GByte以内に収めることができる。その結果、検索装置１０は、登録対象のruleを登録することができる。
【００４２】
［第４の実施形態］
次に、第４の実施形態の検索装置１０を説明する。前記した実施形態と同じ構成は同じ符号を付して説明を省略する。
【００４３】
前記したとおり検索装置１０は、ハッシュ関数の縮尺度を高めることによっても、ハッシュテーブルのツリーが使用するメモリ領域を節約することができる。そこで、予めハッシュテーブルのツリーが使用する最大メモリ領域（閾値）をコンフィグ等で検索装置１０に指定しておき、ハッシュテーブルのツリーの使用メモリの総量が上記の閾値を超える場合、検索装置１０は、ハッシュ関数の縮尺度を高めるようにしてもよい。
【００４４】
ここで、ハッシュ関数の縮尺度を高めるとは、例えば、検索装置１０がハッシュ関数にmod  N（Nは自然数）を用いていた場合、Nの値を今まで使っていた値よりも小さくする。あるいは、検索装置１０がもともとハッシュ関数に恒等関数を用いていた場合、ハッシュ関数にmod  N（Nは自然数）を用いるようにすることである。この場合の実施形態を第４の実施形態として説明する。
【００４５】
例えば、第３の実施形態の項で述べたとおり、検索装置１０が10万ruleを登録する場合において、ハッシュ関数として恒等関数を用いると、ハッシュテーブルのツリーの使用メモリの総量は16GByteを超える可能性がある。しかし、検索装置１０が、例えば、ハッシュ関数としてy=x  mod  8192(縮尺  1/8)を用いることで、10万ruleを登録する場合でも、ハッシュテーブルのツリーの使用メモリ量は、最大で約13.6GByteで、に抑えることができる。このことを、図５を用いて説明する。
【００４６】
例えば、図５に示すように、検索装置１０が64bitのハッシュ区間を４分割し、10万ruleを登録する場合において、各ハッシュテーブルに用いるハッシュ関数としてmod  8192(縮尺  1/8)を適用したとき、ハッシュテーブルのテーブル数は最大で1+8192+100000+100000=208193となる。よって、ハッシュテーブルのツリーの使用メモリ量は、最大で約13.6GByteで、16GByte以内に収まる。
【００４７】
[その他の実施形態]
なお、検索装置１０は、ハッシュテーブルのツリーの使用メモリの総量が所定の閾値を超える場合、ハッシュ空間の分割数を増加させる（第３の実施形態参照）か、ハッシュテーブルに用いられるハッシュ関数の縮尺度を高める（第４の実施形態参照）かを、検索装置１０の利用者が設定してもよい。
【００４８】
この場合、検索装置１０は、ハッシュテーブルのツリーの使用メモリの総量が所定の閾値を超える場合、ハッシュ空間の分割数を増加させるか、ハッシュ関数の縮尺度を高めるかを示す設定情報を入力部１１経由で受け付けると、当該設定情報を記憶部１３に格納しておく。そして、検索装置１０の指示部１２５（図１参照）は、ハッシュテーブルのツリーの使用メモリの総量が所定値を超える場合、記憶部１３に記憶された設定情報に従い、分割制御部１２４に分割数を所定値よりも増加させる指示、または、テーブル作成部１２２に、ハッシュテーブルに用いられるハッシュ関数の縮尺度を所定値よりも高める指示を行う。
【００４９】
このようにすることで、ハッシュテーブルのツリーの使用メモリの総量が所定値を超える場合、検索装置１０がハッシュ空間の分割数を増加させる（第３の実施形態参照）方式を採るか、各ハッシュテーブルに用いられるハッシュ関数の縮尺度を高める（第４の実施形態参照）方式を採るかを検索装置１０の利用者が指定することができる。
【００５０】
なお、検索装置１０は、ハッシュテーブルのツリーの使用メモリの総量に応じて、ハッシュ空間の分割数、および、各ハッシュテーブルに用いられるハッシュ関数の縮尺度を決定してもよい。例えば、検索装置１０は、ハッシュテーブルのツリーの使用メモリの総量が大きいほど（つまり、登録rule数が多いほど）、ハッシュ空間の分割数を増加させ、あるいは、各ハッシュテーブルに用いられるハッシュ関数の縮尺度を高くしてもよい。
【００５１】
［プログラム］
また、上記の実施形態で述べた検索装置１０の機能を実現するプログラムを所望の情報処理装置（コンピュータ）にインストールすることによって実装できる。例えば、パッケージソフトウェアやオンラインソフトウェアとして提供される上記のプログラムを情報処理装置に実行させることにより、情報処理装置を検索装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータ、ラック搭載型のサーバコンピュータ等が含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等がその範疇に含まれる。また、検索装置１０を、クラウドサーバに実装してもよい。
【００５２】
図６を用いて、上記のプログラムを実行するコンピュータの一例を説明する。図６に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００５３】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【００５４】
ここで、図６に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。前記した実施形態で説明した各種データや情報は、例えばハードディスクドライブ１０９０やメモリ１０１０に記憶される。
【００５５】
そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００５６】
なお、上記のプログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、上記のプログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮやＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００５７】
１０  検索装置
１１  入力部
１２  制御部
１３  記憶部
１２１  分割部
１２２  テーブル作成部
１２３  検索部
１２４  分割制御部
１２５  指示部
【図１】
2020119363.tif 000003
【図２】
2020119363.tif 000004
【図３】
2020119363.tif 000005
【図４】
2020119363.tif 000006
【図５】
2020119363.tif 000007
【図６】
2020119363.tif 000008