ハッシュ法でのデータ管理について教えてください

質問

ハッシュ法でのデータ管理をするプログラムを作りたいんですが長いことPASCALに触ってなかったせいか全く分かりません。
どなたか教えていただけないでしょうか？？問題の概要は以下のようなものです。
表に登録するデータについては、キーは英数字からなる長さ８までの文字列でデータ本体は整数（型名はintegerでよい）です。
ハッシュ表のサイズは１１とします。
ハッシュ関数は文字列xの各文字のASCIIコードの総和を１１で割った余りとします。
さらにメニュー表示として入力した文字により行う操作を決定します。
どの文字がどのような操作を行うのかは以下のとおりです。

's' の場合： ハッシュ表に登録されている全レコードを，ハッシュ関数値毎に(キーの値とデータの両方を)すべて表示します．

'r' の場合： さらに「キーの値」と「データ」を入力し，すでに同じキーをもつデータがあれば「二重登録」として検出し，そうでなければ，そのレコードをハッシュ表に登録します．

'e' の場合： さらに「キーの値」を入力し，そのキーをもつデータがハッシュ表に登録されているならば，
そのデータを表示します．さらに削除するかどうかを入力させて，削除する選択をした場合にはそのレ
コードを削除します．そのキーをもつデータがハッシュ表にない場合には「そのキーをもつレコードが
ないこと」を出力しますが，ハッシュ表には操作を加えません．

'i' の場合： ハッシュ表に登録されている全レコードを，キーの値が小さい順に表示します．ここで「キー
の値の順」とは，文字列の辞書順のことを意味します．Pascal では，文字列a,b に対して，a がb より
辞書的順序が先(小さい) ときには「a<b」で表現できます．

'd' の場合： 「'i' の場合」の逆で，キーの値が大きい順に表示します．

'q' の場合： プログラムを終了します．具体的には，実行文部の最後の「end.」の直前までジャンプし
ます．

長くなってすいません。ちょっとしたヒントでもいいので教えていただければ幸いです。

回答No.3

sakusaker7 · ベストアンサー

function hash はこれだと、受け取る文字列が必ず8文字ということになっちゃいますね。
問題文は「最大8文字」ですから、その長さに応じて繰り返しの回数を
変えないといけません。

質問者さんが使っているPascalがどういうPascalかわかりませんが、
使える型として string とかがあったりしませんか?
あーでもあれか、使っていない部分に 0 が埋まっているということにしていいのなら
hash の返す値は文字列の長さで打ち切ったときと変わりませんね。

procedure insert はまあそれでいいんですけど、問題文ではハッシュが衝突
したときはエラーになって、登録はしないでいいみたいですから、

begin
h := hash(x);
new(p);
with p^ do
begin key := x; next := y end;
hashtable[h] := p
end;

あたらしく list 型のノードを作る必要はなくて、
hashtable[n] にすでにデータが存在するかどうかをチェックして、
先客がいたらエラー。ということでいいと思います。
ところでnext に代入している y ってどこから沸いて出た?

入力キーが 'i', 'd' のときはこの hashtable の内容をそれぞれキー文字列を
昇順/降順にソートした順序で出力すればいいですね。
表を直接ソートするとそのあとで使えなくなっちゃいますから、注意しましょう。

回答No.8

SHIMAPEE

ANo.7 お礼への回答です。Resultはご推察のとおり関数の戻り値を格納する変数です。

strLcomp、strLCopy、StrtoIntDefはDelphiの文字列用の関数です。「Delphi strLcomp」などで検索するとわかると思います。

あとコンパイラで違いがあるところは入出力ですかね。私はDelphi以外は試せません…。

回答No.7

SHIMAPEE

ANo.5の改造版の抜粋です。チェーン内でキーが昇順になるようにしてみました。WindwosXP+Delphi2007で試しました。

ANo.5で、やや不自然か、とコメントしたのは、挿入した逆順に表示されるからです。そう作ったのだからそれはそうなのですが、挿入した順に表示された方が人間にはわかりやすいと思いました。

今回、更に考えてキーの昇順にしてみました。キーの大小関係を見ながら検索、挿入するので衝突が多い場合は性能向上が図れると思います。ま、いろいろ勉強してみました、ということでご参考まで。

