JPH02231675A - データを構成、管理又は検索するための方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明はデータ処理システム中Ｋ記憶されたデータの検
索に関し、さらに詳しくはスペース効率ハツシュ検索テ
ーブルを用いてキーにより認識されるテーブル・エント
リの検索方法に関する。

Ｂ．従来技術および解決課題 データ処理プログラム情報の多くの部分は後の使用のた
めに記憶あるいは分離されている。この情報はデータ処
理プログラムによって処理される対象として、例えばカ
スタマ、サプライア等の名前がついている。検索テーブ
ルは情報記憶のためのデータ構造としてよく使われる。

第４図および第５図に見られるようにテーブル１０はエ
ントリ１６を有し、各エントリはキー１２を有する。キ
ー１２に加え、各エントリは分離された追加情報を持つ
。第４図，第５図の実施例においてはキー１２としてラ
ストネームを持ち、追加情報として対応の電話番号を持
つ。すなわち、キー１２に対するデータ１４である。検
索テーブルにおいて実行される基本的な処理Ｋは次のよ
うなものがある。

Ｉ　ＮＳ　ＥＲＴ　　テーブル中に新しいエントリを挿
入ＤＥＬＥＴＥ　　テーブル●エントリの削除ＦＩＮＤ
　　与えられたキーによってすべての（又は１つの）エ
ントリを発見 これらの用語は本説明において通常使用されるものとし
て扱うが、他のシステムでは同様の処理を異なる用語で
行うこともある。

ＦＩＮＤがＩＮＳＥＲＴあるいはＤＥＬＥＴＥよりも頻
繁に使用される環境においては、検索テーブルは非常に
有用である。というのはＦ　Ｉ　ＮＤ処理はＩＮＳＥＲ
ＴあるいはＤＥＬＥＴＥ処理に比較して非常に早く処理
できるからである。さらに、ＦＩＮＤは検索テーブルの
基本的処理であり、ＩＮＳＥＲＴおよびＤＥＬＥＴＥは
多くの場合、必ずしも必要ではない。

多ぐのデータ病造においては、効率的な情報検索の問題
はアドレスである。第４図に示すように、最も単純な検
索テーブル構造はリスト中にエントリを順番に配列した
ものである。このようなテーブル１０の検索は各工冫ト
リを初めから所定のキー１２が見つかるまで順次確かめ
るものである。

これは不要なエン｝　ＩＪを見る必要が．１，時間のか
かる結果となる。Ｎ個のエンｌのテーブルでは、目的の
ものを探すのに平均Ｎ／２のエントリを確かめなければ
ならない。さらに、所定のキーがテーブル中に存在しな
い場合にはすべてＯ，Ｎエントリを確認する必要がある
。この構成にも調書が無いわけではない。これはシンプ
ルであり、スペースの無駄がなく、エントリ・サイズの
Ｎ倍のスペースを使用する。シーケンシャル検索テーフ
ルのサーチをスピードアップする方法もある。

例えば「テーブルｍサーテ処理」″Ｉ　ＢＭ　Ｔｅｃｈ
ｎｉｃａｌＤｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ，
　Ｖｏｌ．　１７，　Ｎｏ．４，Ｓｅｐｔｅｍｂｅｒ　
　１９８４，ｐａｇｅ　９６４−９６５”である。しか
し、検索時間はテーブルの大きさＮに比例するという問
題は解決されない。

検索テーブルの検索効率を高める方法として、シーケン
シャル―テーブルの記憶データをキーの順序に上から順
に、あるいは下から順にソートすることである。例えば
、第２図に示すようにデータ１４をキー１２のラストネ
ームのアルファベット順に上から配列する。テーブルが
このように構成されていれば、検索対象となる所定のキ
ー以降については検索必要のないことが確信できる。従
って、エントリ発見に要する時間は平均でＮ／２となシ
、テーブル中に所定のキーがないことを確認するのに要
する時間もＮ／２となる。この検索方法はソート●リニ
ア・サーチと以下呼ぶ。

このようなソート・シーケンシャル検索テーブルを用い
て、検索速度を高めることはできる。この検索技術を２
進サーチと呼ぶ。この２進サーチの使用により、ＦＩＮ
Ｄ処理の効率は大きく高められる。２進サーチの間、テ
ーフルｅエントリの並びは維持される。検索キーはこの
レンジにあるかもしれないし、このテーブルには無いか
もしれない。最初、このレンジはすべてのデーブルをカ
バーする。２進サーチのかくステップの間、このレンジ
の中間が確かめられる。これが対象キーであれば値その
時点で検索は完了する。そうでなけれは、中間のキーと
検索対象キーの比較結果に基づいて、中間エントリを上
側値又は下側に調整する。次に、新しいレンジにおいて
、中間エン｝　ＩＪを確かめる。

かくステップにおいて、レンジは２分されるこの処理は
レンジに残りのテーブル・エントリがなくなるか、所望
のキーが見つかるまで続けられる。

各ステップにおいてレンジのエントリ数は半分に削減さ
れる。従って、サーチはｌｏｇＮに比例して終息する。

この検索テーブル構成はコンパクトであり、エントリの
Ｎ倍に比例したスペースを必要とするのみである。しか
し、これはＩＮＳＥＲＴ％ＤＥＬＥＡＴＥ処理が実行さ
れるごとにエントリの再構成を必要とする。先Ｋ述べた
ように、ＦＩＮＤ処理を最大限に利用することが重要で
ある。２進サーチ手法については「テーブル検索」″’
　ＩＢＭ　Ｔｅｃｈｎｉｃａｌ　Ｄｉｓｃｌｏｓｕｒｅ
　Ｂｕｌｌｅｔｉｎ，Ｖｏｌ．　１４，　Ｎｏ．　１０
，　Ｍａｒｃｈ　　１　９７２”に記載されている。

