JPH02156348A - 複数のハッシュ表のあふれ領域管理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 複数のハツシュ表のあふれ領域管理方法に関し、比較的
小規模のメモリ構成のコンピュータにおいて、複数のハ
ツシュ表を使用する場合、比較的十分なあふれ領域が確
保出来る、複数のハツシュ表のあふれ、領域管理方法の
提供を目的とし、メモリに、複数のハツシュ表“領域及
び、複数のハッシュ表夫々のあふれ領域として共通に使
用するメモリプールを確保し、処理手段にて、記号登録
時あふれ領域が必要になると該メモリプールよりあふれ
領域を確保して登録し、削除する時は削除し、該あふれ
領域が空になると解放するように構成する。

〔産業上の利用分野〕

本発明は、例えば、複数の映画館の予約を行う、比較的
小規模のメモリ構成のコンピュータを用いる予約システ
ムで、映画館毎に予約者を登録したり削除したりする場
合、複数のハツシュ表を利用して予約者対応の記号を登
録、削除する場合等の、複数のハツシュ表のあふれ領域
管理方法に関する。

ハツシュ表とは、記号を表（ハツシュ表）に登録する場
合、探索が短時間で出来るようにする為に、記号Ｘに対
してｎ＝１．２，３．　　・・・の整数になるようにハ
ツシュ関数をほどこし、ｎ＝ｆ（Ｘ）を求め、第７図（
Ａ）に示すハツシュ表のｆ　（ｘ）の列の１．２，３．
　　・・・の該当数字の行に登録するものである。

こうすると、記号Ｘを検索する時にハツシュ関数で計算
すれば、ハツシュ表の行の値が求まるので簡単に探索が
出来る。

一般にハツシュ関数をどのように選んでも、記号ｘ、ｙ
に対しｆ　（ｘ）　＝ｆ　（ｙ）と同じ値となり登録し
ようとしても衝突することがあり、このような場合は、
Ｘはハツシュ表に既に登録しであるので、ｙはあふれ領
域に登録し、ポインタにてリンクするようにしてｙの探
索を容易にする。

又記号ｘ、ｙ、ｚに対しｆ　（ｘ）　＝ｆ　（ｙ）　＝
ｆ　（ｚ）となった場合は、ｙ、ｚはあふれ領域に登録
し、ｙと２とは更にポインタにてリンクするようにして
２の探索を容易にする。

近年マイクロプロセッサを使用したシステムは、他の制
約からメモリを十分持つことが出来ない場合もあり、こ
のような、比較的小規模のメモリ構成のコンピュータで
、複数のハツシュ表を利用して記号を登録、削除する場
合、メモリの効率的な利用が必要になってくる。

〔従来の技術〕

従来、複数のハツシュ表を利用する場合は、夫々のハツ
シュ表に対して、予め必要と思われる十分なあふれ領域
をメモリ上で確保していた。

この場合、あふれ領域の使用量にアンバランスが生ずる
こともあり、使用量の小さいあふれ領域に割当だメモリ
領域は無駄になってしまう。

〔発明が解決しようとする課題〕

従来の方法では、無駄なメモリ領域を含み、十分大きい
メモリ領域が必要となり、比較的小規模のメモリ構成の
コンピュータでは、十分なあふれ領域が確保出来ない問
題点がある。

本発明は、比較的小規模のメモリ構成のコンピュータに
おいて、複数のハツシュ表を使用する場合比較的十分な
あふれ領域が確保出来る、複数のハツシュ表のあふれ領
域管理方法の提供を目的としている。

〔課題を解決するための手段〕

第１図は本発明の原理ブロック図である。

第１図に示す如く、メモリに、複数のハツシュ表領域１
．２．３．　　・・及び、複数のハッシュ表夫々のあふ
れ領域として共通に使用するメモリプール５を確保し、
処理手段６にて、記号登録時あふれ領域が必要になると
該メモリプール５よりあふれ領域を確保して登録し、削
除する時は削除し、該あふれ領域が空になると解放する
ようにする。

〔作　用〕

本発明によれば、予め各ハツシュ表に対してあふれ領域
を確保する従来の場合の、あふれ領域の合計よりも小さ
い領域の、各ハシシュ表夫々のあふれ領域として共通に
使用するメモリプール５をメモリ上に確保し、処理手段
６にて、記号登録時あふれ領域が必要になると該メモリ
プール５よりあふれ領域を確保して登録し、削除する時
は削除し、該あふれ領域が空になると解放するようにし
て、メモリ領域を効率的に使用するようにしているので
、比較的十分なあふれ領域が確保出来る。

