(57)【要約】【課題】  データ検索処理不可によるサービスの開始遅延・中断などを防止するとともに、ハッシュアルゴリズムの選び直しやそれに伴うデータの再格納処理の頻発を防止し、システム全体への影響を最小限に抑えることができるハッシュテーブルの生成方法を提供する。【解決手段】  一つのハッシュテーブル（以下、運用テーブルとよぶ）を使用してデータ格納およびデータ検索を行う運用モードと、運用テーブルのハッシュアルゴリズムを選定するために異なるハッシュアルゴリズムに基づいた複数のハッシュテーブル（以下、サンプルテーブルとよぶ）を用いてデータ格納およびデータ検索を行うサンプリングモードとを持つ。両モードの切り替えは、モードの有効期間切れを契機に自動的に行われる。【選択図】  図４
2008084244.tif 000002
【特許請求の範囲】
【請求項１】
一つのハッシュテーブルを使用してデータ格納およびデータ検索を行う運用モードと、
前記運用モードで用いるハッシュテーブルのハッシュアルゴリズムを選択するために異なるハッシュアルゴリズムに基づく複数のハッシュテーブルを用いてデータ格納およびデータ検索を行うサンプリングモードとを備え、
前記二つのモードの切り替えを、モード毎の有効期間が切れたことにより行うことを特徴とするハッシュテーブル生成方法。
【請求項２】
請求項１のハッシュテーブル生成方法において、
前記サンプリングモードから前記運用モードへの切り替えの際に、サンプリングモード時に用いていた複数のハッシュテーブル毎にデータの偏りについての標準偏差を計算して、最も偏りが小さいハッシュアルゴリズムを選定し、
前記選定したアルゴリズムを用いてサンプリングモード時に用いられていた複数のハッシュテーブルに分散格納されていた全データを運用モードで用いるための一つのハッシュテーブルに格納する制御処理を行うことを特徴とするハッシュテーブル生成方法。
【請求項３】
請求項１のハッシュテーブル生成方法において、
前記運用モードから前記サンプリングモードの切り替えの際には、運用モード時に用いていた一つのハッシュテーブルに格納されていた全データをサンプリングモードで用いる複数のハッシュテーブルに分散格納する制御処理を行うことを特徴とするハッシュテーブル生成方法。
【請求項４】
請求項１のハッシュテーブル生成方法について、
前記運用モードと前記サンプリングモードを切り替えるコマンドに従って、前記モード切り替えを行うことを特徴とするハッシュテーブル生成方法。
【請求項５】
請求項１のハッシュテーブル生成方法について、
前記サンプリングモード時のサンプルテーブルの総数やサンプルモード時間をユーザが指定できる設定機能を有することを特徴とするハッシュテーブル生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュテーブルの生成方法に関し、特にハッシュテーブルのデータ格納およびデータ検索のためのハッシュテーブル生成方法に関する。
【背景技術】
【０００２】
データ検索速度を早めるためのデータの格納方法として、ハッシュテーブルを利用する方法がある。
【０００３】
ハッシュテーブルでは、データはハッシュアルゴリズムによって計算されたハッシュ値に対応するエントリに格納される。このため、ハッシュテーブルを利用したデータ検索は各種のツリー構造と異なり静的な配列だけで簡単に実装でき、かつ高速にデータ検索が行える非常に実用的な手法の一つである。
【０００４】
しかし、データの傾向と使用するハッシュアルゴリズムによっては、データの格納状況に偏りが生じてしまう場合があり、偏りがない場合に比べてデータの検索速度が遅くなってしまう問題がある。
【０００５】
格納データの偏りによる検索速度低下の問題の解決方法について、下記特許文献１や下記特許文献２に記載されたものが知られている。
【０００６】
下記特許文献１は、ハッシュアルゴリズムの計算式の係数を変化させたものについて順にデータをハッシュ計算してハッシュの分布情報を作成し、最初に空きエントリと最大分布数が一定値を下回ったハッシュアルゴリズムを採用するというものである。
【０００７】
また、下記特許文献２は、データが追加されるたびにハッシュテーブルの偏りを計算して、偏りが一定値を超えた時点で次の別のハッシュアルゴリズムを採用してハッシュテーブルを再作成するというもので、傾向の異なるデータが追加されるような状況でも動的にハッシュアルゴリズムを変更していくためデータの偏りを一定値以内に押さえることができ、かつ検索速度の低下を防ぐことができるというものである。
【０００８】
【特許文献１】特開平７−１６８８４１号公報
【特許文献２】特開平１１−８５７７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、上記特許文献１では、最適なハッシュアルゴリズムを選定するために係数の異なる複数のハッシュアルゴリズムを順次用いて格納対象となる全データのハッシュ値の個数分布を計算し、最初に偏りの分布が一定値を下回ったアルゴリズムを採用する方式であるため、ハッシュアルゴリズムが選定されるまでは実データによるハッシュテーブルの作成が行われない。そのため、システムの初期立ち上げ時のようにハッシュテーブルが存在しない状況ではハッシュアルゴリズムの選定が終わりハッシュテーブルが作成されるまでデータ検索ができないため運用状態に入れず、その分だけ初期化処理に時間が掛かってしまう問題がある。
【００１０】
また、上記特許文献２では、偏りが一定値を超えた時点を契機に別ハッシュアルゴリズムでハッシュテーブルを再作成するが、それでも偏りが解消されない場合などはハッシュアルゴリズムの選定のやり直しや、それに伴うデータの再格納処理が頻発する可能性がある。データの再格納処理は、データ量が多いほどシステムへの影響も大きいため処理遅延の原因となる。
【００１１】
本発明の目的は、ハッシュテーブル運用時の格納データの偏りについての解決方法として、データ検索処理不可によるサービスの開始遅延・中断などを防止するとともに、ハッシュアルゴリズムの選び直しやそれに伴うデータの再格納処理の頻発を防止するといった上記特許文献１および上記特許文献２の弱点を克服することを実現し、システム全体への影響を最小限に抑えることができるハッシュテーブルの実装方式を提供することにある。
【課題を解決するための手段】
【００１２】
本発明では、ハッシュテーブルは二つのモードを取る。具体的には、一つのハッシュテーブル（以下、運用テーブルとよぶ）を使用してデータ格納およびデータ検索を行う運用モードと、運用テーブルのハッシュアルゴリズムを選定するために異なるハッシュアルゴリズムに基づいた複数のハッシュテーブル（以下、サンプルテーブルとよぶ）を用いてデータ格納およびデータ検索を行うサンプリングモードとを持つ。両モードの切り替えは、モードの有効期間切れを契機に自動的に行われる。これにより、検索速度の劣化するような場合でも、定期的にサンプリングモードに切り替わることで最適なハッシュアルゴリズムを再選定して運用テーブルを再作成できるので、データの傾向の変化にも動的に対応することができる。
【００１３】
また、上記特許文献１の問題を解決する手段として、サンプリングモード時におけるハッシュアルゴリズムの選定の際でもサンプルテーブルを用いることにより、データ検索処理要求が発生しても、これらのサンプルテーブルを検索することで対応することができる。そのため、運用モード中でもサンプリングモード中でも常にデータの検索処理を行うことが可能であり、データ検索処理不可によるサービスの開始遅延・中断などを防止することができる。
【００１４】
次に、上記特許文献２の問題を解決する手段として、サンプリングモード時のハッシュアルゴリズム選定の際に複数のサンプルテーブルの中から最良のものを決定する方式を実装する。具体的には、サンプルテーブル毎に各ハッシュ値に対応して格納されたデータ個数の分散度合いを示す標準偏差を求め、この標準偏差の最も小さいサンプルテーブルで用いられているハッシュアルゴリズムを選定する。これにより、ハッシュアルゴリズムの選定のやり直しやそれに伴うデータの再格納処理の頻発を防止し、システムへの影響を最小限にすることができる。
【００１５】
前記の解決策に加えて、運用モードとサンプリングモードとを切り替えるコマンドを実装し、ユーザによる任意のモード切り替えをも可能とする。また、サンプリングモード時のサンプリングモードの有効時間やサンプルテーブル数をユーザが設定できるようにすることで、システムの運用への影響を配慮し、またアルゴリズムの選定の精度を調整できる。
【発明の効果】
【００１６】
本発明により、以下の効果がある。
（１）運用サービス中は常にデータ検索を行うことができるため、データ検索処理不可によるサービスの開始遅延・中断などを防止することができる。
（２）ハッシュアルゴリズムの選定のやり直しやそれに伴うデータの再格納処理の頻発を防止し、システムへの影響を最小限にすることができる。
（３）サンプリングモード時のサンプリングモード実行時間やサンプルテーブルの総数をユーザが設定できるようにすることで、システムの運用への影響やアルゴリズムの選定の精度を調整できる。
（４）追加データの傾向が変わってハッシュテーブルのデータ格納状況に偏りが生じても、ユーザがサンプリングモードに切り替えることで最適なハッシュテーブルを再作成できるので、データの偏りに動的に対応することができる。
【発明を実施するための最良の形態】
【００１７】
図１は、本発明によるハッシュテーブルが持ちうる２つの状態を表した状態遷移図である。運用モード（１０１）とサンプリングモード（１０２）の２つの状態を持ち、運用モードからサンプリングモードへの状態遷移（１０３）はユーザによるモード切り替えのコマンド投入、または運用モードの有効時間切れを契機として行われる。またはサンプリングモードから運用モードへの状態遷移（１０４）はサンプリングモードの有効時間切れを契機として行われる。
【００１８】
図２は、サンプリングモードでの処理概要図である。ユーザが設定したサンプルテーブルの総数（以下、サンプル総数と呼ぶ）N個の、各々異なるハッシュアルゴリズムによるハッシュテーブル（２０１、２０２、２０３、２０４）に対してデータの追加および検索を行う。なお、サンプリングモード中に追加データ（２０５）が発生した際は、時間帯に応じて特定のサンプルテーブルに対してデータの追加を行う。この時間帯の設定については、ユーザが設定したサンプルモードの有効期間（以下、サンプリング時間と呼ぶ）Tに基づき、一つのサンプルテーブルがもつデータ追加有効期間をT/Nとして、各サンプルテーブルを順番に持ちまわりにするものとする。また、サンプリングモード中にデータ検索を行う場合は、N個のサンプルテーブル全てに対して検索を行うため、サンプリングモード中でもデータ検索が中断されることなく実行でき、システム運用を継続的に行うことを可能にする。
【００１９】
また、サンプルモードの有効期間が終了した時点で、各サンプルテーブルの格納データの個数分布について、最も小さい標準偏差の値を持つサンプルテーブルのハッシュアルゴリズムを運用テーブルのためのアルゴリズムとして選定する。
【００２０】
図３は、サンプリングモードの処理概要を示すフローチャートである。
【００２１】
ユーザによってあらかじめ設定されているサンプル総数、サンプリング時間をそれぞれ変数N、変数Tに設定する（ステップ３０１）。もし、ユーザによってこれらの設定がされていなかった場合はデフォルト値等で対応する
次に、運用テーブルにデータがあれば、それらのデータをN個のサンプルテーブルに分散して格納し（ステップ３０２）、そののち不要となった運用テーブルをクリアする。（ステップ３０３）
また、サンプリングモードの経過時間を表すパラメータtを０で初期化し（ステップ３０４）、サンプルテーブルを番号として区別するためのパラメータiを１で初期化する（ステップ３０５）。
【００２２】
そして、各サンプルテーブルのサンプリング時間をT/Nとし、追加データが発生した際はtについて、(i-1)T/N≦t≦i・T/Nの条件を満たす期間中は第i番目のサンプルテーブルにのみデータの格納を行う（ステップ３０７、ステップ３０８、ステップ３０９）。第i番目のサンプルテーブルへのデータ格納期間が終了したら、第i番目のサンプルテーブルについてデータの個数分布の標準偏差を計算し（ステップ３１０）、パラメータiをインクリメントする（ステップ３１１）。これらの一連の処理（ステップ３０７、ステップ３０８、ステップ３０９、ステップ３１０、ステップ３１１）をパラメータiについて1からNまでループ処理で行う（ステップ３０６、ステップ３１２）ことで、全サンプルテーブルについてデータ格納処理を行う。
【００２３】
全サンプルテーブルへのデータ格納が終了した時点で、各サンプルテーブルのデータ個数の標準偏差について、最も小さい標準偏差をもつサンプルテーブルのハッシュアルゴリズムを運用テーブルのためのハッシュアルゴリズムとして採用して（ステップ３１３）サンプルモードを終了する。
【００２４】
図４は、運用モードの処理概要図である。
【００２５】
サンプリングモード時に使用していた全サンプルテーブル（４０１、４０２、４０３、４０４）のうち、格納データの標準偏差が最も小さいものが第２番目のサンプルテーブル（４０２）だった場合、第２番目のサンプルテーブルで採用していたハッシュアルゴリズムを各サンプルテーブルに格納されている全データに適用して、一つの運用テーブル（４０６）に統合する。そのため、運用モードではデータの追加（４０５）や検索処理が発生した場合は、この運用テーブル（４０６）に対して必要な処理を行う。
【００２６】
図５は、運用モードのうち、運用モード開始直後に行う運用テーブル生成処理の概要に特化したフローチャート図である。
【００２７】
ユーザによってあらかじめ設定されているサンプル総数を変数Nに設定する（ステップ５０１）。もし、ユーザによってこれらの設定がされていなかった場合はデフォルト値等で対応する
また、サンプルテーブルを番号として区別するためのパラメータiを１で初期化する（ステップ５０２）。
【００２８】
そして、i番目のサンプルテーブルに格納されている全データを、サンプリングモード時に採用されたハッシュアルゴリズムで再計算して運用テーブルに格納する（ステップ５０４）。つづいて、不要となった第i番目のサンプルテーブルをクリアし（ステップ５０５）、パラメータiをインクリメントする（ステップ５０６）。これら一連の処理（ステップ５０４、ステップ５０５、ステップ５０６）をパラメータiについて1からNまでループ処理で行う（ステップ５０３、ステップ５０７）。これにより、全サンプルテーブルに格納されている全データに対してサンプルモード時に採用されたハッシュアルゴリズムによってハッシュを再計算し、運用テーブルへデータを再格納する。
【００２９】
このほか、本発明では運用モードとサンプリングモードを手動で切り替えるためのコマンドを実装する。これは、追加データの傾向が一定な場合やデータの追加される割合が極端に小さいような状況では、複数回サンプリングモードに切り替わったとしても同じハッシュアルゴリズムが選定され続けてしまう可能性があり、その結果として運用モードに切り替わるたびに同じテーブルを再作成しつづけてしまう問題を回避するためのものである。具体的な利用方法としては、運用モードとサンプリングモードとを有効期間を設定することにより周期的に切り替えるのではなく、サンプリングモードの有効期間を０にして常に運用モードでハッシュテーブルを運用し、必要に応じてユーザが任意でサンプリングモードに手動で切り替える、というものである。
【図面の簡単な説明】
【００３０】
【図１】運用モードとサンプリングモードの状態遷移図
【図２】サンプリングモードの処理概要図
【図３】サンプリングモードの処理フローチャート図
【図４】運用モードの処理概要図
【図５】運用テーブル生成処理のフローチャート図
【符号の説明】
【００３１】
１０１  運用モードの状態
１０２  サンプリングモードの状態
１０３  運用モードからサンプリングモードへの状態遷移
１０４  サンプリングモードから運用モードへの状態遷移
２０１  サンプリングモードにおける、第１番目のサンプルテーブル
２０２  サンプリングモードにおける、第２番目のサンプルテーブル
２０３  サンプリングモードにおける、第（N−１）番目のサンプルテーブル
２０４  サンプリングモードにおける、第N番目のサンプルテーブル
２０５  サンプリングモード時に発生した追加データ
【図１】
2008084244.tif 000003
【図２】
2008084244.tif 000004
【図３】
2008084244.tif 000005
【図４】
2008084244.tif 000006
【図５】
2008084244.tif 000007