さらに高速の検索テーブル構成は「ハツシング」を使用
したものである。このハツシングを基本としたテーブル
においてはテーブル中にエントリを入れる際の第１ステ
ップはエントリ・キーをハッシュすることである。これ
はキーに対してハッシュ機能，すなわちキーによって０
からＭ−１のランダムな値を応答する機能を付与するこ
とを含む。

ここでＭはテーブルのエントリ数の最大値である。

良好なハツシュ機能は２つの似たキーに対して全く異な
る値を生成する。例えば、挿入されるエントリに対して
Ｈのノ・ツシュ値が得られると、エントリはＨによって
識別される位置、あるいはそれに続く位置であいている
部分に挿入される。重要なＦＩＮＤ処理は検索キーのハ
ツシング、その位置におけるテーブルのサーチを始める
ことによって素早く実行される。同じインデックスに複
数のキーがハツシュしている場合は複数のサーチが必要
となる。テーブル・エントリの１０〜２０９６を未使用
状態にしておけば、２番目のサーテ総量はメモリの使用
を最小にしたものにできる。このハツシュ検索テーブル
方法は、テーブルが完全に埋まった状況でない限シにお
いては従来の２進サーチ技術よりも速いＦＩＮＤ処理を
達成する。

ハツシュ●ベース検索テーブルの例を第６Ａ〜第６Ｊ図
の解放アドレス・ハツシュ検索テーブル１１として示す
。テーブル１１は０から１１の１２、すなわちＭ−１の
エントリを持つ。エントリ数は第６５図に示すようにデ
ータ１４よりも２０％多い。ハツシュ●ペース検索テー
ブル１１は、例えばキー１２のラストネームをハツシュ
するために以下のハツシュ関数１３を適用する。

ハツシュ関数 ｆ（Ａ）−１，ｆ（Ｂ）＝２，．．．ｆ（Ｚ）＝２６ｈ
ａｓｈ　（”ＡＢＣ”）＝（ｆ　（Ａ　）＋ｆ　（　Ｂ
　）＋ｔ　（ｃ　）　）ｍｏｄ　１２このハツシュ関数
の意味はラストネームの各々にアルファベットに対応す
る１から２６までの数字を付与することである。ラスト
ネームの各々に数値が与えられる。加算値が１１Ｋ達し
たら、また０から１１を繰シ返す。このラストネーム１
２のハツシュ関数の結果は第６Ｋ図に示す。

テーブルへのデータ１４の挿入は以下のようにして実行
される。最初に［ＪｏｈｎｓｏｎＪがハツシュされ、第
６Ａ図に示すようにテーブル１１の位Ｄｊｔ１１にデー
タ１４とともに挿入される。同様に、次に続くネームと
データがテーブル１１に、以下のように挿入される。Ｂ
ａｃｋｌｕｎｄが８番目の位置（第６Ｂ図）％Ｓｍｉｔ
ｈが９番目の位置（第６Ｃ図）、Ｑｏｓｓが０番目の位
置（第６Ｄ図）、Ｂｌｅｄｓｏｅが２番目の位置（第６
Ｅ図）、Ｏｌｓｏｎが３番目の位置（第６Ｆ図）、であ
る。［ＴｕｒｎｅｒＪのハツシュ関数結果は０であり、
この場合は０番に続くあいているスペースに入る。Ｇｏ
ｓｓが０番を占めているので、第６Ｇ図に示すように次
の１番のスペースに入る。同様にＷｉｌｓｏｎはハツシ
ュ関数結果が第６Ｋ図に示すようにＢｕｃｋｌｕｎｄと
同じ８である。Ｓｍｉｔｈが９番目を占めているので、
８番に続く最初の空きスペースは第６Ｈ図に示すように
１０番目の位置となる。次にＮａｓｈのハツシュ関数結
果は６となる。Ｎａｓｈは第６Ｉ図のごとく、そのデー
タとともに６番目に挿入される。最後にハツシュ関数は
Ｍｏｒｇａｎ　に適用され、値８が得られる。Ｂａｃｋ
ｌｏｕｎｄがすでに８の値を持っているので、８番に続
く空きスペースを捜す。９番、１０番、１１番はすでに
Ｓｍｉｔｈ１Ｗｉｌｓｏｎ％Ｊｏｈｓｏｎによって占有
されているので、ここから０に戻って捜すこととなる。

０番、１番、２番、３番もＧｏｓｓ％Ｔｕｒｎｅｒ％Ｂ
ｌｅｄｓｏｅ１Ｑｌｓｏｎによって占有されているので
８番に続く最初の空きスペースは第６５図に示すように
４番となる。

第６５図において，ＦＩＮＤ処理は以下のように実行さ
れる。検索のキーがＳｍｉｔｈであるとすると、ハツシ
ュ関数がＳｍｉｔｈに適用され、結果９を生成する。Ｆ
ＩＮＤ処理は即座にキーＳｍｉｔｈおよび対応データを
捜すために９番目の位置に行く。同様に、Ｍｏｒｇａｎ
　がキーである場合はノ・ツシュ関数がＭｏｒｇａｎ　
に適用され、８が産出される。しかし、ＦＩＮＤ処理が
８番目に直行しても、そこには検索キーはない。追加サ
ーチがキーＭａｒｇａｎ　を検索するために、８番目の
位置から始められる。

第７Ａ〜７５図に同じノ’％ツシュを有するテープｋ　
ｔ７）異なるハツシュ構成リンク・エントリを示す。

この方法ではエントリのＭ個のリンク・リストが保持さ
れる。検索キーが第７Ａに示すように０〜Ｍ−１の範囲
にハツシュされる。所望のキーを有するエントリをサー
チするために対応リンク・リストが検索される。この方
法を使用したエントリの検索に要する時間は平均Ｎ／（
２Ｍ）である。