〔実施例］ 第２図は本発明の実施例のメモリの割当を示す図、第３
図は本発明の実施例の登録プログラムのフローチャート
、第４図は本発明の実施例の削除プログラムのフローチ
ャート、第５図は本発明の実施例の整理プログラムのフ
ローチャート、第６図は１例の本発明を適用するコンピ
ュータの構成を示す図、第７図は本発明の実施例のハツ
シュ表。

メモリブロック、未使用リストを示す図、第８図は本発
明の実施例のメモリプールの管理表を示す図である。

複数のハツシュ表を使用する、メモリが小規模なコンピ
ュータの構成を示すと第６図に示す如くで、例えば映画
館Ａ、Ｂ、Ｃの映画館毎に予約者を登録したり削除した
りする場合等で、複数のハツシュ表を利用して予約者の
記号を登録、削除する場合、例えば、映画館Ａ用の記号
を入力すると、マイクロプロセッサｌＯは、映画館Ａ用
の記号に適用するハツシュ関数演算プログラムをＲＯＭ
１２より読み出し、演算し、演算結果によりメモリ１１
の映画館Ａ用のハツシュ表に登録したり削除したりする
。

このメモリｌｌ上でのハツシュ表及びメモリプールの割
当は第２図に示す如くで、複数のハツシュ表１．２，３
．　　・・及び、各ハツシュ表のあふれ領域として共通
に利用するメモリプール５を割当ておく。

この場合のメモリプール５の大きさは従来のあふれ領域
の合計より小さいものであり、又あふれ領域が必要にな
った時あふれ領域として割り当てるメモリブロックは、
従来のあふれ領域よりは小さいものであり、メモリブー
ル５内には多数のメモリブロックを含んでいる。

ハツシュ表を示すと、第７図（Ａ）に示す如くで、ハツ
シュ関数で求めた値のｆ　（ｘ）の列、記号（ｘ）を登
録する列、記号に対する情報を示す列、あふれ領域とリ
ンクする為にあふれ領域のアドレスを書き込むあふれポ
インタの列よりなっている。

又メモリブロックを示すと、第７図（Ｂ）に示す如くで
、記号（ｘ）を登録する列、記号に対する情報を示す列
、メモリブロックの行のアドレスを書き込むあふれポイ
ンタの列よりなっており、各行をセルと呼ぶ。

尚メモリブロックはｌセルの構成にして、削除すれば直
ちに解放出来るようにしてもよいが、メモリブロック獲
得の頻度が増加するので、通常はハツシュ表の１０％程
度のセルを有するものとしている。

そこで、例えば、第７図に示す如く１個のハツシュ表に
対しメモリブロックを獲得した場合で、登録する記号Ａ
Ａのハツシュ関数の値が２であると、記号（ｘ）の列の
２行目に登録し、登録する記号ＢＢのハツシュ関数の値
が４であると、記号（ｘ）の列の４行目に登録し、又登
録する記号ＣＣのハツシュ関数の値が５であると、記号
（ｘ）の列の５行目に登録する。

次に、登録する記号ＥＥのハツシュ関数の値が２となる
と、記号（Ｘ）の列の２行目には記号ＡＡが登録してあ
り、衝突するので、この時は、メモリプール５よりあふ
れ領域としてメモリブロックＮＯ，ｌを確保し、第７図
（Ｂ）に示すメモリブロックＮｏ、１の記号（ｘ）の列
の第１行に登録し、ハツシュ表の２行目のあふれポイン
タにメモリブロックＮ０１１の第１行目のアドレスを書
込みリンクさせる。

次に、登録する記号ＤＤのハツシュ関数の値が５となる
と、記号（Ｘ）の列の５行目には記号ＣＣが登録してあ
り、衝突するので、第７図（Ｂ）に示すメモリブロック
Ｎｏ、１の記号（Ｘ）の列の第２行に登録し、ハツシュ
表の５行目のあふれポインタにメモリブロックＮＯ６１
の第２行目のアドレスを書込みリンクさせる。

