JPH04286072A - テーブル高速検索方式 - Google Patents
テーブル高速検索方式Info
- Publication number
- JPH04286072A JPH04286072A JP3074333A JP7433391A JPH04286072A JP H04286072 A JPH04286072 A JP H04286072A JP 3074333 A JP3074333 A JP 3074333A JP 7433391 A JP7433391 A JP 7433391A JP H04286072 A JPH04286072 A JP H04286072A
- Authority
- JP
- Japan
- Prior art keywords
- hash
- determining means
- value
- determining
- determination means
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 claims description 11
- 239000000470 constituent Substances 0.000 claims description 8
- COCAUCFPFHUGAA-MGNBDDOMSA-N n-[3-[(1s,7s)-5-amino-4-thia-6-azabicyclo[5.1.0]oct-5-en-7-yl]-4-fluorophenyl]-5-chloropyridine-2-carboxamide Chemical group C=1C=C(F)C([C@@]23N=C(SCC[C@@H]2C3)N)=CC=1NC(=O)C1=CC=C(Cl)C=N1 COCAUCFPFHUGAA-MGNBDDOMSA-N 0.000 description 4
- 238000010586 diagram Methods 0.000 description 3
- 230000000694 effects Effects 0.000 description 2
- 230000001174 ascending effect Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、大規模コンピュータシ
ステムにおける、テーブルの高速検索方式に属する。
ステムにおける、テーブルの高速検索方式に属する。
【０００２】
【従来の技術】従来この種の高速テーブル検索方式は、
おもに以下に述べる２つの方式があった。それは、ハッ
シュテーブルを用いてテーブルを検索する方式と、構成
要素名称を昇順（または降順）に並べてバイナリーサー
チを行う方式とであった。
おもに以下に述べる２つの方式があった。それは、ハッ
シュテーブルを用いてテーブルを検索する方式と、構成
要素名称を昇順（または降順）に並べてバイナリーサー
チを行う方式とであった。
【０００３】
【発明が解決しようとする課題】上述した従来の高速テ
ーブル検索方式は、構成要素数が非常に多くなった場合
（例えば、数万以上）に、ハッシュ方式の時は、ハッシ
ュテーブルの大きさが数百〜数千の要素数に対応できて
いても、平均の同値チェイン数は１０〜１００以上の値
となるため平均１０回以上のテーブル検索数が必要とな
るか、またはバイナリーサーチ方式の時は、２分割で検
索して行くため、平均十数回のテーブル検索が必要とな
るかであり、テーブルをすぐに検索できない、という欠
点がある。
ーブル検索方式は、構成要素数が非常に多くなった場合
（例えば、数万以上）に、ハッシュ方式の時は、ハッシ
ュテーブルの大きさが数百〜数千の要素数に対応できて
いても、平均の同値チェイン数は１０〜１００以上の値
となるため平均１０回以上のテーブル検索数が必要とな
るか、またはバイナリーサーチ方式の時は、２分割で検
索して行くため、平均十数回のテーブル検索が必要とな
るかであり、テーブルをすぐに検索できない、という欠
点がある。
【０００４】
【課題を解決するための手段】本発明の端末アドレス決
定手段は、構成要素単位のテーブルがハッシュテーブル
よりポイントされているテーブル群において、ハッシュ
値を返却するハッシュ１決定手段と、前記ハッシュ１決
定手段と異なるハッシュ値を返却するハッシュ２決定手
段と、前記ハッシュテーブルから前記ハッシュ１決定手
段にて決定した値で前記構成要素単位のテーブルをポイ
ントするように組み込むテーブル作成手段と、必要に応
じて前記ハッシュテーブルからの前記構成要素単位のテ
ーブルへの同値チェインが多い場合、前記ハッシュテー
ブルから新たに別のハッシュテーブルをポイントし、前
記別のハッシュテーブルから前記ハッシュ２決定手段に
て決定した値で前記構成要素単位のテーブルをポイント
するように組み込むテーブル再構成手段と、前記ハッシ
ュ１決定手段と前記ハッシュ２決定手段とを用いて目的
の構成要素単位のテーブルを検索するテーブル検索手段
とを設け、検索対象のテーブルを少ないテーブル検索回
数で検索できることを特徴とする。
定手段は、構成要素単位のテーブルがハッシュテーブル
よりポイントされているテーブル群において、ハッシュ
値を返却するハッシュ１決定手段と、前記ハッシュ１決
定手段と異なるハッシュ値を返却するハッシュ２決定手
段と、前記ハッシュテーブルから前記ハッシュ１決定手
段にて決定した値で前記構成要素単位のテーブルをポイ
ントするように組み込むテーブル作成手段と、必要に応
じて前記ハッシュテーブルからの前記構成要素単位のテ
ーブルへの同値チェインが多い場合、前記ハッシュテー
ブルから新たに別のハッシュテーブルをポイントし、前
記別のハッシュテーブルから前記ハッシュ２決定手段に
て決定した値で前記構成要素単位のテーブルをポイント
するように組み込むテーブル再構成手段と、前記ハッシ
ュ１決定手段と前記ハッシュ２決定手段とを用いて目的
の構成要素単位のテーブルを検索するテーブル検索手段
とを設け、検索対象のテーブルを少ないテーブル検索回
数で検索できることを特徴とする。
【０００５】
【実施例】次に、本発明について図面を参照して説明す
る。
る。
【０００６】図１は、本発明の１実施例を示すブロック
図であり、後述するテーブル群２を作成するテーブル作
成手段１１と、テーブル群２を再構成するテーブル再構
成手段１２と、テーブル群２を検索するテーブル検索手
段１３と、ハッシュ値を決定するハッシュ１決定手段１
４と、ハッシュ１決定手段１４と異なるハッシュ値を決
定するハッシュ２決定手段１５と、テーブル群２とから
構成されている。図２は、本発明のテーブル群２の内容
であり、ルートテーブル２１、ルートテーブル２１より
ハッシュ１決定手段１４にて決定したハッシュ値で振り
分けられるハッシュテーブル２２、ハッシュテーブル２
２よりハッシュテーブル決定手段１５にて決定されたハ
ッシュ値で振り分けられているサブハッシュテーブル２
３、個々の構成要素単位の情報を保持しているリソース
テーブル２４、リソーステーブル２５、リソーステーブ
ル２６、リソーステーブル２７とから構成されている。
図であり、後述するテーブル群２を作成するテーブル作
成手段１１と、テーブル群２を再構成するテーブル再構
成手段１２と、テーブル群２を検索するテーブル検索手
段１３と、ハッシュ値を決定するハッシュ１決定手段１
４と、ハッシュ１決定手段１４と異なるハッシュ値を決
定するハッシュ２決定手段１５と、テーブル群２とから
構成されている。図２は、本発明のテーブル群２の内容
であり、ルートテーブル２１、ルートテーブル２１より
ハッシュ１決定手段１４にて決定したハッシュ値で振り
分けられるハッシュテーブル２２、ハッシュテーブル２
２よりハッシュテーブル決定手段１５にて決定されたハ
ッシュ値で振り分けられているサブハッシュテーブル２
３、個々の構成要素単位の情報を保持しているリソース
テーブル２４、リソーステーブル２５、リソーステーブ
ル２６、リソーステーブル２７とから構成されている。
【０００７】本発明の特徴は、図において、テーブル再
構成手段１２、ハッシュ２決定手段１５、サブハッシュ
テーブル２３を設けたことにある。
構成手段１２、ハッシュ２決定手段１５、サブハッシュ
テーブル２３を設けたことにある。
【０００８】次に、本実施例の動作について、以下に説
明する。
明する。
【０００９】個々のテーブルは、テーブルの先頭に、ど
の種類のテーブルであるかという、識別子を持っている
。これにより、ポインタで指されるテーブルが、リソー
ステーブルか、ハッシュテーブル／サブハッシュテーブ
ルか、という区別が容易につく構造となっている。
の種類のテーブルであるかという、識別子を持っている
。これにより、ポインタで指されるテーブルが、リソー
ステーブルか、ハッシュテーブル／サブハッシュテーブ
ルか、という区別が容易につく構造となっている。
【００１０】テーブル作成手段１１が、構成要素単位の
テーブルを新規にテーブル群２に登録する場合、ルート
テーブル２１からのポインタで指されるハッシュテーブ
ル２２のアドレスを得る。ハッシュテーブル２２のハッ
シュ値は、ハッシュ１決定手段１４にて決定された値で
振り分けられる。
テーブルを新規にテーブル群２に登録する場合、ルート
テーブル２１からのポインタで指されるハッシュテーブ
ル２２のアドレスを得る。ハッシュテーブル２２のハッ
シュ値は、ハッシュ１決定手段１４にて決定された値で
振り分けられる。
【００１１】リソーステーブル２７を新規に登録しよう
と、ハッシュ１決定手段１４にてハッシュ値を求めると
、エントリー２であったとする。この時、エントリー２
には、既にリソーステーブル２６がチェインされていた
場合、リソーステーブル２７は、リソーステーブル２６
内の同値チェイン用ポインタより、ポイントされる。
と、ハッシュ１決定手段１４にてハッシュ値を求めると
、エントリー２であったとする。この時、エントリー２
には、既にリソーステーブル２６がチェインされていた
場合、リソーステーブル２７は、リソーステーブル２６
内の同値チェイン用ポインタより、ポイントされる。
【００１２】次に、リソーステーブル２５を新規に登録
しようと、ハッシュ１決定手段１４にてハッシュ値を求
めると、エントリー１であったとする。この時、エント
リー１には、既にリソーステーブル２４をはじめとして
同値チェインが多い場合、テーブル作成手段１１は、同
値チェインの最後のテーブルにリソーステーブル２５を
チェインして、テーブル再構成手段１２にエントリー１
の値を渡す。
しようと、ハッシュ１決定手段１４にてハッシュ値を求
めると、エントリー１であったとする。この時、エント
リー１には、既にリソーステーブル２４をはじめとして
同値チェインが多い場合、テーブル作成手段１１は、同
値チェインの最後のテーブルにリソーステーブル２５を
チェインして、テーブル再構成手段１２にエントリー１
の値を渡す。
【００１３】テーブル再構成手段１２は、ここで、ハッ
シュテーブル２２と異なるサブハッシュテーブル２３を
確保し、エントリー１の指し示す先を、このサブハッシ
ュテーブル２３となるよう、ハッシュテーブル２２を変
更する。そして、今までエントリー１より指されていた
リソーステーブルを、同値チェインをたどりながら順次
、ハッシュ２決定手段１５を用いて得られたハッシュ値
に従って、サブハッシュテーブル２３より、ポイントす
るように変更する。
シュテーブル２２と異なるサブハッシュテーブル２３を
確保し、エントリー１の指し示す先を、このサブハッシ
ュテーブル２３となるよう、ハッシュテーブル２２を変
更する。そして、今までエントリー１より指されていた
リソーステーブルを、同値チェインをたどりながら順次
、ハッシュ２決定手段１５を用いて得られたハッシュ値
に従って、サブハッシュテーブル２３より、ポイントす
るように変更する。
【００１４】ここで、ハッシュテーブル２２では、同値
チェインであったりリソーステーブル２４とリソーステ
ーブル２５は、今度は、ハッシュ関数が異なるため、サ
ブハッシュテーブルのエントリー１はリソーステーブル
２４に、エントリー２はリソーステーブル２５に、とい
う風に、テーブルの同値チェインが解消される。
チェインであったりリソーステーブル２４とリソーステ
ーブル２５は、今度は、ハッシュ関数が異なるため、サ
ブハッシュテーブルのエントリー１はリソーステーブル
２４に、エントリー２はリソーステーブル２５に、とい
う風に、テーブルの同値チェインが解消される。
【００１５】これらのテーブルを検索するテーブル検索
手段１３は、各テーブルに付与されているテーブル識別
子を判断しながら、目的のリソーステーブルを検索する
。
手段１３は、各テーブルに付与されているテーブル識別
子を判断しながら、目的のリソーステーブルを検索する
。
【００１６】たとえば、リソーステーブル２５を検索し
たい場合、ハッシュ１決定手段１４にて得られたエント
リー１より、ハッシュテーブル２２からサブハッシュテ
ーブル２３に到達する。ここで、サブハッシュテーブル
２３の識別子が、サブハッシュテーブルを示しているた
め、テーブル検索手段１３は、当テーブルがサブハッシ
ュテーブルだと認識し、ハッシュ１決定手段１４と異な
るハッシュ値を返却するハッシュ２決定手段１５を用い
て、サブハッシュテーブルのエントリー２を得る。
たい場合、ハッシュ１決定手段１４にて得られたエント
リー１より、ハッシュテーブル２２からサブハッシュテ
ーブル２３に到達する。ここで、サブハッシュテーブル
２３の識別子が、サブハッシュテーブルを示しているた
め、テーブル検索手段１３は、当テーブルがサブハッシ
ュテーブルだと認識し、ハッシュ１決定手段１４と異な
るハッシュ値を返却するハッシュ２決定手段１５を用い
て、サブハッシュテーブルのエントリー２を得る。
【００１７】そして、このエントリーの先にポイントさ
れるリソーステーブル２５に到達することができる。
れるリソーステーブル２５に到達することができる。
【００１８】このように、本実施例によれば、ハッシュ
テーブルの同値チェインが多く存在しても、サブハッシ
ュテーブルを用いることで、それまでの同値チェインを
たどること無く、リソーステーブルの検索が短時間・短
期アクセス回数で行うことが可能になる。
テーブルの同値チェインが多く存在しても、サブハッシ
ュテーブルを用いることで、それまでの同値チェインを
たどること無く、リソーステーブルの検索が短時間・短
期アクセス回数で行うことが可能になる。
【００１９】また、ハッシュテーブルの同値チェインが
存在しない場合は、テーブル再構成手段１２がない事と
、テーブル作成手段１１は最初からハッシュテーブル２
２にサブハッシュテーブル２３をポイントするようにテ
ーブル群２を作成する事とが異なるだけで、他は変わら
ない。
存在しない場合は、テーブル再構成手段１２がない事と
、テーブル作成手段１１は最初からハッシュテーブル２
２にサブハッシュテーブル２３をポイントするようにテ
ーブル群２を作成する事とが異なるだけで、他は変わら
ない。
【００２０】
【発明の効果】以上説明したように本発明は、構成要素
数が非常に多くなった場合（例えば、数万以上）に、ハ
ッシュテーブルを２段階で使用することで、サブハッシ
ュテーブルにて同値チェインがなければ２回のテーブル
検索で、検索すべきテーブルが見つかるため、コンピュ
ータのテーブル検索のためのオーバーヘッドを大幅に削
減する効果がある。
数が非常に多くなった場合（例えば、数万以上）に、ハ
ッシュテーブルを２段階で使用することで、サブハッシ
ュテーブルにて同値チェインがなければ２回のテーブル
検索で、検索すべきテーブルが見つかるため、コンピュ
ータのテーブル検索のためのオーバーヘッドを大幅に削
減する効果がある。
【００２１】
【００２２】
【図１】本発明の実施例のブロック図である。
【００２３】
【図２】図１におけるテーブル群２の内容の例を示す図
である。
である。
【００２４】
１１ テーブル作成手段
１２ テーブル再構成手段
１３ テーブル検索手段
１４ ハッシュ１決定手段
１５ ハッシュ２決定手段
２ テーブル群
２１ ルートテーブル
２２ ハッシュテーブル
２３ サブハッシュテーブル
Claims (2)
- 【請求項１】 構成要素単位のテーブルがハッシュテ
ーブルよりポイントされているテーブル群において、ハ
ッシュ値を返却するハッシュ１決定手段と、前記ハッシ
ュ１決定手段と異なるハッシュ値を返却するハッシュ２
決定手段と、前記ハッシュテーブルから前記ハッシュ１
決定手段にて決定した値で別のハッシュテーブルをポイ
ントし、前記別のハッシュテーブルから前記ハッシュ２
決定手段にて決定した値で前記構成要素単位のテーブル
をポイントするように組み込むテーブル作成手段と、前
記ハッシュ１決定手段と前記ハッシュ２決定手段とを用
いて目的の構成要素単位のテーブルを検索するテーブル
検索手段とを設け、検索対象のテーブルを少ないテーブ
ル検索回数で検索できることを特徴とするテーブル高速
検索方式。 - 【請求項２】 構成要素単位のテーブルがハッシュテ
ーブルよりポイントされているテーブル群において、ハ
ッシュ値を返却するハッシュ１決定手段と、前記ハッシ
ュ１決定手段と異なるハッシュ値を返却するハッシュ２
決定手段と、前記ハッシュテーブルから前記ハッシュ１
決定手段にて決定した値で前記構成要素単位のテーブル
をポイントするように組み込むテーブル作成手段と、前
記ハッシュテーブルからの前記構成要素単位のテーブル
への同値チェインが多い場合、前記ハッシュテーブルか
ら新たに別のハッシュテーブルをポイントし、前記別の
ハッシュテーブルから前記ハッシュ２決定手段にて決定
した値で前記構成要素単位のテーブルをポイントするよ
うに組み込むテーブル再構成手段と、前記ハッシュ１決
定手段と前記ハッシュ２決定手段とを用いて目的の構成
要素単位のテーブルを検索するテーブル検索手段とを設
け、検索対象のテーブルを少ないテーブル検索回数で検
索できることを特徴とするテーブル高速検索方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3074333A JPH04286072A (ja) | 1991-03-15 | 1991-03-15 | テーブル高速検索方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3074333A JPH04286072A (ja) | 1991-03-15 | 1991-03-15 | テーブル高速検索方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04286072A true JPH04286072A (ja) | 1992-10-12 |
Family
ID=13544091
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3074333A Pending JPH04286072A (ja) | 1991-03-15 | 1991-03-15 | テーブル高速検索方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04286072A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011215765A (ja) * | 2010-03-31 | 2011-10-27 | Nec Corp | テーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置 |
-
1991
- 1991-03-15 JP JP3074333A patent/JPH04286072A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011215765A (ja) * | 2010-03-31 | 2011-10-27 | Nec Corp | テーブル構成方法、データアクセス方法、コンピュータプログラム、テーブル構成装置及びデータ処理装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN100377154C (zh) | 改进型多路基数树 | |
| EP0304302A2 (en) | Data retrieval system | |
| CN102867049B (zh) | 一种基于单词查找树实现的汉语拼音快速分词方法 | |
| JP2003224581A (ja) | 最長一致検索回路および方法およびプログラムおよび記録媒体 | |
| JPH04286072A (ja) | テーブル高速検索方式 | |
| JPH03174653A (ja) | キーワード管理方法およびその装置 | |
| CN101127052A (zh) | 一种有序链表节点的快速搜索方法及装置 | |
| JPH04153764A (ja) | 分散ｃｐｕの処理高速化方式 | |
| JPH0644309A (ja) | データベース管理方式 | |
| JPH10240741A (ja) | 木構造型データの管理方法 | |
| JPH0696124A (ja) | 情報検索装置 | |
| JP3061486B2 (ja) | データソート処理システム | |
| JPH09330322A (ja) | データ検索装置 | |
| JP3824091B2 (ja) | リレーショナルデータベースシステム | |
| JPH0452967A (ja) | 集合ファイルに対する論理積演算処理方式 | |
| JPH0340053A (ja) | 複数通信手順制御方式 | |
| JPH0916223A (ja) | シーケンスプログラムソートシステム | |
| JPH0667968A (ja) | オブジェクト指向におけるデータ管理方式 | |
| JPH04155521A (ja) | ソーティング処理方式 | |
| JPH02270029A (ja) | パッチエリア使用パッチ情報抽出システム | |
| JPH01258125A (ja) | レコードのキー順検索方式 | |
| JPH03216730A (ja) | 電子計算機 | |
| JPH03216729A (ja) | 電子計算機 | |
| JPH0199131A (ja) | 記号表の登録及び探索方式 | |
| JPH06149635A (ja) | レコード追加処理方法 |