これはリストにおいてもノ・ツシュ関数がＮエントリに
負献するからである。しかし、速度はアップするが、こ
の方法はリストの次のエントリへのリンクをホールドす
るために各エントリに追加スペースが必要となる。

第７Ａ〜７Ｊ図はり冫ク・ノ１ツシュ検索テーブルによ
る方法を示したものである。この例では第７Ａ図におけ
る各キー１２は以下に示すノ・ツシュ関数によってノ・
ツシュされる。

ハツシュ関数 ｆ（Ａ）＝１，ｆ（Ｂ）＝２，．．．ｆ（Ｚ）＝２６ｈ
ａｓｈ（″’ＡＢＣ”）＝（ｆ　（Ａ）＋ｆ　（Ｂ）＋
ｆ（Ｃ））ｍｏｄ１０このハツシュ関数から得られた値
は第７Ａ図１３に示す。Ｊｏｈｎｓｏｎのノ１ツシュ値
は５であり、エントリのリンク拳リスト１８の５番目の
エントリは０である。従って、キーＪｏｈｎａｏｎおよ
び関連データは第７Ｂ図のテーブル１７の０番の位置に
ある。同様に、Ｂａｅｋｌｕｎｄのノ１ツシュ値は８で
あり、リンク・リストの８番目のエントリは１であるの
で、キーＢａｃｋｌｕｎｄおよび関連データは第７Ｃ図
のテーブル１７の１番の位置にある。

このプロセスがＳｍｉｔｈ，Ｇｏｓｓ％Ｂｌｅｄｓｏｅ
と第７Ｄｓ　７Ｅ、７Ｆ図に示すように進行する。しか
し、Ｏｌｓｏｎはノ・ツシュ値が５となシ、０番の位置
にあるＪｏｈｎａｏｎと同様Ｋなる。従って、０番の位
置において、５を有するり冫ク１５がＯのハッシュ値の
Ｑｌｓｏｎに対して５番目の位置を提供する（第７Ｇ図
、テーブル１７参照）。同様に、Ｗｉｌ’ｇｏｎのハツ
シュ値も第７Ａ図に示すようにＢｌｅｄｓｏｅと同じ２
となる。リンク・リスト１８の２番目の位置はＢｌｅｄ
ｓｏｅによってテーブル１７の４番目の位置が占められ
ている４番目の位置のリンク１５は７の値を持ち、第７
Ｈ図Ｋ示すようにこの位置にＷ目ｓｏｎ　を見つけるこ
とができる。同様に，Ｎａａｈも値２を持ち、リンク・
リスト１８の２番は、位置４のＢｌｅｄｓｏｅによって
占められ、この４番の位置はＷｉｌｓｏｎ　に対応する
リンク値７を持ち、この７番の位置はリンク値８を持ち
、ここに最終的なキーＮａｓｈを見出すことができる（
第７Ｉ図参照）。１ロのエントリが完了した図を第７５
図に示す。

ハツシュ手段を使用した他の態様としては以下に示す文
献に記載されている。「ハッシングによるインデックス
手法」、ＩＢＭ　　ＴｅｃｈｎｉｃａｌＤｉｓｃｌｏａ
ｕｒｅ　　Ｂｕｌｌｅｔｉｎ，Ｍｏｌ．１６，Ｎｏ．５
．Ａｕｇｕ！Ｉｔ　　１９７３；　　ｒキャッシュ及び
／または仮想メモリを使用したコンピュータにおけるハ
ツシュおよびインデックス技術の改良Ｊ　％　ＩＢＭＴ
ｅｃｈｎｉｃａｌ　　Ｄｉｓｃｌｏｓｕｒｅ　　Ｂｕｌ
ｌｅｔｉｎ，Ｍｏｌ．３１，Ｎｏ．１，Ｊｕｎｅ　　１
９８８　；　ｒノ１ツシュ●ツリーＪ　，　　Ｉ　ＢＭ
　Ｔｅｃｈｎｉｃａｌ　ＤｉｓｃｌｏｓｕｒｅＢｕｌｌ
ｅｔｉｎ，Ｖｏｌ．３０，Ｎｏ．５，Ｏｃｔｏｂｅｒ１
９８７． Ｃ．発明の概要および解決課題 本発明の目的は、従来の方法に比較して、より速い検索
テーブルにおけるエントリの検索手段を提供し、なお、
従来の方法よりも少ないスペースの使用を達成すること
を目的とする。

本発明のシステムおよび装置においては、高速検索テー
ブルは、１つの小さなエクストラルメモリを使用するよ
うに構成されている。通常のハッシュ・テーブルにおい
ては使用メモリの総量はエントリの数に比例し、エン｝
　ＩＪ数の内容およびエントリ　サイズには比例しない
。

本発明の検索テーブルはエントリのベクトルとして考え
られる。テーブル中のエントリは、各エントリ・キーの
ハッシュ値によって定義されるソート順に保持される。

単純なハッシングでは１０〜２０９６の予約部分が要求
されるのに対して、サイズＮのベクトルにおいてはＮエ
ントリが保持される。オフセット−テーブルと呼ばれる
Ｎ，？７セットのエクストラ慟ベクトルが保持される。

ＰＩＮＤ処理によってキーがハッシュされ、オフセット
・テーブルでのインデックスを獲得する。さらに、オリ
ジナル・インデックスにオフセット値を加算して，サー
チの開始されるテーブル・エントリのベクトルでのイン
デックスを獲得する。オフセット・ベクトル中での次の
位ｔｉｔ（ｎｅｘｔ　ｐｏｓｉｔｉｏｎ）におけるオフ
セットがテーブル・エントリナなわち、キーによって検
索されていたテーブル・エントリのベクトル中の位置を
検索する。これらの手段はＦＩＮＤ処理が、検索キーを
持つエントリがないことを全くサーチせずに判断するこ
とを可能とする。従って、ＦＩＮＤ処理は第２のサーチ
に、速い２進サーチを適用できる。

