JPH03164866A - ハッシュ符号化回路 - Google Patents
ハッシュ符号化回路Info
- Publication number
- JPH03164866A JPH03164866A JP1302142A JP30214289A JPH03164866A JP H03164866 A JPH03164866 A JP H03164866A JP 1302142 A JP1302142 A JP 1302142A JP 30214289 A JP30214289 A JP 30214289A JP H03164866 A JPH03164866 A JP H03164866A
- Authority
- JP
- Japan
- Prior art keywords
- hash
- data
- hash address
- bit
- key
- 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 |
|---|---|---|---|
| JP1302142A JPH03164866A (ja) | 1989-11-22 | 1989-11-22 | ハッシュ符号化回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1302142A JPH03164866A (ja) | 1989-11-22 | 1989-11-22 | ハッシュ符号化回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH03164866A true JPH03164866A (ja) | 1991-07-16 |
Family
ID=17905414
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1302142A Pending JPH03164866A (ja) | 1989-11-22 | 1989-11-22 | ハッシュ符号化回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH03164866A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7409542B2 (en) * | 2001-09-26 | 2008-08-05 | Intel Corporation | Security association management through the use of lookup tables |
| CN116189734A (zh) * | 2021-11-29 | 2023-05-30 | 美光科技公司 | 用于行地址跟踪的主草图和精细草图电路的装置、系统和方法 |
| US12592271B2 (en) | 2022-12-22 | 2026-03-31 | Micron Technology, Inc. | Apparatuses and methods for increased reliability row hammer counts |
| US12597459B2 (en) | 2021-12-29 | 2026-04-07 | Micron Technology, Inc. | Apparatuses and methods for row hammer counter mat |
-
1989
- 1989-11-22 JP JP1302142A patent/JPH03164866A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7409542B2 (en) * | 2001-09-26 | 2008-08-05 | Intel Corporation | Security association management through the use of lookup tables |
| CN116189734A (zh) * | 2021-11-29 | 2023-05-30 | 美光科技公司 | 用于行地址跟踪的主草图和精细草图电路的装置、系统和方法 |
| US12597459B2 (en) | 2021-12-29 | 2026-04-07 | Micron Technology, Inc. | Apparatuses and methods for row hammer counter mat |
| US12592271B2 (en) | 2022-12-22 | 2026-03-31 | Micron Technology, Inc. | Apparatuses and methods for increased reliability row hammer counts |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5199073A (en) | Key hashing in data processors | |
| EP0158530B1 (en) | Nonrestoring divider | |
| JPH02190928A (ja) | 除算器 | |
| JPH03164866A (ja) | ハッシュ符号化回路 | |
| US3223831A (en) | Binary division apparatus | |
| US4173789A (en) | Multiplication control system | |
| JPS58129653A (ja) | 乗算方式 | |
| JPH08202533A (ja) | 除算処理装置 | |
| KR100195719B1 (ko) | 나눗셈기 | |
| JP3917357B2 (ja) | 非線形変換方法及びプログラムを記録したコンピュータ読み取り可能な記録媒体及び非線形変換装置 | |
| EP0208238A2 (en) | High speed residue calculating apparatus | |
| US7685221B1 (en) | Efficient remainder calculation for even divisors | |
| JP3251311B2 (ja) | 数値を表わすデータのソーティング方法 | |
| JPH0471228B2 (ja) | ||
| JP3074910B2 (ja) | 除算装置 | |
| JP2708625B2 (ja) | 均質ハッシング処理方式 | |
| JP3539077B2 (ja) | 並列演算方式による除算方法 | |
| SU1688239A1 (ru) | Устройство дл делени дес тичных чисел | |
| JPH06110661A (ja) | 除算装置 | |
| JPH0370252B2 (ja) | ||
| JPS6126135A (ja) | 浮動小数点デ−タ変換回路 | |
| JPH06180640A (ja) | 除算装置及び方法 | |
| JPH02178833A (ja) | 異なるビット長のデータを加算する加算器 | |
| JPS63231621A (ja) | 演算処理装置 | |
| JPH02156329A (ja) | 剰余テーブル作成装置 |