JPH0638264B2 - ハツシユ回路 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、情報処理装置によるデータ管理システム等に
おいて用いられるハッシュ回路に関する。

［従来の技術］ 従来、ハッシュ回路のハッシュ関数については、種々の
ものが提案されており、除算法、乗算法、基本変換法、
代数符号化法などがあり、さらに、統合法として、重ね
合わせ法、折り返し法などがある。

除算法は、データの内部コードを２進数値と見なし、Ｍ
（整数…実際にはハッシュ表のサイズ）で割った剰余を
ハッシュアドレスとする方法である。

乗算法は、データをそれ自身、あるいはある定数と乗
じ、その結果のビット列の中央付近からハッシュ表サイ
ズに従って所要のビット数だけを抽出する方法である。

基本変換法は、データをｐ進数の数字列と見なし、それ
をｑ進数に変換した数字列から必要なビット数だけ取り
出す方法である（変換の演算の除算の繰り返しとな
る）。

代数符号化法は、考え方は除算法と類似しており、整数
で割る代わりに多項式表現での剰余計算を行うものであ
る。

重ね合わせ法は、データをある単位で区分し、各区分に
ついて加算、排他的論理和（XXOR）などを行うものであ
り、折り返し法は上記の各区分を折り畳むように演算を
行うものである。

なお、ハッシュ関数を解説した公知文献としては、例え
ば、「電子通信学会誌」（Vol.63,No1,pp.20-26,1980）
の弓場敏嗣著“ハッシングによる見出し探索の技法［Ｉ
Ｉ］”及び「情報処理」（VOl.21,NO.9,pp.980-991,198
0）の西原清一著“ハッシングの技法と応用”などが挙
げられる。

［発明が解決しようとする問題点］ ここで、上記除算法、乗算法、基本変換法、代数符号化
法、を各演算に対応する回路で実現する場合、回路が複
雑となり、ハードウェア規模が大きくなること、またハ
ッシュ値を得るまでの処理時間が大きいという問題点が
あった。

本発明の目的は、上記のごとき問題点を解決するもので
あり、テーブルを用いて、回路を簡単に構成でき、ハー
ドウエア規模が小さく、かつ、ハッシュ値を得るまでの
処理時間を短縮できるハッシュ回路を提供することにあ
る。

［問題点を解決するための手段と作用］ 本発明は、入力データ値に対応するハッシュ値を予め求
め、求めたハッシュ値をテーブルに格納しておくことに
より、入力データがアドレスレジスタに設定されると対
応するハッシュ値が出力されるようにしたこと、 及び入力データを予め定められた固定長に分割し（分割
された入力データの各区分を以下では部分データとい
う）、部分データ値に対応するハッシュ値（以下では中
間ハッシュ値という）を予め区分毎に求めて区分対応の
テーブルに格納しておくことにより、部分データがアド
レスレジスタに設定されると対応する中間ハッシュ値を
各テーブルから出力し、出力された各中間ハッシュ値を
統合し、入力データに対応するハッシュ値が出力される
ようにしたこと に特徴がある。

［実施例］ 第１図は本発明の理解を容易にするためのハッシュ回路
を示す図であって、入力データを区分せずにハッシュ値
を求める例である。

１２０はＲＡＭあるいはＲＯＭ上に作成された入力デー
タに対応するハッシュ値を保持するテーブル、９０はテ
ーブル１２０をアドレスするアドレスレジスタ、１００
はテーブル１２０から読み出した内容を設定するレジス
タである。

ここで、予め、入力するデータの全ての値に対してラン
ダム性の良い変換値を計算し、その変換値（ハッシュ
値）を格納するテーブル１２０を作成しておくものとす
る。具体的な変換値の例としては、乗算法における入力
するデータの値と定数との乗算結果を格納することがあ
るが、これに限られるものでは無く、テーブルとしてラ
ンダム性の良い変換値を出力するものであれば、いずれ
の方法でもよい。また、テーブルのエントリ数は入力デ
ータ長に応じて設定される。

ここで、アドレスレジスタ９０の長さＭ（入力データ長
により定まる整数）ビット、出力レジスタ１００の長さ
はＮ（予め与えられる任意の整数）ビットとする。

アドレスレジスタ９０に入力データの値を設定すること
により、テーブル１２０の内容を読み出し、出力レジス
タ１００に設定し、ハッシュ値を得るものである。

第２図は本発明の一実施例を示す図であって、１１０は
テーブル１３０，１４０，１５０から各々出力される中
間ハッシュ値を加算（ＡＤＤ）する、あるいは排他的論
理和（EXOR）をとる統合回路、１３０，１４０，１５０
は部分データ対応の中間ハッシュ値を保持するテーブル
である。