このオフセット●ハツシングはリンク●ハツシング法と
同じオーダーのサーチ・タイムを持つ。

最初のハツシュはエントリ・パケットのサーチに続いて
実行される。オフセット・ハツシング構成においては、
エントリ・パケットは近接したものであり、位ｆｉｔｈ
（キー）とｈ（キー）＋１のオフセット・テーブル中に
あるオフセットによって制限される。リンク・ハツシン
グ構成においてはエントリ・パケットはすなわちリンク
・リストである。従って、オフセット・ハツシングのス
ピードは上述の検索テーブルのなかでも最も早いものと
同じか、ときにはそれ以上のスピードを持つ。というの
は第２サーチがリンク・リストとは違い、連続的に実行
されるからである。オフセット・ノ１ッシング方法にお
ける他のスピード上のメリットはアルゴリズムを使用し
たデータの良好な配置にある。良好な配置は仮想メモリ
におけるページ不在を減少させる。

２進サーチ検索テーブル構成は最も小スペースではある
がオフセット・ハッシングほどのスピードはない。他の
ハツシング法はスピードはあっても、よル多くのスペー
スが必要となる。オフセット・ハツシング法においてス
ペース効率も考慮されたものがオフセットのベクトルで
ある。オフセットは極めて小さくでき、リンク・ハッシ
ング法Ｋおけるリンクよクも小さい。リンク・ハッシン
グ法の一般的な構成ではリンク・リスト・アンカーのベ
クトルおよび各エントリ中のリンクが必要とされる。オ
フセット●ハッシング法では各工ｙトリごとのリンクは
必要としない。

かなり、大きなテーブルにおいても、１バイトのオフセ
ットが適当である。ハッシュ関数がＮ個のテーブル・ス
ロツ｝Ｋ導入された場合、最悪のオフセット（テーブル
の中心において）は標準偏差分布をする。オフセットは
正でも負でも有りえるので、４０９６のエントリのテー
ブルの場合は４シグマＫ対して、１６３８４のテーブル
の場合は２シグマに対して、１バイト・オフセットが適
当となる。たった１０ビットのオフセットで１ｏＯ万の
エントリを超えるテーブルの２シグマをカバーする。も
し、ある状態におけるオフセットが所定のビット数に適
合しない場合には、エスケープが供給され、第２サーチ
がエントリの一部において単純な２進サーチを実行する
。１バイト・オフセットにおける適当なエスケープは．
検索エントリはテーブルの１２７前のエントリより前で
あることを示すＪ　＋１　２８オフセット、および検索
エントリが１２７後のエントリより後であることを示す
−１２８のオフセットである。

Ｄ．実施例 本発明における検索テーブルにおいて、ハッシュ関数は
各キーにおいてある値を生成するのに使用される。本実
施例において使用されるハッシュ関数は以下に示す通り
である。

ハツシュ関数 ｆ（Ａ）＝ｉ，ｆ（Ｂ）＝２，．．ｙｒ（Ｚ）＝２６ｈ
ａｓｈ　（″ＡＢＣ″）＝（ｆ（Ａ）十ｆ（Ｂ）＋ｆ（
Ｃ））ｍｏｄ１０このハツシュ関数値を計算するいくつ
かのサンプル・コードを以下に示す。

ＩＮＰＵＴ　　　ＡＳ ＳＵＭ＝Ｏ ＦＯＲ　　Ｉ　＝　Ｉ　　ＴＯ　　ＬＥＮ（ＡＳ）ＳＵ
Ｍ　＝　ＳＵＭ＋ＡＳＣ（ＭＩＤＳ（ＡＳ，Ｉ，１））
−ＡＳＣ（″ａ”）＋１ ＮＥＸＴ ＰＲＩＮＴ　　ＳＵＭ　　ＭＯＤ　　　１０上記のハツ
シュ関数の意味は、キーの各文字はアルファベットに対
応した１から２６までの値を持つということである。各
文字の値は加算される。

加算がキー数−１の値に達すると、加算はＯＫ戻り繰シ
返される。第１Ａ図に示す場合、キー数は１０である。

したがって、ハツシュ関数は各キーに対して０から９ま
での値を生成する。第１Ａ図は各キー１２に対するハツ
シュ関数１３の値を示す。ここではキーはラスト・ネー
ムを関連データは電話番号としてある。

第１Ｂ図に示すごとく、エントリ１６は、第１Ａ図のリ
ストの各エントリ・キーのハツシュ関数１３の値の順に
ソートされたテーブル２０中に保持されている。例えば
、キーＧｏｓｓは０のハッシュ関数値１３を持つ。従っ
て、工７　｝　’）　Ｇｏｓａは第１Ｂ図のテーブル２
０の０番の位置にある。次のハッシュ関数値は２であり
、これはＢｌｅｄｓｏｅ，Ｗｉｌｓｏｎ，およびＮａｓ
ｈ　に対応する。従って、これらのエントリは第１Ｂ図
のテープＡ／２０の次の位置に位置する。これらの３つ
のエントリはテーブル２０の第１、第２、第３のどの位
置に配置されてもいいことになるが、この実施例ではア
ルファペット順、すなわちＢｌｅｄｓｏｅが１番、Ｎａ
ａｈが２番、そしてＷ目ｓｏｎが３番の位置を占めてい
る。これはすなわち、オフセット・ハッシング検索テー
ブルにおいて、いくつかのキーが同じ値になったときの
ＦＩＮＤ処理の際Ｋ２進サーチ、あるいはソート・リニ
ア●サーチを可能とする。

