Orderded minimal perfect hashing functionについて

概要

論文の詳細を見る
これまで、キー番地変換の一手法として様々なハッシュ関数が提案されてきた。しかし、それらは一般にキー(整数)の集合W={W1,W2…,WN}から番地の集合I={0,1,2,…M-1}への多対1変換となるため、相異なるキーが同じ番地に変換される現象、いわゆる衝突、を生じるという問題点を持っている。従って衝突が起こった場合の処理についての研究もいろいろと行われて来たが、一方で、衝突の全く起こらない、キーから番地への1対1変換となるハッシュ関数を構成出来ないかという研究が、主に静的および探索と格納を含む準静的ファイルに対して行われてきた。そうしたハッシュ関数を、完全ハッシュ関数(Perfect Hashing Function 以下 PHF)と呼び、その中でもキーの集合の大きさと番地の集合の大きさが等しい,つまりテーブルサイズ最小のものを、最小完全ハッシュ関数 (Minimal PHF 以下 MPHF),その上、データの格納番地の順序がキーの順序に従い、そのシーケンシャル性を保つものを、順配置最小完全ハッシュ関数(Ordered MPHF 以下OMPHF)と呼ぶ,こうしたPHFの研究の中から、幾つかのPHFおよびその構成法が提案されてきた。Jaeschkeは、h(w)=⌊C/(Dw+E)⌋mod NなるMPHFを提案し、与えられたWに対し、hがMPHFになるような、整数C、D、そしてEを決めるアルゴリズムを与えた(なお、⌊・⌋は切り捨てを表す)。井上は、Jaeschkeの関数がOMPHFになるためのWに関する必要十分条件を求め、それを用いて、hがOMPHFとなるようなC、D、そしてEの決定アルゴリズムを与えた。Changは、h(w)=C mod p(w)なる素数関数pを用いたOMPHFを提案し、与えられたWに対し、hがOMPHFになるように、整数Cを決めるアルゴリズムを与えた。Changの関数は、Jaeschkeの関数に比較し、必ずOMPHFが求まると言う利点があるが、その素数関数の与え方や、整数Cの大きさがかなり大きくなることなど議論の残るところである。以上2つのハッシュ関数が、整数論の中国式剰余定理の応用であるのに対し、Sprugnoli は、違った観点から、h(w)=⌊(w+C)/D⌋なるPHFを提案し、整数C、Dを決めるアルゴリズムを与えた。Sprugnoliのそれは、データの値に偏りがある場合に、最小性が得られないという弱点はあるが、MPHFとならない場合でも、順配置の性質を持っており、(つまり、必らずOrdered PHFになる)、また先の2つと異なって、新しいデータの追加においてもそれが保持されるという点で、検討する価値はかなり大きいと思われる。そこで我々は、ここでは、検討の第1段階として、Sprugnoliの関数が、OMPHFとなるためのWに関する必要十分条件を考察する。そして、その結果を用いてOMPHFになる場合の整数C、Dの決定アルゴリズムを与える。また、OMPHFとならない場合に、Sprugnoliが導入したカッティングの手法を拡張、適用してみる。
1986-10-01

Orderded minimal perfect hashing functionについて

スポンサーリンク

概要

著者

関連論文

スポンサーリンク