(57)【要約】【課題】ハッシュテーブルに使用されるメモリ資源の無駄な消費を防ぎ、かつ、ハッシュテーブルの再構築に要する再計算処理の集中を回避すること。【解決手段】複数のハッシュテーブルを用いてデータを登録する際に、既存のテーブルが有するデータ量とハッシュ法を用いてデータを登録する。そして、情報処理装置３００が、テーブルに登録するデータ量に基づいて、テーブルの追加や削除を行う。その後、テーブルに登録されたデータを参照する場合に、情報処理装置３００が、テーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、参照対象となったデータを算出した登録位置から検索し、データを参照することができない場合に、再び登録位置の再計算を行う。【選択図】図２
2010191538.tif 000002
【特許請求の範囲】
【請求項１】
複数のテーブルにデータを登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、
前記テーブルの追加または削除を行うテーブル管理部と、
前記テーブル管理部によって前記テーブルが追加または削除された後に、テーブルに登録されたデータを参照する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、当該登録位置に参照対象となるデータが存在するか否かを判定する判定部と、
前記登録位置に参照対象となるデータが存在しない場合に、前記データの登録位置を再計算する再計算部と、
を備えた情報処理装置。
【請求項２】
前記再計算部によってデータの登録位置が再計算された場合に、再計算された登録位置に登録されたデータを、再計算される前に算出された登録位置に移動する移動部を更に備えた請求項１に記載の情報処理装置。
【請求項３】
前記既存のテーブルの総データ量の履歴情報を記録する履歴記録部を更に備え、前記再計算部は、前記履歴情報に基づいて前記データの位置を再計算する請求項１または２に記載の情報処理装置。
【請求項４】
記憶装置とテーブル作成装置とを有する情報処理システムであって、
前記テーブル作成装置は、
前記記憶装置内の複数のテーブルにデータを登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、
前記テーブルの追加または削除を行うテーブル管理部と、
前記テーブル管理部によって前記テーブルが追加または削除された後に、テーブルに登録されたデータを参照する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、当該登録位置に参照対象となるデータが存在するか否かを判定する判定部と、
前記登録位置に参照対象となるデータが存在しない場合に、前記データの登録位置を再計算する再計算部と、
を備えた情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置に関し、例えば、ハッシュ法を用いてデータを管理した場合に、テーブルの数を変更しつつ、ハッシュ値の再計算に要する処理の集中を回避する情報処理装置および情報処理システムを提供することに関する。
【背景技術】
【０００２】
一般に、電子計算機等が、テーブルに登録されているデータを検索する際、検索を高速にする手法としてハッシュ法が広く知られている。ハッシュ法の一例として、所定のハッシュ関数を用いて、データをリンクさせているキーの値からハッシュ値を算出し、そのハッシュ値に基づいて、キーとキーにリンクされているデータとをハッシュテーブルに登録する、という手法が知られている。
【０００３】
ハッシュ法の一例について具体的に図を用いて説明する。なお、キーが登録されるハッシュテーブル内の位置（以下、ポインタとする）は、算出されたハッシュ値と等しい値を有するポインタに登録するものとし、以下説明する。
【０００４】
図２２は、ハッシュ法を説明するための図である。まず、電子計算機がデータを登録する際の処理ついて説明した後、その登録されたデータを検索する際の処理について説明する。
【０００５】
図２２に示すように、４桁の数字からなる一連のキー（例えば、１２５０、８６８１、７５４２・・・）をハッシュテーブル１０に登録する例を挙げる。なお、キーにリンクされているデータの図示は、説明の便宜上省略するものとする。
【０００６】
まず、図２２で用いるハッシュ関数ｈ（ｋ）を以下の式（１）で示す。
ｈ（ｋ）＝ｋ％Ｎ・・・（１）
ただし、％は剰余を示すものとする。
【０００７】
なお、ｋはキーの値を示し、Ｎはハッシュテーブル１０のテーブルサイズを示すものとする。このテーブルサイズは、ハッシュテーブルが有するメモリ数に相当し、図２２のハッシュテーブル１０のテーブルサイズは、説明の便宜上「１０」とする。
【０００８】
上述した式（１）より、電子計算機は、ハッシュ値を「キーの値を１０で割った余り」で計算することから、キー「１２５０」のハッシュ値として「０」を算出する。したがって、電子計算機は、キー「１２５０」をポインタ０に登録する。同様に、その他のキーについても式（１）を用いて、ハッシュ値を算出し、そのハッシュ値に対応するポインタに登録する。
【０００９】
一方、電子計算機が、キー「４６８４」を検索する際、式（１）に示したハッシュ関数ｈ（ｋ）より、キー「４６８４」からハッシュ値「４」を算出する。したがって、電子計算機は、ポインタ４を検索すれば、４６８４を参照することになり、データの参照時間が、実質的にＯ（１）：（１オーダー）となる。
【００１０】
同様に、キー「８６８１」についても、電子計算機が、ポインタ１を検索すれば、８６８１を参照することになり、データの参照時間が実質的にＯ（１）となる。なお、所定のキーを参照するまでに必要な計算回数を計算量（オーダー）とする。
【００１１】
このように、ハッシュ法を使用することで、電子計算機の参照時間は、実質的にＯ（１）となり、高速なデータ検索が可能となる。
【００１２】
一方、ハッシュ法を用いずに、キーを任意のポインタに登録した場合、検索するキーに応じて、電子計算機等の参照時間が異なり、検索に必要以上の処理時間を要してしまうことがある。具体的に図を用いて説明する。図２３は、ハッシュ法を用いずにキーを登録した場合の不具合を説明するための図である。
【００１３】
説明の便宜上、図２３に示したテーブル１には、図２２に示したキーと同様の４桁の数字からなる一連のキーを使用し、ハッシュ法を用いずにテーブル１に登録するものとする。例えば、キー「３４６３」を検索する場合、電信計算機は、キー「３４６３」のテーブル１におけるポインタが分からないため、先頭のポインタ０から順に検索していくことになる。
【００１４】
したがって、キー「３４６３」は、ポインタ０に登録されていることから、参照時間がＯ（１）になるが、キー「４６５８」を検索する場合についても同様に、電子計算機は、先頭のポインタ０から順に調べていくしかないので、参照時間がＯ（８）になってしまう。また、キー「３４５７」の場合においては、参照時間がＯ（１０）になる。一般には、データ数ｎのとき参照時間はＯ（ｎ）となる。
【００１５】
一方、図２２に示したように、ハッシュ法を使用した場合、キー「３４６３」は、ポインタ３に登録されていることから、最初に、ポインタ３を参照すれば、キー「３４６３」を参照することが可能となり、参照時間はＯ（１）になる。
【００１６】
また、キー「４６５８」、キー「３４５７」についても同様に、最初にポインタ８、ポインタ７を参照すれば、それぞれキーを参照することができ、参照時間はＯ（１）になる。一般には、データ数ｎのときでも、Ｏ（１）となる。このようにして、ハッシュ法を使用することで、データ検索を高速にすることが可能となる。
【００１７】
また、ハッシュテーブルは、電子計算機等の主メモリ上に確保されることから、ハッシュテーブルに使用されるメモリ資源を有効に活用するためには、実際に扱うキーの数に応じて、テーブルサイズを変化させることが望ましい。
【００１８】
これは、電子計算機が、実際に取扱うキーに対して、テーブルサイズが余分に確保されていれば、テーブルサイズを縮小することが望ましく、一方、ハッシュテーブルに対して新たにキーを追加する際に、テーブルサイズが不足していたら、テーブルサイズを拡大する必要がある。
【００１９】
このテーブルサイズを拡大する技術について、２つの例を挙げて以下説明する。まず、第１の例として、テーブルサイズを拡大する際、拡大したテーブルサイズに合わせて、全ハッシュ値の再計算を実施し、ハッシュテーブルの再構築を行うという技術が知られている。
【００２０】
具体的には、図２２に示したハッシュテーブル１０に対して、新たにキー「９９９９」を追加する場合に、ハッシュテーブル１０のメモリ数を一つ増やすことになり、テーブルサイズは１１となる。
【００２１】
その結果、式（１）に示したＮの値は１１となり、キー「９９９９」に加えて、ポインタ０〜ポインタ９に登録されていた全てのキーに対して、式（１）を使用し、ハッシュ値の再計算を実施し、ハッシュテーブルを再構築することになる。
【００２２】
そして、ハッシュテーブルの再構築に費やすメモリ数の消費が、再構築する前のメモリ数の消費に比べて、約２倍のメモリ数を消費する場合がある。（例えば、非特許文献１参照）。
【００２３】
次に、第２の例として、上述した第１の例とは異なり、ハッシュテーブルを新たに再構築せずに、テーブルサイズを拡大するという技術が知られている。
【００２４】
例えば、図２２に示したハッシュテーブル１０に対して、新たにキー「９９９９」を追加する場合に、ハッシュテーブル１０にキー「９９９９」を追加せずに、あらかじめ用意しておいた別のハッシュテーブル、もしくは新たに作成したハッシュテーブルにキー「９９９９」を登録する。（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【００２５】
【特許文献１】特開平８−２７８８９４号公報
【非特許文献】
【００２６】
【非特許文献１】ｈｔｔｐ：／／ｊａｖａ．ｓｕｎ．ｃｏｍ／ｊａｖａｓｅ／ｊａ／６／ｄｏｃｓ／ｊａ／ａｐｉ／ｊａｖａ／ｕｔｉｌ／ＨａｓｈＭａｐ．ｈｔｍｌ
【発明の概要】
【発明が解決しようとする課題】
【００２７】
しかしながら、上述した従来の技術では、ハッシュテーブルに使用されるメモリ資源の無駄を省き、かつ、ハッシュテーブルの再構築に要する再計算処理の集中を回避することができないという問題があった。
【００２８】
例えば、ＷＷＷ（World  Wide  Web）システムのＷｅｂページの表示に用いる各種データを上述したハッシュテーブルで管理している場合について説明する。なお、Ｗｅｂページの表示にかかるレスポンスタイムの上限がＳＬＡ（Service  Level  Agreement）で定められるとし、ここでは「３秒」とする。システムはこのＳＬＡを守るように制御されなければならない。
【００２９】
そして、Ｗｅｂページの表示にハッシュテーブルの再構築が求められたら、ＷＷＷシステムの計算装置は、全ハッシュ値の再計算処理を実施する。この場合、ハッシュテーブルの大きさによっては、再計算に要する処理時間が大きくなることは多々あり、上記の３秒以上費やすことは珍しくない。このような場合は、処理時間の最悪値を超えてしまい、ＳＬＡ違反となる。
【００３０】
また、ハッシュテーブルの再構築を行わずに、テーブルサイズを拡大した場合、ハッシュテーブルの再構築に要する再計算処理の集中は回避できるが、一度追加したハッシュテーブルや、あらかじめ用意しておいたハッシュテーブルを削除することができないので、登録するキーの数に合わせて、テーブルサイズを変更できず、メモリ資源を無駄に消費してしまう。
【００３１】
この発明は、上述した従来技術による課題を解消するためになされたものであり、登録するキーの数に合わせてテーブルサイズを変更することができ、かつ、テーブルサイズの変更に伴うハッシュテーブルの再構築は実施せず、その結果、ハッシュ値の再計算に要する処理の集中を回避できる情報処理装置および情報処理システムを提供することを目的とする。
【課題を解決するための手段】
【００３２】
上述した課題を解決し、目的を達成するために、本願に開示する情報処理装置は、複数のテーブルにデータを登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、前記テーブルの追加または削除を行うテーブル管理部と、前記テーブル管理部によって前記テーブルが追加または削除された後に、テーブルに登録されたデータを参照する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、当該登録位置に参照対象となるデータが存在するか否かを判定する判定部と、前記登録位置に参照対象となるデータが存在しない場合に、前記データの登録位置を再計算する再計算部とを備えたことを要件とする。
【発明の効果】
【００３３】
本願に開示した情報処理装置によれば、テーブルに使用するデータ量に応じて、テーブルサイズを変更し、メモリ資源の無駄な消費を防ぐことができる。
【００３４】
また、情報処理装置は、テーブルサイズの変更に伴う全ハッシュ値の再計算を即時に実施しないで、必要に応じて、ハッシュ値の再計算を所定のデータについてのみ行う。したがって、ハッシュ値の再計算に要する処理の集中を回避し、ＳＬＡで定められる処理時間の最悪値を低減することができる。
【図面の簡単な説明】
【００３５】
【図１】図１は、発明の概要を説明するための図である。
【図２】図２は、実施例に係る情報処理装置の構成を示す機能ブロック図である。
【図３】図３は、テーブル管理テーブルのデータ構造の一例を説明するための図である。
【図４】図４は、テーブルサイズ履歴テーブルのデータ構造の一例を説明するための図である。
【図５】図５は、内部ハッシュテーブルのデータ構造の一例を説明するための図である。
【図６】図６は、情報処理装置が有するデータ構造の一例を説明するための図である。
【図７】図７は、テーブル合計サイズ拡張前のデータ追加時の処理を説明するための図である。
【図８】図８は、テーブル合計サイズ拡張前のデータ削除時の処理を説明するための図である。
【図９】図９は、テーブル合計サイズの拡張時の処理を説明するための図である。
【図１０】図１０は、テーブル合計サイズ拡張後のデータ追加時の処理を説明するための図である。
【図１１】図１１は、テーブル合計サイズ拡張後にキー８を参照する場合の処理を説明するための図である。
【図１２】図１２は、キー８の移動処理を説明するための図である。
【図１３】図１３は、テーブル合計サイズ拡張後のデータ削除時の処理を説明するための図である。
【図１４】図１４は、テーブル合計サイズ縮小の処理を説明するための図である。
【図１５】図１５は、データ追加時の処理手順を示すフローチャートである。
【図１６】図１６は、データ参照時の処理手順を示すフローチャートである。
【図１７】図１７は、データ移動時の処理手順を示すフローチャートである。
【図１８】図１８は、データ削除時の処理手順を示すフローチャートである。
【図１９】図１９は、テーブル合計サイズ拡大時の処理手順を示すフローチャートである。
【図２０】図２０は、テーブル合計サイズ縮小時の処理手順を示すフローチャートである。
【図２１】図２１は、ハッシュ法によるデータ管理を実現するシステムの構成を示す機能ブロック図である。
【図２２】図２２は、ハッシュ法を説明するための図である。
【図２３】図２３は、ハッシュ法を用いずにキーを登録した場合の不具合を説明するための図である。
【発明を実施するための形態】
【００３６】
以下に、本発明にかかる情報処理装置および情報処理システムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００３７】
（発明の概要）
まず、本実施例に係る発明の概要について説明する。本実施例に係る情報処理装置は、複数のハッシュテーブルを用いてデータを登録する場合に、既存のテーブルが有するデータ量とハッシュ法を用いてデータを登録する。
【００３８】
そして、情報処理装置は、テーブルに使用するデータ量に基づいて、テーブルの追加や削除を行う。その後、テーブルに登録されたデータを参照する場合に、情報処理装置は、テーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出する。
【００３９】
そして、情報処理装置は、参照対象となったデータを上述した登録位置から検索し、データを参照することができない場合に、再び登録位置の再計算を行う。
【００４０】
続いて、上述した情報処理装置について具体的に図を用いて説明する。図１は、発明の概要を説明するための図である。図１に示した情報処理装置が有するテーブル５０は、複数のハッシュテーブル（内部ハッシュテーブル２００〜２０２）と、それら複数のハッシュテーブルをリンクさせるテーブル管理テーブル１００とを有する。
【００４１】
なお、説明の便宜上、キー「０」、「２」、「４」、「６」、「９」、「１１」が各内部ハッシュテーブルに既に存在するものとし、また、上述した複数の内部ハッシュテーブルが有する合計のメモリ数を「テーブル合計サイズ」とする。
【００４２】
テーブル管理テーブル１００は、テーブル番号を有しており、このテーブル番号は、内部ハッシュテーブルの位置を示している。例えば、テーブル番号０は、内部ハッシュテーブル２００の位置を示し、テーブル番号１は、内部ハッシュテーブル２０１の位置を示している。
【００４３】
内部ハッシュテーブル２００〜２０２は、キーに基づいてデータを記憶するテーブルで、上述したテーブル番号が示す位置に登録されている。また、これら内部ハッシュテーブルは、キーを登録するポインタに相当するテーブルインデックスを有する。例えば、内部ハッシュテーブル２００であれば、「０」、「１」、「２」、「３」がテーブルインデックスとなる。
【００４４】
そして、テーブル５０にキーを登録する際、情報処理装置は、所定のハッシュ関数を用いて、キーの値に対応するハッシュ値を算出し、算出したハッシュ値に基づいて、上述したテーブル番号とテーブルインデックスとを求める。そして、キーが所定の内部ハッシュテーブルに登録される。
【００４５】
続いて、情報処理装置にデータを追加する際の処理について説明する。なお、説明の便宜上、登録するデータの一例として、キー「３」を有するデータを追加する例を挙げる。まず、情報処理装置は、キー「３」と、テーブル５０のテーブル合計サイズとからハッシュ値を算出する。
【００４６】
そして、情報処理装置は、算出したハッシュ値に基づいて、テーブル番号と、テーブルインデックスを決定して、キー「３」を登録するテーブル５０内の位置を定める（ステップＳ１）。
【００４７】
この際、情報処理装置は、内部ハッシュテーブル２００のテーブルインデックス１に登録する場合は、登録されている他のキーは存在しないので、キー「３」を同テーブルのテーブルインデックス１に登録する。
【００４８】
一方、同テーブルのテーブルインデックス２に登録する場合は、キー「２」が既に登録されているので、キー「２」とテーブルインデックス２との間に、キー「３」を挿入し、リスト形式にてキー「３」を登録する。
【００４９】
また、登録データに対して、テーブル５０が有するメモリ数に余裕がある場合に、情報処理装置は、例えば、内部ハッシュテーブル２０２を削除する（ステップＳ２）。その結果、情報処理装置は、テーブル５０のテーブル合計サイズを「１２」から「８」に削減する。
【００５０】
そして、情報処理装置は、内部ハッシュテーブル２０２に登録していたキー「９」、キー「１１」を内部ハッシュテーブル２００、もしくは内部ハッシュテーブル２０１に再登録する。
【００５１】
また、キー「３」を追加した後や内部ハッシュテーブル２０２を削除した後に、例えば、情報処理装置がキー「６」の参照命令を受けた場合、情報処理装置は、キー「６」に対して、所定のハッシュ関数を使用してハッシュ値を算出する。そして、情報処理装置は、算出したハッシュ値から、テーブル番号と、テーブルインデックスとを決定して、キー「６」の参照位置を決定する。
【００５２】
その後、情報処理装置は、内部ハッシュテーブル２０１のテーブルインデックス２を検索し、キー「６」を参照するが、キー「３」の追加や内部ハッシュテーブル２０２の削除に伴ってテーブル合計サイズに変更が生じた場合、キー「３」を検索できない場合がある。
【００５３】
この場合、情報処理装置は、テーブルサイズ履歴テーブルから、テーブルサイズ変更前に遡ってテーブル合計サイズを読み取り、キー「３」に対してハッシュ値の再計算からテーブルインデックスの決定までの処理を再び行い、キー「３」の参照位置を決定する。そして、情報処理装置は、キー「３」の再検索を行う。
【００５４】
これを、キー「３」が見つかるか、テーブルサイズ履歴テーブルを遡れなくなるまで繰り返す。このように、テーブルサイズ変更があった場合、参照命令の処理時にハッシュ値計算が増えるが、依然として参照時間はデータ量に比例せず、ほぼＯ（１）である。
【００５５】
このように、本実施例に係る情報処理装置は、データをリンクさせているキーを登録する複数のハッシュテーブルと、それら複数のハッシュテーブルをリンクさせる管理テーブルとを有し、登録するキーの数に応じてテーブル合計サイズを変更する。
【００５６】
また、テーブル合計サイズの変更に伴う全ハッシュ値の再計算を即時に実施せず、かつ、ハッシュテーブルの再構築も実施しない。そして、ハッシュ値の再計算は、必要に応じ、参照されたキーに対してのみ行われる。
【００５７】
したがって、情報処理装置が、テーブルに使用するデータ量に応じて、ハッシュテーブルのテーブル合計サイズを変更し、結果として、ハッシュテーブルに使用されるメモリ資源の無駄な消費を省くことができる。
【００５８】
また、情報処理装置がハッシュ値の再計算を即時に実施しないことで、ハッシュ値の再計算に要する処理の集中を回避し、上述したＳＬＡで定められる処理時間の最悪値を低減させることができる。
【００５９】
（実施例）
次に、本実施例に係る情報処理装置の構成について説明する。図２は、実施例に係る情報処理装置の構成を示す機能ブロック図である。なお、説明の便宜上、図２に示した情報処理装置３００がコンピュータ内部のプログラムとして利用される例を挙げて以下説明する。
【００６０】
図２に示した情報処理装置３００は、各種データの参照や追加等の命令を受けた後、ハッシュ法を用いて、データをハッシュテーブルに登録し、そのデータを識別するキーの数に応じてテーブル合計サイズを変更する。このハッシュテーブルは、情報処理装置３００内に複数存在し、後述する所定のテーブルにリンクされている。
【００６１】
そして、情報処理装置３００は、インターフェース３１０と、テーブル管理部３２０と、内部ハッシュテーブル３３０ａ〜３３０ｚとを有する。なお、利用プログラム６０が実行する装置は、情報処理装置３００に対して、キーの登録／参照／追加等の命令や、テーブル合計サイズの変更等の命令を行うプログラムである。
【００６２】
インターフェース３１０は、利用プログラム６０から情報処理装置３００に対して、各種キーの参照や追加等の命令に対する処理を行うインターフェースである。例えば、利用プログラム６０からキー「０」に関連付けられているデータの参照命令がインターフェース３１０に入力された場合に、インターフェース３１０は、テーブル管理部３２０に対して、キー「０」の参照命令を行う。
【００６３】
テーブル管理部３２０は、インターフェース３１０から入力される各種命令に対する処理や、内部ハッシュテーブル３３０ａ〜３３０ｚに登録されるキーの数に応じて、テーブル合計サイズの変更を行う管理部である。
【００６４】
そして、テーブル管理部３２０は、管理部３２０ａと、テーブル管理テーブル３２０ｂと、テーブルサイズ履歴テーブル３２０ｃとを有する。
【００６５】
管理部３２０ａは、インターフェース３１０から入力される各種命令に応じて、テーブル管理テーブル３２０ｂが有するテーブル番号や、テーブルサイズ履歴テーブル３２０ｃが有するテーブル合計サイズのデータ管理を行う手段である。
【００６６】
さらに、管理部３２０ａは、利用プログラム６０からの命令に応じて、内部ハッシュテーブル３３０ａ〜３３０ｚに登録されているキーのハッシュ計算や、キーの参照／削除や、内部ハッシュテーブルの追加／削除を行う。
【００６７】
テーブル管理テーブル３２０ｂは、内部ハッシュテーブル３３０ａ〜３３０ｚをリンクさせるテーブルであり、具体的なデータ構造について、図を用いて説明する。図３は、テーブル管理テーブルのデータ構造の一例を説明するための図である。
【００６８】
図３に示すテーブル管理テーブル３２０ｂは、図１に示したテーブル管理テーブル１００に相当するもので、管理部３２０ａが、データの更新等を行う。そして、テーブル管理テーブル３２０ｂは、「テーブル番号」を有する。
【００６９】
「テーブル番号」は、内部ハッシュテーブル３３０ａ〜３３０ｚのポインタを示す。例えば、テーブル番号０は、内部ハッシュテーブル３３０ａのポインタを示し、テーブル番号１は、内部ハッシュテーブル３３０ｂのポインタを示す。
【００７０】
テーブルサイズ履歴テーブル３２０ｃは、内部ハッシュテーブル３３０ａ〜３３０ｚの合計メモリ数（上述したテーブル合計サイズに相当する）の履歴が記憶されるテーブルで、管理部３２０ａが、データの更新等を行う。具体的なデータ構造について、図を用いて説明する。図４は、テーブルサイズ履歴テーブルのデータ構造の一例を説明するための図である。
【００７１】
図４のテーブルサイズ履歴テーブル３２０ｃは、「履歴番号」、「テーブル合計サイズ」を有し、「履歴番号」は、情報処理装置３００のテーブル合計サイズの履歴を管理する番号を示し、初期値は０とする。そして、内部ハッシュテーブルが１つ加えられるごとに、履歴番号が合わせて、「１」、「２」・・・と１つずつ増えていく。
【００７２】
「テーブル合計サイズ」は、上述したように、情報処理装置３００が有する内部ハッシュテーブル３３０ａ〜３３０ｚの合計メモリ数を示す。なお、単一の内部ハッシュテーブルが有するメモリ数（以下、単位テーブルサイズ）は、「４」とする。
【００７３】
この場合、内部ハッシュテーブルが１つ追加されるごとに、単位テーブルサイズが有するメモリ数「４」が追加され、テーブル合計サイズが「８」、「１２」・・・と増えていく。
【００７４】
内部ハッシュテーブル３３０ａ〜３３０ｚは、キーに基づいてデータを記憶するハッシュテーブルで、具体的なデータ構造について、内部ハッシュテーブル３３０ａを例に挙げ、図を用いて説明する。図５は、内部ハッシュテーブルのデータ構造の一例を説明するための図である。
【００７５】
なお、図５に示す内部ハッシュテーブル３３０ａは、図１に示した内部ハッシュテーブル２００に相当するものとする（内部ハッシュテーブル３３０ｂ以下についても同様に図１に示した内部ハッシュテーブルに相当するものとする）。
【００７６】
そして、この内部ハッシュテーブル３３０ａは、「テーブルインデックス」を有し、このテーブルインデックスに各種キーが登録されている。そして、管理部３２０ａが、データ管理を行う。なお、説明の便宜上、キーに対応付けられているデータの図示は省略する。
【００７７】
テーブルインデックスは、内部ハッシュテーブル３３０ａが有するポインタを示し、このポインタに、キーが登録される。そして、このキーに各種データが対応付けられている。
【００７８】
例えば、キー「０」を登録するポインタが内部ハッシュテーブル３３０ａのテーブルインデックス０に決定された場合、管理部３２０ａは、キー「０」を内部ハッシュテーブル３３０ａのテーブルインデックス０に登録する。
【００７９】
その後、管理部３２０ａがキー「８」を更に登録する際、キー「８」を登録するポインタが同テーブルのテーブルインデックス０に決定された場合、管理部３２０ａは、キー「０」に対して、キー「８」をリスト形式で登録する。
【００８０】
なお、図５では、説明の便宜上、キーの値を整数としたが、キーの値は整数に限定されず、例えば、“Ｈｅｌｌｏ”や“Ｏｂｊｅｃｔ１”といった文字列にしても良い。この場合、“Ｈｅｌｌｏ”や“Ｏｂｊｅｃｔ１”のデータ構造が示すキーの値と、ハッシュ関数とに基づいて内部ハッシュテーブルのインデックスが決定され、管理部３２０ａが所定のテーブルインデックスにデータを登録する。
【００８１】
このように、本実施例では、データを追加する際、登録位置となるテーブルインデックスに、既存のデータが存在していた場合、いわゆる連鎖法を用いて、データを追加していくものとする。
【００８２】
したがって、登録対象となる内部ハッシュテーブルのインデックスに、既にデータが登録されていても、管理部３２０ａは、リスト形式で登録データを追加する。その結果、管理部３２０ａが使用するハッシュ関数は１種類で良いものとする。
【００８３】
次に、図２に示した情報処理装置３００が行うデータ処理について以下説明する。なお、説明の便宜上、あらかじめ情報処理装置３００が、以下の図６に示すデータを有するものとする。
【００８４】
なお、上述したように、情報処理装置３００が有する各内部ハッシュテーブルのメモリ数を単位テーブルサイズとし、この単位テーブルサイズを便宜的に「４」とする。
【００８５】
また、管理部３２０ａが、各種キー「ｋ」（ｋは数字）からハッシュ値を求める際に使用するハッシュ関数Ｈ（ｋ）と、テーブル番号を求める際に使用する関数ｈ１（ｘ）と、テーブルインデックスを求める際に使用する関数ｈ２（ｘ）とを、以下の式（２）〜式（４）に定める。
【００８６】
Ｈ（ｋ）＝ｋ％Ｎ・・・（２）
ただし、％は剰余を示し、ｋはキーの値を示し、Ｎはテーブル合計サイズを示す。
【００８７】
ｈ１（ｘ）＝ｘ／ｎ・・・（３）
ただし、ｘは式（２）より求められたハッシュ値を示し、ｎは単位テーブルサイズを示す。
【００８８】
ｈ２（ｘ）＝ｘ％ｎ・・・（４）
ただし、％は剰余を示し、ｘは式（２）より求められたハッシュ値を示し、ｎは単位テーブルサイズを示す。
【００８９】
図６は、情報処理装置が有するデータ構造の一例を説明するための図である。図６に示した情報処理装置３００のテーブル合計サイズは「８」であり、そして、キー「０」、「２」は、内部ハッシュテーブル３３０ａのテーブルインデックス０、２にそれぞれ登録されている。
【００９０】
また、キー「４」は、内部ハッシュテーブル３３０ｂのテーブルインデックス０に登録され、キー「６」、「１４」は、内部ハッシュテーブル３３０ｂのテーブルインデックス２に登録されている。
【００９１】
そして、テーブル管理テーブル３２０ｂのテーブル番号０、１には、内部ハッシュテーブル３３０ａと、内部ハッシュテーブル３３０ｂとがそれぞれ登録されている。そして、テーブルサイズ履歴テーブル３２０ｃには、「４」、「８」が記憶されている。
【００９２】
（テーブルサイズ拡張前のデータ追加）
まず、図６に示したデータ構造にキー「８」を追加した際、情報処理装置３００が行う処理について、図を用いて説明する。図７は、テーブル合計サイズ拡張前のデータ追加時の処理を説明するための図である。
【００９３】
まず、図２に示した管理部３２０ａは、上述した利用プログラム６０からキー「８」の追加命令を受け、式（２）〜式（４）を使用し、キー「８」を追加する位置を算出する。以下、この算出過程について説明する。
【００９４】
まず、管理部３２０ａは、キー「８」と、テーブル合計サイズ「８」とを用いて、キー「８」に対応するハッシュ値を式（２）より求める。そして、キー「８」に対応するハッシュ値として「０」を算出する。
【００９５】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「０」と、単位テーブルサイズ「４」とを用いて、ハッシュ値「０」に対応するテーブル番号を式（３）より求める。そして、ハッシュ値「０」に対応するテーブル番号として「０」を算出する。
【００９６】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「０」と、単位テーブルサイズ「４」とを用いて、テーブル番号０に対応するテーブルインデックスを式（４）より求める。そして、テーブル番号０に対応するテーブルインデックスとして「０」を算出する。
【００９７】
以上より、管理部３２０ａは、キー「８」を追加する位置を内部ハッシュテーブル３３０ａのテーブルインデックス０に決定し、同テーブルのインデックスを検索する（ステップＳ３）。
【００９８】
この場合、内部ハッシュテーブル３３０ａのテーブルインデックス０にデータ（キー＝０）が既に存在するので、管理部３２０ａは、内部ハッシュテーブル３３０ａとキー０との間にキー８を挿入し、リスト形式にてキー「８」を登録する（ステップＳ４）。
【００９９】
なお、ステップＳ４にて示したように、管理部３２０ａが、リストの線形探索を便宜的にするため、キー「８」を内部ハッシュテーブル３３０ａのテーブルインデックス０に登録しているが、既に存在するキー「０」の後ろにリスト形式で登録しても良い。
【０１００】
（テーブルサイズ拡張前のデータ参照）
次に、管理部３２０ａが、キー「８」を参照する際の処理について説明する。まず、管理部３２０ａは、上述した利用プログラム６０からキー「８」の参照命令を受けて、キー「８」を追加した際に実行した計算をキー「８」に対して式（２）〜式（４）を用いて行う。
【０１０１】
その結果、キー「８」の参照位置は、内部ハッシュテーブル３３０ａのテーブルインデックス０に一意に決定される。これは、図７に示したように、キー「８」が、リスト形式で接続されていても同様である。
【０１０２】
そして、管理部３２０ａは、キー「８」を内部ハッシュテーブル３３０ａのテーブルインデックス０より検索する。この場合、図７に示したように、キー「８」は、テーブルインデックス０にリスト形式で登録されているので、管理部３２０ａは、キー「８」を参照し、参照したデータをインターフェース３１０に返す。
【０１０３】
（テーブルサイズ拡張前のデータ削除）
次に、図７で説明したキー「８」を削除する際の処理について、図を用いて説明する。図８は、テーブル合計サイズ拡張前のデータ削除時の処理を説明するための図である。
【０１０４】
まず、管理部３２０ａは、上述した利用プログラム６０からキー「８」の削除命令を受け、キー「８」を追加した際に実行した計算を式（２）〜式（４）を用いて行う。
【０１０５】
その結果、削除対象であるキー「８」の参照位置は、内部ハッシュテーブル３３０ａのテーブルインデックス０に決定されるので、管理部３２０ａは、キー「８」を同テーブルのインデックス０から検索する。
【０１０６】
この場合、図８に示したように、キー「８」は、内部ハッシュテーブル３３０ａのテーブルインデックス０にリスト形式で登録されているので、管理部３２０ａは、同テーブルのテーブルインデックス０からキー「８」を参照し、キー「８」を削除する（ステップＳ５）。
【０１０７】
続いて、管理部３２０ａは、内部ハッシュテーブル３３０ａのテーブルインデックス０が示すポインタを、キー「０」につなぎ直し、キー「８」およびキー「８」に対応するデータに使用されていたメモリを開放する（ステップＳ６）。
【０１０８】
一方、削除対象のキー「８」の後続にデータがリンクされていない場合、管理部３２０ａは、キー「８」およびキー「８」に対応するデータに使用されていたメモリを開放する。
【０１０９】
（テーブル合計サイズ拡張）
次に、テーブル合計サイズを拡張する際の処理について、図を用いて説明する。図９は、テーブル合計サイズ拡張時の処理を説明するための図である。
【０１１０】
例えば、上述した利用プログラム６０からテーブル合計サイズの拡張命令を受けて、管理部３２０ａは、テーブル管理テーブル３２０ｂに新しいテーブル番号「２」をテーブル番号１の後ろに作成する。
【０１１１】
そして、管理部３２０ａは、単位テーブルサイズが「４」である内部ハッシュテーブル３３０ｃを作成し、作成した内部ハッシュテーブルを新しく追加したテーブル番号２にリンクさせる。
【０１１２】
また、管理部３２０ａは、テーブルサイズ履歴テーブル３２０ｃに、これまでのテーブル合計サイズ「８」に単位テーブルサイズ「４」を加えた「１２」をテーブルサイズ履歴テーブル３２０ｃの末尾に追加する。
【０１１３】
なお、利用プログラム６０からの命令を受けて、テーブル合計サイズを拡張する場合を例に挙げて説明したが、例えば、管理部３２０ａが、内部ハッシュテーブルに記憶されているキーの数等から、テーブル合計サイズが不足していると判定した場合に、テーブル合計サイズを拡張しても良いものとする。
【０１１４】
（テーブル合計サイズ拡張後のデータ追加）
次に、テーブル合計サイズが拡張された後の処理について説明する。一例として、情報処理装置３００に対してキー「９」、キー「１１」を追加した際の処理について、図を用いて説明する。図１０は、テーブル合計サイズ拡張後のデータ追加時の処理を説明するための図である。
【０１１５】
まず、管理部３２０ａは、上述した利用プログラム６０からキー「９」と、キー「１１」の追加命令を受けて、キー「９」と、キー「１１」とに対して式（２）を用い、ハッシュ値をそれぞれ求める。なお、式（２）で使用するテーブル合計サイズは「１２」とする。
【０１１６】
その結果、管理部３２０ａは、キー「９」に対応するハッシュ値が「９」、キー「１１」に対応するハッシュ値が「１１」とそれぞれ算出される。
【０１１７】
続いて、管理部３２０ａは、ハッシュ値「９」と、ハッシュ値「１１」とに対して、式（３）を用い、テーブル番号をそれぞれ求める。この結果、ハッシュ値「９」と、ハッシュ値「１１」とに対応するテーブル番号は、いずれも「２」と算出される。
【０１１８】
続いて、管理部３２０ａは、ハッシュ値「９」と、ハッシュ値「１１」とに対して、式（４）を用い、対応するテーブルインデックスを求める。この結果、ハッシュ値「９」と、ハッシュ値「１１」とに対応するテーブルインデックスは、それぞれ、内部ハッシュテーブル３３０ｃのテーブルインデックス「１」、「３」に算出される。
【０１１９】
以上より、キー「９」は、内部ハッシュテーブル３３０ｃのテーブルインデックス１に登録され、キー「１１」は、同テーブルのテーブルインデックス３に登録される。
【０１２０】
（テーブルサイズ拡張後のデータ参照）
次に、管理部３２０ａが、図１０にて追加したキー「９」を参照する際の処理について説明する。まず、管理部３２０ａは、上述した利用プログラム６０からキー「９」の参照命令を受けて、キー「９」と、テーブル合計サイズ「１２」とを用いて、キー「９」に対応するハッシュ値を式（２）から求める。そして、キー「９」に対応するハッシュ値として「９」を算出する。
【０１２１】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「９」と、単位テーブルサイズ「４」とを用いて、ハッシュ値「９」に対応するテーブル番号を式（３）から求める。そして、ハッシュ値「９」に対応するテーブル番号として「２」を算出する。
【０１２２】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「９」と、単位テーブルサイズ「４」とを用いて、テーブル番号２に対応するテーブルインデックスを式（４）より求める。そして、テーブル番号２に対応するテーブルインデックスとして「１」を算出する。
【０１２３】
以上より、管理部３２０ａは、キー「９」の参照位置を、内部ハッシュテーブル３３０ｃのテーブルインデックス１に決定し、キー「９」を検索する。この場合、図１０に示したように、管理部３２０ａは、同テーブルのテーブルインデックス１にキー「９」を参照し、参照したデータをインターフェース３１０に返す。
【０１２４】
次に、テーブル合計サイズを拡張した後、キー「８」を参照する場合に実施する処理について図を用いて説明する。図１１は、テーブル合計サイズ拡張後にキー８を参照する場合の処理を説明するための図である。
【０１２５】
まず、管理部３２０ａは、上述した利用プログラム６０からキー「８」の参照命令を受けて、キー「８」と、テーブル合計サイズ「１２」とを用いて、キー「８」に対応するハッシュ値を求める。そして、キー「８」に対応するハッシュ値として「８」を算出する。
【０１２６】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「８」と、単位テーブルサイズ「４」とを用いて、キー「８」に対応するテーブル番号を式（３）より求める。そして、ハッシュ値「８」に対応するテーブル番号として「２」を算出する。
【０１２７】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「８」と、単位テーブルサイズ「４」とを用いて、テーブル番号２に対応する内部ハッシュテーブルのテーブルインデックスを式（４）より求める。そして、テーブル番号２に対応するテーブルインデックスとして「０」を算出する。
【０１２８】
以上より、管理部３２０ａは、キー「８」の参照位置を、内部ハッシュテーブル３３０ｃのインデックス０に決定し、キー「８」を参照する。この場合、管理部３２０ｂは、同テーブルのインデックス０にキー「８」を参照できない。
【０１２９】
そこで、管理部３２０ａは、テーブルサイズ履歴テーブル３２０ｃを参照し、テーブル合計サイズ「１２」の１つ前のテーブル合計サイズ「８」で、ハッシュ値の再計算をキー「８」に対して行う。
【０１３０】
したがって、管理部３２０ａは、キー「８」と、テーブル合計サイズ「８」とを用いて、キー「８」に対応するハッシュ値を式（２）より求める。そして、キー「８」に対応するハッシュ値として「０」を算出する。
【０１３１】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「０」と、単位テーブルサイズ「４」とを用いて、キー「８」に対応するテーブル番号を式（３）から求める。そして、ハッシュ値「０」に対応するテーブル番号として「０」を算出する。
【０１３２】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「０」と、単位テーブルサイズ「４」とを用いて、テーブル番号２に対応するテーブルインデックスを式（４）より求める。そして、テーブル番号０に対応するテーブルインデックスとして「０」を算出する。
【０１３３】
以上より、管理部３２０ａは、キー「８」の参照位置を、内部ハッシュテーブル３３０ａのインデックス０に決定し、キー「８」を検索する。この場合、管理部３２０ａは、内部ハッシュテーブル３３０ａのインデックス０にキー「８」を参照するので、参照したデータをインターフェース３１０に返す。
【０１３４】
なお、図１１にてキー「８」が参照された場合、管理部３２０ａは、テーブルサイズ履歴テーブル３２０ｃを使用することで、キー「８」の登録位置を最新のテーブル合計サイズ１２で求められる参照位置に再登録する。
【０１３５】
具体的に図を用いて説明する。図１２は、キー８の移動処理を説明するための図である。図１２に示すように、管理部３２０ａは、参照したキー「８」と、テーブルサイズ履歴テーブル３２０ｃの末尾に登録されているテーブル合計サイズ「１２」とに基づいて、再度、式（２）から式（４）を用いて、ハッシュ値の再計算を行う。
【０１３６】
そして、管理部３２０ａは、キー「８」に対応するテーブル番号と、テーブルインデックスとを決定する。この場合、キー「８」の参照位置は、内部ハッシュテーブル３３０ｃのインデックス０に決定される。
【０１３７】
そして、管理部３２０ａは、キー「８」を内部ハッシュテーブル３３０ａのインデックス０から、算出した内部ハッシュテーブル３３０ｃのインデックス０に移動する。
【０１３８】
その後、データ削除時と同様に、管理部３２０ａは、テーブルインデックス０が示すポインタを、削除対象のキー「８」の後続にリンクされているキー「０」につなぎ直し、キー「８」と、キー「８」に使用されていたメモリを開放する。
【０１３９】
なお、上述した場合において、キー「８」を参照できなかった場合に、その参照位置（例えば、内部ハッシュテーブル３３０ｃのテーブルインデックス０）を記憶しておき、その後、キー「８」の参照に成功した際、記憶しておいた検索位置に基づいて、キー「８」を再登録しても良いものとする。
【０１４０】
このように、管理部３２０ａが、キー「８」を最新のテーブル合計サイズに合わせて、再登録することで、管理部３２０ａが再びキー「８」を参照した際に、キー「８」に対するハッシュ値の再計算は必要なく、検索時間を低減させることができる。
【０１４１】
なお、上述したように、管理部３２０ａは、１つ前のテーブル合計サイズ「８」で参照された場合について説明したが、テーブル合計サイズ「８」でも参照されなかった場合、管理部３２０ａは、テーブル合計サイズ「８」の１つ前のテーブル合計サイズ「４」で、ハッシュ値の再計算からテーブルインデックスの決定まで行い、データの検索を行う。
【０１４２】
そして、管理部３２０ａは、テーブル合計サイズ「４」でもデータを参照できなかった場合は、データが参照できなかった旨を示す応答をインターフェース３１０に返す。
【０１４３】
（テーブル合計サイズ拡張後のデータ削除）
次に、テーブル合計サイズ拡張後に、データを削除する際の処理について、図を用いて説明する。図１３は、テーブル合計サイズ拡張後のデータ削除時の処理を説明するための図である。なお、説明の便宜上、キー「９」と、キー「１４」とを削除する場合を例に挙げて説明する。
【０１４４】
まず、キー「９」を削除する場合を例に挙げる。管理部３２０ａは、上述した利用プログラム６０からキー「９」の削除命令を受けて、削除対象であるキー「９」を参照する。この際、管理部３２０ａは、キー「９」の参照位置を式（２）〜式（４）より算出する。
【０１４５】
そして、管理部３２０ａは、キーの参照位置を内部ハッシュテーブル３３０ｃのテーブルインデックス１に決定し、キー「９」を参照する。そして、管理部３２０ａは、同テーブルのテーブルインデックス１にキー「９」を参照できるので、キー「９」を削除する。
【０１４６】
続いて、キー「１４」を削除する場合を例に挙げる。まず、管理部３２０ａは、上述した利用プログラム６０からキー「１４」の削除命令を受けて、削除対象であるキー「１４」を参照する。
【０１４７】
この際、管理部３２０ａは、キー「１４」と、テーブル合計サイズ「１２」とを用いて、キー「１４」に対応するハッシュ値を式（２）から求める。そして、キー「１４」に対応するハッシュ値として「２」を算出する。
【０１４８】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「２」と、単位テーブルサイズ「４」とを用いて、キー「１４」に対応するテーブル番号を式（３）から求める。そして、ハッシュ値「２」に対応するテーブル番号として「０」を算出する。
【０１４９】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「２」と、単位テーブルサイズ「４」とを用いて、テーブル番号０に対応するテーブルインデックスを式（４）から求める。そして、テーブル番号０に対応するテーブルインデックスとして「２」を算出する。
【０１５０】
以上より、管理部３２０ａは、キー「１４」の参照位置を、内部ハッシュテーブル３３０ａのテーブルインデックス２に決定し、キー「１４」を参照する。この場合、管理部３２０ａは、同テーブルのインデックス２にキー「１４」を参照できない（ステップＳ７）。
【０１５１】
そこで、管理部３２０ａは、テーブルサイズ履歴テーブル３２０ｃを参照し、テーブル合計サイズ「１２」の１つ前のテーブル合計サイズ「８」で、ハッシュ値の再計算をキー「１４」に対して行う。
【０１５２】
したがって、管理部３２０ａは、キー「１４」と、テーブル合計サイズ「８」とを用いて、キー「１４」に対応するハッシュ値を式（２）から求める。そして、キー「１４」に対応するハッシュ値として「６」を算出する。
【０１５３】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「６」と、単位テーブルサイズ「４」とを用いて、キー「１４」に対応するテーブル番号を式（３）から求める。そして、ハッシュ値「６」に対応するテーブル番号として「１」を算出する。
【０１５４】
続いて、管理部３２０ａは、式（２）より求めたハッシュ値「６」と、単位テーブルサイズ「４」とを用いて、テーブル番号１に対応するテーブルインデックスを式（４）から求める。そして、テーブル番号１に対応するテーブルインデックスとして「２」を算出する。
【０１５５】
以上より、管理部３２０ａは、キー「１４」の参照位置を、内部ハッシュテーブル３３０ｂのテーブルインデックス２に決定し、キー「１４」を検索する。この場合、管理部３２０ａは、内部ハッシュテーブル３３０ｂのテーブルインデックス２にキー「１４」を参照し、キー「１４」を削除する。その後、管理部３２０ａは、キー「１４」と、キー「１４」に使用されていたメモリを開放する（ステップＳ８）。
【０１５６】
（テーブル合計サイズ縮小）
次に、テーブル合計サイズを縮小する場合の処理について説明する。図１４は、テーブル合計サイズ縮小の処理を説明するための図である。なお、図９にて説明したようにテーブル合計サイズが拡張された後に、情報処理装置３００が、テーブル合計サイズを縮小する場合について説明する。
【０１５７】
まず、管理部３２０ａは、上述した利用プログラム６０からテーブル合計サイズの縮小命令を受けて、テーブルサイズ履歴テーブル３２０ｃから最新のテーブルサイズ履歴「１２」を削除し、最新のテーブル合計サイズを「８」とする（ステップＳ９）。
【０１５８】
そして、管理部３２０ａは、テーブル番号２にリンクされている内部ハッシュテーブル３３０ｃに登録されているキー「９」と、キー「１１」とを削除対象となっていない内部ハッシュテーブル３３０ａや内部ハッシュテーブル３３０ｂに移動させる（ステップＳ１０）。
【０１５９】
この場合、管理部３２０ａは、キー「９」と、キー「１１」とに対応するハッシュ値を、各キーの値と、テーブル合計サイズ「８」とを用いて求める。そして、キー「９」に対応するハッシュ値として「１」、キー「１１」に対応ハッシュ値として「３」をそれぞれ算出する。
【０１６０】
続いて、管理部３２０ａは、ハッシュ値「１」と、ハッシュ値「３」とに対して、式（３）を用いて、対応するテーブル番号をそれぞれ求める。そして、ハッシュ値「１」に対応するテーブル番号は「０」、ハッシュ値「３」に対応するテーブル番号も同様に「０」を算出する。
【０１６１】
続いて、管理部３２０ａは、ハッシュ値「１」と、ハッシュ値「３」とに対して、式（４）を用いて、テーブル番号０に対応するテーブルインデックスを求める。この結果、ハッシュ値「１」と、ハッシュ値「３」とに対応するテーブルインデックスは、それぞれ、「１」、「３」と算出される。
【０１６２】
以上より、管理部３２０ａは、キー「９」を内部ハッシュテーブル３３０ａのテーブルインデックス１に登録し、キー「１１」を同テーブルのテーブルインデックス３に登録する。
【０１６３】
その後、管理部３２０ａは、内部ハッシュテーブル３３０ｃを削除し（ステップＳ１１）、テーブル管理テーブル３２０ｂが有する末尾のテーブル番号２を削除する（ステップＳ１２）。
【０１６４】
なお、上述した場合では、内部ハッシュテーブル３３０ｃを削除するまで説明したが、削除対象となった内部ハッシュテーブルと、リンクされているキーを即座に削除しないで、「削除テーブル」として残しておいても良い。
【０１６５】
例えば、上述した場合において、管理部３２０ａは、削除対象となっている内部ハッシュテーブルを削除テーブルとして残しておき、テーブルサイズ履歴テーブル３２０ｃに記憶するデータについても、削除前のテーブル合計サイズ「１２」を削除前テーブル合計サイズとして記憶しておく。
【０１６６】
その後、キー「９」と、キー「１１」とが参照された場合に、管理部３２０ａは、削除前テーブル合計サイズ「１２」を使用して、キー「９」と、キー「１１」とを参照する。
そして、キー「９」を内部ハッシュテーブル３３０ａのテーブルインデックス１に登録し直し、キー「１１」を同テーブルのテーブルインデックス１に登録する。
【０１６７】
そして、管理部３２０ａは、内部ハッシュテーブル３３０ｃに登録されているデータが無くなった後に、同テーブルを削除し、使用されていたメモリを開放する。
【０１６８】
そして、管理部３２０ａは、内部ハッシュテーブル３３０ａをリンクさせているテーブル番号２を削除し、テーブル番号２に使用されているメモリを開放する。
【０１６９】
次に、情報処理装置３００が、データ追加時に実施する処理手順について説明する。図１５は、データ追加時の処理手順を示すフローチャートである。
【０１７０】
まず、情報処理装置３００が、利用プログラム６０からキーの追加命令を受け、ハッシュ関数Ｈ（ｋ）を用いて、登録するキーのハッシュ値の計算を行う（ステップＳ１００）。
【０１７１】
その後、情報処理装置３００は、ステップＳ１００にて算出したハッシュ値と、関数ｈ１（ｋ）とを使用して、キーに対応するテーブル番号を決定する（ステップＳ１０１）。そして、情報処理装置３００は、ステップＳ１００にて算出したハッシュ値と、関数ｈ２（ｋ）とを使用して、キーに対応するテーブルインデックスを決定する（ステップＳ１０２）。
【０１７２】
続いて、情報処理装置３００は、算出されたテーブル番号と、テーブルインデックスとに基づいて、登録対象となっている内部ハッシュテーブルのポインタにキーを追加する（ステップＳ１０３）。
【０１７３】
このフローチャートによれば、キーを追加したことで、テーブル合計サイズが変更されても、テーブル合計サイズの変更に伴う全ハッシュ値の再計算を即時に実施せず、かつ、ハッシュテーブルの再構築も実施しない。したがって、ハッシュ値の再計算に要する処理の集中を回避することができる。
【０１７４】
次に、情報処理装置３００が、データ参照時に実施する処理手順について説明する。図１６は、データ参照時の処理手順を示すフローチャートである。
【０１７５】
まず、情報処理装置３００が、利用プログラム６０からデータ参照の命令を受け、テーブルサイズ履歴テーブル３２０ｃの末尾の履歴データを参照する（ステップＳ２００）。
【０１７６】
そして、情報処理装置３００は、参照対象となっているデータのキーに対して、図１５のステップＳ１００からステップＳ１０２のシーケンスを実施する（ステップＳ２０１）。その後、情報処理装置３００は、ステップＳ２０１で決定されたキーの参照位置に基づいてデータを検索する（ステップＳ２０２）。
【０１７７】
そして、情報処理装置３００が、ステップＳ２０１にて決定されたキーの参照位置に、データを発見できなかった場合（ステップＳ２０３、Ｎｏ）、情報処理装置３００は、テーブルサイズ履歴テーブル３２０ｃの履歴番号を参照する（ステップＳ２０４）。
【０１７８】
この時、情報処理装置３００が参照した履歴番号が初期値０であれば（ステップＳ２０５、Ｙｅｓ）、履歴番号の初期値まで遡ってデータを検索したことになるので、データが参照できなかった旨を報告する（ステップＳ２０６）。
【０１７９】
一方、情報処理装置３００が参照した履歴番号が初期値０でなければ（ステップＳ２０５、Ｎｏ）、ステップＳ２００にて参照したテーブル合計サイズの１つ前に遡ったテーブル合計サイズの履歴を参照し（ステップＳ２０７）、ステップＳ２０１へ移行する。
【０１８０】
また、ステップＳ２０３で、情報処理装置３００が、ステップＳ２０１にて決定されたキーの参照位置に、データを発見した場合（ステップＳ２０３、Ｙｅｓ）、検索したデータを利用プログラム６０に返す（ステップＳ２０８）。
【０１８１】
次に、情報処理装置３００が、データ移動時に実施する処理手順について説明する。図１７は、データ移動時の処理手順を示すフローチャートである。
【０１８２】
まず、情報処理装置３００が、利用プログラム６０からデータ参照の命令を受け、テーブルサイズ履歴テーブル３２０ｃの末尾の履歴データを参照する（ステップＳ３００）。
【０１８３】
そして、参照対象となっているデータのキーに対して、図１５のステップＳ１００からステップＳ１０２のシーケンスを実施する（ステップＳ３０１）。その後、情報処理装置３００は、ステップＳ３０１で決定されたキーの参照位置に基づいてデータを検索する（ステップＳ３０２）。
【０１８４】
そして、情報処理装置３００が、ステップＳ３０１にて決定されたキーの参照位置に、データを発見できなかった場合（ステップＳ３０３、Ｎｏ）、情報処理装置３００は、テーブルサイズ履歴テーブル３２０ｃの履歴番号を参照する（ステップＳ３０４）。
【０１８５】
この時、情報処理装置３００が参照した履歴番号が初期値０であれば（ステップＳ３０５、Ｙｅｓ）、履歴番号の初期値まで遡ってデータを検索したことになるので、データが参照できなかった旨を報告する（ステップＳ３０６）。
【０１８６】
一方、情報処理装置３００が参照した履歴番号が初期値０でなければ（ステップＳ３０５、Ｎｏ）、ステップＳ３００にて参照したテーブル合計サイズの１つ前に遡ったテーブル合計サイズの履歴を参照し（ステップＳ３０７）、ステップＳ３０１へ移行する。
【０１８７】
そして、情報処理装置３００は、ステップ３００で参照したテーブル合計サイズの１つ前に遡ったテーブル合計サイズで決定されたキーの参照位置を検索し（ステップＳ３０２）、データを発見できた場合（ステップＳ３０３、Ｙｅｓ）、ステップ３０８へ移行する。
【０１８８】
そして、ハッシュ値の再計算が実施されていた場合（ステップＳ３０８、Ｙｅｓ）、情報処理装置は、発見したデータを取り除き（ステップＳ３０９）、ステップＳ３００で参照したテーブル合計サイズにて、データ追加時のシーケンスを実施し（ステップＳ３１０）、利用プログラム６０にデータを返す（ステップＳ３１１）。
【０１８９】
一方、ステップＳ３０３で発見されたデータのキーに対して、ハッシュ値の再計算が実施されていない場合（ステップＳ３０８、Ｎｏ）、ステップＳ３１１に移行する。
【０１９０】
このフローチャートによれば、ハッシュ値の再計算により参照されたデータの検索位置を、最新のテーブル合計サイズに合わせて、移動させることができ、再度同一のデータを検索する際、ハッシュ値の計算が一回で済むことになる。
【０１９１】
次に、情報処理装置３００が、データ削除時に実施する処理手順について説明する。図１８は、データ削除時の処理手順を示すフローチャートである。
【０１９２】
まず、情報処理装置３００が、利用プログラム６０からデータ削除の命令を受け、テーブルサイズ履歴テーブル３２０ｃの末尾の履歴データを参照する（ステップＳ４００）。
【０１９３】
そして、削除対象となっているデータのキーに対して、図１５に示したステップＳ１００からステップＳ１０２のシーケンスを実施する（ステップＳ４０１）。その後、情報処理装置３００は、ステップＳ４０１で決定されたキーの参照位置に基づいてデータを検索する（ステップＳ４０２）。
【０１９４】
そして、情報処理装置３００が、ステップＳ４０１にて決定されたキーの参照位置に、データを発見できなかった場合（ステップＳ４０３、Ｎｏ）、情報処理装置３００は、テーブルサイズ履歴テーブル３２０ｃの履歴番号を参照する（ステップＳ４０４）。
【０１９５】
情報処理装置３００が参照した履歴番号が初期値０であれば（ステップＳ４０５、Ｙｅｓ）、履歴番号の初期値まで遡ってデータを検索したことになるので、データが参照できなかった旨を報告する（ステップＳ４０７）。
【０１９６】
一方、情報処理装置３００が参照した履歴番号が初期値０でなければ（ステップＳ４０５、Ｎｏ）、ステップＳ４００にて参照したテーブル合計サイズの１つ前に遡ったテーブル合計サイズの履歴を参照し（ステップＳ４０６）、ステップＳ４０１へ移行する。
【０１９７】
また、ステップＳ４０３で、情報処理装置３００が、ステップＳ４０１にて決定されたキーの参照位置に、データを発見した場合（ステップＳ４０３、Ｙｅｓ）、検索したデータを削除する（ステップＳ４０８）。
【０１９８】
次に、情報処理装置３００が、テーブル合計サイズを拡大する際の処理手順について説明する。図１９は、テーブル合計サイズ拡大時の処理手順を示すフローチャートである。
【０１９９】
まず、情報処理装置３００が、利用プログラム６０からテーブル合計サイズの拡大命令を受け、単位テーブルサイズ４を有する内部ハッシュテーブルを新しく作成する（ステップＳ５００）。
【０２００】
その後、情報処理装置３００は、ステップＳ５００にて作成した内部ハッシュテーブルをテーブル管理テーブル３２０ｂが有するテーブル番号の末尾に追加登録する（ステップＳ５０１）。
【０２０１】
そして、情報処理装置３００は、自己が有する内部ハッシュテーブルのテーブル合計サイズを更新する（ステップＳ５０２）。そして、情報処理装置３００は、テーブルサイズ履歴テーブル３２０ｃの末尾に最新のテーブル合計サイズを追加する（ステップＳ５０３）。
【０２０２】
このフローチャートによれば、情報処理装置３００は、内部ハッシュテーブルを新規に追加することで、ハッシュテーブルを再構築せずに、テーブル合計サイズを拡大することができる。
【０２０３】
次に、情報処理装置３００が行うテーブル合計サイズ縮小時の処理手順について説明する。図２０は、テーブル合計サイズ縮小時の処理手順を示すフローチャートである。
【０２０４】
まず、情報処理装置３００が、利用プログラム６０からテーブル合計サイズの縮小命令を受け、テーブルサイズ履歴テーブル３２０ｃが有する末尾のテーブル合計サイズを削除する（ステップＳ６００）。
【０２０５】
そして、情報処理装置３００は、自己が有する内部ハッシュテーブルのテーブル合計サイズを更新する（ステップＳ６０１）。
【０２０６】
その後、情報処理装置３００は、内部ハッシュテーブルを削除し（ステップＳ６０２）、削除された内部ハッシュテーブル３３０ｃに登録されているキーに対し、図１５に示したステップＳ１００〜ステップＳ１０２のシーケンスを実施する（ステップＳ６０３）。
【０２０７】
そして、情報処理装置３００は、削除した内部ハッシュテーブルに使用していたメモリを解放し（ステップＳ６０４）、削除した内部ハッシュテーブルに対応するテーブル番号の削除を行う（ステップＳ６０５）。
【０２０８】
このフローチャートによれば、情報処理装置３００は、登録されるデータに応じて、内部ハッシュテーブルを削除することができ、その結果、メモリ資源の無駄な消費を防ぐことができる。
【０２０９】
上述したように、本願に開示した情報処理装置３００によれば、自装置が有する内部ハッシュテーブルに使用されるデータ量に応じて、そのテーブル合計サイズを変更することができる。その結果、内部ハッシュテーブルに使用されるメモリの無駄な消費を防ぐことができる。
【０２１０】
また、情報処理装置３００は、テーブル合計サイズの変更に伴うハッシュ値の再計算を即時に実施しないで、キーを参照した際、必要に応じて、再計算を実施する。したがって、ハッシュ値の再計算に要する処理の集中を回避することができ、ＳＬＡで定められる処理時間の最悪値を低減させることができる。
【０２１１】
なお、連鎖法を用いることで、各内部ハッシュテーブルのテーブルインデックスに登録されているキーのリスト検索は、リストの長さ「ｍ」に対して、参照時間はＯ（ｍ）となるが、テーブル合計サイズが増えるに連れ、同一のリストに登録されるデータが分散されるため「ｍ」の値が小さくなる。
【０２１２】
したがって、従来技術では、データを追加していき、テーブルサイズが大きくなるほど、検索に時間を費やしていたが、本実施例に示した情報処理装置３００は、データの検索時間を短縮できる。
【０２１３】
ところで、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部あるいは一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータを含む情報については、特記する場合を除いて任意に変更することができる。
【０２１４】
また、図２に示した情報処理装置３００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限らず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０２１５】
例えば、情報処理装置３００が有する機能は同一端末内に有する必要はなく、通信機能を介して接続された別サーバに内部ハッシュテーブルを配置しても良い。具体的に図を用いて説明する。
【０２１６】
図２１は、ハッシュ法によるデータ管理を実現するシステムの構成を示す機能ブロック図である。図２１に示したシステム４００は、図２に示した情報処理装置３００が有する機能と同様の機能を発揮し、クライアント４０１と、ネットワーク４０２と、管理装置４０３と、ネットワーク４０４と、サーバ４０５ａ〜４０５ｚとを有する。
【０２１７】
クライアント４０１は、管理装置４０３に対して、データ参照等の要求を行う装置で、ハッシュテーブル利用プログラム４０１ａと、通信機能４０１ｂとを有し、図２に示した利用プログラム６０に相当する。
【０２１８】
ハッシュテーブル利用プログラム４０１ａは、管理装置４０３に対して、サーバ４０５ａ〜４０５ｚが有するデータの参照、追加、削除等を要求するプログラムである。
【０２１９】
通信機能４０１ｂは、ネットワーク４０２を介して管理装置４０３とのデータ処理を行うインターフェースである。
【０２２０】
ネットワーク４０２は、クライアント４０１と管理装置４０３との接続を行うネットワークである。
【０２２１】
管理装置４０３は、クライント４０１からの要求に応じて、各種データ処理や、サーバ４０５ａ〜４０５ｚが有する内部ハッシュテーブルのデータの管理を行う装置で、通信機能４０３ａと、管理部４０３ｂと、テーブル管理テーブル４０３ｃと、テーブルサイズ履歴テーブル４０３ｄと、通信機能４０３ｅとを有する。
【０２２２】
通信機能４０３ａは、ネットワーク４０２を介してクライント４０１からの各種データ処理命令を管理部４０３ｂに出力するともに、管理部４０３ｂからデータが入力された場合は、データの応答をクライント４０１に行うインターフェースである。そして、この通信機能４０３ａは、図２に示したインターフェース３１０に対応するものとする。
【０２２３】
管理部４０３ｂは、図２に示した管理部３２０ａに対応するもので、通信機能４０３ａから入力される各種処理命令に対する応答を行う処理部である。そして、各種処理命令に応じて、テーブル管理テーブル４０３ｃに対するデータ処理やハッシュ計算を行い、合わせて、テーブルサイズ履歴テーブル４０３ｄのデータ管理を行う。
【０２２４】
テーブル管理テーブル４０３ｃは、図３に示したテーブル管理テーブル３２０ｂに相当するものとし、サーバ４０５ａ〜４０５ｚが有する内部ハッシュテーブルを登録するテーブル番号を有し、テーブル番号の管理を行う。
【０２２５】
テーブルサイズ履歴テーブル４０３ｄは、図３に示したテーブルサイズ履歴テーブル３２０ｃに相当するものとし、サーバ４０５ａ〜４０５ｚが有する内部ハッシュテーブルの合計メモリ数の履歴が記憶される。そして、管理部４０３ｂが、データの更新を行う。
【０２２６】
通信機能４０３ｅは、ネットワーク４０４を介してサーバ４０５ａ〜４０５ｚのデータ処理のやり取りを行うインターフェースである。
【０２２７】
ネットワーク４０４は、管理装置４０３と、サーバ４０５ａ〜４０５ｚとの接続を行うネットワークである。
【０２２８】
サーバ４０５ａ〜４０５ｚは、クラインアント４０１からの要求に応じて、キーと、キーにリンクされているデータを記憶する内部ハッシュテーブルを各々有し、各種サーバが有する内部ハッシュテーブルは、図２に示した内部ハッシュテーブル３３０ａに対応するものとする。以下、システム４００が複数有するサーバのうち、サーバ４０５ａを例に挙げ説明する。
【０２２９】
サーバ４０５ａは、クライアント４０１が利用する各種データを記憶する装置で、通信機能４１０と、データ管理部４１１と、内部ハッシュテーブル４１２とを有する。
【０２３０】
通信機能４１０は、ネットワーク４０４を介して管理装置４０３とデータのやり取りを行う処理部で、クラインアント４０１からの要求に応じて、キーと、キーにリンクされているデータを管理装置４０３から受信する。
【０２３１】
データ管理部４１１は、通信機能４１０が受信したデータを内部ハッシュテーブル４１２に登録する。なお、データが登録される位置は、管理部４０３ｂによって求められるものとする。
【０２３２】
内部ハッシュテーブル４１２は、クライアント４０１が利用する各種データと、それら各種データを識別するキーとを記憶するハッシュテーブルで、図２に示した内部ハッシュテーブル３３０ａに相当するものとする。
【０２３３】
そして、これら内部ハッシュテーブル４１２は、キーと、キーが有する各種データを登録するポインタに相当するテーブルインデックスを有し、キーが、所定のテーブルインデックスに登録される。
【０２３４】
また、図２１に示したサーバ４０５ｚも、上述したサーバ４０５ａと同様の機能を有し、通信機能４１０に相当するものとして、通信機能４２０を有し、データ管理部４１１に相当するものとして、データ管理部４２１を有し、内部ハッシュテーブル４１２に相当するものとして内部ハッシュテーブル４２２を有する。
【０２３５】
なお、本実施例で使用したハッシュ関数Ｈ（ｋ）は、キーの値とテーブル合計サイズから求められる関数であれば良く、必ずしも上述した式（２）に限定されることはない。
【０２３６】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２３７】
（付記１）複数のテーブルにデータを登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、
前記テーブルの追加または削除を行うテーブル管理部と、
前記テーブル管理部によって前記テーブルが追加または削除された後に、テーブルに登録されたデータを参照する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、当該登録位置に参照対象となるデータが存在するか否かを判定する判定部と、
前記登録位置に参照対象となるデータが存在しない場合に、前記データの登録位置を再計算する再計算部と、
を備えた情報処理装置。
【０２３８】
（付記２）前記再計算部によってデータの登録位置が再計算された場合に、再計算された登録位置に登録されたデータを、再計算される前に算出された登録位置に移動する移動部を更に備えた付記１に記載の情報処理装置。
【０２３９】
（付記３）前記既存のテーブルの総データ量の履歴情報を記録する履歴記録部を更に備え、前記再計算部は、前記履歴情報に基づいて前記データの位置を再計算する付記１または２に記載の情報処理装置。
【０２４０】
（付記４）データをテーブルに登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、
前記テーブルの追加または削除を行うテーブル管理部と
を備えた情報処理装置。
【０２４１】
（付記５）記憶装置とテーブル作成装置とを有する情報処理システムであって、
前記テーブル作成装置は、
前記記憶装置内の複数のテーブルにデータを登録する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、データを前記登録位置に登録する登録部と、
前記テーブルの追加または削除を行うテーブル管理部と、
前記テーブル管理部によって前記テーブルが追加または削除された後に、テーブルに登録されたデータを参照する場合に、既存のテーブルの総データ量とハッシュ法とを基にしてデータの登録位置を算出し、当該登録位置に参照対象となるデータが存在するか否かを判定する判定部と、
前記登録位置に参照対象となるデータが存在しない場合に、前記データの登録位置を再計算する再計算部と、
を備えた情報処理システム。
【符号の説明】
【０２４２】
１、５０  テーブル
６０  利用プログラム
１０  ハッシュテーブル
１００、３２０ｂ、４０３ｃ  テーブル管理テーブル
２００、２０１、２０２、３３０ａ〜３３０ｚ、４１２、４２２  内部ハッシュテーブル
３００  情報処理装置
３１０  インターフェース
３２０  テーブル管理部
３２０ａ、４０３ｂ  管理部
３２０ｃ、４０３ｄ  テーブルサイズ履歴テーブル
４００  システム
４０１  クライアント
４０１ａ  ハッシュテーブル利用プログラム
４０１ｂ、４０３ａ、４０３ｅ、４１０、４２０  通信機能
４０２、４０４  ネットワーク  
４０５ａ〜４０５ｚ  サーバ
４１１、４２１  データ管理部
【図１】
2010191538.tif 000003
【図２】
2010191538.tif 000004
【図３】
2010191538.tif 000005
【図４】
2010191538.tif 000006
【図５】
2010191538.tif 000007
【図６】
2010191538.tif 000008
【図７】
2010191538.tif 000009
【図８】
2010191538.tif 000010
【図９】
2010191538.tif 000011
【図１０】
2010191538.tif 000012
【図１１】
2010191538.tif 000013
【図１２】
2010191538.tif 000014
【図１３】
2010191538.tif 000015
【図１４】
2010191538.tif 000016
【図１５】
2010191538.tif 000017
【図１６】
2010191538.tif 000018
【図１７】
2010191538.tif 000019
【図１８】
2010191538.tif 000020
【図１９】
2010191538.tif 000021
【図２０】
2010191538.tif 000022
【図２１】
2010191538.tif 000023
【図２２】
2010191538.tif 000024
【図２３】
2010191538.tif 000025