ハッシュ法について演習ができていなかったので、前半座学(ガベージコレクタ)と後半演習(ハッシュ法)
ガベージコレクタ
前回、malloc などで使用を終えたデータを free で開放する際に発生する問題について説明し、その問題の解決法として参照カウンタ法を説明した。しかし、参照カウンタ法は循環リストなどが含まれる場合、free で開放できない状態が発生する場合があることを説明した。
このため、malloc で確保したデータ領域を、free で開放する処理は、複雑なデータ構造の場合かなり処理の記述が大変になる。
そこで最近のプログラム言語では、ガベージコレクタがある。この方法では、プログラムが malloc で確保した動的データ領域は、データが不要となっても開放処理 free は行わない。
しかし、このままでは、不要となったデータ領域がメモリに溢れ、メモリ不足が発生してしまう。そこで、一定量のメモリを使い切ったら、不要なメモリ(ゴミ=ガベージ)を回収(コレクタ)する。
マーク&スイープ法
ガベージコレクタの方法には、色々あるが、マーク&スイープ法では、
- 処理を一旦停止し、
- 動的メモリの領域すべてに「未使用マーク」をつける。
- 実際に使用している変数や、その変数が指している領域には「使用中マーク」をつける。
- マーク処理が終わったら「未使用マーク」の付いているデータは誰も使っていないので回収する。
他にも、コピー法といった方法もあるが説明は割愛する。
上で述べた様に、ガベージコレクタはプログラムを一旦停止し、全動的メモリ領域を検査するという手間のかかる作業を行うため、通常は「一時的にプログラムが止まる」ことからリアルタイムに処理を行うような場合には、極めて不都合が多い。
このため、最近では参照カウンタ法の技術なども取り入れ、局所変数は参照カウンタ法の技法を中心に回収し、大域変数はガベージコレクタの技法で回収する。
CやC++言語では、ガベージコレクタは基本的には利用できず、ガベージコレクタが取り入れられた言語としては、Java が有名。Java では、ガベージコレクタが実装されているため、通常のプログラミングでは、free や delete といった処理は不要である。しかし、処理速度や突発的な一時停止を避ける場合には、適切なタイミングで変数に null を代入するといった処理を明記するなどのテクニックが重要となる。
局所変数とスタック
局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。
関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放されることから、スタック上に保存される。
演習(ハッシュ法)
ハッシュ法のプログラム(オープンアドレス法もしくはチェイン法)を用いて、
(1)名前と電話番号,(2)名前と住所,(3)名前と誕生日について、名前をキーとして検索するプログラムを作成せよ。
「出席番号 % 3 + 1」の番号のテーマに取り組むこと。
レポートを作成する際には、ハッシュ関数を変更してどういった変化があるか確認せよ。
ハッシュサイズは、10〜20件程度で良い。