次に、登録する記号ＦＦのハツシュ関数の値が２となる
と、記号（Ｘ）の列の２行目には記号ＡＡが登録してあ
り、又あふれポインタの列の２行目にはメモリブロック
Ｎ００１−の１行目のアドレスが書き込んであるので、
この１行目をみるが、ここにも記号ＥＥが書き込んであ
るので、メモリブロックＮ００１の記号（ｘ）の列の第
３行に登録し、第１行のあふれポインタにメモリブロッ
クＮｏ、１の第３行目のアドレスを書込みリンクさせる
。

又メモリブロックを獲得すると、メモリ上に、メモリブ
ロック毎に、第７図（Ｃ）に示す如き未使用セルのリス
トを作り、未使用リストへのポインタには未使用リスト
の第１行目のセルのアドレスを書込み、又未使用リスト
の各セルのあふれポインタには次のセルのアドレスを書
込み、次々とリンクさせておき、例えば、メモリブロッ
クの第１行目のセルに記号を占き込むと、未使用リスト
の第１行目のセルは取り除き、未使用リストへのポイン
タには第２行目のセルのアドレスを書込む。

又、メモリ上に、第８図に示す如きメモリプール管理表
を設け、メモリブロックのＮＯｏ及びメモリブロックの
先頭のアドレス及びメモリブロック内のセルの数を書き
込む領域を設けておく。

又第６図のＲＯＭ１２には、処理プログラムとして、第
３図〜第５図に示す登録プログラム、削除プログラム及
び整理プログラムを格納しておき、マイクロプロセッサ
１０はこれを読み出し処理を行う。

次に、記号登録について、第３図の登録プログラムに従
って説明する。

ステップ１にて、記号のハツシュ関数を計算し、ステッ
プ２にて、ハツシュ表の計算結果の行に記号が登録され
ているかを見、登録されていなければ、ステップ３にて
ハツシュ表に登録する。

登録されていると、ステップ４にて、第７図（Ｃ）の未
使用リストへのポインタにアドレスが書き込まれている
かを見、書き込まれていなければ、ステップ５にてメモ
リプール５からメモリブロックを獲得し、ステップ６に
て、メモリブロックの各セルを第７図（Ｃ）に示す如く
、未使用リストへのポインタ及び未使用セルのリストに
てリンクさせ又ステップ７にて第８図のメモリプール管
理表に獲得したメモリブロックのアドレス及びセルの数
を登録してステップ８に進む。

ステップ８では、第７図（Ｃ）の未使用リストへのポイ
ンタのアドレスにより未使用セルを獲得し、ステップ９
にて、獲得したメモリブロックの未使用セルに内容を登
録し、上位のハツシュ表又はセルのあふれポインタに登
録したセルのアドレスを書込みリンクさせる。

次に、記号削除について第４図の削除プログラムに従っ
て説明する。

ステップ１にて、削除する記号のハツシュ関数を計算し
、ハツシュ表の行の値を求める。

■削除する記号がハツシュ表中の該当行に有り、該行の
あふれポインタにはセルのアドレスが書き込まれていな
い時は、ステップ２にて内容を削除する。

■削除する記号がハツシュ表中の該当行に有り、該行の
あふれポインタにはセルのアドレスが書き込まれている
場合は、ステップ３にてあふれポインタにて最初にリン
クしているセルの内容を上書きして削除し、ステップ４
にて、第８図のメモリプール管理表の、削除したセルの
メモリブロックＮｏ、のセルの使用数を１減じステップ
５に進む。

ステップ５ではセルの使用数の残りが使用数の約３０％
程度以下でなければ終了し、以下になればメモリブロッ
クを次に説明する整理プログラムにて整理する。

■記号がメモリブロックにある場合は、ステップ７にて
メモリブロックのあふれポインタに、次のセルのアドレ
スが書き込まれているかを見、書き込まれていればステ
ン１プ８に進み、次のリンクのセルの内容を前のセルに
上書きして削除しステップ１０に進む。

ステップ７にて次のセルが書き込まれていなければ、ス
テップ９にてセルの内容を削除しステップ１０に進む。

ステップ１０では、メモリプール管理表の、削除したセ
ルのメモリブロックＮＯ，の使用数を１減ずし、ステッ
プ１１に進む。

ステップ１１にて、セルの使用数の残りが使用数の約３
０％程度以下でなければ終了し、以下になればメモリブ
ロックを次に説明する整理プログラムにて整理する。