第１Ａ図に戻って、値２０次のハツシュ値はキ−　Ｊ　
ｏ　ｈ　ｎ　ｔｓ　ｏ　ｎ１およびＯｌｓｏｎが持つ値
５である。

再び、同じハツシュ値を持つものの２進サーチ用にテー
フル２０がアルファベット順に構成される。

すなわち、第１Ｂ図、テーブル２０に示すごとくＪｏｈ
ｎｓｏｎが次のスペース、第４番に入り、Ｏｌｓｏｎが
次の工冫ト１ハすなわち第１番に入る。

同様、次のハツシュ値は第１Ｂ図に示すととく６である
。Ｔｕｒｎｅｒ　が次の位置をしめる。次のハツシュ値
は８であり、ＢａｃｋｌｕｎｄとＭｏｒｇａｎがアルフ
ァペット順にテーブルの次のスペースを占める。次のそ
して最後のハッシュ値は９であり、Ｓｍｉｔｈがテーブ
ル２０の最後の位置を占める。

第１Ｂ図のベクトル２２が次に０から始まり、Ｎ−１ま
での位置に構成される。ここでＮはエントリ数である。

ＦＩＮＤ処理はオフセットテーブルのインデックスを獲
得するためキーのハッシュを実行する。各位置（０から
Ｎ−１）の値２４は、オフセット・ベクトル２２中の位
置１’ｌｉ１１に等しい、あるいは大きいハッシュ値を
持つテーブル２０の第１エントリを指示する。オフセッ
ト・ベクトル２２のそれぞれの″ｉ”番の位置において
、″ｉ”２３に位置Ｎｉ”の値２４が加算されたものが
、”ｉ”より大きい、あるいは等しいハツシュ値ヲ持っ
た検索テーブルの第１二ントリのインデックスである。

これは以下のように表される。

オフセット働ベクトル［ｉ］十ｉ ＝ハツシュ値を持つテーブルの第１エントリ・インデッ
クス 〉または＝ｉ 例えば、検索キーが値０にハツシュされたときは、オフ
セット・ベクトル２２の０番の位置の値が０に加算され
る。０十〇＝０であるから、テーブル２０の０番の位置
は０より太きいあるいは等しいハツシュ値を持った第１
エントリが占める。

検索キーが値１にハツシュされると、オフセット・ベク
トル２２の１番の位置の値が１に加算される。１番の位
置の値は０であるから、０＋１＝１となり、テーブル２
０の１番の位置はハツシュ値が１より大きいが等しい第
１エントリとなる。

Ｂｌｅｄｓｏａのハツシュ値は２であるので、値１にハ
ツシュされた検索キーを持つものはテーブル２０にはな
いことが即座に判明する。

他の例として、ＦＩＮＤ処理の間に検索キーが２にハツ
シュされたとする。このとき、オフセット・ベクトル中
の位置２の値が２に加算される。

位置２の値は−１であるので，２＋−１＝１となり、テ
ーブル２００１番の位置はハツシュ値が２以上のものと
なる。テーブル２０の位置１からスタートして、検索キ
ーを捜すためにノ・ツシュ値２を持つ他のエン｝　ＩＪ
−のサーチが実行される。例えば、検索キーがＣｏｘで
あると、テーブル２０中にＣｏｘがあるとすれば、それ
は旧ｅｄｓｏｅとＮａｓｈとの間にあるはずであるので
、とζでサーチは終了する。

さらに，他の例として検索キーが３に７・ツシュされた
とする。オフセット・ベクトル２２中の３番の位置の値
が３に加算される。３番の位置の値は＋１であるので３
＋１＝４となり、テーブル２０の４番の位置にはハツシ
ュ値が３以上のものが占めることになる。３または４の
値のハッシュ・キーは存在しないので４番の位置はハツ
シュ値５が割当てられる。従って、検索キーがハツシュ
値３を持つとすれば、ＦＩＮＤ処理は太き表ハツシュ値
を持つ第１エントリに行くので、検索キーはテーブル２
０には存在しないことが即座に判明する。従って、ＦＩ
ＮＤ処理は検索キーを持つエントリがないことをサーチ
を実行せずに判断できる。

例えば、第１Ｂ図に示すごとくテーブル２８のエントリ
は矢印２５で示すように位置ｈ（キー）とｈ（キー）＋
１においてオフセット・テーブル２２中でオフセットに
より区分けされている。例えば、ハツシュ値０を持つキ
ーはテーブル中の位［０と位置１の開始位置に境界があ
る。ハツシュ値１のキーは位置１の上と下の境界を持つ
。従って、テーブル２０にはハツシュ値１を持つエント
リが存在しな・いことがサーチを実行することなく判明
する。

第１Ｂ図のオフセット●ハツシュ検索テーブルはオフセ
ット・ベクトルのためのわずかな付加メモリを要するに
すぎない。このオフセット・ハツシンク構成のスペース
増加はこのオフセット・ベクトルのみである。オフセッ
トは極めて小さくで＠、第７．ｒ図のリンク・ハツシュ
法のリンク費リストよりも小さい。第１Ｂ図のオフセッ
ト・ベクトル２２のためのメモリ量は第７Ｊ図のリンク
１５とリンク・リスト１８に必要なメモリよりも小さい
ものとなる。第７Ｊ図のリンク・ハツシング法の基本的
な構成ではリンク・リスト・アンカーのベクトルと各エ
ンドリ中に保持されたリンク１５を必要とする。本発明
のオフセット・ハツシング法は各エントリに対してリン
クを必要としない。

このために追加のメモリ・スペースが小さくなる。

さらに、オフセット・ベクトル２２に必要なメモリの総
量は第６Ａ〜６５図に示すオープン・アドレツシング検
索テーブルに必要な追加メモリの１０９６から２０％よ
りも小さい。

