JPH0357500B2 - - Google Patents
Info
- Publication number
- JPH0357500B2 JPH0357500B2 JP59242564A JP24256484A JPH0357500B2 JP H0357500 B2 JPH0357500 B2 JP H0357500B2 JP 59242564 A JP59242564 A JP 59242564A JP 24256484 A JP24256484 A JP 24256484A JP H0357500 B2 JPH0357500 B2 JP H0357500B2
- Authority
- JP
- Japan
- Prior art keywords
- hashing
- range
- function
- functions
- data
- 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.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は大規模な定義域を小規模な範囲に写像
するための技術すなわちハツシング技術に関す
る。
するための技術すなわちハツシング技術に関す
る。
ハツシングの概念はよく知られており、データ
ポイントを大きなセツトから小さなセツトに写像
することが必要であるような様々な分野に適用さ
れている。
ポイントを大きなセツトから小さなセツトに写像
することが必要であるような様々な分野に適用さ
れている。
ハツシングの適用範囲は広くたとえばその用途
の１つの例として、大規模なメモリと小規模なキ
ヤツシユとの関係がある。ここではメモリの或る
アドレスの内容をキヤツシユへ選択的に記憶する
ことが望まれる。キヤツシユにデータを記憶する
際、データを記憶すべきところのキヤツシユのア
ドレスを生成するのにハツシング関数を用いるこ
とができる。たとえばキヤツシユが256ワードの
記憶容量を有し、メモリが4096ワードの記憶容量
を有するとすれば、キヤツシユのアドレスは８ビ
ツトで指定されメモリのアドレスは12ビツトで指
定される。簡単なタイプのハツシング関数の１つ
に、メモリアドレスの初めの８ビツトをキヤツシ
ユアドレスとして用いるものがある。この場合、
所与のキヤツシユアドレスに写像できるメモリア
ドレスは16個存在する。メモリのアドレスが既に
占領されたアドレスのところへハツシングされる
ときは、キヤツシユの記憶場所の中で空いたとこ
ろを見つけるために幾つかの付加的なステツプが
試行される。このような“衝突”は出来る限り回
避することが望ましい。
の１つの例として、大規模なメモリと小規模なキ
ヤツシユとの関係がある。ここではメモリの或る
アドレスの内容をキヤツシユへ選択的に記憶する
ことが望まれる。キヤツシユにデータを記憶する
際、データを記憶すべきところのキヤツシユのア
ドレスを生成するのにハツシング関数を用いるこ
とができる。たとえばキヤツシユが256ワードの
記憶容量を有し、メモリが4096ワードの記憶容量
を有するとすれば、キヤツシユのアドレスは８ビ
ツトで指定されメモリのアドレスは12ビツトで指
定される。簡単なタイプのハツシング関数の１つ
に、メモリアドレスの初めの８ビツトをキヤツシ
ユアドレスとして用いるものがある。この場合、
所与のキヤツシユアドレスに写像できるメモリア
ドレスは16個存在する。メモリのアドレスが既に
占領されたアドレスのところへハツシングされる
ときは、キヤツシユの記憶場所の中で空いたとこ
ろを見つけるために幾つかの付加的なステツプが
試行される。このような“衝突”は出来る限り回
避することが望ましい。
メモリからのデータの選択がランダムであつ
て、かつキヤツシユに既に置かれている要素の数
がキヤツシユのサイズに比べて十分に小さいとき
は、新しいメモリアドレスと前のメモリアドレス
とが衝突する確率は比較的小さい。しかしなが
ら、メモリからのデータの選択はランダムではな
く連続的なアドレスで選択される場合がほとんど
である。上記の例でメモリの連続的なアドレスが
同じハツシングアドレスを有する確率は比較的大
きいので、この場合の衝突の頻度は容認できるも
のではない。
て、かつキヤツシユに既に置かれている要素の数
がキヤツシユのサイズに比べて十分に小さいとき
は、新しいメモリアドレスと前のメモリアドレス
とが衝突する確率は比較的小さい。しかしなが
ら、メモリからのデータの選択はランダムではな
く連続的なアドレスで選択される場合がほとんど
である。上記の例でメモリの連続的なアドレスが
同じハツシングアドレスを有する確率は比較的大
きいので、この場合の衝突の頻度は容認できるも
のではない。
入力の分布に関係なく衝突の確率を比較的小さ
く保てるようなハツシング手法を提供するため
に、これまで多大な努力がなされてきた。たとえ
ば、“ハツシユ関数のユニバーサルクラス
（Universal Classes of Hash Functions）”、コ
ンピユータおよびシステム科学ジヤーナル
（Journal of Computer and System Sciences）、
第18巻、第２号 1979年４月、143ないし154ペー
ジに示される論文には、ハツシング関数を１つだ
けでなくセツトで提供するという手法が提案され
ている。この手法によればアプリケーシヨンが走
行するたびに（またはそれ程頻繁にしなくてもよ
いならば適当な頻度で）ハツシング関数のセツト
から１つのハツシング関数が選択される。ハツシ
ング関数のセツトをユニバーサル2クラスになる
ように正確に選択すれば、入力の分布に無関係な
良好な性能が得られる。ユニバーサル2という用
語は前記論文に詳述されている。要約すると、任
意の２つのデータポイントの衝突の確率が1/b
（ただしｂはレンジＢのサイズ）以下であればハ
ツシング関数のセツトはユニバーサル2とみなさ
れる。言い換えると、そのセツトの1/bよりも多
いハツシング関数のもとでは衝突するデータポイ
ント対は存在しない。
く保てるようなハツシング手法を提供するため
に、これまで多大な努力がなされてきた。たとえ
ば、“ハツシユ関数のユニバーサルクラス
（Universal Classes of Hash Functions）”、コ
ンピユータおよびシステム科学ジヤーナル
（Journal of Computer and System Sciences）、
第18巻、第２号 1979年４月、143ないし154ペー
ジに示される論文には、ハツシング関数を１つだ
けでなくセツトで提供するという手法が提案され
ている。この手法によればアプリケーシヨンが走
行するたびに（またはそれ程頻繁にしなくてもよ
いならば適当な頻度で）ハツシング関数のセツト
から１つのハツシング関数が選択される。ハツシ
ング関数のセツトをユニバーサル2クラスになる
ように正確に選択すれば、入力の分布に無関係な
良好な性能が得られる。ユニバーサル2という用
語は前記論文に詳述されている。要約すると、任
意の２つのデータポイントの衝突の確率が1/b
（ただしｂはレンジＢのサイズ）以下であればハ
ツシング関数のセツトはユニバーサル2とみなさ
れる。言い換えると、そのセツトの1/bよりも多
いハツシング関数のもとでは衝突するデータポイ
ント対は存在しない。
こうしたハツシング技術に係る問題は、既知の
ユニバーサル2のクラスが通常非常に多数のハツ
シング関数を有するということである。たとえば
ｎビツトの名前をハツシングできるユニバーサル
２は通常は2O(n)個のハツシング関数を有する。し
たがつて選択されたハツシング関数を指定するに
はO(o)個のビツトが必要である。ここでO(o)は一
般にｎの１次関数であることを示す。また、確認
タグを生成するためにハツシングを利用する場合
に、ハツシング関数を指定するのに多くのビツト
を必要とするということはシステムとしては実用
的でない。
ユニバーサル2のクラスが通常非常に多数のハツ
シング関数を有するということである。たとえば
ｎビツトの名前をハツシングできるユニバーサル
２は通常は2O(n)個のハツシング関数を有する。し
たがつて選択されたハツシング関数を指定するに
はO(o)個のビツトが必要である。ここでO(o)は一
般にｎの１次関数であることを示す。また、確認
タグを生成するためにハツシングを利用する場合
に、ハツシング関数を指定するのに多くのビツト
を必要とするということはシステムとしては実用
的でない。
“確認およびセツトの等価性における新しいハ
ツシユ関数とその使用法（New Hash
Functions and Their Use in Authentication
and Set Equality）”、コンピユータおよびシス
テム科学ジヤーナル（Journal of Computer
and System Sciences）、第22巻、第３号、1981
年６月、265ないし279ページに示される論文に
は、選択されたハツシング関数を指定するのにわ
ずかｍ・log（ｎ）ビツトしか必要としないような
小規模ではあるが十分に強力なハツシング関数の
セツトが提案されている（ただしｍは出力される
ビツトの長さである）。この改良はハツシングの
一部の適用分野にとつては実用的であるが、それ
でもなおさらに小規模のハツシングのクラスで満
足の行く結果を得たい場合もある。すなわち、長
いデータストリングをハツシングするにはｍ・
log（ｎ）ビツトでさえ長過ぎるという場合があ
る。
ツシユ関数とその使用法（New Hash
Functions and Their Use in Authentication
and Set Equality）”、コンピユータおよびシス
テム科学ジヤーナル（Journal of Computer
and System Sciences）、第22巻、第３号、1981
年６月、265ないし279ページに示される論文に
は、選択されたハツシング関数を指定するのにわ
ずかｍ・log（ｎ）ビツトしか必要としないような
小規模ではあるが十分に強力なハツシング関数の
セツトが提案されている（ただしｍは出力される
ビツトの長さである）。この改良はハツシングの
一部の適用分野にとつては実用的であるが、それ
でもなおさらに小規模のハツシングのクラスで満
足の行く結果を得たい場合もある。すなわち、長
いデータストリングをハツシングするにはｍ・
log（ｎ）ビツトでさえ長過ぎるという場合があ
る。
以上示したように従来のハツシング関数のクラ
スはその規模が大きいという問題がある。
スはその規模が大きいという問題がある。
したがつて本発明の目的は従来に比べて小規模
のハツシング関数のクラスで、大規模なハツシン
グプログラムを必要とせずしかも衝突の確率を小
さく保てるような、ハツシングの装置を提供する
ことにある。
のハツシング関数のクラスで、大規模なハツシン
グプログラムを必要とせずしかも衝突の確率を小
さく保てるような、ハツシングの装置を提供する
ことにある。
本発明を一般的に表現すれば以下のようにな
る。
る。
入力データｘをｎ個の部分x1ないしxoに分け
て、ｂ＝pm（ただしｐは素数、ｍは正の整数）個
の出力データのうちの１個を、関数fy（ｘ）＝y0x1
＋y1x2＋y2x3＋…＋yn-1xoに従つて生成する（た
だしｙはｂ個の元から成る有限体のうちの１個の
元であり、この演算は有限体の演算である）。
て、ｂ＝pm（ただしｐは素数、ｍは正の整数）個
の出力データのうちの１個を、関数fy（ｘ）＝y0x1
＋y1x2＋y2x3＋…＋yn-1xoに従つて生成する（た
だしｙはｂ個の元から成る有限体のうちの１個の
元であり、この演算は有限体の演算である）。
以上のようにして入力データｘをｂ個の出力デ
ータのうちの１個に写像する。
ータのうちの１個に写像する。
１実施例としてこれを別な表し方をすれば次の
ようになる。
ようになる。
定義域Ａの要素ｘをサイズｂの範囲Ｂにハツシ
ングするに際し、ｘを２を底として表示しそれを
x1、x2、…、xoなるｎ個のサブストリングに分け
る。ここで各サブストリングのビツト長は、log2
(b)以下で最大の整数ｋに等しいかまたはそれより
小さい値である。ｂが素数の場合について考え
る。これは前記の表現でpmのｍ＝１の場合であ
る（ｂ＝pm＝p1；すなわち素数）。そうするとハ
ツシング関数のクラスＨは、ｂ個のハツシング関
数f0、f1、…、fb-1から成り、任意の関数fyはfy
（ｘ）＝（y0x1＋y1x2＋…＋yn-1xo（mod ｂ）で与
えられる。
ングするに際し、ｘを２を底として表示しそれを
x1、x2、…、xoなるｎ個のサブストリングに分け
る。ここで各サブストリングのビツト長は、log2
(b)以下で最大の整数ｋに等しいかまたはそれより
小さい値である。ｂが素数の場合について考え
る。これは前記の表現でpmのｍ＝１の場合であ
る（ｂ＝pm＝p1；すなわち素数）。そうするとハ
ツシング関数のクラスＨは、ｂ個のハツシング関
数f0、f1、…、fb-1から成り、任意の関数fyはfy
（ｘ）＝（y0x1＋y1x2＋…＋yn-1xo（mod ｂ）で与
えられる。
以上のようにすれば、任意の異なる要素ｘおよ
び要素x′に対してfy（ｘ）＝fy（x′）となるｙはわず
か（ｎ−１）個にすぎない。したがつてこれらの
要素の衝突する確率は（ｎ−１）／ｂである。
び要素x′に対してfy（ｘ）＝fy（x′）となるｙはわず
か（ｎ−１）個にすぎない。したがつてこれらの
要素の衝突する確率は（ｎ−１）／ｂである。
衝突の確率をさらに小さくしたいとき、または
ｂを素数以外の数にしたいときは、２段階のハツ
シングを遂行する。これに関する実施例は〔実施
例〕の後半のところで詳しく説明する。
ｂを素数以外の数にしたいときは、２段階のハツ
シングを遂行する。これに関する実施例は〔実施
例〕の後半のところで詳しく説明する。
実施例は定義域Ａから範囲Ｂへの写像に関連し
て説明する。第１の実施例では、範囲Ｂのサイズ
ｂは素数であると仮定する。この場合、クラスＨ
のハツシング関数はf0、f1、…、fb-1のｂ個のハ
ツシング関数から成る。クラスＨに属する特定の
ハツシング関数fyを用いて定義域Ａの要素ｘを範
囲Ｂにハツシングするために、要素ｘは２を底と
して表示しx1、x2、…、xoのサブストリングに分
ける。x1、x2、…、xoの各サブストリングのビツ
ト長log2(b)以下で最大の整数ｋに等しいかまたは
それよりも小さい値である。こうして範囲Ｂにお
けるハツシングされたアドレスは、 fy(x)＝（y0x1＋y1x2＋…＋yn-1xn） （mod ｂ） で与えられる。例として定義域Ａが64K（65536）
のワードを有し範囲Ｂが101個のメモリ場所（す
なわちｂ＝101）を有する場合について考える。
そうすると、クラスＨはf0ないしf100（101個）の
ハツシング関数から成り、ｋは６である。定義域
Ａの要素ｘをたとえば0111001111000101（２を底
とする表示による）とすると、要素ｘは各々最高
６ビツトまでの３つのサブストリングに分けられ
る。すなわちx1＝011100＝28、X2＝111100＝60、
およびx3＝0101＝５である。このような様式の一
貫性を維持するならば、16ビツトのワードを、４
つの４ビツトのサブストリングまたはデータスト
リングの別の組合せに分けることも可能である。
て説明する。第１の実施例では、範囲Ｂのサイズ
ｂは素数であると仮定する。この場合、クラスＨ
のハツシング関数はf0、f1、…、fb-1のｂ個のハ
ツシング関数から成る。クラスＨに属する特定の
ハツシング関数fyを用いて定義域Ａの要素ｘを範
囲Ｂにハツシングするために、要素ｘは２を底と
して表示しx1、x2、…、xoのサブストリングに分
ける。x1、x2、…、xoの各サブストリングのビツ
ト長log2(b)以下で最大の整数ｋに等しいかまたは
それよりも小さい値である。こうして範囲Ｂにお
けるハツシングされたアドレスは、 fy(x)＝（y0x1＋y1x2＋…＋yn-1xn） （mod ｂ） で与えられる。例として定義域Ａが64K（65536）
のワードを有し範囲Ｂが101個のメモリ場所（す
なわちｂ＝101）を有する場合について考える。
そうすると、クラスＨはf0ないしf100（101個）の
ハツシング関数から成り、ｋは６である。定義域
Ａの要素ｘをたとえば0111001111000101（２を底
とする表示による）とすると、要素ｘは各々最高
６ビツトまでの３つのサブストリングに分けられ
る。すなわちx1＝011100＝28、X2＝111100＝60、
およびx3＝0101＝５である。このような様式の一
貫性を維持するならば、16ビツトのワードを、４
つの４ビツトのサブストリングまたはデータスト
リングの別の組合せに分けることも可能である。
クラスＨのハツシング関数fyをたとえばfy＝f2
に選択すれば、ハツシングされるアドレスは、f2
（ｘ）＝（(1)（28）＋(2)（60）＋(4)(5)）（mod 101
）＝
57で与えられる。fy＝f5に選択すれば、ハツシン
グされるアドレスは、f5（ｘ）＝（(1)（28）＋(5)
（60）＋（25）(5)）（mod 101）＝49で与えられる。
に選択すれば、ハツシングされるアドレスは、f2
（ｘ）＝（(1)（28）＋(2)（60）＋(4)(5)）（mod 101
）＝
57で与えられる。fy＝f5に選択すれば、ハツシン
グされるアドレスは、f5（ｘ）＝（(1)（28）＋(5)
（60）＋（25）(5)）（mod 101）＝49で与えられる。
当該技術分野においてよく知られるように、デ
ータストリームの中にハツシングされるべきメツ
セージの長さに関する標識を包含させることが要
求される場合もあるが、これに関しては本発明を
構成するものではないので説明は省略する。
ータストリームの中にハツシングされるべきメツ
セージの長さに関する標識を包含させることが要
求される場合もあるが、これに関しては本発明を
構成するものではないので説明は省略する。
任意の異なる要素ｘおよび要素x′に対してfy
（ｘ）＝fy（x′）となるｙはわずか（ｎ−１）個に
すぎない（この証明は容易である）。したがつて
異なる要素ｘおよび要素x′が衝突する確率は（ｎ
−１）／ｂである。第１の実施例で使用するハツ
シング関数の数はｂ個である。したがつてハツシ
ング関数の必要数は定義域Ａの要素の数には依存
しない。このように本発明に従つたハツシング手
法は、少数のハツシング関数で長いデータストリ
ングをハツシングする場合に特に有益である。
（ｘ）＝fy（x′）となるｙはわずか（ｎ−１）個に
すぎない（この証明は容易である）。したがつて
異なる要素ｘおよび要素x′が衝突する確率は（ｎ
−１）／ｂである。第１の実施例で使用するハツ
シング関数の数はｂ個である。したがつてハツシ
ング関数の必要数は定義域Ａの要素の数には依存
しない。このように本発明に従つたハツシング手
法は、少数のハツシング関数で長いデータストリ
ングをハツシングする場合に特に有益である。
さらに、ハツシング関数を決定するのに定義域
Ａのサイズを知る必要はないという利点もある。
通常は、定義域のサイズが異なればそのデータス
トリングに対して同等の効率を有するように同じ
ハツシング関数を使用できるようその決定に際し
定義域のサイズを知る必要がある。
Ａのサイズを知る必要はないという利点もある。
通常は、定義域のサイズが異なればそのデータス
トリングに対して同等の効率を有するように同じ
ハツシング関数を使用できるようその決定に際し
定義域のサイズを知る必要がある。
衝突の確率をさらに小さくしたいとき、または
ｂが素数でないような範囲を利用したいときは、
クラスH′のハツシング関数を生成するのに２段
階の処理を用いることもできる。以下この第２の
実施例について説明する。
ｂが素数でないような範囲を利用したいときは、
クラスH′のハツシング関数を生成するのに２段
階の処理を用いることもできる。以下この第２の
実施例について説明する。
クラスH′のハツシング関数は２つの番号ｙお
よびｚで指標付けされ、要素ｘを代入すべき、ク
ラスH′に属する特定のハツシング関数の値はgz
（fy（ｘ））に等しい。すなわち、最初の関数fy
（ｘ）を用いて要素ｘを定義域Ａから範囲P′に写
像し、さらにその結果を第２の関数gzを用いて範
囲p′から範囲Ｂに写像する。
よびｚで指標付けされ、要素ｘを代入すべき、ク
ラスH′に属する特定のハツシング関数の値はgz
（fy（ｘ））に等しい。すなわち、最初の関数fy
（ｘ）を用いて要素ｘを定義域Ａから範囲P′に写
像し、さらにその結果を第２の関数gzを用いて範
囲p′から範囲Ｂに写像する。
次に関数fyおよびgzについて詳しく説明する。
ハツシングは２段階で達成される。第１段階は定
義域Ａから範囲P′への要素のハツシングに関係
し、第２段階は範囲P′から範囲Ｂへの要素のハツ
シングに関係する。範囲P′のサイズｐは範囲Ｂの
サイズｂより大きい素数となるように選択する。
第１段階のハツシング関数fy（ｘ）は先に説明し
たようにして計算されるが、この場合、その範囲
は０、１、…、ｐ−１である。すなわちハツシン
グ関数fy（ｘ）＝（y0x1＋y1x2＋…＋yn-1xo）（mod
ｐ）の形式の多項式が定義域Ａの要素を範囲Ｐに
ハツシングする。この場合、任意の２つの要素ｘ
および要素x′の衝突する可能性は（ｎ−１）／ｐ
である。したがつてｐが大きくなればなるほど、
衝突の確率は小さくなる。
ハツシングは２段階で達成される。第１段階は定
義域Ａから範囲P′への要素のハツシングに関係
し、第２段階は範囲P′から範囲Ｂへの要素のハツ
シングに関係する。範囲P′のサイズｐは範囲Ｂの
サイズｂより大きい素数となるように選択する。
第１段階のハツシング関数fy（ｘ）は先に説明し
たようにして計算されるが、この場合、その範囲
は０、１、…、ｐ−１である。すなわちハツシン
グ関数fy（ｘ）＝（y0x1＋y1x2＋…＋yn-1xo）（mod
ｐ）の形式の多項式が定義域Ａの要素を範囲Ｐに
ハツシングする。この場合、任意の２つの要素ｘ
および要素x′の衝突する可能性は（ｎ−１）／ｐ
である。したがつてｐが大きくなればなるほど、
衝突の確率は小さくなる。
第２段階のハツシング関数gzはユニバーサル2
のクラスから単に選択される。この関数はたとえ
ば最初に示した論文“ハツシユ関数のユニバーサ
ルクラス（Universal Classes of Hash
Functions）”の関数でその範囲のサイズがｂの
ものである。したがつてgzは真にユニバーサル2
であるので、第２段階での衝突の確率はせいぜい
１／ｂである。そうすると定義域Ａから範囲Ｂへの
写像における衝突の確率は、わずか１／ｂ＋（ｎ
−１）／ｐにすぎない。したがつてｐが大きくな
れば衝突の確率は1/bに近づく。
のクラスから単に選択される。この関数はたとえ
ば最初に示した論文“ハツシユ関数のユニバーサ
ルクラス（Universal Classes of Hash
Functions）”の関数でその範囲のサイズがｂの
ものである。したがつてgzは真にユニバーサル2
であるので、第２段階での衝突の確率はせいぜい
１／ｂである。そうすると定義域Ａから範囲Ｂへの
写像における衝突の確率は、わずか１／ｂ＋（ｎ
−１）／ｐにすぎない。したがつてｐが大きくな
れば衝突の確率は1/bに近づく。
これまでに説明した第２の実施例では、最終の
範囲Ｂのサイズｂを素数にしなくてもよいように
多項式のハツシングは第１段階にだけ使用され
る。中間の範囲Ｐのサイズｐは素数でなければな
らないが、多項式のハツシングの範囲はメモリ
（要素がハツシングされるところの）のサイズに
は依存しないので、ｐの値は自由に大きくでき
る。したがつて衝突の確率を減少させることがで
きる。
範囲Ｂのサイズｂを素数にしなくてもよいように
多項式のハツシングは第１段階にだけ使用され
る。中間の範囲Ｐのサイズｐは素数でなければな
らないが、多項式のハツシングの範囲はメモリ
（要素がハツシングされるところの）のサイズに
は依存しないので、ｐの値は自由に大きくでき
る。したがつて衝突の確率を減少させることがで
きる。
第１の実施例および第２の実施例はいずれも少
数のハツシング関数しか使用しないにもかかわら
ず衝突の確率を小さく保てる。したがつて小規模
のハツシングプログラムでも非常に長いデータス
トリングをハツシングでき、仮りにハツシングさ
れるデータストリングが全く同じものであるとし
てもそれが何度も衝突するということもない。
数のハツシング関数しか使用しないにもかかわら
ず衝突の確率を小さく保てる。したがつて小規模
のハツシングプログラムでも非常に長いデータス
トリングをハツシングでき、仮りにハツシングさ
れるデータストリングが全く同じものであるとし
てもそれが何度も衝突するということもない。
以上の説明により、これを実現するための回路
は当業者には容易に設計できるであろうが、簡単
な構成例を図に示したので、図を参照して回路構
成の説明をする。
は当業者には容易に設計できるであろうが、簡単
な構成例を図に示したので、図を参照して回路構
成の説明をする。
ホーナー（Horner）の法則を用いて方程式
fy（ｘ）＝（y0x1＋y1x2＋…＋yn-1xoを、
fy（ｘ）＝x1＋ｙ（x2＋ｙ（x3＋…＋ｙ（xo））…）
と変形できる。ハツシング関数fy（ｘ）のための
この変形の公式は、もとの関数をｙの乗算とxiの
加算の形で表現し直したものである。こうすれ
ば、ｙの累乗を別々に計算する必要がないので、
計算の過程における乗算の回数を減らすことがで
きる。
この変形の公式は、もとの関数をｙの乗算とxiの
加算の形で表現し直したものである。こうすれ
ば、ｙの累乗を別々に計算する必要がないので、
計算の過程における乗算の回数を減らすことがで
きる。
図に示す構成で遂行されるオペレーシヨンのシ
ーケンスは、 t1＝xo ti＝xo-i+1＋ｙ（ti−１） ｉ＝２、……、ｎ fy（ｘ）＝to で定義できる。図に示す構成（以下ハツシング機
構という）はアキユムレータ１０、アキユムレー
タ１２、加算器１４、および乗算器１６を含む。
ハツシング機構は２位相のクロツク（図示せず）
で動作する。第１のクロツク位相においては、ア
キユムレータ１０の内容が加算器１４でxiに加算
され、加算結果がアキユムレータ１２へロードさ
れる。第２のクロツク位相においては、アキユム
レータ１２の内容に乗算器１６でｙが乗算され、
乗算結果がアキユムレータ１０へロードされる。
前記第１の実施例および第２の実施例の場合は、
xiは逆の順番で加算器１４に供給される（すなわ
ちxoで始まつてx1で終わる）。しかしながら、
個々のサブストリングの番号付けは任意であるの
で、このような様式の一貫性を維持する限りは、
加算器１４にはサブストリングxiをどのような順
番で与えてもよい。
ーケンスは、 t1＝xo ti＝xo-i+1＋ｙ（ti−１） ｉ＝２、……、ｎ fy（ｘ）＝to で定義できる。図に示す構成（以下ハツシング機
構という）はアキユムレータ１０、アキユムレー
タ１２、加算器１４、および乗算器１６を含む。
ハツシング機構は２位相のクロツク（図示せず）
で動作する。第１のクロツク位相においては、ア
キユムレータ１０の内容が加算器１４でxiに加算
され、加算結果がアキユムレータ１２へロードさ
れる。第２のクロツク位相においては、アキユム
レータ１２の内容に乗算器１６でｙが乗算され、
乗算結果がアキユムレータ１０へロードされる。
前記第１の実施例および第２の実施例の場合は、
xiは逆の順番で加算器１４に供給される（すなわ
ちxoで始まつてx1で終わる）。しかしながら、
個々のサブストリングの番号付けは任意であるの
で、このような様式の一貫性を維持する限りは、
加算器１４にはサブストリングxiをどのような順
番で与えてもよい。
いずれにしても連続的なクロツクサイクルによ
るハツシング機構のシーケンスは最後のxiが加算
器１４に与えられるまで続き、最後のxiが加算器
１４に与えられた時点でのアキユムレータ１２の
内容がfy（ｘ）を表わす。
るハツシング機構のシーケンスは最後のxiが加算
器１４に与えられるまで続き、最後のxiが加算器
１４に与えられた時点でのアキユムレータ１２の
内容がfy（ｘ）を表わす。
ハツシング機構の参照番号１８の部分は値ｙの
情報源を一般的に示すものである。この部分は適
切なハードウエアまたはソフトウエアを用いて
様々な方法で実現することができる（さらに簡単
に手動的な選択を用いても実現できる）。
情報源を一般的に示すものである。この部分は適
切なハードウエアまたはソフトウエアを用いて
様々な方法で実現することができる（さらに簡単
に手動的な選択を用いても実現できる）。
第１の実施例すなわち１段階式のハツシングの
場合は、加算器１４および乗算器１６はモジユロ
ｂの装置である。ただしｂは要素ｘが写像される
べきところの範囲Ｂのサイズを定義する素数であ
る。加算器１４の出力がハツシング関数を構成す
る。第２の実施例すなわち２段階式のハツシング
の場合は、加算器１４および乗算器１６はモジユ
ロｐの装置である。ただしｐはｂより大なる素数
である。アキユムレータ１２の出力fy（ｘ）はgz
回路（図示せず）へ供給され、そこで通常の方法
によりgz（fy（ｘ））の値が計算される。
場合は、加算器１４および乗算器１６はモジユロ
ｂの装置である。ただしｂは要素ｘが写像される
べきところの範囲Ｂのサイズを定義する素数であ
る。加算器１４の出力がハツシング関数を構成す
る。第２の実施例すなわち２段階式のハツシング
の場合は、加算器１４および乗算器１６はモジユ
ロｐの装置である。ただしｐはｂより大なる素数
である。アキユムレータ１２の出力fy（ｘ）はgz
回路（図示せず）へ供給され、そこで通常の方法
によりgz（fy（ｘ））の値が計算される。
図に示すハツシング機構から得られるハツシン
グ関数出力は様々な分野に広く適用できることは
当業者には明らかであろう。たとえば大規模のデ
ータベースの要素ｘを小規模のメモリへ記憶させ
るようなシステムにおけるデータの記憶および検
索の目的に、本発明で得られるハツシング関数を
用いて記憶すべきデータをハツシングされたアド
レスと共にメモリへ供給することができる。ハツ
シングされたアドレスはアキユムレータ１２の出
力から直接得られるか（第１の実施例）または前
記gz回路から得られる（第２の実施例）。
グ関数出力は様々な分野に広く適用できることは
当業者には明らかであろう。たとえば大規模のデ
ータベースの要素ｘを小規模のメモリへ記憶させ
るようなシステムにおけるデータの記憶および検
索の目的に、本発明で得られるハツシング関数を
用いて記憶すべきデータをハツシングされたアド
レスと共にメモリへ供給することができる。ハツ
シングされたアドレスはアキユムレータ１２の出
力から直接得られるか（第１の実施例）または前
記gz回路から得られる（第２の実施例）。
他の適用例としてたとえばエラー検知の場合
は、データは対応するハツシング関数出力と共に
送ることができる。受信データが正しいかどうか
を判断するために、ハツシング関数は受信側で再
び計算されて受信されたハツシング関数の値と比
較される。
は、データは対応するハツシング関数出力と共に
送ることができる。受信データが正しいかどうか
を判断するために、ハツシング関数は受信側で再
び計算されて受信されたハツシング関数の値と比
較される。
確認タグの生成において本発明を適用する場合
もエラー検知の場合と同様にして実現できる。し
かしながら一般的にはハツシング関数の変更は安
全のためメツセージごとに行われることが望まし
く、１つのメツセージの連続的な部分を別々にハ
ツシングするのではなく１つのメツセージ全体か
ら単一のハツシング値を生成することが望ましい
ので、確認タグの手法は複雑になるであろう。確
認タグの要件に関する詳細は２番目に示した論文
“確認およびセツトの等価性における新しいハツ
シユ関数とその使用法（New Hash Functions
and Their Use in Authentication and Set
Equality）”に記載されている。
もエラー検知の場合と同様にして実現できる。し
かしながら一般的にはハツシング関数の変更は安
全のためメツセージごとに行われることが望まし
く、１つのメツセージの連続的な部分を別々にハ
ツシングするのではなく１つのメツセージ全体か
ら単一のハツシング値を生成することが望ましい
ので、確認タグの手法は複雑になるであろう。確
認タグの要件に関する詳細は２番目に示した論文
“確認およびセツトの等価性における新しいハツ
シユ関数とその使用法（New Hash Functions
and Their Use in Authentication and Set
Equality）”に記載されている。
以上説明したように、本発明によれば、従来に
比べて少数のハツシング関数しか使用しないにも
かかわらず衝突の確率を小さく保てるので、小規
模のハツシングプログラムでも非常に長いデータ
ストリングをハツシングすることができる。
比べて少数のハツシング関数しか使用しないにも
かかわらず衝突の確率を小さく保てるので、小規
模のハツシングプログラムでも非常に長いデータ
ストリングをハツシングすることができる。
図は本発明に基づくハツシング関数の値を計算
するための回路構成の例を示すブロツク図であ
る。
するための回路構成の例を示すブロツク図であ
る。
Claims (1)
- 【特許請求の範囲】 １ 入力データｘをｂ＝pm（ただしｐは素数、ｍ
は正の整数）個の出力データのセツトのうちの１
個に写像するハツシング装置であつて、 前記入力データｘを複数の部分に分けて、該部
分を順次に受け取る加算手段と、 前記加算手段の出力を累計する第１の累算手段
と、 ｂ個の元からなる有限体のうちの１個の元を選
択して出力する手段と、 前記第１の累算手段及び前記出力する手段の出
力を乗算する乗算手段と、 前記乗算手段の出力を累算し、その累算出力を
前記加算手段へ供給して前記部分と加算させる第
２の累算手段とを具備し、 前記加算手段に前記複数の部分がすべて供給さ
れた後で前記第１の累算手段の出力をハツシング
関数として取り出すようにしたことを特徴とする
ハツシング装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/567,199 US4588985A (en) | 1983-12-30 | 1983-12-30 | Polynomial hashing |
| US567199 | 1983-12-30 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60146346A JPS60146346A (ja) | 1985-08-02 |
| JPH0357500B2 true JPH0357500B2 (ja) | 1991-09-02 |
Family
ID=24266145
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59242564A Granted JPS60146346A (ja) | 1983-12-30 | 1984-11-19 | ハツシング装置 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4588985A (ja) |
| EP (1) | EP0149067B1 (ja) |
| JP (1) | JPS60146346A (ja) |
| DE (1) | DE3479253D1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013232902A (ja) * | 2007-08-06 | 2013-11-14 | Nec Corp | 伝送システムと方法ならびにプログラム |
Families Citing this family (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2136612B (en) * | 1983-03-10 | 1986-04-09 | Ferranti Plc | Word checking system |
| US5111389A (en) * | 1987-10-29 | 1992-05-05 | International Business Machines Corporation | Aperiodic mapping system using power-of-two stride access to interleaved devices |
| US5003307A (en) * | 1989-01-13 | 1991-03-26 | Stac, Inc. | Data compression apparatus with shift register search means |
| US5347652A (en) * | 1991-06-26 | 1994-09-13 | International Business Machines Corporation | Method and apparatus for saving and retrieving functional results |
| US5371499A (en) * | 1992-02-28 | 1994-12-06 | Intersecting Concepts, Inc. | Data compression using hashing |
| US5406278A (en) * | 1992-02-28 | 1995-04-11 | Intersecting Concepts, Inc. | Method and apparatus for data compression having an improved matching algorithm which utilizes a parallel hashing technique |
| US5353024A (en) * | 1992-05-01 | 1994-10-04 | Intersecting Concepts, Inc. | Method for data compression having an improved encoding algorithm which utilizes a token stacking technique |
| US5491749A (en) * | 1993-12-30 | 1996-02-13 | International Business Machines Corporation | Method and apparatus for entity authentication and key distribution secure against off-line adversarial attacks |
| US5491750A (en) * | 1993-12-30 | 1996-02-13 | International Business Machines Corporation | Method and apparatus for three-party entity authentication and key distribution using message authentication codes |
| US6134597A (en) * | 1997-05-28 | 2000-10-17 | International Business Machines Corporation | CRC hash compressed server object identifier |
| US6097725A (en) * | 1997-10-01 | 2000-08-01 | International Business Machines Corporation | Low cost searching method and apparatus for asynchronous transfer mode systems |
| US6373986B1 (en) | 1998-04-08 | 2002-04-16 | Ncr Corporation | Compression of data transmission by use of prime exponents |
| US6760752B1 (en) * | 1999-06-28 | 2004-07-06 | Zix Corporation | Secure transmission system |
| US6690667B1 (en) | 1999-11-30 | 2004-02-10 | Intel Corporation | Switch with adaptive address lookup hashing scheme |
| US6654701B2 (en) * | 2001-08-30 | 2003-11-25 | Spirent Communications | Method and apparatus for measuring protocol performance in a data communication network |
| US8341609B2 (en) * | 2007-01-26 | 2012-12-25 | Oracle International Corporation | Code generation in the presence of paged memory |
| US8413125B2 (en) * | 2007-01-26 | 2013-04-02 | Oracle International Corporation | Asynchronous dynamic compilation based on multi-session profiling to produce shared native code |
| US8037460B2 (en) * | 2007-01-26 | 2011-10-11 | Oracle International Corporation | Code persistence and dependency management for dynamic compilation in a database management system |
| CA2769682C (en) * | 2008-08-01 | 2015-03-03 | Nikolajs Volkovs | System and method for the calculation of a polynomial-based hash function and the erindale-plus hashing algorithm |
| US20140009314A1 (en) | 2012-07-06 | 2014-01-09 | International Business Machines Corporation | Efficient string hash computation |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4295124A (en) * | 1979-08-13 | 1981-10-13 | National Semiconductor Corporation | Communication method and system |
-
1983
- 1983-12-30 US US06/567,199 patent/US4588985A/en not_active Expired - Fee Related
-
1984
- 1984-11-19 JP JP59242564A patent/JPS60146346A/ja active Granted
- 1984-11-27 DE DE8484114281T patent/DE3479253D1/de not_active Expired
- 1984-11-27 EP EP84114281A patent/EP0149067B1/en not_active Expired
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013232902A (ja) * | 2007-08-06 | 2013-11-14 | Nec Corp | 伝送システムと方法ならびにプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0149067A2 (en) | 1985-07-24 |
| DE3479253D1 (en) | 1989-09-07 |
| US4588985A (en) | 1986-05-13 |
| EP0149067A3 (en) | 1985-10-02 |
| JPS60146346A (ja) | 1985-08-02 |
| EP0149067B1 (en) | 1989-08-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0357500B2 (ja) | ||
| JP4717154B2 (ja) | オフセット表を使用する完全ハッシュの生成 | |
| US6353910B1 (en) | Method and apparatus for implementing error correction coding (ECC) in a dynamic random access memory utilizing vertical ECC storage | |
| JPS5927944B2 (ja) | マトリクスデ−タ並列処理システム | |
| US4800535A (en) | Interleaved memory addressing system and method using a parity signal | |
| CN112162975A (zh) | 基于单哈希均分布隆过滤器的重复数据删除技术实现方法 | |
| US5848436A (en) | Method and apparatus for efficiently providing data from a data storage medium to a processing entity | |
| US6308249B1 (en) | Storing data in a grey code system | |
| JP2662124B2 (ja) | 高速フーリエ変換における信号シーケンス発生方法、装置およびシステム並びに高速フーリエ変換処理装置 | |
| EP1481319B1 (en) | Method and apparatus for parallel access to multiple memory modules | |
| KR20030055467A (ko) | 다단계 분할을 이용한 기억소자 할당방법 | |
| JPH0289132A (ja) | 論理アドレス生成方式 | |
| JPH11184549A (ja) | サイン／コサイン・ルックアップ・テーブル | |
| KR100954843B1 (ko) | 센서 모트에서의 블록 인덱싱 기반의 타원 곡선 암호 연산 방법, 그 장치 및 이를 기록한 기록 매체 | |
| US5134694A (en) | Method and device for the processing of address words | |
| JP2004213588A (ja) | 半導体装置 | |
| US7065606B2 (en) | Controller architecture for memory mapping | |
| JP2684752B2 (ja) | 拡張記憶制御方式 | |
| US6904505B1 (en) | Method for determining valid bytes for multiple-byte burst memories | |
| JPH01260530A (ja) | データファイル装置 | |
| JPH03179520A (ja) | データデコーダ | |
| JPS63126326A (ja) | シ−ケンシヤル復号器 | |
| JPH04101272A (ja) | データエレメント検索方法 | |
| JPH01310463A (ja) | 緩衝記憶装置 | |
| JP2000020392A (ja) | 巡回アドレス発生回路 |