次に、メモリブロックの整理につき第５図のメモリブロ
ックの整理プログラムに従って説明する。

ステップ１にて、複数のハツシュ表中のあふれポインタ
を探索してステップ２に進む。

ステップ２にて、リンク先のセルが整理メモリブロック
である時は、複数のメモリブロックの未使用リストから
未使用のセルを獲得しこれに内容をコピーし、リンクし
ている上位のハツシュ表又はセルのあふれ領域のアドレ
スを、コピーした未使用リストのセルのアドレスとし、
ステップ３にてメモリプール管理表の整理したセルの該
当メモリブロツタの使用数を１：＄ｉじステップ４に進
む動作を、複数のハツシュ表の終わり迄繰り返し、ステ
ップ５に進む。

ステップ５にて、使用数が０になれば、ステップ６にて
該整理メモリブロックを解放して再度使用出来るように
する。

ステップ５にて、使用数がＯにならなければステップ７
に進み、複数のメモリブロックの未使用リストをたどり
ブロックＮＯ，を検索し、ステップ８にて、ブロックＮ
Ｏ９が整理メモリブロックならば１つ前のセルのあふれ
ポインタを次のセルのアドレスとし、ステップ９にてメ
モリプール管理表の該当ブロックＮＯ１の使用数を１減
じステップ１０に進む、ステップ７からステップｌＯ迄
の動作を、未使用リストの終わり迄繰り返す。

すると整理メモリブロックは空になるので、ステップＩ
Ｉにて整理メモリブロックを解放して再度使用出来るよ
うにする。

このようにして、メモリプールのあふれ領域としてのメ
モリブロックを動的に割当てメモリの使用効率を高めて
いるので、比較的十分なあふれ領域が確保出来る。

尚コンピュータのＯ３としてｌＴＲ０Ｎ仕様にもとづく
ものを使用すれば、タスクがメモリブロックを獲得する
には例えばシステムコールｇｅｔ−ｂｌｋを使用し、解
放する時はｔｅｌ−ｂｌｋを使用するようにすれば、メ
モリブロックの獲得解放が容易に出来る。

〔発明の効果〕

以上詳細に説明せる如く本発明によれば、あふれ領域を
割り当てるのに、複数のハツシュ表が共通にあふれ領域
として使用するメモリプールを設け、メモリプールのあ
ふれ領域としてのメモリブロックを動的に割当てメモリ
の使用効率を高めているので、比較的小規模のメモリ構
成のコンピュータで、複数のハツシュ表を利用して記号
を登録、削除する場合、比較的十分なあふれ領域が確保
出来る効果がある。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の実施例のメモリの割当を示す図、第３
図は本発明の実施例の登録プログラムのフローチャート
、 第４図は本発明の実施例の削除プログラムのフローチャ
ート、 第５図は本発明の実施例の整理プログラムのフローチャ
ート、 第６図は１例の本発明を適用するコンピュータの構成を
示す図、 第７図は本発明の実施例のハンシュ表、メモリブロック
、未使用リストを示す図、 第８図は本発明の実施例のメモリプールの管理表を示す
図である。 図において、 １．２．３はハツシュ表、 ５はメモリプール、 ６は処理手段、 １０はマイクロプロセッサ、 １１はメモリ、 １２はＲＯＭ。 Ｉ３は記号入力部を示す。 禾斃明の原理プロ・ンクロ 第 図 本尭８月／）火施イダ・１のメモリの富１当てを汀、寸
図第 １イグ・ｖ本系明８通、出するコシピユータの構成ヒホ
す図第 乙 図 メモリアールの電は１表 をホす図 第 図

Claims (1)

1. 【特許請求の範囲】 比較的小規模のメモリ構成のコンピュータで、複数のハ
   ッシュ表を利用して記号を登録、削除するに際し、 メモリに、複数のハッシュ表領域（１、２、３、・・）
   及び、複数のハッシュ表夫々のあふれ領域として共通に
   使用するメモリプール（５）を確保し、処理手段（６）
   にて、記号登録時あふれ領域が必要になると該メモリプ
   ール（５）よりあふれ領域を確保して登録し、削除する
   時は削除し、該あふれ領域が空になると解放するように
   したことを特徴とする複数のハッシュ表のあふれ領域管
   理方法。