(57)【要約】      （修正有）【課題】複数種類のメモリデバイスを併用してデータを保存する装置において、ハッシュテーブルにおける衝突の対処を早くする。【解決手段】情報処理装置は、第１メモリデバイス又は第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、キーの第１識別子を加え、検索キーに基づいて値を検索する場合に、当該検索キーと同族のキーに係るリストにおいて当該検索キーの第１識別子と紐付けられたエントリから値を取得する。【選択図】図５Ａ
2018116541.tif 000002
【特許請求の範囲】
【請求項１】
第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加える追加部と、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する取得部と
を有する情報処理装置。
【請求項２】
前記第１識別子は、前記第１ハッシュ値の算出に用いられたハッシュ関数と異なるハッシュ関数によって算出される第２ハッシュ値である
請求項１記載の情報処理装置。
【請求項３】
更に、
前記検索キーに基づいて前記値を検索した場合に、前記リストにおける当該検索キーの前記第１識別子の順位を上位方向に変更する変更部
を有する請求項１又は２記載の情報処理装置。
【請求項４】
更に、
前記第１メモリデバイスに新たなエントリを格納する領域が足りない場合に、前記第１メモリデバイスに格納されているエントリを前記第２メモリデバイスに移す移動部
を有する請求項１乃至３のいずれか１つ記載の情報処理装置。
【請求項５】
前記追加部は、前記リストに前記第１識別子を加える際に、前記リストに更に前記キーの第２識別子を加え、
前記取得部は、前記リストにおいて前記検索キーの前記第１識別子及び前記検索キーの第２識別子と紐付けられた前記エントリから前記値を取得する
請求項１乃至４のいずれか１つ記載の情報処理装置。
【請求項６】
前記取得部は、前記検索キーの第１識別子と紐付けられた前記エントリに含まれるキーが前記検索キーと一致するか否かを判定する
請求項１乃至４のいずれか１つ記載の情報処理装置。
【請求項７】
前記第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加え、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する
処理を含み、コンピュータにより実行される情報処理方法。
【請求項８】
第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加え、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数種類のメモリデバイスを用いてデータを保持する技術に関する。
【背景技術】
【０００２】
最近のアプリケーションで扱われるデータの量は、大きくなっている。しかし、大量のデータを保持するためのＤＲＡＭ（Dynamic Random Access Memory）を備えた装置は、高価である。そこで、ＤＲＡＭに加えて、比較的安価なメモリデバイスを併用する装置が考えられる。但し、このようなメモリデバイスは、レイテンシが大きい。
【０００３】
また、大量のデータを保持する装置でハッシュテーブルを用いることが、一般的に行われている。但し、ハッシュテーブルを用いる場合には、異なるキーから同一のハッシュ値が生まれ、ハッシュ値だけで所望の値を特定できない事態に至ることがある。このような事態を、ハッシュテーブルにおける衝突という。
【０００４】
衝突の対処のためにＤＲＡＭに大きな管理データを保持すれば、本来保持すべきデータに割り当てられるＤＲＡＭ領域が小さくなり、アクセス性能が劣化する。一方、衝突の対処のために安価なメモリデバイスにアクセスする回数が増えれば、衝突に係るデータの検索処理が遅くなる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０５−１２３３７号公報
【特許文献２】特開平０４−１０１２７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、一側面では、複数種類のメモリデバイスを併用してデータを保存する装置において、ハッシュテーブルにおける衝突の対処を早くすることである。
【課題を解決するための手段】
【０００７】
一態様に係る情報処理装置は、（Ａ）第１メモリデバイス又は第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、キーの第１識別子を加える追加部と、（Ｂ）検索キーに基づいて値を検索する場合に、当該検索キーと同族のキーに係るリストにおいて当該検索キーの第１識別子と紐付けられたエントリから値を取得する取得部とを有する。
【発明の効果】
【０００８】
一側面としては、複数種類のメモリデバイスを併用してデータを保存する装置において、ハッシュテーブルにおける衝突の対処が早くなる。
【図面の簡単な説明】
【０００９】
【図１】図１は、データ保存装置のハードウエア構成例を示す図である。
【図２】図２は、メモリデバイスに対する記憶部の割り当ての例を示す図である。
【図３Ａ】図３Ａは、データ構成の第１参考例を示す図である。
【図３Ｂ】図３Ｂは、データ構成の第１参考例を示す図である。
【図４Ａ】図４Ａは、データ構成の第２参考例を示す図である。
【図４Ｂ】図４Ｂは、データ構成の第２参考例を示す図である。
【図５Ａ】図５Ａは、実施の形態１におけるデータ構成を示す図である。
【図５Ｂ】図５Ｂは、実施の形態１におけるデータ構成を示す図である。
【図６】図６は、データ保存装置のモジュール構成例を示す図である。
【図７】図７は、メイン処理フローを示す図である。
【図８】図８は、登録処理（Ａ）フローを示す図である。
【図９】図９は、エントリレコード設定処理（Ａ）フロー例を示す図である。
【図１０】図１０は、ノード追加処理（Ａ）フローを示す図である。
【図１１Ａ】図１１Ａは、検索処理（Ａ）フローを示す図である。
【図１１Ｂ】図１１Ｂは、検索処理（Ａ）フローを示す図である。
【図１２Ａ】図１２Ａは、検索処理（Ｂ）フローを示す図である。
【図１２Ｂ】図１２Ｂは、検索処理（Ｂ）フローを示す図である。
【図１３】図１３は、エントリレコード設定処理（Ｂ）フローを示す図である。
【図１４】図１４は、実施の形態４におけるデータ構成を示す図である。
【図１５】図１５は、登録処理（Ｂ）フローを示す図である。
【図１６】図１６は、ノード追加処理（Ｂ）フローを示す図である。
【図１７Ａ】図１７Ａは、検索処理（Ｃ）フローを示す図である。
【図１７Ｂ】図１７Ｂは、検索処理（Ｃ）フローを示す図である。
【図１８】図１８は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１０】
［実施の形態１］
図１は、データ保存装置１００のハードウエア構成例を示す図である。ＣＰＵ（Central Processing Unit）１０１は、ＤＲＡＭ制御回路１０３、ＮＶＲＡＭ（Non-Volatile Random Access Memory）制御回路１０７及び通信制御回路１１１と接続している。ＤＲＡＭ制御回路１０３は、ＤＲＡＭ１０５と接続している。ＤＲＡＭ制御回路１０３は、ＤＲＡＭ１０５を制御する。ＮＶＲＡＭ制御回路１０７は、ＮＶＲＡＭ１０９と接続している。ＮＶＲＡＭ制御回路１０７は、ＮＶＲＡＭ１０９を制御する。ＤＲＡＭ１０５及びＮＶＲＡＭ１０９は、主記憶装置として用いられる。通信制御回路１１１は、ネットワーク通信を制御する。尚、ＮＶＲＡＭ１０９は、ＤＲＡＭ１０５よりもレイテンシが大きい。ＮＶＲＡＭ１０９は、例えばＰＣＭ（Phase Change Memory）、ＲｅＲＡＭ（Resistive Random Access Memory）又はＭＲＡＭ（Magnetoresistive Random Access Memory）である。
【００１１】
図２は、メモリデバイスに対する記憶部の割り当ての例を示す図である。ハッシュテーブル記憶部２０１、リンクリスト記憶部２０３及び第１エントリ記憶部２０５は、ＤＲＡＭ１０５に割り当てられている。第２エントリ記憶部２０７は、ＮＶＲＡＭ１０９に割り当てられている。
【００１２】
ハッシュテーブル記憶部２０１において記憶されるハッシュテーブルは、キーと値との組を登録し、検索キーに基づいて値を検索するプログラムによって、検索性能を高めるために用いられる管理データである。尚、キーと値との組をエントリということがある。
【００１３】
ハッシュテーブルは、キーに基づいて算出されたハッシュ値を用いる。具体的には、ハッシュテーブルは、ハッシュ値をインデックスとした配列である。配列要素は、リンクリストの先頭ノードを特定するリンクデータである。リンクリストについては、後述する。
【００１４】
ハッシュ値を算出するハッシュ関数は、入力されるキーが異なる場合でも同一のハッシュ値を出力することがある。ハッシュテーブルにおいて、同一のハッシュ値の元となるキーを同族キーという。つまり、異なるキーに基づいて算出された結果が同じであれば、それらは同族キーである。
【００１５】
リンクリスト記憶部２０３は、同族キーに係るエントリを関連付けるリストを記憶する。この例におけるリストは、リンクリスト形式である。リンクリストは、連結リストということもある。リンクリストは、ノードの連なりである。この例では、ノードは、同族キーの各々に対応する。
【００１６】
第１エントリ記憶部２０５は、ＤＲＡＭ１０５に割り当てられたエントリをレコード形式で記憶する。また、第２エントリ記憶部２０７は、ＮＶＲＡＭ１０９に割り当てられたエントリをレコード形式で記憶する。
【００１７】
本実施の形態は、ＤＲＡＭ１０５とＮＶＲＡＭ１０９とを併用するデータ保存装置１００において、ハッシュテーブルにおけるハッシュ値（この例では、第１ハッシュ値）に関する衝突を解消するための仕組みに関する。具体的には、衝突を解消する連鎖法におけるデータ構成に着目する。
【００１８】
本実施の形態について説明する前に、２つの参考例について説明する。第１参考例では、エントリが第１エントリ記憶部２０５及び第２エントリ記憶部２０７のいずれかのレコード（以下、エントリレコードという。）として記憶される。図３Ａ及び図３Ｂは、データ構成の第１参考例を示す図である。
【００１９】
まず、ハッシュテーブルの構成について説明する。この例におけるハッシュテーブルは、シーケンシャルな第１ハッシュ値に対応するレコードを有している。ハッシュテーブルは、第１ハッシュ値が格納されているフィールドと、リンクデータを設定するためのフィールドとを有している。
【００２０】
第１ハッシュ値は、配列のインデックスである。リンクデータは、リンクリストの先頭ノードを特定する。リンクデータは、例えば当該先頭ノードのアドレス又は当該先頭ノードのＩＤである。尚、リンクリストが未だ設けられていない場合には、リンクデータのためのフィールドには未使用コードが設定される。
【００２１】
この例で、キーＸに基づく第１ハッシュ値ＨａX、キーＹに基づく第１ハッシュ値ＨａY及びキーＺに基づく第１ハッシュ値ＨａZは、いずれも０ｘ０００１である。つまり、キーＸ、キーＹ及びキーＺは同族キーである。また、この同族キーに関するリンクリストの先頭ノードへのリンクデータがＬXである。具体的には、ＬXは、リンクリスト記憶部２０３に図示した１番目のノードを特定する。
【００２２】
続いて、リンクリストの構成について説明する。リンクリストは、同族キー毎に設けられる。リンクリストにおいて、同族キーと同数のノードが連なる。ノードは、ポインタを設定するためのフィールドと、リンクデータを設定するためのフィールドとを有している。
【００２３】
ポインタは、当該同族キーを含むエントリレコードの開始アドレスを指す。リンクデータは、次のノードを特定する。リンクデータは、例えば次のノードのアドレス又は次のノードのＩＤである。尚、最後のノードの場合に、リンクデータのフィールドには終端コードが設定される。
【００２４】
図示した１番目のノードは、キーＫXに対応する。このノードにおけるポインタのフィールドには、キーＫX及び値ＶXを含むエントリレコードの開始アドレスを指すポインタＰXが設定されている。また、このノードには、２番目のノードを特定するリンクデータＬYが設定されている。
【００２５】
図示した２番目のノードは、キーＫYに対応する。このノードにおけるポインタのフィールドには、キーＫY及び値ＶYを含むエントリレコードの開始アドレスを指すポインタＰYが設定されている。また、このノードには、３番目のノードを特定するリンクデータＬZが設定されている。
【００２６】
図示した３番目のノードは、キーＫZに対応する。このノードにおけるポインタのフィールドには、キーＫZ及び値ＶZを含むエントリレコードの開始アドレスを指すポインタＰZが設定されている。また、このノードが終端であるので、リンクデータのフィールドには終端コードが設定されている。
【００２７】
第１エントリ記憶部２０５及び第２エントリ記憶部２０７には、キー及び値を含むエントリが記憶されている。
【００２８】
続いて、検索要求に含まれる検索キーがＫZである場合の動作について説明する。まず、検索キーＫZのハッシュ値ＨａZ（０ｘ０００１）に対応するリンクデータＬXが読まれる（Ｓ３０１）。更に、リンクデータＬXによって特定される１番目のノードに設定されているポインタＰXが読まれる（Ｓ３０２）。そして、ポインタＰXによって特定される第２エントリ記憶部２０７のエントリレコードに設定されているキーＫXが読まれる（Ｓ３０３）。読み取ったキーＫXが検索キーＫZと一致しないので、当該エントリレコードは参照対象でない。
【００２９】
従って、１番目のノードに設定されているリンクデータＬYが読まれる（Ｓ３０４）。更に、リンクデータＬYによって特定される２番目のノードに設定されているポインタＰYが読まれる（Ｓ３０５）。そして、ポインタＰYによって特定される第２エントリ記憶部２０７のエントリレコードに設定されているキーＫYが読まれる（Ｓ３０６）。読み取ったキーＫYが検索キーＫZと一致しないので、当該エントリレコードは参照対象でない。
【００３０】
従って、２番目のノードに設定されているリンクデータＬZが読まれる（Ｓ３０７）。更に、リンクデータＬZによって特定される３番目のノードに設定されているポインタＰZが読まれる（Ｓ３０８）。そして、ポインタＰZによって特定される第１エントリ記憶部２０５のエントリレコードに設定されているキーＫZが読まれる（Ｓ３０９）。読み取ったキーＫZが検索キーＫZと一致するので、当該エントリレコードは、参照対象である。
【００３１】
この場合には、当該エントリレコードに設定されている値ＶZが読まれる（Ｓ３１０）。この値ＶZが、検索結果となる。
【００３２】
この例では、同族キーが第１エントリ記憶部２０５及び第２エントリ記憶部２０７に分散する。従って、検索キーを含むエントリレコードを探索する過程で、Ｓ３０３及びＳ３０６に示したようにＮＶＲＡＭ１０９からキーを読み取ることになる。そのために、同族キーに係る検索の処理速度が遅くなることがある。
【００３３】
続いて、第２参考例について説明する。図４Ａ及び図４Ｂは、データ構成の第２参考例を示す図である。第２参考例では、エントリレコードにおいてキーを設定するためのフィールドが省かれている。一方、ノードに当該キーを設定するためのフィールドが設けられている。
【００３４】
第２参考例におけるハッシュテーブルの構成は、第１参考例の場合と同様である。
【００３５】
第２参考例におけるリンクリストの構成について説明する。ノードは、ポインタを設定するためのフィールドと、リンクデータを設定するためのフィールドとの他に、キーを設定するためのフィールドを有している。このフィールドに設定されるキーは、同族キーに相当する。
【００３６】
図示した１番目のノードには、キーＫXが設定されている。同じく２番目のノードには、キーＫYが設定されている。同じく３番目のノードには、キーＫZが設定されている。
【００３７】
続いて、検索要求に含まれる検索キーがＫZである場合の動作について説明する。まず、検索キーＫZのハッシュ値ＨａZ（０ｘ０００１）に対応するリンクデータＬXが読まれる（Ｓ４０１）。更に、リンクデータＬXによって特定される１番目のノードに設定されているキーＫXが読まれる（Ｓ４０２）。読み取ったキーＫXが検索キーＫZと一致しないので、当該ノードは参照対象に関らない。
【００３８】
従って、１番目のノードに設定されているリンクデータＬYが読まれる（Ｓ４０３）。更に、リンクデータＬYによって特定される２番目のノードに設定されているキーＫYが読まれる（Ｓ４０４）。読み取ったキーＫYが検索キーＫZと一致しないので、当該ノードは参照対象に関らない。
【００３９】
従って、２番目のノードに設定されているリンクデータＬZが読まれる（Ｓ４０５）。更に、リンクデータＬZによって特定される３番目のノードに設定されているキーＫZが読まれる（Ｓ４０６）。読み取ったキーＫZが検索キーＫZと一致するので、当該エントリレコードは、参照対象である。
【００４０】
この場合には、３番目のノードに設定されているポインタＰZが読まれる（Ｓ４０７）。そして、ポインタＰZによって特定される第１エントリ記憶部２０５のエントリレコードに設定されている値ＶZが読まれる（Ｓ４０８）。値ＶZが、検索結果となる。
【００４１】
この例では、同族キーがリンクリスト記憶部２０３に集中する。従って、検索キーを含むエントリレコードを探索する過程で、第２エントリ記憶部２０７にアクセスせずに済む。そのために、同族キーに係る検索の処理速度が速くなる。但し、ノードのフィールドが増えるのでリンクリスト記憶部２０３の領域が大きくなる。これに伴い、第１エントリ記憶部２０５の領域が小さくなる。従って、ＤＲＡＭ１０５に記憶される値の割合が少なくなるので、高速に検索されないケースが増えるという問題が生じる。
【００４２】
図５Ａ及び図５Ｂは、本実施の形態におけるデータ構成を示す図である。本実施の形態では、エントリレコードは、第１参考例の場合と同様である。一方、ノードに、第２参考例におけるキーを設定するためのフィールドの代わりに、第２ハッシュ値を設定するためのフィールドが設けられている。第２ハッシュ値は、第１ハッシュ値と同様にキーに基づいて算出される。但し、第２ハッシュ値は、第１ハッシュ値を算出するハッシュ関数と異なるハッシュ関数によって算出される。
【００４３】
本実施の形態におけるハッシュテーブルの構成は、第１参考例の場合と同様である。
【００４４】
本実施の形態におけるリンクリストの構成について説明する。ノードは、ポインタを設定するためのフィールドと、リンクデータを設定するためのフィールドとの他に、第２ハッシュ値を設定するためのフィールドを有している。
【００４５】
図示した１番目のノードには、キーＫXに基づく第２ハッシュ値ＨｂXが設定されている。同じく２番目のノードには、キーＫYに基づく第２ハッシュ値ＨｂYが設定されている。同じく３番目のノードには、キーＫZに基づく第２ハッシュ値ＨｂZが設定されている。
【００４６】
本実施の形態における第１エントリ記憶部２０５及び第２エントリ記憶部２０７の構成は、第１参考例の場合と同様である。
【００４７】
続いて、検索要求に含まれる検索キーがＫZである場合の動作について説明する。まず、検索キーＫZのハッシュ値ＨａZ（０ｘ０００１）に対応するリンクデータＬXが読まれる（Ｓ５０１）。更に、リンクデータＬXによって特定される１番目のノードに設定されている第２ハッシュ値ＨｂXが読まれる（Ｓ５０２）。読み取った第２ハッシュ値ＨｂXが検索キーＫZの第２ハッシュ値ＨｂZと一致しないので、当該ノードは参照対象に関らない。
【００４８】
従って、１番目のノードに設定されているリンクデータＬYが読まれる（Ｓ５０３）。更に、リンクデータＬYによって特定される２番目のノードに設定されている第２ハッシュ値ＨｂYが読まれる（Ｓ５０４）。読み取った第２ハッシュ値ＨｂYが検索キーＫZの第２ハッシュ値ＨｂZと一致しないので、当該ノードは参照対象に関らない。
【００４９】
従って、２番目のノードに設定されているリンクデータＬZが読まれる（Ｓ５０５）。更に、リンクデータＬZによって特定される３番目のノードに設定されている第２ハッシュ値ＨｂZが読まれる（Ｓ５０６）。読み取った第２ハッシュ値ＨｂZが検索キーＫZの第２ハッシュ値ＨｂZと一致するので、当該ノードに対応するエントリレコードは、参照対象の候補である。
【００５０】
この場合には、３番目のノードに設定されているポインタＰZが読まれる（Ｓ５０７）。そして、ポインタＰZによって特定される第１エントリ記憶部２０５のエントリレコードに設定されているキーＫZが読まれる（Ｓ５０８）。読み取ったキーＫZが検索キーＫZと一致するので、当該エントリレコードは、参照対象である。そして、ポインタＰZによって特定される第１エントリ記憶部２０５のエントリレコードに設定されている値ＶZが読まれる（Ｓ５０９）。値ＶZが、検索結果となる。
【００５１】
第２ハッシュ値のサイズはキーのサイズよりも小さいので、本実施の形態におけるリンクリスト記憶部２０３の領域は、第２参考例に比べて小さい。従って、第１エントリ記憶部２０５の領域は、それほど圧迫されず、高速に検索されないケースが増えるという第２参考例の問題は解消される。
【００５２】
また、エントリレコードを探索する過程で、第２エントリ記憶部２０７からキーを読み取る機会が少ないので、同族キーに係る検索の処理速度はあまり遅くならない。以上で本実施の形態における概要の説明を終える。
【００５３】
以下、データ保存装置１００の動作について説明する。図６に、データ保存装置１００のモジュール構成例を示す。データ保存装置１００は、受付部６０１、返答部６０３、登録部６０５、検索部６１１、第１算出部６１７、第２算出部６１９、変更部６２１、移動部６２２、第３算出部６２３、ハッシュテーブル記憶部２０１、リンクリスト記憶部２０３、第１エントリ記憶部２０５及び第２エントリ記憶部２０７を有する。
【００５４】
受付部６０１は、クライアントから登録要求又は検索要求を受け付ける。返答部６０３は、処理結果又は検索された値をクライアントへ返答する。
【００５５】
登録部６０５は、登録要求に基づいて新たなエントリを登録する。登録部６０５は、設定部６０７及び追加部６０９を有する。設定部６０７は、新たなエントリレコードを設定する。追加部６０９は、新たなエントリレコードに対応するノードを追加する。
【００５６】
検索部６１１は、検索要求に基づいて値を検索する。検索部６１１は、探索部６１３及び取得部６１５を有する。探索部６１３は、検索キーと一致するキーを含むエントリレコードを探索する。取得部６１５は、探索されたエントリレコードから値を取得する。
【００５７】
第１算出部６１７は、第１ハッシュ値を算出する。第２算出部６１９は、第２ハッシュ値を算出する。変更部６２１は、実施の形態２においてリンクリストに含まれるノードの順位を変更する。移動部６２２は、実施の形態３においてエントリレコードを移動する。第３算出部６２３は、実施の形態４において第３ハッシュ値を算出する。
【００５８】
上述した通り、ハッシュテーブル記憶部２０１は、ハッシュテーブルを記憶する。リンクリスト記憶部２０３は、リンクリストを記憶する。第１エントリ記憶部２０５は、ＤＲＡＭ１０５に割り当てられたエントリレコードを記憶する。第２エントリ記憶部２０７は、ＮＶＲＡＭ１０９に割り当てられたエントリレコードを記憶する。
【００５９】
上述した受付部６０１、返答部６０３、登録部６０５、設定部６０７、追加部６０９、検索部６１１、探索部６１３、取得部６１５、第１算出部６１７、第２算出部６１９、変更部６２１、移動部６２２及び第３算出部６２３は、ハードウエア資源（例えば、図１及び図１８）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【００６０】
上述したハッシュテーブル記憶部２０１、リンクリスト記憶部２０３、第１エントリ記憶部２０５及び第２エントリ記憶部２０７は、ハードウエア資源（例えば、図１及び図１８）を用いて実現される。
【００６１】
続いて、データ保存装置１００における処理について説明する。図７は、メイン処理フローを示す図である。データ保存装置１００は、クライアントから要求を受け付ける。クライアントは、例えばデータ保存装置１００以外の装置である。但し、クライアントは、データ保存装置１００に含まれるソフトウエアであってもよい。
【００６２】
受付部６０１は、クライアントから登録要求を受け付けたか否かを判定する（Ｓ７０１）。登録要求は、クライアントがエントリの登録を要求する場合に発行される。登録要求には、キーと値との組、つまり登録すべきエントリが含まれている。
【００６３】
クライアントから登録要求を受け付けたと判定した場合には、登録部６０５は、登録処理を実行する（Ｓ７０３）。登録処理では、受け付けたエントリの登録を行う。登録処理については、図８乃至図１０を用いて後述する。登録処理を終えると、Ｓ７０１に示した処理に戻って、上述した処理を繰り返す。
【００６４】
一方、クライアントから登録要求を受け付けていないと判定した場合には、受付部６０１は、検索要求を受け付けたか否かを判定する（Ｓ７０５）。検索要求は、クライアントが検索キーに対応する値を取得する場合に発行される。検索要求には、検索キーが含まれている。クライアントから検索要求を受け付けていないと判定した場合には、Ｓ７０１に示した処理に戻って、上述した処理を繰り返す。
【００６５】
クライアントから検索要求を受け付けたと判定した場合には、検索部６１１は、検索処理を実行する（Ｓ７０７）。検索処理では、検索キーに基づいて値を検索する。検索処理については、図１１Ａ及び図１１Ｂを用いて後述する。
【００６６】
本実施の形態では、Ｓ７０３において登録処理（Ａ）を実行する。図８は、登録処理（Ａ）フローを示す図である。第１算出部６１７は、登録要求に含まれるキーに基づく第１ハッシュ値を算出する（Ｓ８０１）。第２算出部６１９は、登録要求に含まれるキーに基づく第２ハッシュ値を算出する（Ｓ８０３）。
【００６７】
設定部６０７は、エントリレコード設定処理を実行する（Ｓ８０５）。エントリレコード設定処理では、第１エントリ記憶部２０５又は第２エントリ記憶部２０７に新たなエントリレコードを設定する。
【００６８】
本実施の形態では、エントリレコード設定処理（Ａ）を実行する。図９は、エントリレコード設定処理（Ａ）フロー例を示す図である。設定部６０７は、第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域があるか否かを判定する（Ｓ９０１）。第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域があると判定した場合には、設定部６０７は、第１エントリ記憶部２０５に新たなエントリレコードを設ける（Ｓ９０３）。
【００６９】
一方、第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域がないと判定した場合には、設定部６０７は、第２エントリ記憶部２０７に新たなエントリレコードを設ける（Ｓ９０５）。
【００７０】
設定部６０７は、新たなエントリレコードに、登録要求に含まれるキーと値とを設定する（Ｓ９０７）。エントリレコード設定処理（Ａ）を終えると、呼び出し元の登録処理（Ａ）に復帰する。
【００７１】
図８の説明に戻る。次に、追加部６０９は、ノード追加処理（Ａ）を実行する（Ｓ８０７）。ノード追加処理（Ａ）では、リンクリストに、新たなエントリレコードに対応するノードを追加する。
【００７２】
図１０は、ノード追加処理（Ａ）フローを示す図である。追加部６０９は、Ｓ８０１で算出された第１ハッシュ値に対応するリンクデータを特定する（Ｓ１００１）。リンクデータによって、第１ハッシュ値にかかる同族キーに関するリンクリストの先頭ノードが特定される。
【００７３】
追加部６０９は、当該先頭ノードの前に新たなノードを挿入する（Ｓ１００３）。具体的には、新たなノードには、Ｓ１００１で特定されたリンクデータが設定される。更に、第１ハッシュ値に対応するリンクデータは、新たなノードを特定するためのリンクデータに書き換えられる。
【００７４】
このようにすれば、時間的局所性の面から、データ保存装置１００における検索性能が良くなる。但し、新たなノードを先頭以外の位置に加えるようにしてもよい。例えば、リンクリストの末尾に新たなノードを追加するようにしてもよい。
【００７５】
追加部６０９は、新たなノードに、Ｓ８０３で算出された第２ハッシュ値を設定する（Ｓ１００５）。追加部６０９は、新たなノードに、Ｓ８０５で設定されたエントリレコードの開始アドレスを指すポインタを設定する（Ｓ１００７）。ノード追加処理（Ａ）を終えると、呼び出し元の登録処理（Ａ）に復帰する。
【００７６】
図８の説明に戻る。最後に、返答部６０３は、処理結果を返答する（Ｓ８０９）。上述した処理が正常に行われた場合には、処理結果として成功を返答する。但し、例えば記憶領域が足りない場合には、処理結果として失敗を返答することもある。登録処理（Ａ）を終えると、呼び出し元のメイン処理に復帰する。
【００７７】
続いて、検索処理について説明する。本実施の形態では、Ｓ７０７において検索処理（Ａ）を実行する。図１１Ａ及び図１１Ｂは、検索処理（Ａ）フローを示す図である。
【００７８】
第１算出部６１７は、検索要求に含まれる検索キーに基づく第１ハッシュ値を算出する（Ｓ１１０１）。第２算出部６１９は、検索要求に含まれる検索キーに基づく第２ハッシュ値を算出する（Ｓ１１０３）。そして、探索部６１３は、ハッシュテーブルにおいて、Ｓ１１０１で算出された第１ハッシュ値に対応するリンクデータを特定する（Ｓ１１０５）。端子Ａを介して、図１１Ｂに示したＳ１１０７の処理に移る。
【００７９】
探索部６１３は、リンクデータに基づいてリンクリストに含まれるノードを１つ特定する（Ｓ１１０７）。例えば、探索部６１３は、リンクされている順番に従ってノードを特定する。
【００８０】
探索部６１３は、当該ノードから第２ハッシュ値を読む（Ｓ１１０９）。探索部６１３は、読み取った第２ハッシュ値が、Ｓ１１０３で算出された第２ハッシュ値と一致するか否かを判定する（Ｓ１１１１）。
【００８１】
当該２つの第２ハッシュ値が一致しないと判定した場合には、探索部６１３は、未特定のノードがあるか否かを判定する（Ｓ１１１３）。例えば、探索部６１３は、リンクされている順番に従って次のノードがあるか否かを判定する。Ｓ１１０７において特定されたノードにリンクデータに代えて終端コードが設定されていれば、未特定のノードはないと判定する。
【００８２】
未特定のノードがないと判定した場合には、返答部６０３は、処理結果として失敗を返答する（Ｓ１１１５）。そして、検索処理（Ａ）を終え、呼び出し元のメイン処理に復帰する。
【００８３】
一方、未特定のノードがあると判定した場合には、Ｓ１１０７に示した処理に戻って、上述した処理を繰り返す。
【００８４】
Ｓ１１１１に示した処理の説明に戻る。読み取った第２ハッシュ値が、Ｓ１１０３で算出された第２ハッシュ値と一致すると判定した場合には、探索部６１３は、Ｓ１１０７で特定されたノードからポインタを読む（Ｓ１１１７）。更に、探索部６１３は、当該ポインタで特定されるエントリレコードからキーを読む（Ｓ１１１９）。そして、探索部６１３は、読み取ったキーが、検索要求に含まれる検索キーと一致するか否かを判定する（Ｓ１１２１）。
【００８５】
当該２つのキーが一致しないと判定した場合には、Ｓ１１１３の処理に移る。一方、当該２つのキーが一致すると判定した場合には、取得部６１５は、Ｓ１１１９で特定されたエントリレコードから値を読む（Ｓ１１２３）。そして、返答部６０３は、当該値を返答する（Ｓ１１２５）。検索処理（Ａ）を終えると、呼び出し元のメイン処理に復帰する。
【００８６】
本実施の形態によれば、複数種類のメモリデバイスを併用してデータを保存する装置において、ハッシュテーブルにおける衝突の対処が早くなる。
【００８７】
また、衝突の対処にキーに基づく第２ハッシュ値を用いるので、ＤＲＡＭの領域を圧迫し難い。
【００８８】
［実施の形態２］
本実施の形態では、参照対象となったエントリレコードに対応するノードを、リンクリストの先頭に繰り上げる例について説明する。
【００８９】
本実施の形態では、検索処理（Ａ）に代えて、検索処理（Ｂ）を実行する。図１２Ａ及び図１２Ｂは、検索処理（Ｂ）フローを示す図である。Ｓ１１０１乃至Ｓ１１２５に示した処理は、図１１Ａ及び図１１Ｂの場合と同様である。
【００９０】
Ｓ１１２５において、検索された値を返答すると、変更部６２１は、Ｓ１１０７で特定されたノードの順位をリンクリストの先頭に繰り上げる（Ｓ１２０１）。具体的には、第１ハッシュ値に対応するリンクデータが、Ｓ１１０７で特定されたノードを特定するためのリンクデータに書き換えられる。更に、Ｓ１１０７で特定されたノードの前のノードに設定されているリンクデータが、Ｓ１１０７で特定されたノードの次のノードを特定するためのリンクデータに書き換えられる。
【００９１】
尚、変更部６２１は、Ｓ１１０７で特定されたノードの順位を所定数だけ繰り上げるようにしてもよい。
【００９２】
尚、登録処理は、実施の形態１の場合と同様である。
【００９３】
本実施の形態によれば、時間的局所性の面から、検索された値の再検索を行う処理が速くなる。
【００９４】
［実施の形態３］
本実施の形態では、第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き容量が足りない場合に、第１エントリ記憶部２０５に記憶されているエントリレコードを第２エントリ記憶部２０７に移す例について説明する。
【００９５】
本実施の形態では、実施の形態１又は２を基礎として、エントリレコード設定処理（Ａ）に代えて、エントリレコード設定処理（Ｂ）を実行する。
【００９６】
図１３に、エントリレコード設定処理（Ｂ）フローを示す。設定部６０７は、第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域があるか否かを判定する（Ｓ１３０１）。第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域があると判定した場合には、設定部６０７は、そのまま第１エントリ記憶部２０５に新たなエントリレコードを設ける（Ｓ１３０５）。
【００９７】
一方、第１エントリ記憶部２０５に新たなエントリレコードを設けるための空き領域がないと判定した場合には、移動部６２２は、第１エントリ記憶部２０５のエントリレコードのうち、検索頻度が基準よりも低いエントリレコードを第２エントリ記憶部２０７に移す（Ｓ１３０３）。このとき、当該エントリレコードに対応するノードにおけるリンクデータも更新される。その後、設定部６０７は、第１エントリ記憶部２０５に新たなエントリレコードを設ける（Ｓ１３０５）。
【００９８】
そして、設定部６０７は、新たなエントリレコードに、登録要求に含まれるキーと値とを設定する（Ｓ１３０７）。エントリレコード設定処理（Ｂ）を終えると、呼び出し元の登録処理（Ａ）に復帰する。
【００９９】
尚、検索頻度のフィールドは、ノード或いはエントリレコードのいずれに設けるようにしてもよい。そして、検索処理（Ａ）又は検索処理（Ｂ）では、参照対象となったエントリレコードの検索頻度を計数する。
【０１００】
本実施の形態によれば、時間的局所性の面から、最近登録されたエントリに係る値を検索する場合の処理が速くなる。
【０１０１】
［実施の形態４］
本実施の形態では、第２ハッシュ値に関する衝突に対処するために、更に第３ハッシュ値を用いる例について説明する。
【０１０２】
図１４は、実施の形態４におけるデータ構成を示す図である。本実施の形態のリンクリストにおけるノードは、実施の形態１の場合のフィールドに加えて、第３ハッシュ値を設定するためのフィールドを有している。第３ハッシュ値は、第１ハッシュ値及び第２ハッシュ値と同様にキーに基づいて算出される。但し、第３ハッシュ値は、第１ハッシュ値を算出するハッシュ関数及び第２ハッシュ値を算出するハッシュ関数と異なるハッシュ関数によって算出される。
【０１０３】
第３ハッシュ値は、第１ハッシュ値に関する同族キーが第２ハッシュ値に関しても同族である場合に、キーを区別するために用いられる。以下の例では、キーＫYとキーＫZが、第１ハッシュ値に関する同族であると共に、第２ハッシュ値に関しても同族であるものとする。つまり、第１ハッシュ値ＨａYと第１ハッシュ値ＨａZとは等しく、更に第２ハッシュ値ＨｂYと第２ハッシュ値ＨｂZとは等しいものとする。
【０１０４】
ハッシュテーブル、第１エントリ記憶部２０５及び第２エントリ記憶部２０７の構成は、実施の形態１の場合と同様である。
【０１０５】
続いて、検索要求に含まれる検索キーがＫZである場合の動作について説明する。まず、検索キーＫZのハッシュ値ＨａZ（０ｘ０００１）に対応するリンクデータＬXが読まれる（Ｓ１４０１）。更に、リンクデータＬXによって特定される１番目のノードに設定されている第２ハッシュ値ＨｂXが読まれる（Ｓ１４０２）。読み取った第２ハッシュ値ＨｂXが検索キーＫZの第２ハッシュ値ＨｂZと一致しないので、当該ノードは参照対象に関らない。
【０１０６】
従って、１番目のノードに設定されているリンクデータＬYが読まれる（Ｓ１４０３）。更に、リンクデータＬYによって特定される２番目のノードに設定されている第２ハッシュ値ＨｂYが読まれる（Ｓ１４０４）。読み取った第２ハッシュ値ＨｂYが検索キーＫZの第２ハッシュ値ＨｂZと一致するので、更に２番目のノードに設定されている第３ハッシュ値ＨｃYが読まれる（Ｓ１４０５）。但し、読み取った第３ハッシュ値ＨｃYが検索キーＫZの第３ハッシュ値ＨｃZと一致しないので、当該ノードは参照対象に関らない。
【０１０７】
従って、２番目のノードに設定されているリンクデータＬZが読まれる（Ｓ１４０６）。更に、リンクデータＬZによって特定される３番目のノードに設定されている第２ハッシュ値ＨｂZが読まれる（Ｓ１４０７）。読み取った第２ハッシュ値ＨｂZが検索キーＫZの第２ハッシュ値ＨｂZと一致するので、更に３番目のノードに設定されている第３ハッシュ値ＨｃZが読まれる（Ｓ１４０８）。そして、読み取った第３ハッシュ値ＨｃZが検索キーＫZの第３ハッシュ値ＨｃZと一致するので、当該ノードに対応するエントリレコードは、参照対象の候補である。
【０１０８】
この場合には、３番目のノードに設定されているポインタＰZが読まれる（Ｓ１４０９）。そして、ポインタＰZによって特定される第１エントリ記憶部２０５のエントリレコードに設定されているキーＫZが読まれる（Ｓ１４１０）。読み取ったキーＫZが検索キーＫZと一致するので、当該エントリレコードは、参照対象である。そして、当該エントリレコードに設定されている値ＶZが読まれる（Ｓ１４１１）。値ＶZが、検索結果となる。
【０１０９】
本実施の形態における処理の説明に移る。本実施の形態では、登録処理（Ａ）に代えて、登録処理（Ｂ）を実行する。図１５に、登録処理（Ｂ）フローを示す。
【０１１０】
Ｓ８０１及びＳ８０３に示した処理は、図８の場合と同様である。第３算出部６２３は、キーに基づく第３ハッシュ値を算出する（Ｓ１５０１）。
【０１１１】
Ｓ８０５に示した処理は、図８の場合と同様である。追加部６０９は、ノード追加処理（Ａ）に代えて、ノード追加処理（Ｂ）を実行する（Ｓ１５０３）。
【０１１２】
図１６は、ノード追加処理（Ｂ）フローを示す図である。Ｓ１００１乃至Ｓ１００５に示した処理は、図１０の場合と同様である。追加部６０９は、新たなノードに第３ハッシュ値を設定する（Ｓ１６０１）。
【０１１３】
Ｓ１００７に示した処理は、図１０の場合と同様である。ノード追加処理（Ｂ）を終えると、呼び出し元の登録処理（Ｂ）に復帰する。
【０１１４】
図１５の説明に戻る。Ｓ８０９に示した処理は、図８の場合と同様である。
【０１１５】
また、本実施の形態では、検索処理（Ｃ）を実行する。図１７Ａ及び図１７Ｂは、検索処理（Ｃ）フローを示す図である。
【０１１６】
Ｓ１１０１及びＳ１１０３に示した処理は、図１１Ａの場合と同様である。第３算出部６２３は、検索要求に含まれる検索キーに基づく第３ハッシュ値を算出する（Ｓ１７０１）。
【０１１７】
Ｓ１１０５乃至Ｓ１１１５に示した処理は、図１１Ａ及び図１１Ｂの場合と同様である。Ｓ１１１１において、上述した２つの第２ハッシュ値が一致すると判定した場合には、探索部６１３は、当該ノードから第３ハッシュ値を読む（Ｓ１７０３）。探索部６１３は、読み取った第３ハッシュ値が、Ｓ１７０１で算出された第３ハッシュ値と一致するか否かを判定する（Ｓ１７０５）。当該２つの第３ハッシュ値が一致しないと判定した場合には、Ｓ１１１３に示した処理に移る。
【０１１８】
一方、当該２つの第３ハッシュ値が一致すると判定した場合には、Ｓ１１１７に示した処理に移る。
【０１１９】
Ｓ１１１７乃至Ｓ１１２５に示した処理は、図１１Ｂの場合と同様である。検索処理（Ｃ）を終えると、呼び出し元のメイン処理に復帰する。
【０１２０】
本実施の形態によれば、第２ハッシュ値に関する衝突が生じる場合にキーを読み取らずに済むので、当該衝突の対処が早くなる。
【０１２１】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上述の機能ブロック構成はプログラムモジュール構成に一致しない場合もある。
【０１２２】
また、上で説明した各記憶領域の構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ、処理の順番を入れ替えることや複数の処理を並列に実行させるようにしても良い。
【０１２３】
なお、上で述べたデータ保存装置１００は、コンピュータ装置であって、図１８に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１２４】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１２５】
本実施の形態に係る情報処理装置は、（Ａ）第１メモリデバイス又は第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、キーの第１識別子を加える追加部と、（Ｂ）検索キーに基づいて値を検索する場合に、当該検索キーと同族のキーに係るリストにおいて当該検索キーの第１識別子と紐付けられたエントリから値を取得する取得部とを有する。
【０１２６】
このようにすれば、複数種類のメモリデバイスを併用してデータを保存する装置において、ハッシュテーブルにおける衝突の対処が早くなる。
【０１２７】
更に、第１識別子は、第１ハッシュ値の算出に用いられたハッシュ関数と異なるハッシュ関数によって算出される第２ハッシュ値であってもよい。
【０１２８】
このようにすれば、第２ハッシュ値を用いるので、第１メモリデバイスの領域を圧迫し難い。
【０１２９】
更に、検索キーに基づいて値を検索した場合に、リストにおける検索キーの第１識別子の順位を上位方向に変更する変更部を有するようにしてもよい。
【０１３０】
このようにすれば、時間的局所性の面から、検索された値の再検索を行う処理が速くなる。
【０１３１】
更に、第１メモリデバイスに新たなエントリを格納する領域が足りない場合に、第１メモリデバイスに格納されているエントリを第２メモリデバイスに移す移動部を有するようにしてもよい。
【０１３２】
このようにすれば、時間的局所性の面から、最近登録されたエントリに係る値を検索する場合の処理が速くなる。
【０１３３】
更に、上記追加部は、リストに第１識別子を加える際に、リストに更にキーの第２識別子を加えるようにしてもよい。そして、上記取得部は、リストにおいて検索キーの第１識別子及び検索キーの第２識別子と紐付けられたエントリから値を取得するようにしてもよい。
【０１３４】
このようにすれば、第１識別子に関する衝突が生じる場合に、当該衝突の対処が早くなる。
【０１３５】
更に、上記取得部は、検索キーの第１識別子と紐付けられたエントリに含まれるキーが検索キーと一致するか否かを判定するようにしてもよい。
【０１３６】
このようにすれば、衝突の対処がより確実になる。
【０１３７】
なお、上で述べたデータ保存装置１００の処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納されるようにしてもよい。尚、中間的な処理結果は、一般的にメインメモリ等の記憶装置に一時保管される。
【０１３８】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１３９】
（付記１）
第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加える追加部と、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する取得部と
を有する情報処理装置。
【０１４０】
（付記２）
前記第１識別子は、前記第１ハッシュ値の算出に用いられたハッシュ関数と異なるハッシュ関数によって算出される第２ハッシュ値である
付記１記載の情報処理装置。
【０１４１】
（付記３）
更に、
前記検索キーに基づいて前記値を検索した場合に、前記リストにおける当該検索キーの前記第１識別子の順位を上位方向に変更する変更部
を有する付記１又は２記載の情報処理装置。
【０１４２】
（付記４）
更に、
前記第１メモリデバイスに新たなエントリを格納する領域が足りない場合に、前記第１メモリデバイスに格納されているエントリを前記第２メモリデバイスに移す移動部
を有する付記１乃至３のいずれか１つ記載の情報処理装置。
【０１４３】
（付記５）
前記追加部は、前記リストに前記第１識別子を加える際に、前記リストに更に前記キーの第２識別子を加え、
前記取得部は、前記リストにおいて前記検索キーの前記第１識別子及び前記検索キーの第２識別子と紐付けられた前記エントリから前記値を取得する
付記１乃至４のいずれか１つ記載の情報処理装置。
【０１４４】
（付記６）
前記取得部は、前記検索キーの第１識別子と紐付けられた前記エントリに含まれるキーが前記検索キーと一致するか否かを判定する
付記１乃至４のいずれか１つ記載の情報処理装置。
【０１４５】
（付記７）
前記第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加え、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する
処理を含み、コンピュータにより実行される情報処理方法。
【０１４６】
（付記８）
第１メモリデバイス又は前記第１メモリデバイスよりもレイテンシが大きい第２メモリデバイスに、キー及び値を含むエントリを格納する際に、第１ハッシュ値を用いるハッシュテーブルにおける同族キー毎に前記第１メモリデバイスに設けられたリストに、当該エントリと紐付けられた、前記キーの第１識別子を加え、
検索キーに基づいて前記値を検索する場合に、当該検索キーと同族のキーに係る前記リストにおいて当該検索キーの第１識別子と紐付けられた前記エントリから前記値を取得する
処理をコンピュータに実行させるプログラム。
【符号の説明】
【０１４７】
１００  データ保存装置    １０１  ＣＰＵ
１０３  ＤＲＡＭ制御回路    １０５  ＤＲＡＭ
１０７  ＮＶＲＡＭ制御回路    １０９  ＮＶＲＡＭ
１１１  通信制御回路    ２０１  ハッシュテーブル記憶部
２０３  リンクリスト記憶部    ２０５  第１エントリ記憶部
２０７  第２エントリ記憶部    ６０１  受付部
６０３  返答部    ６０５  登録部
６０７  設定部    ６０９  追加部
６１１  検索部    ６１３  探索部
６１５  取得部    ６１７  第１算出部
６１９  第２算出部    ６２１  変更部
６２２  移動部    ６２３  第３算出部
【図１】
2018116541.tif 000003
【図２】
2018116541.tif 000004
【図３Ａ】
2018116541.tif 000005
【図３Ｂ】
2018116541.tif 000006
【図４Ａ】
2018116541.tif 000007
【図４Ｂ】
2018116541.tif 000008
【図５Ａ】
2018116541.tif 000009
【図５Ｂ】
2018116541.tif 000010
【図６】
2018116541.tif 000011
【図７】
2018116541.tif 000012
【図８】
2018116541.tif 000013
【図９】
2018116541.tif 000014
【図１０】
2018116541.tif 000015
【図１１Ａ】
2018116541.tif 000016
【図１１Ｂ】
2018116541.tif 000017
【図１２Ａ】
2018116541.tif 000018
【図１２Ｂ】
2018116541.tif 000019
【図１３】
2018116541.tif 000020
【図１４】
2018116541.tif 000021
【図１５】
2018116541.tif 000022
【図１６】
2018116541.tif 000023
【図１７Ａ】
2018116541.tif 000024
【図１７Ｂ】
2018116541.tif 000025
【図１８】
2018116541.tif 000026