オフセット・ベクトルの二ントリ・サイズは、同じハツ
シュ値を持つ対応キー・レンジの第１テーブル・エント
リの参照に必要なサイズよリモ大きくてはならない。前
に述べたように、これらオフセットは通常小さいサイズ
である。オフセット・ベクトルのためのスペースが特定
のノ・ツシュ値に対して適当なオフセットを供与しない
ような特殊な場合は、いくつかの解決策がある。新しい
ハツシュ関数が選択され、テーブル・エントリに適用さ
れる。これが適当なオフセツ．ト・ベクトル・スペース
に適応するオフセットを与えることとなる。他の解決策
はオフセットがオフセット・ベクトル中に保持可能な範
囲よりも大きいことを示すためにオフセット値の絶対値
における最大値（正でも負でも可）を供与することであ
る。この場合、サーチ幅はオフセット幅よりも大であり
、検索キーのハツシュ値外のハツシュ値ヲ含む。

テーブルが完全に満たされていない場合は、未使用テー
ブル・エントリが予約キーの値が検索可能なキーより大
きいことを示すか、または各テーブル・エントリが各々
特定フラグを持ち、それによってその使用の有無を示す
。

第１Ｂ図に示す本発明のオフセット・ノ１ノシング法は
第７Ｊ図に示すリンク・ハッシング法と同じオーダの検
索時間を保持する。どちらの場合も最初のハツシュはエ
ントリ・パケットのサーチに続いて実行される。しかし
、本発明のオフセット・ハツシング法では同じノ・ツシ
ュ値を持つエントリは連続しておシ、オフセット・テー
ブルのｈ（キー）．！：ｈ（キー）＋１との位置のオフ
セットにより限定されている。従って、オフセット・ハ
ッシング法は、テーブル２８における第２サーチが連続
エントリ中で実行され、リンク・リストを持たないので
なお一層高速となる。同じノ・ツシュ値ヲ持つ連続エン
トリはオフセット・ハッシング法に他の速度的効果をも
たらす。さらに、本発明で採用されているデータの良好
な配置は仮想メモリにおけるページ不在を削減する。

以下に示すプログラム・コードは本発明のオフセット検
索テーブルの生成を説明したものである。

グロシージャー構成 一デープル中に記憶されたＮエン｝　ＩＪに関するリス
トから、サイズＮのオフセット検索テープルを構成する
。

開始 リストからＮエントリをテーブル中に挿入する。

テーブル・エントリの各々にノ・ツシュ関数を適用する
。

ハツシュ値ＫＫつでテーブル・エントリヲソートする。

同じハツシュ値はキーに従ってソートする。

一一オフセット・ベクトルの生成。

ＯＦＦＳＥＴ　　ＶＥＣＴＯＲ［０｝　　：０；ｆｏｒ
　　Ｉ　　＝１　　ｔｏ　　Ｎ　−１　　ｄｏＯＦＦＳ
ＥＴ　　ＶＥＣＴＯＲ［Ｉコ　　：：ＯＦＦＳＥＴ　Ｖ
ＦＪＣＴＯＲ［Ｉ−１］　；ｗｈｉｌｅ　　ＯＦＦＳＥ
Ｔ−ＶＥＣＴＯＲ［Ｉ］＋（Ｎａ　ｎ　ｄ　　　　ＨＡ
ＳＨ（ＴＡＢＬＥ　［ＯＦＦＳＥＴ−ＶＥＣＴＯＲ［■
コ＋■コＫＥＹ） 〈Ｉ ｄｏ ＯＦＦＳＥＴ−ＶＥＣＴＯＲ　［１］　　：ＯＦＦＳＥ
Ｔ　　ＶＥＣＴＯＲ　［Ｉ］　　＋　１　；ｅｎｄ　　
ｗｈｉｌｅ； ｅｒｌｄ　　ｆｏｒ； ｅｎｄｐｒｏｃｅｄｕｒｅ　　ｃｏｎｓｔｒｕｃｔ；こ
のプログラム言語をフローに示すと第６図のごとくなる
。オフセット検索テーブルの構成はエントリのリス｝Ｎ
によってステップ８０から開始される。これらのエント
リはステップ８１においてテーブルに挿入されるステッ
プ８２においてこれらのエントリの各々に対してノ・ツ
シュ関数が適用される。ステップ８６において、ノ〜ツ
シュ値に従って，同じハツシュ値に対してはキーの値に
従ってテーブルの記憶が行なわれる。ζとまででテーブ
ル・エントリが完成する。ステップ８４−９２ではオフ
セット・ベクトルを生成する。ステップ８４において、
インデックス０において、オフセット・ベクトル中の第
１エントリは０にセットされる。オフセット・ベクトル
に対するインデックス、初期設定Ｉがステップ８５で１
にセットされる。ステップ８６でＩがＮよりも小さい間
は、ステップ８７からステップ９１が繰り返される。

一方、オフセット・ベクトルが完成し、ステップ９２で
手続きが完了する。ステップ８７において、夏によって
インデックスされたオフセット・ベクトルの初期値がＩ
−１によるインデックス・オフセット・ベクトルの値か
ら得られる。この値ＯＦＦは，ＯＦＦの加算値プラスＩ
がＮに等しくなるまで（ステップ８８），あるいはイン
デックスＯＦＦ−１−Ｉに保持されたテーブル・エント
リのキーのハツシュがＩより大きいか等しい（ステップ
８９）場合には、ステップ９０において増分される。

ステップ８８、８９、９０におけるＯＦＦの増分が終了
すると、インデックス■のオフセット・ベクトルはＯＦ
Ｆの値を指定し、ステップ９１においてオフセット・ベ
クトルの次のエントリをインデックスするためにｌが増
分される。