function search(x:charstring; var p:list): boolean;
var
previous:list;
comp:integer;
begin
Result:=false;
previous:=nil;
p:=hashtable[hash(x)];
while p<>nil do begin {ハッシュ表が空の場合、pはnilを返す。}
comp:=strLcomp(p^.key, x, sizeof(x)-1);
if comp=0 then begin {キーが一致したならば、}
Result:=true; {結果をtrueにして、}
break {pはキーが一致したレコードを返す。}
end;
if comp<0 then begin {xの方が大きければ、}
if p^.next<>nil then begin {次のレコードがあれば、}
previous:=p; {前のレコードの位置を覚えて、}
p:=p^.next; {チェーンをたどる。}
end
else {次のレコードがなければ、}
break {pはチェーン最後のレコードを返す。}
end
else begin {xの方が小さければ、}
p:=previous; {pは前のレコードの位置を返す。先頭だった場合はnilを返す。}
break
end;
end;
end;

procedure insert(x:charstring; y:integer; previous:list);
var h : integer;
newp : list;
begin
h := hash(x);
new(newp);
newp^.key := x;
newp^.othertype := y;
if previous=nil then begin {前のレコードがなければ、}
newp^.next:=hashtable[h];{先頭に挿入する。}
hashtable[h]:=newp
end
else begin {前のレコードがあれば}
newp^.next:=previous.next;{そのレコードの次に挿入する。}
previous.next:=newp; {（チェーン内のキーは昇順）}
end;
end;
　：
　：
'r':begin {登録=========================================================}
write('キー　:'); readln(strx);
write('データ:'); readln(stry);
for ix:=0 to sizeof(x)-1 do x[ix]:=#0;
strLCopy(x, PChar(strx), sizeof(x)-1);
y:=StrtoIntDef(stry, 0);
if search(x, p) then
writeln('キー"'+x+'"は既に登録されています。データ：', IntToStr(p^.othertype))
else
insert(x, y, p);
end;

お礼

Resultはsearchのことだと思うのですが,strLcomp、strLCopy、StrtoIntDefとかって何のことですか？？

回答No.6

sakusaker7

> {チェーンの先頭に挿入していますね。やや不自然か}

そんなことはありません。

単方向リストならリストの先頭に追加する方が末尾に追加するより楽です。
順序そのものに意味がないのなら、わざわざ手間のかかるやり方を
する必要はないでしょう。

回答No.5

SHIMAPEE