入力データを予め定められた長さの部分データに分割
し、部分データを各々対応するアドレスレジスタに設定
することにより、各部分データに対応する中間ハッシュ
値を保持するテーブル１３０，１４０，１５０の内容を
読み出す。ここで、テーブル１３０，１４０，１５０
は、予め、入力する部分データの全ての値に対してラン
ダム性の良い中間ハッシュ値を計算し、それを格納して
おくものとする。テーブルとしてはランダム性の良い中
間ハッシュ値を出力するものであれば、いずれの方法で
もよい。

ここで、入力するデータの長さＭビットで、Ｍ／２ビッ
ト固定の長さの部分データに区分し、上位Ｍ／２ビット
の部分データ１、下位Ｍ／２ビットの部分データ２をア
ドレスレジスタ９１，９２に保持し、下位Ｍ／２ビット
の部分データ２に対してはテーブルを２つ用意し（テー
ブル１４０，１５０）、中間ハッシュ値を２つ求める場
合を例に説明する。また、出力レジスタ１００の長さは
Ｎビットとする。

アドレスレジスタ９１をテーブル１３０のアドレスとし
て、テーブル１３０の該アドレスに格納されている中間
ハッシュ値を、また、アドレスレジスタ９２をアドレス
といて、テーブル１４０及び１５０の当該アドレスに格
納されている中間ハッシュ値を読み出す。次に、テーブ
ル１３０，１４０，１５０から読み出された３つの中間
ハッシュ値の排他的論理和又は３つの中間ハッシュ値の
加算値を統合回路１１０により求め、その結果を出力レ
ジスタ１００に設定し、ハッシュ値を得るものである。

この様に入力データを部分データに区分し、各部分デー
タ毎のテーブルを用意することにより、テーブルを格納
するメモリ容量を低減できる。例えば入力データ長
（Ｍ）が６４ビットの場合、第１図の構成（部分データ
に区分しない場合）では、２^６４（２の６４乗）個のエ
ントリが必要となるが、第２図の構成では、（３×２
^３２）個のエントリを持てばよい。

さらに入力データを４分割し、各区分ごとに、中間ハッ
シュ値を格納するテーブルを１つづつ用意する構成とす
れば、テーブルのエントリ数は、４×２^１６＝２^１８個
のエントリ数に減少できる。

第２図では、部分データの一方に対して２個のテーブル
１４０，１５０を用意した例で説明している。これは、
入力データのうち下位部分データに対するハッシュ値の
ランダム性を上位部分データの場合よりも向上させる必
要が有る場合に有効である。例えば入力データの内容が
住所や社員の所属コード等の場合、下位部分データより
上位部分データが共通となるデータ数が多いため、下位
部分データの方が情報としての価値が高い。そのため、
下位部分データのランダム性をより高める方が有益とな
る。

第３図は本発明の他の実施例を示す図であって、入力す
るデータの長さが長い場合において、第２図における手
法をもとに、ハッシュ値の統合を多段に行うものであ
る。入力するデータは、固定の長さで複数のデータブロ
ックに区分するものとする。

８０はハッシュ値の出力端子、２０はデータの値を保持
する入力データブロックレジスタ、４０は第２図の構成
からなるテーブルハッシュ器、１６０は各データブロッ
ク対応のハッシュ値をさらに排他的論理和等の演算処理
をほどこして、入力データブロックに対応するハッシュ
値を求める統合回路である。統合回路１６０の中で、３
０は重ね合わせ回路６０の出力内容を保持するハッシュ
レジスタ、５０はテーブルハッシュ器４０の出力内容と
ハッシュレジスタ３０の出力内容又は、ハッシュレジス
タ３０の出力内容を加工したデータとを特定の演算（加
算あるいは排他的論理和など）を施して重ね合わせてハ
ッシュレジスタ３０へ書き戻す重ね合わせ回路、６０は
ハッシュレジスタの内容を全て指定されたビット数だけ
ローテイトするローテイト回路、７０はローテイト回路
６０のローテイトするビット数を指示する信号の入力端
子である。第３図の動作は次の通りである。ここで、変
換対象の入力データブロック全体のデータ長Ｍ１（任意
の整数）が３２バイト、このデータをｍ＝８バイト即ち
Ｍ＝６４ビット単位のデータブロックに切断して処理す
る場合を説明する。

まず、入力レジスタに格納されているデータブロックの
１つを選択してテーブルハッシュ器に送出する。

テーブルハッシュ器４０は、データブロック（長さｍバ
イト）の値をアドレスとして（第２図のアドレスレジス
タ９０に格納）、テーブルの内容を読み出した中間ハッ
シュ値、または、中間ハッシュ値に簡単な演算を施して
得たデータブロックに対応するハッシュ値を出力する。
ハッシュ値が出力レジスタ１００に格納されると、格納
された内容をブロック統合回路に出力するとともに、入
力レジスタから次のデータブロックがアドレスレジスタ
に入力される様セレクタに制御信号を送る。