以下に検索キーに関連するデータの検索に使用可能なｆ
ｉｎｄ処理を実行するプログラム言語コードを示す。

ｏｐｅｒａｔｉｏｎ　　ｆｉｎｄ（Ｋ）一一テーブル中
に検索キーが存在する場合は、その検索キー、Ｋに等し
いテーブル・エントリのインデックスに戻り、存在しな
い場合は−１にもどる。

ｂｅｇｉｎ −−データは０からＮ−１の値によってインデックスさ
れたオフセット・−ベクトルおよび，長さＮのテーブル
を持つと仮定する。

Ｈ　：＝ＨＡＳＨ（Ｋ）；　−一注：Ｈは０からＮ−１
一一検索キーを持つ第１エントリのインデックスにＪを
セット Ｊ　：＝ＯＦＦＳＥＴ　ＶＥＣＴＯＲ［Ｈ］　十Ｈ；一
検索キーを持つ最終エントリのインデックスより１つ大
のものにリミット２をセットｉｆＨ＝Ｎ−ｆ ｔｈｅｎ　Ｚ　　：＝　Ｎ ｅｌｓｅ　Ｚ　：＝　ＯＦＦＳＥＴ−ＶＥＣＴＯＲ［Ｈ
＋１］　；−−一Ｋに対するサーチ・レンジをＪからＺ
−１とする。

ｗｈｔｌｅ　Ｊ　（　Ｚ　ａｎｄ　ＴＡＢＬＥ　［Ｊ］
　．ＫＥＹ　　（　Ｋ　ｄｏＪ：＝Ｊ＋１； −−Ｋを発見できた？ ｉｆ　　Ｊ　＝Ｚ　　ｏｒ　　ＴＡＢＬＥ［Ｊ］　．Ｋ
ＥＹ　）Ｋｔｈｅｎ　　ｒｅｔｕｒｎ　−１　　　−−
ＦＡＩＬＵＲＥｅｌｓｅ　　ｒｅｔｕｒｎ　　Ｊ；　　
　−−ＳＵＣＣＥＳＳｅｎｄ　　ｏｐｅｒａｔｉｏｎ　
　ｆｉｎｄ；以上のプログラム言語コードを図に示した
のが第２図である。検索キーをＫとして、ステップ６０
において、ＦＩＮＤ処理が開始する。ステップ６１にお
いて、検索キーがハツシュ値にハツシュされる。Ｎエン
トリのテーブルではハツシュ値は０からＮ−ｉの範囲で
ある。検索キーを持つであろうテーブル中の第１エント
リはステップ６２において決定され，変数Ｊが指定され
る。ステップ６２において、ハツシュ値がオフセット・
ベクトルのインデックスに使用される。仁のインデック
スのオフセット・ベクトル中の値が第１エントリを決定
したハツシュ値に加算される。検索キーを有するテーブ
ル中の最終エン｝　ＩＪはステップ６３、６４、６５で
決定され、ζこではテーブルやインデックスより１大き
い値に変数２をセットする。

ステップ６６、６７、６８が、エントリをインデックス
ＪからＺ−１の間でサーチし、検索キーが見つかった時
点でストップする。レンジすべての範囲のエントリの検
索終了時点（ステップ６６）、またはレンジ中の残シの
エントリにはキーが存在しないことが判明したとき（ス
テップ６７）においてストップする。このサーチの出力
を決定するテストがステップ６９と７０で実行される。

すべてのエントリが検索が不成功であるとステップ６９
で判断されたときはａ−１が失敗を示す意味で戻される
（ステップ７２）。ステップ７０において検索キーか発
見されると，このキーを持つテーブル・エントリのイン
デックスＪがステップ７１において戻される。さもなけ
れば、ａ−１はステップ７２において失敗を示す意味で
戻される。

Ｅ．発明の効果 上述のごとく本発明は、従来の方法に比較して、検索テ
ーブルにおけるより早いエントリの検索手段を゜従来の
′方法よりも少ないスペースの使用によって達成するも
のである。

【図面の簡単な説明】

第１Ａ図は本発明Ｋおけるオフセット・ハツシング検索
テーブル中において使用される各キーのハツシュ値を示
した図、第１Ｂ図は本発明のオフセット・ハツシュ検索
テーブルを示す図、第２図はオフセット検索テーブル中
に保持されたデータの検索処理を示すフロー図、第３図
はオフセット検索テーブルを生成するステップを示すフ
ロー図、第４図は従来のシーケンシャル・サーチ検索テ
ーブルを示す図、第５図は従来のシンプル検索テーブル
を示す図，第６Ａ〜第６Ｊ図は従来のオープン●アドレ
ツシング●ハツシング検索テーブルを生成する手段を示
す図、第６Ｋ図は第６Ａ〜６Ｊ図の検索テーブルにおい
て使用される各キーのハツシュ関数の結果値を示す図、
第７Ａ図は従来の第７Ａ〜ＺＪ図のリンク魯ハツシング
検索テーブルにおいて使用される各キーのハツシュ関数
の結果値を示す図、第７Ｂ〜第７Ｊ図は従来のリンク・
ハツシング検索テーブルの生成方法を示す図である。 く ８＼ ”＼ へ ＱＦ囚のマＩＪ）一さＱｌｌ　Ｏ）　Ｃ）　一ＪＯＨＮ
ＳＯＮ ＢＡＣＫＬＵＮＤ ＳＭＩＴ｝ｌ ＧＯＳＳ ＢＬＥＤＳＯε ＯＬＳＯＮ ＴＵＲＮＥＲ ＷＩＬＳＯＮ ＮＡＳＨ ＭＯＲＧＡＮ ＪＯＨＮＳＯＮ ＢＡＣＫＬＬＩＮＤ ＳＭｆｆＨ ＧＯＳＳ Ｏ ＢＬＥＤＳＯＥ ＯＬＳＯＮ ＴＵＲＮＥＲ ＭＯＲＧＡＮ 第７１図