ANo.4 お礼への回答です。「感じ」はよさそうですけれども、実際に動くまでには先は長そうに思います。(^^;;;

じっくり考えるのはとても大事なことですが、もし環境が手元にあるのでしたら動かしてみるのも勉強になります。

そこで勉強がてら、's'、'r'の処理をWindwosXP+Delphi2007で動かしてみました。定義は抜粋です。なるべくkkk152さんの意図を汲んだつもりですが、追加訂正したところもありますので比べてみて下さい。なお、入出力と文字列の処理はDelphi風です。お手持ちのコンパイラに合わせて書き換える必要があるでしょう。

type charstring = packed array[0..8] of char; {Delphi文字列処理のため変更}
　：
function hash (x : charstring): integer;
var y, i : integer;
begin
y := 0;
for i := 0 to 7 do {Delphi文字列処理のため変更}
y := y + ord(x[i]);
hash := y mod 11;
end;

function search(x:charstring; var p:list): boolean;
begin
p:=hashtable[hash(x)];
while p<>nil do
if strLcomp(p^.key, x, sizeof(x)-1)=0 then
break
else
p:=p^.next;
Result:=(p<>nil);
end;

procedure insert(x:charstring; y:integer);
var h : integer;
p : list;
begin
h := hash(x);
new(p);
with p^ do
begin key := x; othertype := y; next := hashtable[h] end;
hashtable[h] := p {チェーンの先頭に挿入していますね。やや不自然か}
end;

var
ix: integer;
p : list;
strx, stry: string;
begin
for ix := 0 to tablesize - 1 do hashtable[ix]:=nil; {初期設定を忘れずに}
while true do begin
writeln('メニュー');
writeln('s) ハッシュ値ごとのデータ表示, r) 登録, e) 探索・削除, i) 小さい順に表示, d) 大きい順に表示, q) おわり');
write('操作：'); readln(a);
case a of
's':begin {ハッシュ値ごとのデータ表示===================================}
for ix := 0 to tablesize - 1 do begin
writeln('hashtable[', InttoStr(ix), ']');
p:=hashtable[ix];
while p<>nil do begin
writeln('　キー："', p^.key, '", データ：', IntToStr(p^.othertype));
p:=p^.next;
end;
end;
end;
'r':begin {登録=========================================================}
write('キー　:'); readln(strx);
write('データ:'); readln(stry);
for ix:=0 to sizeof(x)-1 do x[ix]:=#0;
strLCopy(x, PChar(strx), sizeof(x)-1);
y:=StrtoIntDef(stry, 0);
if search(x, p) then
writeln('キー"'+x+'"は既に登録されています。データ：', IntToStr(p^.othertype))
else
insert(x, y);
end;
'q':break; {おわり=======================================================}
else
writeln('入力エラー：', a);
end;
end;
end.

回答No.4

SHIMAPEE

procedure insertは下のような手順になるのではないでしょうか。ANo.2 補足に書かれたコードは【 】の部分が抜けていると思いますよ。

(1)キーからハッシュ値を求める
(2)そのハッシュ値の【キーの「二重登録」をチェックする】
(3)キーと【データと】チェーンのレコードを作る
(4)レコードをハッシュ表に登録する

なお、上の手順(2)は、裏返していうとキーによる検索です。それは'e'の処理の一部にもなりますから関数にしておくとよいと思います。

お礼

じゃあ方はこんな感じで定義して、

type charstring = packed array[1..8] of char;

type list = ^cell;
cell = record key:charstring;
othertype:integer;
next:list
end;

var hashtable : array[0..(tablesize-1)] of list;
x : charstring;
b, y : integer;
a : char;
found : boolean;

insertをこんな感じで、
procedure insert(x:charstring; y:othertype; var p:list );
var h : integer;

begin
h := hash(x);
new(p);
with p^ do
begin key := x; othertype := y; end;
p^.next := hashtable[h];
hashtable[h] := p
end;

メニュー表示で下のようにすればちゃんと動きますかね？？
1 : found := false;
writeln('メニュー');
writeln('s) ハッシュ値ごとのデータ表示, r) 登録, e) 探索・削除, i) 小さい順に表示, d) 大きい順に表示, q) おわり');
write('操作：'); read(a);
if a = r then
begin
x:= ''; read(x, y);
search(x, found, p);
if found = true then insert(x, y, p);
else wirte('この文字列は既に登録されています。');
goto 1
end;

回答No.2

sakusaker7

それはPascalに長いこと触ってなかったからわからないじゃなくて
根本的なところからわかってないんじゃない?(^^;
このままだと丸投げな依頼になっちゃうので、ここまでは書けましたというのを
補足してもらって、わからない部分が具体的になっていれば
教えてくれる人入るんじゃないかな。

んで、よく読み返してみたら衝突のことは書いてあるね。
>'r' の場合： さらに「キーの値」と「データ」を入力し，すでに同じキーをもつデータがあれば「二重登録」として検出し，そうでなければ，そのレコードをハッシュ表に登録します

ということでまず、'i', 'd', 'e' のことは忘れて、入力したキーに対して
ハッシュ値を計算して表に登録するというところまでは書ける?

お礼

とりあえずハッシュ関数はできました。

type charstring = packed array[1..8] of char;

function hash (x : charstring): integer;
var y, i : integer;
begin
y := 0;
for i := 1 to 8 do
y := y + ord(x[i]);
hash := y mod 11;
end;

こんな感じですか？

補足

procedure insert(x:charstring; y:list );
var h : integer;
p : list;

begin
h := hash(x);
new(p);
with p^ do
begin key := x; next := y end;
hashtable[h] := p
end;

挿入はこんな感じですか？？

回答No.1

sakusaker7

ハッシュ値が衝突したときどうするのか書いていないのでは?
それからPascalだからわからない?
この言語でなら組めるとかあるんでしょうか。

お礼

返信ありがとうございます。
ハッシュ値の衝突はチェイン法で回避するらしいです。
まだハッシュ関数ができたところくらいまでしかできていません（泣）
学生なのでpascal以外の言語は全く分かりません。