(57)【特許請求の範囲】
【請求項１】
ハッシュ値を計算する方法であって、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することを可能にし、ここで、入力キーはＬビットであり、ハッシュ値はＮビットであり、且つ、Ｎ≦Ｌであり、前記方法は、コンピュータが、生成された或る１つのハッシュ関数の計算を、
事前に生成された所定の乱数列に基づいて、前記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択するステップと、
事前に生成された所定の乱数列に基づいて、前記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある複数個のビットを選択するステップと、
前記１個のビットを選択するステップで選択された前記１個のビットと、前記複数個のビットを選択するステップで選択された前記複数個のビットとについて、全ビットの排他的論理和を計算するステップと、
当該計算された排他的論理和を前記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てるステップと、
前記１個のビットを選択するステップにおいて前記下位Ｎビットのうちのまだ選択されていないビットに対して、前記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、前記１個のビットを選択するステップ、前記複数個のビットを選択するステップ、前記計算するステップ及び前記割り当てるステップを繰り返すステップと
を含む、前記方法。
【請求項２】
前記複数個のビットを選択するステップが、
前記複数個のビットを選択する場合に、前記入力キーの上位Ｌ−Ｎビットのうちの２つ以上の異なる位置から複数個のビットを選択するステップ、又は、
前記複数個のビットを選択する場合に、前記入力キーの上位Ｌ−Ｎビットのうちの全て異なる位置から複数個のビットを選択するステップ
を含む、請求項１に記載の方法。
【請求項３】
前記繰り返すステップにおいて、前記複数個のビットを選択するステップを繰り返す場合に、当該複数個のビットを選択するステップが、
前記入力キーの上位Ｌ−Ｎビットのうちの先に選択された位置と異なる位置のビットを選択するステップ
を含む、請求項１又は２に記載の方法。
【請求項４】
前記繰り返すステップにおいて、前記複数個のビットを選択するステップを繰り返す場合に、当該複数個のビットを選択するステップが、
前記入力キーの上位Ｌ−Ｎビットを均等に分けた個数のビットを選択するステップであって、前記均等に分けた個数は前記複数個のビットを選択するステップが最初に実行されたときに選択されたビットの個数である、前記選択するステップ
を含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れる場合には、（Ｌ−Ｎ）／Ｎ個である、請求項４に記載の方法。
【請求項６】
前記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れない場合には、［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個であり、ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数である、請求項４に記載の方法。
【請求項７】
前記上位Ｌ−Ｎビットが同一の２Ｎ個のキー  ｛２Ｎ×ａ，２Ｎ×ａ＋１，２Ｎ×ａ＋２，．．． ，２Ｎ×（ａ＋１）−１｝  （ａは非負整数である）である、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記入力キーがランダム・キーである、請求項１〜６のいずれか一項に記載の方法。
【請求項９】
前記割り当てるステップにおいて、排他的論理和の計算値を求めるステップが、
入力キーｋのハッシュ値の下位からｒビット目ｈ（ｋ，ｒ）を、入力キーｋの下位からｐビット目を返す関数ｂ（ｋ、ｐ）のｐに前記乱数列を代入して計算するステップを含む、
請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記コンピュータが、
空の記憶領域を用意するステップ
をさらに実行することを含み、
前記１個のビットを選択するステップが、当該１個のビットを選択するステップで選択した前記１個のビットを前記記憶領域に追加するステップをさらに含み、
前記複数個のビットを選択するステップが、当該複数個のビットを選択するステップで選択した前記複数個のビットを前記記憶領域に追加するステップをさらに含む、
請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記１個のビットを選択するステップが前記複数個のビットを選択するステップと並列して実行され、前記１個のビットを選択するステップが前記複数個のビットを選択するステップよりも先に実行され、又は、前記複数個のビットを選択するステップが前記１個のビットを選択するステップよりも先に実行される、請求項１〜９のいずれか一項に記載の方法。
【請求項１２】
前記生成したハッシュ関数の複数からなるハッシュ関数群が、ユニバーサル・ハッシング（Universal Hashing）として使用される、又はマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用される、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
前記生成した１つのハッシュ関数が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力するステップ
を含む、請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
前記コンピュータが、
ハッシュテーブルを用意するステップと、
前記生成したハッシュ関数の１つに、又はその複数からなるハッシュ関数群に基づいて前記ハッシュテーブル内のデータへアクセスするステップと、
をさらに実行することを含む、請求項１〜１３のいずれか一項に記載の方法。
【請求項１５】
前記コンピュータが、
ハッシュテーブルを、ＦＰＧＡ（Field Programmable Gate Array）内のメモリ・ブロック上に用意するステップ
をさらに実行することを含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１６】
ハッシュ値を計算する為のコンピュータであって、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することを可能にし、ここで、入力キーはＬビットであり、ハッシュ値はＮビットであり、且つ、Ｎ≦Ｌであり、前記コンピュータが、生成された或る１つのハッシュ関数の計算をする為に、
ビット選択手段が、事前に生成された所定の乱数列に基づいて、前記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択し、
前記ビット選択手段が、事前に生成された所定の乱数列に基づいて、前記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある複数個のビットを選択し、
ビット割当手段が、前記選択された前記１個のビットを、前記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当て、
前記ビット割当手段が、前記下位Ｎビットから選択された前記１個のビットと、前記上位Ｌ−Ｎビットから選択された前記複数個のビットとについて、全ビットの排他的論理和を計算し、当該計算された排他的論理和を前記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当て、
前記１個のビットを選択することにおいて前記下位Ｎビットのうちのまだ選択されていないビットに対して、前記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、前記ビット選択手段が、前記１個のビットを選択すること及び複数個のビットを選択すること、並びに、前記ビット割当手段が、前記計算すること及び前記割り当てることを繰り返す、
前記コンピュータ。
【請求項１７】
ハッシュ値を計算する為のコンピュータ・プログラムであって、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することを可能にし、ここで、入力キーはＬビットであり、ハッシュ値はＮビットであり、且つ、Ｎ≦Ｌであり、生成された或る１つのハッシュ関数の計算をする為に、コンピュータに、請求項１〜１５のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値の計算技法であり、特には、ビットを選択する位置を変更することで、ハッシュ関数を１つ以上、特に複数生成することが可能なハッシュ値を計算する技法に関する。
【背景技術】
【０００２】
ハッシュテーブルに、空間効率良くキーを格納する手法として、異なるハッシュ関数を用いてハッシュテーブルを分割するマルチレベル・ハッシュテーブル（Multi-level hash table：ＭＨＴ）と呼ばれる手法が知られている（下記非特許文献１及び２を参照）。
【０００３】
下記特許文献１は、２種類のハッシュ関数を用いて、入力された固定長データの第１及び第２のハッシュ値を求めるハッシュ演算手段と、Ｎ（Ｎは２以上の整数）個のメモリバンクから成り、多数の固定長データが保持されるデータ・テーブルを格納するデータ・テーブル・メモリと、各固定長データの格納先のメモリアドレスが、前記第１のハッシュ値をインデックスとして保持される主メモリ・ポインタ・テーブル、及び、各固定長データの格納先のメモリアドレスが、前記第２のハッシュ値をインデックスとして保持される副メモリ・ポインタ・テーブルを格納するポインタ・テーブル・メモリと、前記Ｎ個のメモリバンクの同一メモリアドレスに格納されている複数の固定長データと、前記ハッシュ演算手段に入力された一つの固定長データとを同時に比較し、比較結果を出力する比較手段と、を備える固定長データ検索装置を記載する（請求項７）。
【０００４】
下記特許文献２は、２つのタグ・メモリ・アドレスが、２つの異なるハッシュ関数により同時に計算されること：第１及び第２のハッシュ関数６４及び６６は、各々、引き数として主メモリ・アドレス６０を受け取り、「０」から「ｎ−１」までの範囲のタグ・メモリ・アドレスについての値を返すこと、ここで、ｎは、キャッシュ・エントリの数であること：第１のハッシュ関数６４及び第２のハッシュ関数６６は、第１のハッシュ関数６４であるＦ１（ｖ）がいずれかの引き数ｖに対して値ｉを返し、第２のハッシュ関数６６であるＦ２（ｖ）がいずれかの引き数ｖに対して値ｊを返し、そして所与のビット値に関してｉとｊとが常に異なるように選ばれること：この例では、ビット１０が、値ｉと値ｊとの間で異なるビットとして選択されていること：このようなｉとｊとの間で値が異なるようなビットは、制御ビットとして用いることができることを記載する（段落００２５）。
【０００５】
下記特許文献３は、ハッシュ値計算に使用する係数の値を変化させて、最もハッシュ値の偏りの少ない係数を求めることにより検索効率・メモリ使用効率の良いハッシュテーブルを生成することを特徴とするハッシュテーブル生成方法を記載する（請求項１）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２２９１６３号公報
【特許文献２】特開平８−２３５０６０号公報
【特許文献３】特開平７−１６８８４１号公報
【非特許文献】
【０００７】
【非特許文献１】Andrei Z. Broder et. al., "Multilevel Adaptive Hashing", SODA'90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pp. 43-53, January 1990
【非特許文献２】Adam Kirsch et. al., "The Power of One Move: Hashing Schemesfor Hardware", IEEE/ACM Transactions on Networking (TON), Vol. 18, No. 6, December 2010＜URL:http://www.eecs.harvard.edu/~michaelm/postscripts/infocom_hardware_submit.pdf＞から入手可能
【非特許文献３】Udit Dhawan et. al., "Area-Efficient Near-Associative Memories on FPGAs", FPGA 2013 Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, pp. 191-200, February 2013
【非特許文献４】「3. TriMatrix Embedded Memory Blocks in Stratix IV Devices」, ALTERA（登録商標）＜URL:http://www.altera.com/literature/hb/stratix-iv/stx4_siv51003.pdf＞から入手可能
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＦＰＧＡ（Field Programmable Gate Array）は、半導体の製造工程ではなく、機器の生産ラインや現地で（＝field）、内部を書き換え可能な（＝programmable）、論理回路（＝logic gate）が多数配列（＝array）された半導体デバイスである。ＦＰＧＡ上にハッシュテーブル（「アソシエイティブ・メモリ」とも呼ばれる）を構築することが出来れば、ＦＰＧＡの並列計算能力を活用した高スループットの処理においてハッシュテーブルが利用可能になる。
【０００９】
ところが、ＦＰＧＡの内部メモリは、小容量のメモリ・ブロックが数多く配置された構成となっており、その細分化されたメモリ機構を使って、メモリ空間効率の良いハッシュテーブルを実現する方法が課題となる。ハッシュテーブルは一般に、入力されるキーの偏りによって使用されないメモリ領域が発生する。限られた容量のＦＰＧＡの内部メモリを有効活用するために、入力されるキーの偏りや、連番キーかランダム・キーかといった性質を利用しようにも、入力されるキーの性質が事前に分からない場合がある。また当該キーの性質が分かったとしても、その性質に合わせてハッシュテーブルのメモリ使用効率を最適化する為にはＦＰＧＡの回路の変更が必要であり、特に回路動作中の最適化は困難である。
【００１０】
ハッシュテーブルに空間効率良くキーを格納する手法として、マルチレベル・ハッシュテーブル（ＭＨＴ）と呼ばれる手法が知られている。しかしながら、ＦＰＧＡにマルチレベル・ハッシュテーブルを実装するには以下に述べる課題がある：
（１）千個を超える膨大なメモリ・ブロック毎に、異なるハッシュ関数が必要である；及び、
（２）スループット向上のためにハッシュ関数を１クロックで計算出来ることが望ましく、そのために乗算のような複雑な演算は避ける必要がある。
【００１１】
ハッシュ関数を多く生成するユニバーサル・ハッシング（Universal Hashing）と呼ばれる枠組みが知られている。しかしながら、ユニバーサル・ハッシングを含む既存のハッシュ関数は乗算や剰余演算があり、ＦＰＧＡに適さない。また、ＦＰＧＡはデジタル・シグナル・プロセッサ（ＤＳＰ）を搭載しているが、１クロックで乗算や剰余演算が終了しないうえ、ＤＳＰの搭載数はメモリ・ブロックの数よりも大幅に少なく、メモリ・ブロック毎に異なるハッシュ関数を利用するという要求を満たせない。
【００１２】
また、非特許文献３では、近似的なアソシエイティブ・メモリ（ハッシュテーブル）をＦＰＧＡ上に実装している。しかしながら、非特許文献３では近似的なデータ格納方法を利用している為に正しいデータ検索を出来ない場合がある。そのために、正確性が求められている場合には、非特許文献３のアソシエイティブ・メモリを使用することができない。
【００１３】
ハッシング方法として、局所性鋭敏型ハッシング（Locality Sensitive Hashing；ＬＳＨ）が知られている。ＬＳＨでは、近いデータが近いハッシュ値になる。しかしながら、ＬＳＨは、出力し得るハッシュ値の全パターンの出現を保証するものでない。
【００１４】
従って、本発明は、上記課題を解決するとともに、また、ＦＰＧＡに限定されること無しに、ハッシュテーブルに空間効率良くキーを格納する為に使用するハッシュ関数群（生成された一つのハッシュ関数を複数集めたものである）を生成することを可能にするハッシュ値計算技法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明は、ハッシュ値を計算する技法を提供し、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することを可能にする技法を提供する。当該技法は、上記ハッシュ値を計算する方法、並びに、上記ハッシュ値を計算する為のコンピュータ、そのコンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。
【００１６】
（本発明に従う第１の態様）
【００１７】
本発明に従う第１の態様において、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することが可能なハッシュ値を計算する方法は、コンピュータが、生成された或る１つのハッシュ関数の計算を、
上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択するステップと、
上記選択された上記１個のビットを、上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てるステップと、
上記選択するステップにおいて上記下位Ｎビットのうちのまだ選択されていないビットに対して、上記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、上記選択するステップ及び上記割り当てるステップを繰り返すステップと
を実行することによって行うことを含む。ここで、入力キーはＬビットであり、ハッシュ値はＮビットであり、且つ、Ｎ≦Ｌである。
【００１８】
本発明の一つの実施態様において、上記コンピュータが、
上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択するステップ
をさらに実行することを含みうる。
この場合に、上記ビットを割り当てるステップが、
上記１個のビットを選択するステップで選択された上記１個のビットと、上記１又は複数個のビットを選択するステップで選択された上記１又は複数個のビットとについて、全ビットの排他的論理和の計算値を求め、当該計算値を上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てるステップ
を含みうる。
また、この場合に、上記繰り返すステップが、
上記１個のビットを選択するステップにおいて上記下位Ｎビットのうちのまだ選択されていないビットに対して、上記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、上記１個のビットを選択するステップ、上記１又は複数個のビットを選択するステップ、及び上記ビットを割り当てるステップを繰り返すステップ
を含みうる。
【００１９】
本発明の一つの実施態様において、上記１又は複数個のビットを選択するステップが、
上記複数個のビットを選択する場合に、上記入力キーの上位Ｌ−Ｎビットのうちの２つ以上の異なる位置から複数個のビットを選択するステップ、又は、
上記複数個のビットを選択する場合に、上記入力キーの上位Ｌ−Ｎビットのうちの全て異なる位置から複数個のビットを選択するステップ
を含みうる。
【００２０】
本発明の一つの実施態様において、上記繰り返すステップにおいて、上記１又は複数個のビットを選択するステップを繰り返す場合に、当該１又は複数個のビットを選択するステップが、
上記入力キーの上位Ｌ−Ｎビットのうちの先に選択された位置と異なる位置のビットを選択するステップ
を含みうる。
【００２１】
本発明の一つの実施態様において、上記繰り返すステップにおいて、上記１又は複数個のビットを選択するステップを繰り返す場合に、当該１又は複数個のビットを選択するステップが、
上記入力キーの上位Ｌ−Ｎビットを均等に分けた個数のビットを選択するステップであって、上記均等に分けた個数は上記１又は複数個のビットを選択するステップが最初に実行されたときに選択されたビットの個数である、上記選択するステップ
を含みうる。
【００２２】
本発明の一つの実施態様において、上記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れる場合には、（Ｌ−Ｎ）／Ｎ個でありうる。
【００２３】
本発明の一つの実施態様において、上記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れない場合には、［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個であり、ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数でありうる。
【００２４】
本発明の一つの実施態様において、上記上位Ｌ−Ｎビットが同一の２Ｎ個のキー  ｛２Ｎ×ａ，２Ｎ×ａ＋１，２Ｎ×ａ＋２，．．． ，２Ｎ×（ａ＋１）−１｝  （ａは非負整数である）でありうる。
【００２５】
本発明の一つの実施態様において、上記入力キーがランダム・キーでありうる。
【００２６】
本発明の一つの実施態様において、上記１個のビットを選択するステップが、事前に生成された所定の乱数列に基づいて、上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択するステップを含みうる。また、本発明の一つの実施態様において、上記１又は複数個のビットを選択するステップが、事前に生成された所定の乱数列に基づいて、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択するステップを含みうる。
【００２７】
本発明の一つの実施態様において、上記割り当てるステップにおいて、排他的論理和の計算値を求めるステップが、入力キーｋのハッシュ値の下位からｒビット目ｈ（ｋ，ｒ）を、入力キーｋの下位からｐビット目を返す関数ｂ（ｋ、ｐ）のｐに上記乱数列を代入して計算するステップを含みうる。
【００２８】
本発明の一つの実施態様において、上記コンピュータが、空の記憶領域を用意するステップを実行することをさらに含みうる。この場合に、上記１個のビットを選択するステップが、当該１個のビットを選択するステップで選択した上記１個のビットを上記記憶領域に追加するステップをさらにみうる。また、この場合に、上記１又は複数個のビットを選択するステップが、当該１又は複数個のビットを選択するステップで選択した上記１又は複数個のビットを上記記憶領域に追加するステップをさらに含みうる。
【００２９】
本発明の一つの実施態様において、上記１個のビットを選択するステップが上記１又は複数個のビットを選択するステップと並列して実行され、上記１個のビットを選択するステップが上記１又は複数個のビットを選択するステップよりも先に実行され、又は、上記１又は複数個のビットを選択するステップが上記１個のビットを選択するステップよりも先に実行されうる。
【００３０】
本発明の一つの実施態様において、上記生成したハッシュ関数の複数からなるハッシュ関数群が、ユニバーサル・ハッシングとして使用されうる、又はマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用されうる。
【００３１】
本発明の一つの実施態様において、上記生成した１つのハッシュ関数が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）が出力するステップを含みうる。
【００３２】
本発明の一つの実施態様において、上記コンピュータが、
ハッシュテーブルを用意するステップと、
上記生成したハッシュ関数の１つに、又はその複数からなるハッシュ関数群に基づいてデータを上記ハッシュテーブル内のデータへアクセスするステップと
をさらに実行することを含みうる。
【００３３】
本発明の一つの実施態様において、上記コンピュータが、ハッシュテーブルを、ＦＰＧＡ内のメモリ・ブロック上に用意するステップをさらに実行しうる。
【００３４】
（本発明に従う第２の態様）
【００３５】
本発明に従う第２の態様において、ハッシュ値を計算する為のコンピュータであって、ビットを選択する所定位置を変更することでハッシュ関数を１つ以上生成することを可能にし、上記コンピュータが、生成された或る１つのハッシュ関数の計算をする為に、
上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択するビット選択手段と、
上記選択された上記１個のビットを、上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てるビット割当手段と
を備えており、
上記コンピュータは、上記下位Ｎビットのうちのまだ選択されていないビットに対して、上記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、上記ビット選択手段が、上記入力キーの下位Ｎビットのうちの上記まだ選択されていないビットのうちの或る所定位置にある１個のビットを選択すること、及び、上記ビット割当手段が、上記選択された上記１個のビットを、上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てることを繰り返しうる。ここで、入力キーはＬビットであり、ハッシュ値はＮビットであり、且つ、Ｎ≦Ｌである。
【００３６】
上記ビット選択手段がさらに、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択し、
上記ビット割当手段が、上記下位Ｎビットから選択された上記１個のビットと、上記上位Ｌ−Ｎビットから選択された上記１又は複数個のビットとについて、全ビットの排他的論理和の計算値を求め、当該計算値を上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当て、
上記下位Ｎビットのうちのまだ選択されていないビットに対して、上記ハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまで、上記ビット選択手段が、上記入力キーの下位Ｎビットのうちの上記まだ選択されていないビットのうちの或る所定位置にある１個のビットを選択すること、及び、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択すること、並びに、上記ビット割当手段が、上記下位Ｎビットから選択された上記１個のビットと、上記上位Ｌ−Ｎビットから選択された上記１又は複数個のビットとについて、全ビットの排他的論理和の計算値を求め、当該計算値を上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てることを繰り返しうる。
【００３７】
本発明の一つの実施態様において、上記ビット選択手段が、
上記入力キーの上位Ｌ−Ｎビットのうちの複数個のビットを選択する場合に、上記入力キーの上位Ｌ−Ｎビットのうちの２つ以上の異なる位置から複数個のビットを選択し、又は、
上記入力キーの上位Ｌ−Ｎビットのうちの複数個のビットを選択する場合に、上記入力キーの上位Ｌ−Ｎビットのうちの全て異なる位置から複数個のビットを選択しうる。
【００３８】
本発明の一つの実施態様において、上記繰り返しにおいて、上記ビット選択手段が、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することを繰り返す場合に、上記入力キーの上位Ｌ−Ｎビットのうちの先に選択された位置と異なる位置のビットを選択しうる。
【００３９】
本発明の一つの実施態様において、上記繰り返しにおいて、上記ビット選択手段が、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することを繰り返す場合に、上記入力キーの上位Ｌ−Ｎビットを均等に分けた個数のビットを選択しうる。ここで、上記均等に分けた個数は、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することが最初に実行されたときに選択されたビットの個数である。
【００４０】
本発明の一つの実施態様において、上記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れる場合には、（Ｌ−Ｎ）／Ｎ個でありうる。
【００４１】
本発明の一つの実施態様において、上記均等に分けた個数が、（Ｌ−Ｎ）がＮで割り切れない場合には、［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個であり、ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数でありうる。
【００４２】
本発明の一つの実施態様において、上記上位Ｌ−Ｎビットが同一の２Ｎ個のキー  ｛２Ｎ×ａ，２Ｎ×ａ＋１，２Ｎ×ａ＋２，．．． ，２Ｎ×（ａ＋１）−１｝  （ａは非負整数である）でありうる。
【００４３】
本発明の一つの実施態様において、上記入力キーがランダム・キーでありうる。
【００４４】
本発明の一つの実施態様において、上記ビット選択手段が、事前に生成された所定の乱数列に基づいて、上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択しうる。また、本発明の一つの実施態様において、上記ビット選択手段が、事前に生成された所定の乱数列に基づいて、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択しうる。
【００４５】
本発明の一つの実施態様において、上記ビット割当手段が、入力キーｋのハッシュ値の下位からｒビット目ｈ（ｋ，ｒ）を、入力キーｋの下位からｐビット目を返す関数ｂ（ｋ、ｐ）のｐに上記乱数列を代入して計算して、上記排他的論理和の計算値を求めうる。
【００４６】
本発明の一つの実施態様において、上記ビット選択手段がさらに、空の記憶領域を用意し、上記入力キーの下位Ｎビットのうちの或る所定位置にある選択した１個のビットを上記記憶領域に追加し、且つ、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある選択した１又は複数個のビットを上記記憶領域に追加しうる。
【００４７】
本発明の一つの実施態様において、上記ビット選択手段が、上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択することを上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することと並列して実行し、又は、上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択することを上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することよりも先に実行し、又は、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択することを上記入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択することよりも先に実行しうる。
【００４８】
本発明の一つの実施態様において、上記生成したハッシュ関数の複数からなるハッシュ関数群が、ユニバーサル・ハッシングとして使用されうる、又はマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用されうる。
【００４９】
本発明の一つの実施態様において、上記生成した１つのハッシュ関数が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力しうる。
【００５０】
本発明の一つの実施態様において、コンピュータが、ハッシュテーブルを用意し、上記生成したハッシュ関数の１つに、又はその複数からなるハッシュ関数群に基づいて上記ハッシュテーブル内のデータへアクセスしうる。
【００５１】
本発明の一つの実施態様において、コンピュータが、ハッシュテーブルを、ＦＰＧＡ内のメモリ・ブロック上に用意しうる。
【００５２】
（本発明に従う第３の態様）
【００５３】
本発明に従う第３の態様において、コンピュータ・プログラム及びコンピュータ・プログラム製品は、生成された或る１つのハッシュ関数の計算をする為に、上記コンピュータに、本発明に従う上記第１の態様の方法の各ステップを実行させる。
【００５４】
本発明の実施態様に従うコンピュータ・プログラムはそれぞれ、一つ又は複数のフレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システム、例えばコンピュータからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、本発明の実施態様に従うコンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明の実施態様に従うコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。本発明の実施態様に従うコンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００５５】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００５６】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００５７】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行として、上記コンピュータ・プログラムをインストールされたコンピュータにおける当該コンピュータ・プログラムの実行が典型的な例として挙げられる。かかる場合、当該コンピュータ・プログラムが当該コンピュータのメモリにロードされて実行されることにより、当該コンピュータ・プログラムは、当該コンピュータを制御し、本発明にかかる処理を実行させる。当該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、当該コンピュータが特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換及び、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、実行することを可能にするものである。
【発明の効果】
【００５８】
本発明の実施態様に従い、入力ビットがＬビットであり且つ生成するハッシュ値がＮビットである場合に本発明の実施態様において生成されたハッシュ関数は、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力するという性質を有する。ハッシュ値の算出において排他的論理和を計算する際のビットの選択を変更することによって、上記性質を満たした多くのハッシュ関数を生成することを可能にする。
【００５９】
本発明の実施態様に従い生成されたハッシュ関数群をマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用する場合に、出力し得るハッシュ値の全て（２Ｎ個）が出現するという性質を利用すると、連続キーを入力した場合、当該メモリの使用効率は１００％になる。すなわち、ＭＨＴが溢れたとき、全てのスロットが埋まっていることになり、メモリ空間が無駄になることを防ぐことを可能にする。
【００６０】
また、本発明の実施態様に従い生成されたハッシュ関数群は、入力キーが連続キーである場合には、従来のハッシュ関数よりも遙かに良い性能を発揮し、入力キーがランダム・キーである場合にも、従来のハッシュ関数と同等な性能を発揮する。
【００６１】
また、本発明の実施態様に従うと、例えばＦＰＧＡ又は専用ハードウェアである場合には１クロック内にハッシュ値の計算を完了することが可能になる。
【００６２】
また、本発明の実施態様に従うと、出力し得るハッシュ値の全て（２Ｎ個）が出現するという性質を利用すると、当該ハッシュ値をメモリ・ブロックのリセットの為に使用出来る。例えば、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を本発明のハッシュ関数に入力する間、出力されたハッシュ値をメモリ・ブロックのアドレスとし、同時にデータとしてゼロを入力すれば、メモリ・ブロック上の全データ（２Ｎ個）のゼロクリアが実現できる。既存のハッシュ関数の場合、出力し得るハッシュ値の全てが出現するとは限らないため、ハッシュ値をそのままリセットのアドレスに利用することはできず、リセット時に専用の回路が必要になる。本発明の実施態様に従った当該ハッシュ値をメモリ・ブロックのリセットの為に使用することによって、メモリ・ブロックのリセットの為の回路を簡略化することが可能である。
【００６３】
また、本発明の実施態様に従い生成されたハッシュ関数群をＭＨＴにおいて使用することが可能である。
【００６４】
また、本発明の実施態様に従い生成されたハッシュ関数群をユニバーサル・ハッシングの目的として使用することが可能である。
【図面の簡単な説明】
【００６５】
【図１Ａ】本発明の実施態様において使用されうるコンピュータ又は本発明の実施態様に従うコンピュータの一例を示した図である。
【図１Ｂ】本発明の実施態様において使用されうるコンピュータ又は本発明の実施態様に従うコンピュータの一例であって、当該コンピュータ上で１又は複数の仮想マシンを稼働させる場合を示した図である。
【図２Ａ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｂ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｃ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｄ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｅ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｆ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図２Ｇ】本発明の実施態様に従い、所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。
【図３Ａ】本発明の実施態様に従い生成されたハッシュ関数群が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力するダイアグラムを示す。
【図３Ｂ】本発明の実施態様に従い生成されたハッシュ関数群が、ランダム・キーを入力することに応じて、ハッシュ値（重複する可能性がある）を出力するダイアグラムを示す。
【図４】本発明の実施態様に従い生成されうるハッシュ関数を作成する動作の一例を示す。
【図５Ａ】本発明の実施態様に従い、生成したハッシュ関数群をマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用するダイアグラムを示す。
【図５Ｂ】マルチレベル・ハッシュ・テーブル（ＭＨＴ）の概念図のダイアグラムを示す。
【図６】本発明の実施態様に従い生成されたハッシュ関数群が、出力し得るハッシュ値の全て（２Ｎ個）を出力するという性質を利用して、メモリ・ブロックをゼロクリアする際のメモリ・アドレスとしてそのハッシュ値を使用するダイアグラムを示す。
【図７】本発明の実施態様に従い、ハッシュテーブルをＦＰＧＡ内のメモリ・ブロック上に用意するダイアグラムを示す。
【図８Ａ】本発明の実施態様に従い、ハッシュ値の一つを生成する処理のフローチャートを示す。
【図８Ｂ】本発明の実施態様に従い、ハッシュ値の一つを生成する処理のフローチャートを示す。
【図９】本発明の実施態様に従い生成されるハッシュ関数の１つ又はその複数からなるハッシュ関数群に基づいて、ハッシュテーブル内のデータへアクセスするダイアグラムを示す。
【図１０】図１Ａ又は図１Ｂに従うハードウェア構成を好ましくは備えており、図８Ａ〜図８Ｂそれぞれに示すフローチャートに従って本発明の実施態様を実施するコンピュータの機能ブロック図の一例を示す図である。
【図１１】本発明の実施態様に従い、生成したハッシュ関数群をマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用した場合の使用されたメモリ・ブロック数の変化を示す。
【発明を実施するための形態】
【００６６】
本発明の実施形態を、以下に図面に従って説明する。以下の図面を通して、特に断らない限り、同一の符号は同一の対象を指す。本発明の実施形態は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。
【００６７】
図１Ａは、本発明の実施態様において使用されうるコンピュータ又は本発明の実施態様に従うコンピュータの一例を示した図である。当該コンピュータは例えば、１又は複数のコンピュータ、例えばサーバ・コンピュータ（例えば、サーバ機能を備えているコンピュータ）でありうるが、これらに制限されるものではない。
【００６８】
コンピュータ（１０１）は、１又は複数のＣＰＵ（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続されている。ＣＰＵ（１０２）は例えば、３２ビット又は６４ビットのアーキテクチャに基づくものである。当該ＣＰＵ（１０２）は例えば、インターナショナル・ビジネス・マシーンズ・コーポレーションのＰｏｗｅｒ（商標）シリーズ、インテル社のＸｅｏｎ（登録商標）シリーズ、Ｃｏｒｅ（商標）  ｉシリーズ、Ｃｏｒｅ（商標）  ２シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ若しくはＡｔｏｍ（商標）シリーズ、又は、ＡＭＤ（Advanced Micro Devices）社のＯｐｔｅｒｏｎ（商標）シリーズ、Ａシリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（登録商標）シリーズ若しくはＳｅｍｐｒｏｎ（商標）でありうる。
【００６９】
バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。また、液晶ディスプレイ（ＬＣＤ）は例えば、タッチパネル・ディスプレイ又はフローティング・タッチ・ディスプレイであってもよい。ディスプレイ（１０６）は、コンピュータ（１０１）上で動作中のソフトウェア（例えば、本発明の実施態様に従うコンピュータ・プログラム又は当該コンピュータ（１０１）上で動作中の任意の各種コンピュータ・プログラム）が稼働することによって表示されるオブジェクトを、適当なグラフィック・インタフェースで表示するために使用されうる。また、ディスプレイ（１０６）は例えば、ウェブ・ブラウザ・アプリケーションの画面を出力しうる。
【００７０】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ディスク（１０８）、例えばハードディスク又はソリッド・ステート・ドライブ（ＳＳＤ）が接続されうる。
【００７１】
バス（１０４）には任意的に、例えばＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。
【００７２】
バス（１０４）には、周辺装置コントローラ（１１０）を介して、例えばキーボード・マウス・コントローラ又はＵＳＢバスを介して、任意的に、キーボード（１１１）及びマウス（１１２）が接続されうる。
【００７３】
ディスク（１０８）には、オペレーティング・システム、例えばメインフレーム用に開発されたオペレーティング・システム（例えば、ｚ／ＯＳ、ｚ／ＶＭ、若しくはｚ／ＶＳＥ）、Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標）、ＭａｃＯＳ（登録商標）、及びＡｎｄｒｏｉｄ（登録商標）、並びにＪ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、本発明の実施態様に従うコンピュータ・プログラム、及びその他の任意の各種コンピュータ・プログラム、並びにデータが、メイン・メモリ（１０３）にロード可能なように記憶されうる。
【００７４】
また、ディスク（１０８）には、本発明の実施態様に従うハッシュ関数群を生成する処理を可能にするソフトウェアが、メイン・メモリ（１０３）にロード可能なように記憶されうる。
【００７５】
ディスク（１０８）は、コンピュータ（１０１）内に内蔵されていてもよく、当該コンピュータ（１０１）がアクセス可能なようにケーブルを介して接続されていてもよく、又は、当該コンピュータ（１０１）がアクセス可能なように有線又は無線ネットワークを介して接続されていてもよい。
【００７６】
ドライブ（１０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラム、例えばオペレーティング・システム、アプリケーション・プログラム又は本発明の実施態様に従うコンピュータ・プログラムをディスク（１０８）にインストールするために使用されうる。
【００７７】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に有線又は無線接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は例えば、無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ-Ｆｉ無線ＬＡＮ環境、又は携帯電話網環境（例えば、３Ｇ、ＬＴＥ又は４Ｇ環境）でありうる。
【００７８】
図１Ｂは、本発明の実施態様において使用されうるコンピュータ又は本発明の実施態様に従うコンピュータの一例であって、当該コンピュータ上で１又は複数の仮想マシンを稼働させる場合を示した図である。当該コンピュータは例えば、ワークステーション、ラックマウント型サーバ、ブレード型サーバ、ミッドレンジ、メインフレームなどのサーバ・コンピュータとして構成されうる。
【００７９】
図１Ｂに示すコンピュータ（１２１）は、ハードウェア・リソース（１２２）として、１又は複数のＣＰＵ（１３１）、メイン・メモリ（１３２）、ストレージ（１３３）、通信コントローラ（１３４）、及び通信インタフェース（１３５）を備えうる。上記１又は複数のＣＰＵ（１３１）、メイン・メモリ（１３２）、ストレージ（１３３）、通信コントローラ（１３４）、及び通信インタフェース（１３５）並びに通信回線（１３６）はそれぞれ、図１Ａに示すコンピュータ（１０１）の１又は複数のＣＰＵ（１０２）、メイン・メモリ（１０３）、ディスク（１０８）、通信コントローラ（１１３）、及び通信インタフェース（１１４）、並びに通信回線（１１５）それぞれに対応しうる。
【００８０】
また、コンピュータ（１２１）は、物理ホストマシンとして稼働し、また、仮想化ソフトウェア（例えば、ＶＭＷａｒｅ（登録商標）、Ｈｙｐｅｒ−Ｖ（登録商標）、Ｘｅｎ（登録商標））のハイパーバイザ（仮想化モニタ又は仮想化ＯＳとも呼ばれる）上で、同一の又は異なるＯＳ（例えば、Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標））をゲストＯＳ（１５６）とした１又は複数の仮想マシン１〜ｎ（１２５−１〜１２５−２）（ドメインＵ又はチャイルド・パーティションとも呼ばれる）を稼働させることが可能である。
【００８１】
また、コンピュータ（１２１）は、上記ハイパーバイザ上で、管理用仮想マシン（１２４）（ドメイン０又はペアレント・パーティションとも呼ばれる）を稼働させることが可能である。管理用仮想マシン（１２４）は、管理用ＯＳ（１４１）、当該管理用ＯＳ（１４１）上で動作する制御モジュール（１４２）、及び仮想リソース（１４３）を含む。制御モジュール（１４２）は、ハイパーバイザ（１２３）に対しコマンドを発行するモジュールである。また、制御モジュール（１４２）は、ハイパーバイザ（１２３）に対して、ユーザドメインの仮想マシン１〜ｎ（１２５−１〜１２５−２）の作成、及びゲストＯＳ（１５６）の起動の命令を発行し、仮想マシン１〜ｎ（１２５−１〜１２５−２）の動作を制御する。仮想リソース（１４３）は、管理用仮想マシン（１２４）の為に割り当てられたハードウェア・リソース（１２２）である。
【００８２】
仮想マシン１〜ｎ（１２５−１〜１２５−２）は、仮想リソース、ゲストＯＳ（１５６）、及び、ゲストＯＳ（１５６）上で動作する種々のアプリケーション１〜ｎ（１５７−１〜１５７−３）を含む。仮想リソースは例えば、仮想ＣＰＵ（１５１）、仮想メモリ（１５２）、仮想ディスク（１５３）、仮想通信コントローラ（１５４）及び仮想通信インタフェース（１５５）を含む。
【００８３】
図２Ａ〜図２Ｇそれぞれは、本発明の実施態様に従い、ハッシュ関数を用いてハッシュ値を生成するダイアグラム、すなわち所定位置からビットを選択し、ハッシュ値を生成するダイアグラムを示す。なお、以下の説明において、コンピュータ（１０１）（図１Ａを参照）との記載は、コンピュータ（１２１）（図１Ｂを参照）と読み替えることも可能である。
【００８４】
図２Ａは請求項１に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２０１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４を参照）。
【００８５】
コンピュータ（１０１）は、８ビットのハッシュ値（２０３）を生成する為に、入力値（２０２）の下位８ビット（Ｎ）（ハッシュ値のビット数と同じである）を使用するとする。
【００８６】
コンピュータ（１０１）は、下位８ビットのうちの或る所定位置にある１個のビットを選択する（ステップ（ａ）：２０４）。図２Ａでは、下位８ビット（１ビット目〜８ビット目）のうちの６ビット目（０）が選択されたことを示す。
【００８７】
コンピュータ（１０１）は、上記選択した１個のビット（０）をハッシュ値（２０３）の８ビットのうちの或る所定位置のビットへ割り当てる（ステップ（ｃ）：２０７）。図２Ａでは、上記選択した１個のビット（０）が、ハッシュ値の８ビット（１ビット目〜８ビット目）のうちのうちの３ビット目に格納されたことを示す（２０９を参照）。
【００８８】
コンピュータ（１０１）は、ハッシュ値（２０３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）及び（ｃ）を繰り返す（ステップ（ｄ）：２０８）。但し、ステップ（ａ）において、下位８ビットのうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。
【００８９】
ハッシュ値（２０９）は、ハッシュ値（２０３）の残りの７ビット全てのビットが割り当てられるまでステップ（ａ）及び（ｃ）を繰り返した後に生成されたハッシュ値を示す。
【００９０】
図２Ｂは、請求項２に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２１１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【００９１】
コンピュータ（１０１）は、８ビットのハッシュ値（２１３）を生成する為に、入力値（２１２）の下位８ビット（Ｎ）（ハッシュ値のビット数と同じである）及び上位２４ビット（Ｌ−Ｎ）を使用するとする。
【００９２】
コンピュータ（１０１）は、下位８ビット（Ｎ）のうちの或る所定位置にある１個のビットを選択する（ステップ（ａ）：２１４）。図２Ｂでは、下位８ビット（１ビット目〜８ビット目）のうちの５ビット目（１）が選択されたことを示す。
【００９３】
また、コンピュータ（１０１）は、ステップ（ａ）と並列して又はステップ（ａ）と前後して、上位２４ビット（Ｌ−Ｎ）のうちの１又は複数個のビットを選択する（ステップ（ｂ）：２１５）。コンピュータ（１０１）は、上位２４ビット（Ｌ−Ｎ）のうちの或る所定位置にある１又は複数個のビットを選択する（ステップ（ｂ）：２１５）際に、上位２４ビット（Ｌ−Ｎ）のうちの同一の位置にあるビットを複数回選択してもよい。図２Ｂでは、上位２４ビット（１ビット目〜２４ビット目）のうちの１６ビット目（１）及び５ビット目（０）の２つが選択されたことを示す。
【００９４】
コンピュータ（１０１）は、ステップ２１５で選択したビット１及び０と、並びにステップ２１４で選択したビット１との３ビットの排他的論理和を計算し、計算値０を求める（ステップ２１６）。
【００９５】
コンピュータ（１０１）は、ステップ２１６で求めた計算値０をハッシュ値（２１３）の８ビットのうちの或る所定位置のビットへ割り当てる（ステップ（ｃ）：２１７）。図２Ｂでは、上記求めた計算値（０）が、ハッシュ値の８ビット（１ビット目〜８ビット目）のうちのうちの３ビット目に格納されたことを示す（２１９を参照）。
【００９６】
コンピュータ（１０１）は、ハッシュ値（２１３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２１８）。但し、ステップ（ａ）において、下位８ビット（Ｎ）のうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。また、当該繰り返しのステップ（ｂ）において、コンピュータ（１０１）は、繰り返しを通じて、上位２４ビット（Ｌ−Ｎ）のうちの或る所定位置にある１又は複数個のビットを選択する際に、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と同じ位置にあるビットを選択し、又は、過去に一度選択された位置と異なる位置にあるビット（すなわち、まだ選択されていない位置にあるビット）を選択しうる。
【００９７】
ハッシュ値（２１９）は、ハッシュ値（２１３）の残りの７ビット全てのビットが割り当てられるまでステップ（ａ）、（ｂ）及び（ｃ）を繰り返した後に生成されたハッシュ値を示す。
【００９８】
図２Ｃは、請求項３に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２２１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【００９９】
図２Ｃは、図２Ｂと下記点以外は同じである（図２Ｃに示す符号２２１〜２２９それぞれは、図２Ｂに示す符号２１１〜２１９それぞれに対応する）。
【０１００】
ステップ（ｂ）において、コンピュータ（１０１）は、上位２４ビット（Ｌ−Ｎ）のうちの複数個のビットを選択する（ステップ（ｂ）：２２５）際に、上位２４ビット（Ｌ−Ｎ）の２つ以上の異なる位置から複数個のビットを選択し、又は、上位２４ビット（Ｌ−Ｎ）のうちの全て異なる位置から複数個のビットを選択しうる。上記２つ以上の異なる位置から複数個のビットを選択する場合において、同一の位置にあるビットを複数回選択することを許容する。なお、上位２４ビット（Ｌ−Ｎ）のうちの複数個のビットを選択する（ステップ（ｂ）：２２５）際に、上位２４ビット（Ｌ−Ｎ）のうちの全て異なる位置から複数個のビットを選択する方が、上位２４ビット（Ｌ−Ｎ）のうち同一の位置にあるビットを複数回選択することを許容した場合よりも、ハッシュ関数の一様分布性能が良くなり、例えばハッシュテーブルにキーを格納する場合に空間効率が良くなりうる。
【０１０１】
図２Ｄは、請求項４に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２３１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【０１０２】
図２Ｄは、図２Ｃと下記点以外は同じである（図２Ｄに示す符号２３１〜２３９それぞれは、図２Ｂに示す符号２２１〜２２９それぞれに対応する）。
【０１０３】
ステップ（ｄ）において、ハッシュ値（２３３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２３８）際に、コンピュータ（１０１）は、ステップ（ｂ）の繰り返しを通じて、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビット（すなわち、まだ選択されていない位置にあるビット）を選択する。なお、ハッシュ値（２３３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２３８）際に、過去に一度選択された位置と異なる位置にあるビットを選択する方が、過去に一度選択された位置と同じ位置にあるビットを選択するよりも、ハッシュ関数の一様分布性能が良くなり、例えばハッシュテーブルにキーを格納する場合に空間効率が良くなりうる。
【０１０４】
図２Ｅは、請求項５に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２４１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【０１０５】
コンピュータ（１０１）は、８ビットのハッシュ値（２４３）を生成する為に、入力値（２４２）の下位８ビット（Ｎ）（ハッシュ値のビット数と同じである）を使用するとする。
【０１０６】
コンピュータ（１０１）は、下位８ビットのうち或る所定位置にある１個のビットを選択する（ステップ（ａ）：２４４）。図２Ｅでは、下位８ビット（１ビット目〜８ビット目）のうちの５ビット目（１）が選択されたことを示す。
【０１０７】
また、コンピュータ（１０１）は、ステップ（ａ）と並列して又はステップ（ａ）と前後して、上位２４ビット（Ｌ−Ｎ）のうちの或る所定位置にある１又は複数個の異なる位置にあるビットを選択する（ステップ（ｂ）：２４５）。図２Ｅでは、上位２４ビット（１ビット目〜２４ビット目）のうちの１６ビット目（１）、１１ビット目（１）及び５ビット目（０）の３つが選択されたことを示す。
【０１０８】
コンピュータ（１０１）は、ステップ２４５で選択したビット１、１及び０、並びにステップ２４４で選択したビット１の排他的論理和を計算し、計算値１を求める（ステップ２４６）。
【０１０９】
コンピュータ（１０１）は、ステップ２４６で求めた計算値１をハッシュ値（２４３）の８ビットのうちの或る所定位置のビットへ割り当てる（ステップ（ｃ）：２４７）。図２Ｅでは、上記求めた計算値（１）が、ハッシュ値の８ビットの（１ビット目〜８ビット目）うちの４ビット目に格納されたことを示す（２４９を参照）。
【０１１０】
コンピュータ（１０１）は、ハッシュ値（２４３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２４８）。但し、ステップ（ａ）において、下位８ビットのうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。また、ステップ（ｄ）において、ハッシュ値（２４３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２４８）際に、コンピュータ（１０１）は、ステップ（ｂ）の繰り返しを通じて、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビット（すなわち、まだ選択されていない位置にあるビット）を選択する。
【０１１１】
また、コンピュータ（１０１）は、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビットを選択する際に、可能な限り、入力キーの上位Ｌ−Ｎビットを均等に分けた個数のビットを可能な限り選択する。ここで、均等に分けた個数とは、（Ｌ−Ｎ）がＮで割り切れる場合には、（Ｌ−Ｎ）／Ｎ個でありうる。また、当該均等に分けた個数は、（Ｌ−Ｎ）がＮで割り切れない場合には、［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個である。ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数でありうる。
【０１１２】
図２Ｆは、請求項６に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２５１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【０１１３】
図２Ｆは、図２Ｅと下記点以外は同じである（図２Ｆに示す符号２５１〜２５９それぞれは、図２Ｅに示す符号２４１〜２４９それぞれに対応する）。
【０１１４】
ステップ（ｄ）において、コンピュータ（１０１）は、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビットを選択する際に、入力キーの上位Ｌ−Ｎビットを均等に分けた個数のビットを選択する。ここで、均等に分けた個数とは、（Ｌ−Ｎ）がＮで割り切れる場合において、（Ｌ−Ｎ）／Ｎ個であることをいう。図２Ｆでは、（Ｌ−Ｎ）＝２４がＮ＝８で割り切れるので、均等に分けた個数は３である。
【０１１５】
図２Ｇは、請求項７に係る発明の実施態様の例示であり、入力値（ｋｅｙ）が３５ビットであり（Ｌ＝３５）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）場合において、所定位置からビットを選択し、ハッシュ値を生成するダイアグラム（２６１）を示す。コンピュータ（１０１）は、どのようにビットを下記ステップ（ａ）及びステップ（ｂ）において選択するかを事前に例えば乱数列を用いて決定しておく（乱数列を使用する場合の例については下記図４に示す乱数列を参照）。
【０１１６】
コンピュータ（１０１）は、８ビットのハッシュ値（２６３）を生成する為に、入力値（２６２）の下位８ビット（Ｎ）を使用するとする。
【０１１７】
コンピュータ（１０１）は、下位８ビットのうちの或る所定位置にある１個のビットを選択する（ステップ（ａ）：２６４）。図２Ｇでは、下位８ビット（１ビット目〜８ビット目）のうちの５ビット目（１）が選択されたことを示す。
【０１１８】
また、コンピュータ（１０１）は、ステップ（ａ）と並列して又はステップ（ａ）と前後して、上位２７ビット（Ｌ−Ｎ）のうちの或る所定位置にある１又は複数個の異なる位置にあるビットを選択する（ステップ（ｂ）：２６５）。図２Ｇでは、上位２７ビット（１ビット目〜２７ビット目）のうちの１６ビット目（１）、１１ビット目（１）及び５ビット目（０）の３つが選択されたことを示す。
【０１１９】
コンピュータ（１０１）は、ステップ２６５で選択したビット１、１及び０、並びにステップ２６４で選択したビット１の排他的論理和を計算し、計算値１を求める（ステップ２６６）。
【０１２０】
コンピュータ（１０１）は、ステップ２６６で求めた計算値１をハッシュ値（２６３）の８ビットのうちの或る所定位置のビットへ割り当てる（ステップ（ｃ）：２６７）。図２Ｇでは、上記求めた計算値（１）が、ハッシュ値の８ビットの（１ビット目〜８ビット目）うちの４ビット目に格納されたことを示す（２６９を参照）。
【０１２１】
コンピュータ（１０１）は、ハッシュ値（２６３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２６８）。但し、ステップ（ａ）において、下位８ビットのうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。また、ステップ（ｄ）において、ハッシュ値（２６３）の残りの７ビット全てのビットが割り当てられるまで、ステップ（ａ）、（ｂ）及び（ｃ）を繰り返す（ステップ（ｄ）：２６８）際に、コンピュータ（１０１）は、ステップ（ｂ）の繰り返しを通じて、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビット（すなわち、まだ選択されていない位置にあるビット）を選択する。また、コンピュータ（１０１）は、過去に一度選択された位置（先のステップ（ｂ）で選択された位置）と異なる位置にあるビットを選択する際に、Ｌ−ＮがＮで割り切れないので、入力キーの上位Ｌ−Ｎビットのうちの［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個のビットを選択する。ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数である。図２Ｇでは、（Ｌ−Ｎ）＝２７がＮ＝８で割り切れないので、［（Ｌ−Ｎ）／Ｎ］＋１＝４個のビットを選択するのが３回であり、［（Ｌ−Ｎ）／Ｎ］＝３個のビットを選択するのは５回としている。
【０１２２】
図３Ａは、請求項８に係る発明の実施態様の例示であり、本発明の実施態様に従い生成されたハッシュ関数が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力するダイアグラムを示す。
【０１２３】
入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）とする。
【０１２４】
コンピュータ（１０１）は、上位Ｌ−Ｎビットが同一の２Ｎ個のキー  ｛２Ｎ×ａ，２Ｎ×ａ＋１，２Ｎ×ａ＋２，．．． ，２Ｎ×（ａ＋１）−１｝  （ａは非負整数である）の全要素が一度ずつ出現するキーの集合を入力値（３０１）として本発明の実施態様に従い生成されたハッシュ関数に入力する。当該ハッシュ関数は、０〜２５５の全ハッシュ値パターンが必ず１度ずつ出現するハッシュ値（３０２）を出力する。なお、上位Ｌ−Ｎビットが同一の２Ｎ個の上記キーは任意の順序で入力されてもよい。
【０１２５】
このように、上位Ｌ−Ｎビットが同一の２Ｎ個のキー  ｛２Ｎ×ａ，２Ｎ×ａ＋１，２Ｎ×ａ＋２，．．． ，２Ｎ×（ａ＋１）−１｝  （ａは非負整数である）の全要素が一度ずつ出現するキーの集合を入力値（３０１）とすると、連続する２値の距離が最大で２Ｎ−１になる。
【０１２６】
図３Ｂは、請求項９に係る発明の実施態様の例示であり、本発明の実施態様に従い生成されたハッシュ関数が、ランダム・キーを入力することに応じて、ハッシュ値（重複する可能性がある）を出力するダイアグラムを示す。
【０１２７】
入力値（ｋｅｙ）が３２ビットであり（Ｌ＝３２）且つハッシュ値ｈ（ｋｅｙ）が８ビットである（Ｎ＝８）とする。
【０１２８】
コンピュータ（１０１）は、ランダム・キーを入力値（３１１）として本発明の実施態様に従い生成されたハッシュ関数に入力する。当該ハッシュ関数は、ハッシュ値（３１２）を出力する。当該ハッシュ値は、重複する可能性がある。ハッシュ値（３１２）において、ハッシュ値１２５及び１２９が重複している。なお、ランダム・キーは上位Ｌ−Ｎビットが同一でなくてもよい。
【０１２９】
図４は、本発明の実施態様に従い生成されうるハッシュ関数を作成する動作の一例を示す。
【０１３０】
ハッシュ関数が生成するハッシュ値をＮビットとし、且つ、入力キーをＬビットとする（Ｎ≦Ｌ）。
【０１３１】
図４の式４０１に示す条件を満たす乱数列ｐｏｓを用意する。一つの乱数列を作る動作は、ハッシュ関数を一つ生成するという動作に相当する。ここで、式４０１中、i, j は共にｐｏｓの添え字であり、1≦ i, j ≦ L をとる任意の整数である。
【０１３２】
乱数列（４１１）は、Ｌ＝３２、Ｎ＝８の場合に式４０１の条件を満たすように生成された乱数列の例である。乱数列（４１１）は、１から８（＝Ｎ）までの値が一度出現する部分（４２１）と、９（＝Ｎ＋１）から３２（＝Ｌ）までの値が任意に出現する部分（４２２）を有する。
【０１３３】
コンピュータ（１０１）は例えば、入力値（ｋｅｙ）ｋの下位ビットからｐビット目を返す関数をｂ（ｋ，ｐ）とし、ｐに乱数列ｐｏｓを代入して、ハッシュ値の下位からｒビット目ｈ（ｋ，ｒ）を図４の４３１に示す排他的論理和の式に従って、計算しうる。乱数を生成した後は、ビットの選択方法は固定され、当該選択方法は変更されない。コンピュータ（１０１）は、ハッシュ値の生成において、上記固定されたビット選択方法に基づいて、選択したビットについて排他的論理和を計算する。
【０１３４】
排他的論理和の式（４３１）のＬ＝３２,Ｎ＝８の時の具体例は例えば、図４の４４１に示す通りである。排他的論理和の式の具体例（４４１）は、部分（４５１）では、キーの下位８ビットから、重複がないようにランダムに選択すること、且つ、部分（４５２）では、キーの上位２４ビットから、重複がないように又は重複があってもよいようにランダムに選択することを示す。排他的論理和の式（４３１）において、乱数列ｐｏｓを変更することによって、多数のハッシュ関数を生成することが可能であり、ハッシュ関数群を構成することができる。
【０１３５】
排他的論理和の式（４６１）は、排他的論理和の式の具体例（４４１）に、乱数列を具体的に代入した場合の式を示す。排他的論理和の式（４６１）において、部分（４７１）では、キーの下位８ビットから、重複がないようにランダムに選択されており、且つ、部分（４７２）では、キーの上位２４ビットから、重複がないようにランダムに選択されている態様を示す。
【０１３６】
図５Ａは、本発明の実施態様に従い、生成したハッシュ関数群をマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用するダイアグラムを示す。
【０１３７】
図５Ａに示す上記ダイアグラムを説明する前に、マルチレベル・ハッシュ・テーブル（ＭＨＴ）の概念図を図５Ｂに示すダイアグラムに従って説明する。
【０１３８】
図５Ｂに示すように、ＭＨＴでは、Ｎ個の異なるハッシュテーブルＴ１〜ＴＮ（５６１，５６２，・・・，５６３）を用意する。また、ハッシュテーブルＴ１〜ＴＮ（５６１，５６２，・・・，５６３）はそれぞれ、６個の記憶容量を有しているとする。また、ＭＨＴでは、ハッシュテーブルＴ１〜ＴＮ（５６１，５６２，・・・，５６３）それぞれに、Ｎ個の異なるハッシュ関数ｈ１（ｋｅｙ）〜ｈＮ（ｋｅｙ）（５５１，５５２，・・・，５５３）を用意する。このように、ＭＨＴでは、ｈ１（ｋｅｙ）〜ｈＮ（ｋｅｙ）のようにテーブル数分の異なるハッシュ関数が必要である。
【０１３９】
コンピュータ（１０１）は、キー（追加したいデータである）のハッシュ値を上記異なるハッシュ関数を使用して計算して、ハッシュテーブルＴ１〜ＴＮ（５６１，５６２，・・・，５６３）のうちの空いているスロットの左端にキーを追加していく。すなわち、コンピュータ（１０１）は、キーの追加時には、ハッシュ関数が指す先の空きスロットのうち、最も左のハッシュテーブルのスロットにキーを追加する。ここでは、黒塗りされているスロットがキーの追加先である。
【０１４０】
また、コンピュータ（１０１）は、キーの検索時には、ハッシュ関数が指す先の全スロットから等しいキーを探す。
【０１４１】
ＭＨＴでは、ハッシュテーブルＴＮ（５６３）のハッシュテーブルにも空きがない場合には溢れるが、Ｎが十分に大きい場合には溢れたときにスロットの大部分が埋まっていることから、ハッシュテーブルの空間効率が良い。
【０１４２】
図５Ａに戻ると、上段に示すハッシュ値の生成（５０１）は、図２Ｅに示すハッシュ値を生成するダイアグラム（２４１）と同じである。
【０１４３】
コンピュータ（１０１）は、ステップ（ｄ）でハッシュ値のまだ割り当てられていないビットの全てが割り当てられるまでステップ（ａ）、（ｂ）及び（ｃ）を繰り返してハッシュ値（１０１０１０１１）（５１１）を生成する。上記ステップ（ａ）及び（ｂ）において、ビットの選び方をランダムに変更することで、異なるハッシュ関数を大量に生成することが可能である。
【０１４４】
そして、コンピュータ（１０１）は、ハッシュ関数が指す先の空きスロットのうち、最も左のハッシュテーブルにキーを追加する。図５Ａでは、ハッシュテーブル（５２２）にキーを追加することを示す。
【０１４５】
このように、本発明の実施態様に従い生成されたハッシュ関数群をＭＨＴにおいて使用することが可能である。
【０１４６】
図６は、本発明の実施態様に従い生成されたハッシュ関数群が、出力し得るハッシュ値の全て（２Ｎ個）を出力するという性質を利用して、メモリ・ブロックをゼロクリアする際のメモリ・アドレスとしてそのハッシュ値を使用するダイアグラムを示す。
【０１４７】
図６の上段に示すダイアグラム（６０１）は、従来技術に従うゼロクリア回路を示す。ここで、メモリ・ブロック（６１１）の容量は２５６エントリとする。従来技術に従うゼロクリア回路では、メモリ・ブロック（６１１）のデータをゼロ（６１３）でリセットをする為に、リセット（６１４）信号に応じて通常動作時のアドレス（６１２）とリセット用のアドレス（０〜２５５を入力）の切り替えの為のマルチプレクサ（６１５）が必要である。すなわち、従来技術に従うゼロクリア回路では、リセットの為の追加の回路が必要である。
【０１４８】
図６の下段に示すダイアグラム（６２１）は、本発明の実施態様に従い生成されたハッシュ値を使用して、メモリ・ブロック（６３１）のデータをゼロでリセットをする一例を示す。本発明の実施態様に従い生成されたハッシュ値を使用して、メモリ・ブロック（６３１）のデータをゼロ（６３３）でリセットをする場合には、当該ハッシュ値（０〜２５５のハッシュ値）をそのまま、リセット動作時のメモリ・アドレスとして利用可能である（６２１）。これは、本発明の実施態様に従うと、生成したハッシュ関数群が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、ランダムな順番ではありうるが、出力し得るハッシュ値の全て（２Ｎ個）（０〜２５５）を出力する為である。従って、図６の上段（６０１）に示すマルチプレクサ（６１５）がゼロクリア回路において不要になる。すなわち、本発明の実施態様に従うと、リセットの為の追加の回路が不要になる。なお、下段に示すダイアグラム（６２１）では、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキーが入力される限りにおいて、キーの入力順序は問わず、さらには０〜２５５の範囲である必要もない。
【０１４９】
図７は、本発明の実施態様に従い、ハッシュテーブルをＦＰＧＡ内のメモリ・ブロック上に用意するダイアグラムを示す。
【０１５０】
コンピュータ（１０１）は、本発明の実施態様に従い、ハッシュテーブルをＦＰＧＡ内のメモリ・ブロック（７０１）上に用意する。例えば、Altera Strarix（登録商標） IVデバイスのＭ９Ｋブロックである。Ｍ９Ｋブロックについては、下記ＵＲＬ＜http://www.altera.com/literature/hb/stratix-iv/stx4_siv51003.pdf＞に記載の「3. TriMatrix Embedded Memory Blocks in Stratix IV Devices」を参照されたい（非特許文献４）。
【０１５１】
そして、コンピュータ（１０１）は、メモリ・ブロック（７０１）上の、ハッシュ関数（７０２）が指す先の空きメモリ・ブロックにキーを追加する。
【０１５２】
このように、ＭＨＴをＦＰＧＡ上に実装して、ＦＰＧＡ上の基本的演算機能によって、本発明の実施態様に従い生成されたハッシュ関数群を使用することが可能である。また、本発明の実施態様に従うことで、排他的論理和によってハッシュ値が計算できることから、１クロック内にハッシュ値の計算を完了することが可能になる。また、ハッシュテーブルをＦＰＧＡ内のメモリ・ブロックに構築することによって、１クロックでハッシュテーブルからのデータ検索が可能になるため、ＦＰＧＡの計算性能を最大限に発揮することが可能になる。
【０１５３】
図８Ａ及び図８Ｂは、本発明の実施態様に従い、生成したハッシュ関数を用いて、入力されたキーのハッシュ値の一つを計算する処理のフローチャートを示す。ここで、或る所定位置とは事前に決定されており、入力キーからどのビットを選択して、排他的論理和を計算するかを決定する。或る所定位置を決定することは、ハッシュ関数を１つ生成することに対応する。なお、以下では、Ｌビットの入力キーから、Ｎビットのハッシュ値を生成する場合（Ｎ≦Ｌ）を示す。
【０１５４】
図８Ａに示すフローチャートは、請求項１に記載の処理に対応する。
【０１５５】
ステップ８０１において、コンピュータ（１０１）は、ハッシュ値を計算する処理を開始する。
【０１５６】
ステップ８０２において、コンピュータ（１０１）は、変数ｉに１を代入する。ここで、１≦ｉ≦Ｎである。
【０１５７】
ステップ８０４において、コンピュータ（１０１）は、入力キーの下位Ｎビットのうちの未選択である所定位置にある１個のビットを選択する。未選択であるビットとは、１≦ｉ≦Ｎを通して、一度も選択されていないビットのことである。
【０１５８】
ステップ８０６において、コンピュータ（１０１）は、ステップ８０４で選択した１個のビットを、ハッシュ値のＮビットのうちの或る所定位置（すなわち、ハッシュ値のｉビット目でなくともよい）へ割り当てる。
【０１５９】
ステップ８０７において、コンピュータ（１０１）は、変数ｉにｉ＋１を代入し、ｉをインクリメントする。なお、コンピュータ（１０１）は、ｉの値を過去のｉと重複しないようにランダムな値になるようにしうる。例えば、ステップ８０７について、変数ｉにｉ＋１を代入し、ｉをインクリメントするループ処理の代わりに、まだｉに代入していない１以上Ｎ以下の値があるかを判断する判断処理に変更しうる。
【０１６０】
ステップ８０８において、コンピュータ（１０１）は、ｉ≦Ｎであるかを判断する。コンピュータ（１０１）は、ｉ≦Ｎであることに応じて、処理をステップ８０４に戻す。一方、コンピュータ（１０１）は、ｉ≦Ｎでないこと（すなわち、Ｎ＜ｉであること）に応じて、処理を終了ステップ８０９に進める。なお、ステップ８０４において、下位Ｎビットのうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。
【０１６１】
ステップ８０９において、コンピュータ（１０１）は、ハッシュ値を計算する処理を終了する。コンピュータ（１０１）は、図８Ａに示すフローチャートの或る所定位置を変更することによって、複数のハッシュ関数が集まったハッシュ関数群を生成することができる。
【０１６２】
図８Ｂに示すフローチャートは、請求項２に記載の処理に対応する。
【０１６３】
ステップ８１１において、コンピュータ（１０１）は、ハッシュ値を計算する処理を開始する。
【０１６４】
ステップ８１２において、コンピュータ（１０１）は、変数ｉに１を代入する。ここで、１≦ｉ≦Ｎである。
【０１６５】
ステップ８１３において、コンピュータ（１０１）は、メモリ内に空の記憶領域を用意する。
【０１６６】
ステップ８１４において、コンピュータ（１０１）は、入力キーの下位Ｎビットのうちの未選択である所定位置にある１個のビットを選択する。未選択であるビットとは、１≦ｉ≦Ｎを通して、一度も記憶領域に追加していないビットのことである。そして、コンピュータ（１０１）は、当該選択した１個のビットを上記記憶領域に追加する。なお、排他的論理和は計算順序が変わってもその計算値は同じであるので、記憶領域への選択したビットの格納の順序は任意である。
【０１６７】
ステップ８１５において、コンピュータ（１０１）は、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択する。コンピュータ（１０１）は、任意の個数の複数個のビットを選択してもよく、又は、１≦ｉ≦Ｎを通して、未選択のビットから（出来るだけ）均等に分けた個数のビットを選択してもよい。未選択のビットから（出来るだけ）均等に分けた個数のビットを選択することによって、一様分布性能の良いハッシュ関数を得ることが可能である。
【０１６８】
未選択のビットから（出来るだけ）均等に分けた個数のビットを選択する場合において、（Ｌ−Ｎ）がＮで割り切れる場合には、当該均等に分けた個数は（Ｌ−Ｎ）／Ｎ個である。
【０１６９】
また、均等に分けた個数のビットを選択する場合において、（Ｌ−Ｎ）がＮで割り切れない場合には、当該均等に分けた個数は、［（Ｌ−Ｎ）／Ｎ］＋１個又は［（Ｌ−Ｎ）／Ｎ］個である。ここで、［（Ｌ−Ｎ）／Ｎ］は（Ｌ−Ｎ）／Ｎ以下の最大の整数である。コンピュータ（１０１）は例えば、ｉ＝Ｎのときの選択が終わったときに、上記入力キーの上位Ｌ−Ｎビットの全てのビットが一度ずつ選択するようにしうる。
【０１７０】
また、コンピュータ（１０１）は、複数個のビットを選択する場合に、（１）上記入力キーの上位Ｌ−Ｎビットのうちの少なくとも１つが異なる位置から複数個のビットを選択する（言い換えれば、上記入力キーの上位Ｌ−Ｎビットのうちの２つ以上の異なる位置からビットを選択する）か、又は、（２）上記入力キーの上位Ｌ−Ｎビットのうちの全て異なる位置から複数個のビットを選択しうる。
【０１７１】
なお、コンピュータ（１０１）は、ステップ８１４とステップ８１５とを並列して実行し、ステップ８１４をステップ８１５よりも先に実行し、又はステップ８１５をステップ８１４よりも先に実行してもよい。
【０１７２】
ステップ８１６において、コンピュータ（１０１）は、上記記憶領域内の全ビットの排他的論理和の計算値を求め（すなわち、ステップ８１４で選択した１個のビットと、ステップ８１５で選択した１又は複数個のビットとについて、全ビットの排他的論理和の計算値を求め）、当該計算値をハッシュ値のＮビットのうちの或る所定位置（すなわち、ハッシュ値のｉビット目でなくともよい）へ割り当てる。コンピュータ（１０１）は例えば、ステップ８１５で２ビット以上を選択した場合には、ステップ８１４で選択した１個のビットと、ステップ８１５で選択した２ビット以上とを合わせて、３ビット以上の排他的論理和の計算値を求める。その結果、１ビットの計算値が得られる。
【０１７３】
ステップ８１７において、コンピュータ（１０１）は、変数ｉにｉ＋１を代入し、変数ｉをインクリメントする。なお、コンピュータ（１０１）は、ｉの値を過去のｉと重複しないようにランダムな値になるようにしうる。例えば、ステップ８０７について、変数ｉにｉ＋１を代入し、ｉをインクリメントするループ処理の代わりに、まだｉに代入していない１以上Ｎ以下の値があるかを判断する判断処理に変更しうる。
【０１７４】
ステップ８１８において、コンピュータ（１０１）は、ｉ≦Ｎであるかを判断する。コンピュータ（１０１）は、ｉ≦Ｎであることに応じて、処理をステップ８１３に戻す。一方、コンピュータ（１０１）は、ｉ≦Ｎでないこと（すなわち、Ｎ＜ｉであること）に応じて、処理を終了ステップ８１９に進める。なお、ステップ８１４において、下位Ｎビットのうち一度選択されたビットは以降の繰り返しのステップにおいて選択されない。
【０１７５】
ステップ８１９において、コンピュータ（１０１）は、ハッシュ値を計算する処理を終了する。コンピュータ（１０１）は、図８Ｂに示すフローチャートの或る所定位置を変更することによって、複数のハッシュ関数が集まったハッシュ関数群を生成することができる。
【０１７６】
図９は、本発明の実施態様に従い生成されるハッシュ関数に基づいて、ハッシュテーブル内のデータへのアクセスに利用するダイアグラムを示す。
【０１７７】
ステップ９０１において、コンピュータ（１０１）は、ハッシュテーブル内のデータへのアクセス処理を開始する。なお、ハッシュ値を生成するコンピュータとハッシュ値を利用する（例えば、ハッシュテーブルへのアクセスを行う）コンピュータとは、同じコンピュータであってもよく又は異なるコンピュータであってもよい。
【０１７８】
ステップ９０２において、コンピュータ（１０１）は、図８Ａ又は図８Ｂに示すフローチャートに従ってハッシュ値を生成する。
【０１７９】
ステップ９０３において、コンピュータ（１０１）は、ステップ９０２で生成したハッシュ値に基づいて、データが格納されていると予期されるスロットにアクセスする。当該データは、ビット列で表現できるものであれば、その内容は制限されない。
【０１８０】
ステップ９０４において、コンピュータ（１０１）は、ハッシュテーブル内のデータへのアクセス処理を終了する。
【０１８１】
図１０は、図１Ａ又は図１Ｂに従うハードウェア構成を好ましくは備えており、図８Ａ〜図８Ｂそれぞれに示すフローチャートに従って本発明の実施態様を実施するコンピュータの機能ブロック図の一例を示す図である。
【０１８２】
コンピュータ（１００１）は例えば、図１Ａに示すコンピュータ（１０１）に示されている構成、例えばＣＰＵ（１０２）、メイン・メモリ（１０３）、記憶装置（１０８）、及びディスク（１０８）を備えている。
【０１８３】
コンピュータ（１００１）は、ビット選択手段（１０１１）及びビット割当手段（１０１２）を備えている。なお、以下では、Ｌビットの入力キーから、Ｎビットのハッシュ値を生成する場合（Ｎ≦Ｌ）を示す。
【０１８４】
ビット選択手段（１０１１）は、入力キーの下位Ｎビットのうちの或る所定位置にある１個のビットを選択する。そして、ビット割当手段（１０１２）は、ビット選択手段（１０１１）によって選択された上記１個のビットを、上記ハッシュ値のＮビットのうちの或る所定位置のビットへ割り当てる。
【０１８５】
ビット選択手段（１０１１）はさらに、上記入力キーの上位Ｌ−Ｎビットのうちの或る所定位置にある１又は複数個のビットを選択する。そして、ビット割当手段（１０１２）は、下位Ｎビットから選択された１個のビットと、上位Ｌ−Ｎビットから選択された１又は複数個のビットとについて、全ビットの排他的論理和の計算値を求め、当該計算値をハッシュ値のＮビットのうちの或る所定位置のビットとして割り当てる。
【０１８６】
ビット選択手段（１０１１）は、図８Ａに記載のステップ８０２〜８０４及び８０７〜８０８、並びに、図８Ｂに記載のステップ８１２〜８１５及び８１７〜８１８を実行しうる。
【０１８７】
ビット割当手段（１０１２）は、図８Ａに記載のステップ８０６、及び図８Ｂに記載のステップ８１６を実行しうる。
【０１８８】
図１１は、本発明の実施態様に従い、生成したハッシュ関数群をマルチレベル・ハッシュ・テーブル（ＭＨＴ）で使用し、キーを追加していった場合の使用されたメモリ・ブロック数の変化を示す。
【０１８９】
グラフ（１１０１）は、本発明に従うハッシュ関数（１１０２）及び従来技術であるユニバーサル・ハッシング（１１０３）それぞれにおいて、追加したデータ個数（２Ｎａ（ａは非負整数）から始まる３２ビット連続整数をキーとした場合のキー追加個数）に対するメモリ・ブロック使用量変化を示す（入力キーＬ＝３２ビット，ハッシュ値Ｎ＝８ビット）。なお、使用されたメモリ・ブロック数が少ないほどメモリ効率の観点から性能が良いことを示す。
【０１９０】
グラフ（１１１１）は、本発明に従うハッシュ関数（１１１２）及び従来技術であるユニバーサル・ハッシング（１１１３）それぞれにおいて、追加したデータ個数（３２ビットランダム整数をキーとした場合のキー追加個数）に対するメモリ・ブロック使用量変化を示す（入力キーＬ＝３２ビット，ハッシュ値Ｎ＝８ビット）。
【０１９１】
グラフ（１１０１）に示されているように、本発明に従うハッシュ関数（１１０２）では、追加したデータ（２Ｎａ（ａは非負整数）から始まる３２ビット連続整数をキーとした場合）において、常に全てのスロットを埋めることができた。すなわち、本発明に従い生成されたハッシュ関数群をＭＨＴに利用し、入力キーが２Ｎａ（ａは非負整数）から始まる３２ビット連続整数がキーである場合には、メモリ使用効率は１００％に達した。すなわち、ＭＨＴが溢れたときに、全てのスロットが埋まっている。これは、本発明の実施対象に従うハッシュ関数群が、上位Ｌ−Ｎビットが同一であり且つ下位Ｎビットを全パターン網羅したキー（２Ｎ個）を入力することに応じて、出力し得るハッシュ値の全て（２Ｎ個）を出力するため、全てのスロットにデータが格納されることによる。また、本発明に従うハッシュ関数（１１０２）では従来技術であるユニバーサル・ハッシングよりも、計算を容易にしつつ、常に良好な性能を実現した。
【０１９２】
グラフ（１１１１）に示されているように、本発明に従うハッシュ関数（１１１２）では、追加したデータ（３２ビットランダム整数をキーとした場合）において、計算を容易にしつつ、従来技術であるユニバーサル・ハッシング（１１１３）と同等の性能を実現することができた。使用効率は、ランダム・キーの場合に、実験的に全ブロック容量の９９．５２％に達した。
【図１Ａ】
0006614632.tif 000002
【図１Ｂ】
0006614632.tif 000003
【図２Ａ】
0006614632.tif 000004
【図２Ｂ】
0006614632.tif 000005
【図２Ｃ】
0006614632.tif 000006
【図２Ｄ】
0006614632.tif 000007
【図２Ｅ】
0006614632.tif 000008
【図２Ｆ】
0006614632.tif 000009
【図２Ｇ】
0006614632.tif 000010
【図３Ａ】
0006614632.tif 000011
【図３Ｂ】
0006614632.tif 000012
【図４】
0006614632.tif 000013
【図５Ａ】
0006614632.tif 000014
【図５Ｂ】
0006614632.tif 000015
【図６】
0006614632.tif 000016
【図７】
0006614632.tif 000017
【図８Ａ】
0006614632.tif 000018
【図８Ｂ】
0006614632.tif 000019
【図９】
0006614632.tif 000020
【図１０】
0006614632.tif 000021
【図１１】
0006614632.tif 000022