Claims (9)

【特許請求の範囲】
1. （１）データ処理装置中における検索のための複数デー
   タの構成方法に関し、 上記個々のデータ要素の各々の対応検索キーのハッシュ
   値によつて決定された順に個々のデータを配列したテー
   ブルを保持するステップと、目的とするキーに等しい検
   索、キーに対応するデータ要素を持つ上記テーブル中の
   位置を決定するため、目的キーのハッシュ値と結合する
   オフセット・ベクトルを保持するステップとからなるデ
   ータ処理装置におけるデータ構成方法。
2. （２）データ処理装置中における検索のための複数デー
   タの構成装置に関し、 上記個々のデータ要素の各々の対応検索キーのハッシュ
   値によつて決定された順に個々のデータを配列したテー
   ブルと、 目的とするキーに等しい検索キーに対応するデータ要素
   を持つ上記テーブル中の位置を決定するため、目的キー
   のハッシュ値と結合するオフセット・ベクトルとからな
   るデータ処理装置におけるデータ構成装置。
3. （３）データ処理装置における情報記憶装置であり、エ
   ントリ・キーのハッシュ値に従つた順にＮ個のエントリ
   の第１ベクトルとして情報を保持する手段と、 ｉ番目の位置の値とｉの値との合計値がｉ−１より大き
   いハッシュ値を持つ上記第１ベクトルにおける情報の第
   １エントリを決定するインデツククスとなるようにｉ番
   目の位置のオフセット・ベクトルを保持する手段とを有
   することを特徴とするデータ処理装置における情報記憶
   装置。
4. （４）データ処理装置における情報記憶装置であり、情
   報のＮ個のエントリの各々のキーをハッシングする手段
   と、 上記ハッシュ・キーのハッシュ結果値に従つた順に上記
   エントリの第１ベクトル中に情報を記憶する手段と、 ｉ番目の内容とｉの値との合計がｉより大、または等し
   いハッシュ値を持つ第１ベクトル中の第１エントリを決
   定するインデックスとなるＮエントリのオフセット・ベ
   クトルを生成する手段とを有することを特徴とするデー
   タ処理装置における情報記憶装置。
5. （５）データ処理装置における情報記憶方法であり、エ
   ントリ・キーのハッシュ値に従つた順にＮ個のエントリ
   の第１ベクトルとして情報を保持するステップと ｉ番目の位置の値とｉの値との合計値がｉより小さくな
   いハッシュ値を持つ上記第１ベクトルにおける情報の第
   １エントリを決定するインデックスとなるようなｉ番目
   の位置のオフセット・ベクトルを保持するステップとを
   有することを特徴とするデータ処理装置における情報記
   憶方法。
6. （６）データ処理装置における情報記憶方法であり、情
   報のＮ個のエントリの各々のキーをハッシングするステ
   ップと、 上記ハッシュ・キーのハッシュ結果値に従つた順に上記
   エントリの第１ベクトル中に情報を記憶するステップと
   、 ｉ番目の位置の内容とｉの値との合計がｉより大、また
   は等しいハッシュ値を持つ第１ベクトル中の第１エント
   リを決定するインデックスとなるＯからＮ−１までのＮ
   エントリのオフセット・ベクトルを生成するステップと
   を有することを特徴とするデータ処理装置における情報
   記憶方法。
7. （７）データ処理装置における情報検索装置であり、エ
   ントリ・キーのハッシュ値に従つた順にＮ個のエントリ
   の第１ベクトルとして情報を保持する手段と、 ｉ番目の位置の値とｉの値との合計値がｉより小さくな
   いハッシュ値を持つ上記第１ベクトルにおける情報の第
   １エントリを決定するインデックスとなるようなｉ番目
   の位置のオフセット・ベクトルを保持する手段と、 上記オフセット・ベクトルのｉ番目の位置の一つが検索
   されるように上記情報の目的キーのハッシングを実行す
   る手段と、 上記オフセット・ベクトルのｉ番目の位置へのハッシュ
   により指示された上記第１ベクトルから情報を取り出す
   手段とからなる情報検索装置。
8. （８）データ処理装置における情報検索方法であり、エ
   ントリ・キーのハッシュ値に従つた順にＮ個のエントリ
   の第１ベクトルとして情報を保持するステップと、 ｉ番目の位置の値とｉの値との合計値がｉより小さくな
   いハッシュ値を持つ上記第１ベクトルにおける情報の第
   １エントリを決定するインデックスとなるようなｉ番目
   の位置のオフセット・ベクトルを保持するステップと、 上記オフセット・ベクトルのｉ番目の位置の一つが検索
   されるように上記情報の目的キーのハッシングを実行す
   るステップと、 上記オフセット・ベクトルのｉ番目の位置へのハッシュ
   により指示された上記第１ベクトルから情報を取り出す
   ステップとからなる情報検索方法。
9. （９）データ処理装置に記憶された情報のエントリの第
   １ベクトルを検索する方法に関し、 各エントリのキーのハッシュ値によつて決定された順番
   に上記情報のエントリの上記第１ベクトルを保持するス
   テップと、 上記第１ベクトルと同じ数のエントリを持つオフセット
   ・ベクトルを保持するステップと、オフセット・ベクト
   ル中の第１インデックスを得るために検索すべき情報の
   キーをハッシングするステップと、 情報検索を開始すべき検索位置での第１ベクトル中にお
   ける第２インデックスを得るために、得られたインデッ
   クス位置におけるオフセット・ベクトルの内容を第１イ
   ンデックスに加えるステップとを有することを特徴とす
   る情報検索方法。