JPS6148034A - ハツシングテ−ブルの動的サイズ変更方式 - Google Patents
ハツシングテ−ブルの動的サイズ変更方式Info
- Publication number
- JPS6148034A JPS6148034A JP59169338A JP16933884A JPS6148034A JP S6148034 A JPS6148034 A JP S6148034A JP 59169338 A JP59169338 A JP 59169338A JP 16933884 A JP16933884 A JP 16933884A JP S6148034 A JPS6148034 A JP S6148034A
- Authority
- JP
- Japan
- Prior art keywords
- hashing
- command
- symbol
- search
- symbols
- 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
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の利用分野〕
本発明は、ハツシング手法を用いた記号テーブルの検索
に係り、特に記号数が動的に大きく変化する記号テーブ
ルの検索方式に好適な、動的にハツシングテーブルと関
数を変更する方式〔発明の背景〕 従来のハツシング手法を用いた記号テーブルの検索方式
では、ハツシングテーブルの大きさや、ハツシング関数
が固定となっていたので、記号数がハツシングチープル
のエン） ’Ｊ 攻ニ近づくと、検索効率が落ちるとい
う欠点があった。
に係り、特に記号数が動的に大きく変化する記号テーブ
ルの検索方式に好適な、動的にハツシングテーブルと関
数を変更する方式〔発明の背景〕 従来のハツシング手法を用いた記号テーブルの検索方式
では、ハツシングテーブルの大きさや、ハツシング関数
が固定となっていたので、記号数がハツシングチープル
のエン） ’Ｊ 攻ニ近づくと、検索効率が落ちるとい
う欠点があった。
これを防ぐには、不必要に大きなハツシングテーブルを
作って、ハツシングチープルカ満杯になることを防ぐ必
要があり、メモリの使用効率の低下をきたしていた。
作って、ハツシングチープルカ満杯になることを防ぐ必
要があり、メモリの使用効率の低下をきたしていた。
本発明の目的は、記号数によってハツシングテーブルの
大きさを変更し、記号数が変更されていっても、検索効
率が落ちることなく、かつ常ニ不必要に大きなハツシン
グチープルヲ４−Ｊ ツ必要のない検索手法を提供する
ことにある。
大きさを変更し、記号数が変更されていっても、検索効
率が落ちることなく、かつ常ニ不必要に大きなハツシン
グチープルヲ４−Ｊ ツ必要のない検索手法を提供する
ことにある。
本発明は、電子計算機システム上で、記号名称とその対
応する値を登録するテーブルとハ。
応する値を登録するテーブルとハ。
シング手法による検索メカニズムから成る記号テーブル
検索システムにおいて、記号Ｊｋハツシング検索に用い
るハツシングチープルのサイズとハツシング関数を変更
して登録されている記号数が変動しても検索効率が落ち
ないようにすることをＲ？：ｔとするものである。
検索システムにおいて、記号Ｊｋハツシング検索に用い
るハツシングチープルのサイズとハツシング関数を変更
して登録されている記号数が変動しても検索効率が落ち
ないようにすることをＲ？：ｔとするものである。
以下、本発明の一実施例を図を用いて説明する。−１第
１図は、本発明の一実施例として、タイムシェアリング
システム（ＴＳＳ）の上に描築すレタコマンドプロファ
イルシステムの全貌を示ス。コマンドプロファイルシス
テムは、端末操作を行う各ユーザが各自のＴＳＳ環境を
作るために各種オプションや記憶値を格納するパーソナ
ルなデータ格納場所を提供するシステムである。本シス
テムでは、コマンド記号名称１という記Ｙン名称で、そ
の記号に対応するコマンド記号１直２という値を検索で
きる。第１図は、ＴＳＳ端末６から電子計算機システム
４上のＴＳＳにＬＱＧＱＮした時に、端末モニタプログ
ラム５中の切！す１化ルーチン６がコマンドプロファイ
ル用データ七ット８から仮想記憶装置上にコマンド記号
テーブル９を作成し、ＬＯＧＯＦＦ時ニ６１ 了ルーチ
ン７がコマンドプロファイル用データセント８にコマン
ド記号テーブル９の内容を格納することを表わす。ＴＳ
Ｓでは、ＬＯＧＯＮから１，０ＧＯＦＦまでの端末操作
単位を’ｒｓｓ−ｔｒショント呼び、そのＴＳＳセショ
ン中は、ｓ： ｓ Ｓのコマンドプロセッサ１１、ユー
ザ作成のプログラム１２、及びコマンドをマクロ化した
コマンドプロシジャ１３からコマンド記号マクロ群１０
を通してアクセスできる。
１図は、本発明の一実施例として、タイムシェアリング
システム（ＴＳＳ）の上に描築すレタコマンドプロファ
イルシステムの全貌を示ス。コマンドプロファイルシス
テムは、端末操作を行う各ユーザが各自のＴＳＳ環境を
作るために各種オプションや記憶値を格納するパーソナ
ルなデータ格納場所を提供するシステムである。本シス
テムでは、コマンド記号名称１という記Ｙン名称で、そ
の記号に対応するコマンド記号１直２という値を検索で
きる。第１図は、ＴＳＳ端末６から電子計算機システム
４上のＴＳＳにＬＱＧＱＮした時に、端末モニタプログ
ラム５中の切！す１化ルーチン６がコマンドプロファイ
ル用データ七ット８から仮想記憶装置上にコマンド記号
テーブル９を作成し、ＬＯＧＯＦＦ時ニ６１ 了ルーチ
ン７がコマンドプロファイル用データセント８にコマン
ド記号テーブル９の内容を格納することを表わす。ＴＳ
Ｓでは、ＬＯＧＯＮから１，０ＧＯＦＦまでの端末操作
単位を’ｒｓｓ−ｔｒショント呼び、そのＴＳＳセショ
ン中は、ｓ： ｓ Ｓのコマンドプロセッサ１１、ユー
ザ作成のプログラム１２、及びコマンドをマクロ化した
コマンドプロシジャ１３からコマンド記号マクロ群１０
を通してアクセスできる。
第２図は、コマンド記号テーブル９の詳細を示す。コマ
ンド記号テーブル９は、コマンド記号管理テーブル１４
、ハツシングテーブル１５とそのオーバー７０−テーブ
ル１６、及びコマンド記号名称−値テーブル１７から成
る。本テーブルを検索するには、コマンド記号名称をハ
ツシング関数１Ｂに渡し ハツシングテーブル中のエン
トリを求める。本エントリから記号名称を捜し当て値を
得る。もし記号名の面突が発生し、ハツシングエントリ
が重なった時には、オーバ７０−テーブルを１史用する
。オーバフローテーブルのサーチは、順に行う。
ンド記号テーブル９は、コマンド記号管理テーブル１４
、ハツシングテーブル１５とそのオーバー７０−テーブ
ル１６、及びコマンド記号名称−値テーブル１７から成
る。本テーブルを検索するには、コマンド記号名称をハ
ツシング関数１Ｂに渡し ハツシングテーブル中のエン
トリを求める。本エントリから記号名称を捜し当て値を
得る。もし記号名の面突が発生し、ハツシングエントリ
が重なった時には、オーバ７０−テーブルを１史用する
。オーバフローテーブルのサーチは、順に行う。
第３図は、ＴＳＳ端末操作者がＬＯＧＯＮフマ〉ドを投
入してＴＳＳセションを開始した時に動作する初凹化用
ルーチン６の静細を示す。
入してＴＳＳセションを開始した時に動作する初凹化用
ルーチン６の静細を示す。
本ルーチンは、コマンドプロファイル用データセクト８
からコマンド記号を読み込みコマンド１；己号テーフ′
ルに展ＩＪｉ□Ｊする。コマンドプロファイル用データ
セクト８の１長初のレコードには、記号数カ・ノンタ１
９が洛納されていて、１υ初にこのカウンタ１１白を１
１完み込み、ハツシングチープルのサイズとハツシング
関数を第４１図、第５図に示すアルゴリズムで決める。
からコマンド記号を読み込みコマンド１；己号テーフ′
ルに展ＩＪｉ□Ｊする。コマンドプロファイル用データ
セクト８の１長初のレコードには、記号数カ・ノンタ１
９が洛納されていて、１υ初にこのカウンタ１１白を１
１完み込み、ハツシングチープルのサイズとハツシング
関数を第４１図、第５図に示すアルゴリズムで決める。
その後、コマンドプロファイル；１１データセツトの第
２レコード以降に格納されているコマンド記号を一つづ
つテーブルに登録する。
２レコード以降に格納されているコマンド記号を一つづ
つテーブルに登録する。
第４図は、ハツシングテーブルのサイズを決定するアル
ゴリズム・を示ず。本アルゴリズムは、ハツシングチー
プルの検索効率が落ちないように予裕を見込み、コマン
ド記号カウンタ１９の値が０から５０までは１００エン
ドす、５１から１００までは２００エントリ、それ以上
はカウンク誼の２倍のエントリを作成している。ハツシ
ングテーブルのサイズを決めるとともに、ハツシング関
数１８ヲハツシングテーブルにできるだけ均一に振り分
ける様に、第５図のアルゴリズムで決める０ ＠５１１！；ｉ、ハクシングルＡ政のアルゴリズムを示
ス。この関数では、ハツシングテーブルのエントリ数で
記号名称をコード化して１６弗の１桁おきに抽出した値
をｔ；１っている。このため、ハツシングテーブルのサ
イズか変っても、ハツシング関数はＩ’ｔＴにハツシン
グテーブル全体をできるだけ均一に使うことになる。
ゴリズム・を示ず。本アルゴリズムは、ハツシングチー
プルの検索効率が落ちないように予裕を見込み、コマン
ド記号カウンタ１９の値が０から５０までは１００エン
ドす、５１から１００までは２００エントリ、それ以上
はカウンク誼の２倍のエントリを作成している。ハツシ
ングテーブルのサイズを決めるとともに、ハツシング関
数１８ヲハツシングテーブルにできるだけ均一に振り分
ける様に、第５図のアルゴリズムで決める０ ＠５１１！；ｉ、ハクシングルＡ政のアルゴリズムを示
ス。この関数では、ハツシングテーブルのエントリ数で
記号名称をコード化して１６弗の１桁おきに抽出した値
をｔ；１っている。このため、ハツシングテーブルのサ
イズか変っても、ハツシング関数はＩ’ｔＴにハツシン
グテーブル全体をできるだけ均一に使うことになる。
第６図は、コマンド記号を参照・登録・変更・削除する
コマンド記号マクロ群１０を示す。コマンド記号のアク
セスは、必ずこのマクロを用いる。このマクロを；１Ｂ
シてコマンド記号を登；Ｑ；Ａする時にはコマンド記号
カウンタ１９ご１増し、フマント記号を削除する時には
１減らす。このため、コマンド記号カウンタ１９は、常
に現状のコマンド記−３故が保たれる。
コマンド記号マクロ群１０を示す。コマンド記号のアク
セスは、必ずこのマクロを用いる。このマクロを；１Ｂ
シてコマンド記号を登；Ｑ；Ａする時にはコマンド記号
カウンタ１９ご１増し、フマント記号を削除する時には
１減らす。このため、コマンド記号カウンタ１９は、常
に現状のコマンド記−３故が保たれる。
第７図は、端末ｉ−☆作者がＬＯＧＯＦＦコマンドを役
人してＴＳＳセションを終了させる時１・Ｉ’ｉｉ＋
ｔ’ｓ：する終Ｊ′ルーチン７の詐≦二〇１全示す。本
ルーチンは、コマンド記号カウンタ１９をコマンドプロ
フチイル１［１データセントに１１シき込み、その後コ
マンド記号名称とｆｉｌ’ｆを書きｉΔむ。こ（−で作
成したコマンドプロファイル用データセットＧ１１ｔ、
次の機会に１，０ＧＯＮＬ／た時に読み込ま１する。
人してＴＳＳセションを終了させる時１・Ｉ’ｉｉ＋
ｔ’ｓ：する終Ｊ′ルーチン７の詐≦二〇１全示す。本
ルーチンは、コマンド記号カウンタ１９をコマンドプロ
フチイル１［１データセントに１１シき込み、その後コ
マンド記号名称とｆｉｌ’ｆを書きｉΔむ。こ（−で作
成したコマンドプロファイル用データセットＧ１１ｔ、
次の機会に１，０ＧＯＮＬ／た時に読み込ま１する。
−回のＴＳＳセションで多くのコマンド記号を登録する
と、次のＴＳＳセションでは、大きなハツシングテーブ
ルとなり検索効率か落ちない。また、ゾｊ１“ｌｉ木か
らａ Ｍ Ｄ Ｐ ＲＯＦコマンドを投入することによ
り、”ｒＳｓセション中に７１ツシングテープルサイズ
？変史することができる。
と、次のＴＳＳセションでは、大きなハツシングテーブ
ルとなり検索効率か落ちない。また、ゾｊ１“ｌｉ木か
らａ Ｍ Ｄ Ｐ ＲＯＦコマンドを投入することによ
り、”ｒＳｓセション中に７１ツシングテープルサイズ
？変史することができる。
以上の説明で明らかなように、本実施例によれば、コマ
ンド記−写のｊｌ（が増加した時には、より大きなハツ
シングテーブルを作り、減少した時には、より小さなハ
ツシングテーブル２作るので、検索効率を落さずにメモ
リを可１約できるという効果がある。
ンド記−写のｊｌ（が増加した時には、より大きなハツ
シングテーブルを作り、減少した時には、より小さなハ
ツシングテーブル２作るので、検索効率を落さずにメモ
リを可１約できるという効果がある。
本発明によれば、ハツシングテーブルを用いた検索シス
テムで、ハツシングテーブルのサイズを動的に変更でき
るので、サイズの変更から次の変更までの間に登録記号
数の増減が５０％以下であれば、平均で２回以内の検索
比較で済み・かつ記憶領域も登録記号数の２倍のエン）
ＩＪ Ｍで済むという効果がある。
テムで、ハツシングテーブルのサイズを動的に変更でき
るので、サイズの変更から次の変更までの間に登録記号
数の増減が５０％以下であれば、平均で２回以内の検索
比較で済み・かつ記憶領域も登録記号数の２倍のエン）
ＩＪ Ｍで済むという効果がある。
第１図はコマンドプロファイルシステムの全貌を表わす
ブロック図、第２図はコマンド記号の詳細を示すブロッ
ク図、第３図はコマンド記号テーブル初期化処理の詳細
を示す構成図、第４図はハツシングテーブル作成アルゴ
リズムを示す説明図、第５図はハツシング関数を示す説
明図、第６図はコマンド記号マクロ群によるアクセス処
理を示すブロック図、′Ｂ７図はコマンド記号テーブル
格納処理の詳細を示す説明図である。 １・・・コマンド記号 ２・・・コマンド記号値 ３・・・ＴＳＳ端末 ４・・・電子計Ｗ（磯システム ５・・・ｆｆ１ｉ、を末モニタプログラム６・・・初期
化ルーチン ７・・・格納ルーチン ９・・・コマンド記号テーブル １０・・・コマンド記号マクロ群 １１・・・コマンドプロセッサ １２・・・ユーザプログラム １６・・コマンドプロシジャ １４・・・コマンド記号管理テーブル １５・・・ハツシングチープル １８・・・ハツシング関数 １９・・・記号数カウンタ
ブロック図、第２図はコマンド記号の詳細を示すブロッ
ク図、第３図はコマンド記号テーブル初期化処理の詳細
を示す構成図、第４図はハツシングテーブル作成アルゴ
リズムを示す説明図、第５図はハツシング関数を示す説
明図、第６図はコマンド記号マクロ群によるアクセス処
理を示すブロック図、′Ｂ７図はコマンド記号テーブル
格納処理の詳細を示す説明図である。 １・・・コマンド記号 ２・・・コマンド記号値 ３・・・ＴＳＳ端末 ４・・・電子計Ｗ（磯システム ５・・・ｆｆ１ｉ、を末モニタプログラム６・・・初期
化ルーチン ７・・・格納ルーチン ９・・・コマンド記号テーブル １０・・・コマンド記号マクロ群 １１・・・コマンドプロセッサ １２・・・ユーザプログラム １６・・コマンドプロシジャ １４・・・コマンド記号管理テーブル １５・・・ハツシングチープル １８・・・ハツシング関数 １９・・・記号数カウンタ
Claims (1)
- １、電子計算機システム上で、記号名称とその対応する
値を登録するテーブルとハッシング手法による検索メカ
ニズムから成る記号テーブル検索システムにおいて、記
号数カウンタで検索に用いるハッシングテーブルのサイ
ズとハッシング関数を変更して登録されている記号数が
変動しても検索効率が落ちないようにすることを特徴と
するハッシングテーブルの動的サイズ変更方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59169338A JPS6148034A (ja) | 1984-08-15 | 1984-08-15 | ハツシングテ−ブルの動的サイズ変更方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59169338A JPS6148034A (ja) | 1984-08-15 | 1984-08-15 | ハツシングテ−ブルの動的サイズ変更方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6148034A true JPS6148034A (ja) | 1986-03-08 |
Family
ID=15884703
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59169338A Pending JPS6148034A (ja) | 1984-08-15 | 1984-08-15 | ハツシングテ−ブルの動的サイズ変更方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6148034A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02231675A (ja) * | 1989-01-31 | 1990-09-13 | Internatl Business Mach Corp <Ibm> | データを構成、管理又は検索するための方法及び装置 |
| JPH03245266A (ja) * | 1990-02-23 | 1991-10-31 | Casio Comput Co Ltd | メモリアクセス装置 |
| JP2003337834A (ja) * | 2002-04-29 | 2003-11-28 | Internatl Business Mach Corp <Ibm> | サイズ変更可能なキャッシュ・センシティブ・ハッシュ・テーブル |
-
1984
- 1984-08-15 JP JP59169338A patent/JPS6148034A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02231675A (ja) * | 1989-01-31 | 1990-09-13 | Internatl Business Mach Corp <Ibm> | データを構成、管理又は検索するための方法及び装置 |
| JPH03245266A (ja) * | 1990-02-23 | 1991-10-31 | Casio Comput Co Ltd | メモリアクセス装置 |
| JP2003337834A (ja) * | 2002-04-29 | 2003-11-28 | Internatl Business Mach Corp <Ibm> | サイズ変更可能なキャッシュ・センシティブ・ハッシュ・テーブル |
| US7085911B2 (en) | 2002-04-29 | 2006-08-01 | International Business Machines Corporation | Resizable cache sensitive hash table |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7653798B2 (en) | Apparatus and method for controlling memory allocation for variable size packets | |
| JP2003114816A (ja) | コンピュータメモリにインデックスを記憶するデータ構造 | |
| JP2769065B2 (ja) | デジタルデータ処理システムに使用する方法及び装置 | |
| CN111984425A (zh) | 用于操作系统的内存管理方法、装置及设备 | |
| CN108763511A (zh) | 页面中图层排版方法、装置、电子设备及存储介质 | |
| US6269363B1 (en) | Method of accessing data using approximate data structures by relaxing the operations that define same | |
| JPS6148034A (ja) | ハツシングテ−ブルの動的サイズ変更方式 | |
| JPH0991303A (ja) | データ管理装置 | |
| JP2874810B2 (ja) | キーの記憶割り当て方法 | |
| CN116467260B (zh) | 一种便于文件查找的文件记录方法、系统、终端及介质 | |
| JPS63143642A (ja) | オ−バフロ−領域管理方式 | |
| JPS62182849A (ja) | デ−タ管理方式 | |
| KR910005150A (ko) | 계산기 및 이 계산기에 이용되는 연산방법 | |
| JPH0394325A (ja) | データ処理装置 | |
| CN119201990A (zh) | 基于多层级介质的数据查询方法、装置、设备及存储介质 | |
| JP3111498B2 (ja) | レコード検索方法及びデータ処理装置 | |
| JPS58214957A (ja) | 計算機システム | |
| JPS61251941A (ja) | デ−タベ−ス管理方式 | |
| JPH08185345A (ja) | 木構造データ格納方式 | |
| CN117851517A (zh) | 身份标识方法、电子设备及存储介质 | |
| JPS63163546A (ja) | デ−タベ−ス更新処理方式 | |
| CN112308707A (zh) | 信息推荐方法、装置及电子设备 | |
| JPS5963082A (ja) | 仮想ペ−ジｉｄによるアドレス空間のペ−ジ管理方式 | |
| JPH0228846A (ja) | データ格納方式 | |
| JPS635451A (ja) | メモリアドレツシング方式 |