次に、ブロック統合回路１６０は、各データブロックに
対するテーブルハッシュ器の出力内容について順次統合
を行っていくものであり、第２図の統合回路１１０にロ
ーテイト回路を付加したものである。ブロック統合回路
１６０の動作を説明する。

ローテイト回路６０は、ローテイトするビット数を指示
する信号（端子７０から入力する）に従い、ハッシュレ
ジスタの全てのビットをそのビット数分ローテイトす
る。（なお、ローテイトするビット数は、入力するデー
タの形式（２進データ形式、文字ストリングデータ形式
など）、最大値（あるいは最大長）、ハッシュ表サイズ
などをもとに決められるものである。） 次に、重ね合わせ回路５０は、テーブルハッシュ器４０
の出力内容と、ローテイト回路６０の出力内容との特定
の演算（加算あるいは排他的理論和（EXOR）などの演
算）を施して、ハッシュレジスタ３０に書き戻す処理を
行う。（なお、ハッシュレジスタ３０において重ね合わ
せ回路５０の出力を入力するサイクルと、保持している
データを出力レジスタ２００，ローテイト回路６０に出
力するサイクルを分離する等により、出力レジスタ２０
０から処理途中の無意味なデータが出力されない様動作
させることは従来技術により容易に実現できる。） 入力レジスタのデータブロックに対して以上の処理を順
次行ってデータブロック対応に得られたハッシュ値を更
新し、全てのデータブロックについて処理を行って得ら
れたハッシュレジスタ３０の内容を出力端子８０を経由
して出力レジスタ２００に出力する。

ここで、統合回路としては、加算あるいは、排他的論理
和（EXOR）などの簡単な演算を用いてもよいし、重ね合
わせあるいは折り返しなどの方法を回路化することで、
容易に構成できる。なお、統合する手段は、これに限ら
れるものはで無く、各中間ハッシュ値または各データブ
ロックのハッシュ値の統合を行えばいずれの方法でもよ
い。

また、入力するデータの長さ、並びにハッシュ値（ハッ
シュアドレスの長さ）は任意の長さの場合においても容
易に構成できる。さらに、データ分割方法（個数、切片
長の固定／可変、等）並びにテーブルの個数が任意の場
合においても、統合の方法を変えることで容易に構成で
きる。

また、入力データを固定長の切片に区分し、その部分デ
ータのバイト幅でストリーム状に入力する場合も容易に
構成できる。

［発明の効果］ 以上説明したように、本発明によれば、１つのテーブル
あるいは複数のテーブルと簡単な統合手段を用いたハッ
シュ回路により、 （１）入力するデータの値に対してランダム性の良い変
数値を出力し、それをハッシュ値とする、あるいは、 （２）入力するデータを固定の長さで複数の切片に区分
し、その部分データの全ての値に対してランダム性の良
い変換値（中間ハッシュ値）を出力し、さらに、各部分
のデータに対するテーブルの出力内容について統合を行
なうことを、部分データの全てについて（データが終わ
るまで）繰り返して、ハッシュ値を得る ようにしたため、回路構成が簡単となり、ハードウエア
規模で小さくでき、かつ、ハッシュ値を得るまでの処理
時間を短縮できるという利点がある。

【図面の簡単な説明】

第１図は本発明の理解を容易にするためのハッシュ回路
の構成図、第２図は本発明の一実施例の構成図、第３図
は本発明の他の実施例の構成図である。 ２０…入力レジスタ、３０…ハッシュレジスタ、４０…
テーブルハッシュ器、５０…重ね合わせ回路、６０…ロ
ーテイト回路、８０…ハッシュアドレスの出力端子、９
０…アドレスレジスタ、１００…出力レジスタ、１１
０，１６０…統合回路、１２０，１３０，１４０，１５
０…テーブル。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 北村 正 神奈川県横須賀市武１丁目2356番地 日本 電信電話株式会社情報通信処理研究所内 (56)参考文献 特開 昭59−125437（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】入力データを予め定めた長さの部分データ
   に区分し、該部分データ値に対応するハッシュ値を中間
   ハッシュ値として保持するテーブルを、該入力データの
   区分毎に１組または複数組設け、 該部分データの値を設定することにより前記テーブルの
   読み出し位置を指定するアドレスレジスタと、 前記テーブルから読み出した各部分データに対応する各
   中間ハッシュ値を演算処理して前記入力データ値に対す
   るハッシュ値として出力する統合回路と を具備することを特徴とするハッシュ回路。