連載 /JavaServer Pages—@ 図 10 ctl:foreach2 のタグハンドラ (Foreach2. java) package co 取 trol ; import j avax. servlet ・」 sp ・ tagext . * ; import javax. servlet ・」 sp ・ * ; import control . * ; public class Foreach2 extends TagSupport { private String name = nu11 ; private ListData value = nu11; public void setName(String nam) { name = nam; public void setVa1ue(ListData v) { value public int d0StartTag() throws JspException { if (name ! = null & & value ! = null & & value. isExist()) { pageContext . setAttribute (name , value. getVaIue ( ) ) ; return EVAL_BODY_INCLUDE ; } else { return SKIP_BODY; public int d0AfterBody() { if (name ! = null & & value ! = null & & value . isExist() ) { pageContext . setAttribute (name , value. getVa1ue ( ) ) ; return EVAL_BODY_AGAIN ; } else { return SKIP_BODY ; public int doEndTag() throws JspException { return EVAL_PAGE ; 生成する JSP ページの変数の値は、文字列 (String 型 ) ではなく任意のオプジェクトを指定できるように する としましよう。これは次のように言己します。 く ct1:foreach2 name=" 変数名” value = " オプジェクト” > 変数を使った処理 く /ct1:foreach2> 図 11 に、 ctI:foreach2 タグの TLD ファイルを示し ます。 ctl:foreach と ctI:foreach2 タグの両方を作って試 してみたい方は、図 11 のく tag 〉タグの内側の部分、 く tag> く name>foreach2 く /name> 72 く /tag> だけを取り出し、図 4 の ctl:foreach 用の TLD ファイ ルに組み込んでください。 web. xml については、図 5 のファイルがそのまま利用 できます。 HTML フォーム ctl:foreach2 タグと OpartsBean オプジェクトを使っ たサンフ。ルの JSP ページをみてみましよう。 最初のページでは、 HTML フォーム (form. html) を 表示します ( 図 12 ) 。図を見れば分かると思いますが、 のフォームでは複数の項目を同時ロ尺できるようにしま す。 UNIX MAGAZINE 2003.4

連載 JavaServer Pages—O 図 2 ctl:foreach のタグハンドラ (Foreach ・ java) package cont て 01 ; import コ avax. servlet ・ j sp ・ tagext . * ; import javax. servlet ・ jsp ・ *; public c1ass Foreach extends TagSupport private 土れ t index = 0 ; private String name = n Ⅱ 11 ; private String value ロ = null ; public void setName(String v) name = v; public void setVa1ue (String ロ value = v; public int d0StartTag() throws JspException index = 0 ; if (name ⅡⅡ 11 Ⅱ value = Ⅱ u11 Ⅱ value. length return SKIP_BODY; } else { pageContext . setAttribute (name , value Cindex] ) ; 図 3 JSP コードの鰰斤と呼び出されるメソッドの系 : <ctl:foreach name="word" value=" く % = sentence % > “ > return EVAL_BODY_INCLUDE ; ゝ public int doAfterBody ( ) { if (name ! = null) { index 十十 ; if (index く value. length) { pageContext . setAttribute (name , value [index] ) ; if (index く value . length) { return EVAL—BODY—AGAIN ; } else { return SKIP_BODY ; public int d0EndTag ( ) throws JspException { return EVAL_PAGE; = の { 三 </ctl:foreach > ・ ② doStartTag() を ④ doEndTag() を 呼び出す 呼び出す ③ doA れ erBody ( ) を呼び出す SK 旧 BODY を返すと、終了 EVAL BODY AGAIN を返 すと、タグ本体の先頭からもう タグを処理する 一度処理する F 。 reach タグハンドラでは、これまでにとりあげたタグ 2. 開始タグの処理か終ると doStartTag() メソッドか呼 び出される。 doStartTag() は、続けてタグ本体を処 ハンドラ (ctl:for のタグハンドラなど ) と異なり、 value 理する場合は EVAL-BODY-INCLUDE を、タグ本 属性で渡された配列から要素を 1 つずっ取り出し、 JSP ページから参照できる変数に設定する必要があります。 体をスキップして終了タグを処理する場合は SKIP- BODY を返す。 まず、 setVaIue() メソッドか呼び出されたときに、タ 3. タグ本体の処理か終ると doAfterBody() メソッドが グの value 属性で指定された配列が Foreach クラスの 呼び出される。 doAfterBody() は、もう一度タグ本体 変数、 を処理する EVAL-BODY-AGAIN か、終了タグを処 private String value ロ = Ⅱ u11 ; 理する SKIP-BODY を返す。 に保存されます。 4. 終了タグの角財こ doEndTag() メソッドか呼び出さ 次に、 doStartTag() メソッドのなかで、 value 配列の れる。 最初の要素を JSP ページから参照できるようにします。 ① setName("word") を 呼び出す set\/alue(sentence) を 呼び出す 66 UNIX MAGAZINE 2003.4

0066 : 0067 : 0068 : 0069 : 0070 : 0071 : 0072 : 0073 : 0074 : 連載 / Linux のプートプロセスをみる一⑨ return 0 ; write—unlock(&binfmt-lock) ; fmt ; formats fmt—>next = formats ; tmp = &(*tmp)->next ; return —EBUSY ; 0100 : { 0101 : 0102 : 0109 : return register—binfmt(&script—format) ; そして、各実行形式を表す linux-binfmt は、 do-init- calls() によってリストに登録されます。一方、 ELF 形式 の linux-binfmt は fs/binfmt-elf. c で定義さ匆月化 関数によってリストに登録されます。 1280 : 1272 : } 1271 : 1270 : { 1269 : 0078 : 0077 : 0076 : module—init(init—elf—binfmt) return register—binfmt (&elf—format) ; static int init—elf—binfmt (void) ELF_EXEC_PAGESIZE load-elf—library, elf—core—dump, NULL , THIS_MODULE , load_elf_binary , static struct linux_binfmt elf_format い犲招こ、 a. out 形式は fs/binfmt-aout. c で次のように 定義、登録されます。 0038 : 0039 : 0040 : 0504 : 0505 : { 0506 : 0507 : 0516 : PAGE_SIZE load—aout—library , aout— NULL, THIS_MODULE , load_ static struct linux_binfmt format={ binary , —dump , core aout ー aout static int init—aout—binfmt (void) return register—binfmt (&aout—format) ; module—init (init—aout—binfmt) ; 実行ファイル形式を定義・登録する部分を以下に示します。 最後に、 fs/binfmt-script. c からシェル・スクリプトの 0095 : 0096 : 0097. 0098 : 0099 : struct linux—binfmt script—format = { NULL , THIS_MODULE , load-script , NULL , NULL , 0 static int init—script—binfmt (void) module—init(init—script—binfmt) load-binary() れぞれ以下の処理をおこなうために呼び出されます。 構造体 linux-binfmt がもつ 3 つの関数ポインタは、そ 7 , 2002 (http://www.moses.uklinux.net/patches/lki. [ 2 ] Tigran Aivazian, 力を nq KerneI 2. イん 7 、れ佖な , August ・ co ・ jp/jp/developer/design/pentium4/manuals/) ーズ・マニュアル」 ( ーヒ・中・ - 杓、 2001 年 (http://www.intel [ 1 ] 「 IA -32 インテルアーキテクチャ・ソフトウェア・デベロッパ [ 赭文献 ] ( しらさき・ひろお IIJ) 次回はシステムコール execve をとりあげます。 今回は、 init() と do-basic-setup() について説明しま ☆ 返します。 あれは実行・環境の準備を開始し、そうでなけれはエラーを イルかどうかを判断します。そして、サポートする形式で の頁部分を読み出し、自分がサポートする実行形式ファ そこで、各 load-binary() は、引数に指定されたファイル タ ( マジックナンバー ) がかならす書き込まれています。 式ファイルの部分には、フォーマット形式を表すデー のメンバーの load-binary() の実行を試みます。実行形 体•linux-binfmt をリストのうから順にアクセスし、そ execve システムコールを発行すると、カーネルは構造 す。 カレントプロセスの実行イメージをファイルに書き出 core-dump() す ) 。 uselib システムコールによって呼び出される。 共有ライプラリをメモリにマップする (mmap しま load-shlib ( ) 作りあげる。 トプロセスの各種デスクリプタを再構築して実行・エ竟を ファイルシステムから実行ファイルを読み込み、カレン html) UNIX MAGAZINE 2003.4 173

連載 JavaServer Pages—@ 図 8 極し里をおこなうカスタムタグ用に定義したインターフェイス (ListData. java package control ; public interface ListData { public Obj ect getVa1ue ( ) ; public boolea れ isExist() ; / / 要素を取得する / / 未処理の要素があるかを調べる 図 9 極し里の文寸象 . にする JavaBean のクラス (OpartsBean ・ java) package control ; import java. uti1. * ; public class OpartsBean implements ListData { private int index = 0 ; private Vector place = Ⅱ u11 ; public OpartsBean() { public Object getVa1ue() { if (isExist()) { return place. e1ementAt (index + + ) ; } else { return Ⅱ u11 ; public boolea れ isExist ( ) { return (place ! = Ⅱ u11 & & index く place. size() ) ; place . addE1ement (v [i] ) ; (int i = 0 ; i く v. length, if (v ! = Ⅱ u11 ) { 0 ; new Vector() ; public void setP1ace(String ロ v) { for index place カスタムタグがそれを呼び出すガ去を知っていれば、複数 の要素を内部的にどんな形式で一尉寺してもかまいません。 そこで、柔軟生をもたせるために、 上記の 2 つの要件を満たす Java のインターフェイス を定義する 図 8 は、 2 不頁のメソッドを旦言した ListData イン ことにします。 スを実装 (implements) したクラスとして定義する 区し処理の対象とするクラスは、このインターフェイ 70 ターフェイスのソースコードです。 getValue() は要素を順番に取得するメソッドで、任意 のオプジェクトを扱うために戻り値の型は Object 型に なっています。 isExist() は未処理の要素があれば true を、なけれは false を返すメソッドです。 繰返し里用の JavaBean 続いて図 9 を見てください。こちらは、 ListData イ ンターフェイスを実装して作った OpartsBean クラス OpartsBean クラスでは、複数の要素を vector 型 の、、 place " 変数でイ寺します。また、次にアクセスする UNIX MÄGAZINE 2003.4

連載 / Linux のプートプロセスをみる一⑨ bdflush-init() は fs/buffer. c で定義されています。 2854 : static int bdflush—init (void) 2855 : { 2858 : 2860 : 2862 : 2863 : } kernel—thread(bdflush , &startup , CLONE_FSI CLONE_FILESI CLONE_SIGNAL) ; kernel—thread (kupdate , &startup , CLONE_FSI CLONE_FILES ー CLONE_SIGNAL) ; return 0 ; 2864 : 2865 : module init (bdflush—init) kswapd-init() は、 mm/vmscan. c で定義されていま 的にディスクに書き出す処理をおこないます。 2 , 860 行目の kupdate は、、、汚れた " バッフアを定期 マニュアルを参照してください ) 。 す処理をおこないます ( 田は、 bdflush のオンライン・ は、メモリ上の、、汚れた " 2 バッフアをディスクに書き出 2 , 858 行目で生成しているカーネルスレッド bdflush 0758 : 0757 : 0756 : } 0755 : 0754 : 0753 : 0752 : 0751 : { 0750 : す。 module—init (kswapd—init) return 0 ; CLONE_FSI CLONE_FILE 引 CLONE_SIGNAL) ; kernel—thread(kswapd , NULL , swap—setup ( ) ; printk( "Starting kswapd\n" ) ; static int kswapd—init (void) UNIX MAGAZINE 2003.4 す。 的に監視し、その値が閾値を下回ったらメモリを回収しま カーネルスレッド kswapd は、空きメモリの量を定期 はまた書き戻していない状態のことてす。 2 ディスクプロックのキャッシュをメモリ上で書き換えたが、ディスクに を発生させて execve システムコールを呼び出すだけで、 切り替えます。ただし、 execve() はソフトウェア割込み 読み込み、実行コンテキスト ( プログラムとスタック ) を execve() は、引数に指定されたプログラム・ファイルを execve() 切替えのための処理そのものか実装されているわけではあ りません。 execve() は、 include/asm/unistd. h で以下のように (unsigned long) ← 125 ) ) { if ( (unsigned 10 Ⅱ g ) (—-res) > = "c" ((long) (argv)) , "int $ 0X80 " asm volatile ( 10 Ⅱ g —-res ; char **argv , char **envp) static inline int execve (const char *file , ように展開されます。 を呼び出すコードを生成します。ー己のコードは、以下の -sysca113 マクロは、 3 つの引数をとるシステムコール char * * , envp) const Char * , file, Char * * , argv, static inline —sysca113(int , execve, 定義されているインライン関数です。 _res errno EAX ( 変数 --res) にシステムコールの戻り値かオ内さ はありません。一方、エラーが発生した場合は、レジスタ に切り替わるため、制御が execve() に戻ってくること execve に成功すると、実行コンテキストか新しいもの ださい ) 。 は、 3 月号の「システムコール呼出し」の節を参照してく という処理がおこなわれます ( 各レジスタの意未について ・ INT 80H を実行 ・ EDX レジスタに 3 番目の引数 (envp) をオ絲 ・ ECX レジスタに 2 番目の引数 (argv) をオ内 ・ EBX レジスタに 1 番目の引数 (file) をオ絲タ をオ内 ・ EAX レジスタに 11 (execve のシステムコール番号 ) ドでは、 まるてを号のようにみえるインライン・アセンプリコー return (int) (——res) ; 171

特集・プログラミング入門 図 14 ハッシュ値 1 のレコードを削除した 0 ■ 0 国 000000 国国 search—add(char *s, int flag) int h; fo て (h = hashpjw(s) % HASHSIZE; bucket [h] ! = NULL ; h = (h + 1 ) % HASHSIZE) if (strcmp(s, bucket Ch] ) = の return bucket [h] ; if (flag = 0 ) return NULL ; bucket Ch] return S ; ループを抜けたとすると、目的の文字列がハッシュには 存在しなかったことになります。その場合には、日 ag の値 にもとづいて値を登録します。 この関数では、登録されているレコード数のチェックは おこなっていません。すべてのノヾケットがすでに埋まって いる状態て新たにデータを登録したり、存在しないデータ を探索したりすると無限ループに入ってしまうので注意が 必要です。これについては、ハッシュに登録されている データの数を把握しておくか、イ直の探索ですべてのデータ を探索したかどうかをチェックすることで対応できます。 分旧当去では間題がないのて触れませんでしたが、線 形探査去では削ド斜巣作カ吠きな間題になります。衝突が発 生するまでは、該当するレコードを削除してもとくに支章 はありません。しかし、いったん衝突が発生してしまうと、 レコードを自由に削除することはできなくなるのです。 図 13 で、ノ、ツシュ値が 1 のレコードを削除すること を考えてみましよう。このハッシュ値は衝突を起こして いませんが、簡単には削除できません。もし削除してしま うと、ハッシュバケットは図 14 のようになります。 こでハッシュ値 12 のレコードを探索すると、↓ 2 の 位置にあるレコードは正しくみつけることができます。し かし、 4 の位置にあるレコードはどうやっても探しだせま せん。 12 、 0 、 1 と調べた段階て空のバケットをみつけて しまうため、 2 、 3 、 4 のバケットは調べられないのです。 そこで、削除する場合には、レコード自体を削除すると ともに、そこにデータが入っていたことを示す印を付けて 126 図 15 線幵査法にかかる手間 調べるべき ハッシュバケットの数 60 50 40 30 20 0.1 0 成功探索 - - 不成功探索 0.2 0.3 0.4 おく必要があります。 0.5 0.6 07 0.8 0.9 このように削余斉み こは、 . レコードを挿入するときは 占有率 ( あ 空のバケットとみなしますが、レコードを探索する際には 使用中のバケットとして扱います。 UNIX MAGAZINE 2003.4 2 ( 1 ー 0 れていないデータを探索する手間は十一一彑アになりま ハッシュに登金求さ ータを探索する手間は当十司・に が、占有率を 0 としたとき、ハッシュに登録されているデ ケット全体 ) に大きく景れます。言田は説明しません ケットの占有率 ( 使用中のノ、ツシュバケット / ハッシュバ この方法を利用する場合の探索の手間は、ハッシュバ トを準備したほうがよいでしよう。 るレコードの数も考えて、十分なサイズのノ、ツシュバケッ 使うとしても、登録されるレコードだけでなく、削除され ガ去を利用したほうがよいかもしれません。線牙豸架査去を 削甜巣作を数多くおこなうのであれば、線形探査法↓リ外の なってしまう場合もあります。したがって、レコードの 速化を目指してハッシュを使っているのに、意味がなく し、この処理は複雑でコストも高くなるため、せつかく高 ークを使わすにレコードを削除することができます。しか 調べ、必要に応して詰める処理をおこなえは、削余斉みマ レコードを削除する際、その後ろにつながるレコードを つれて探索効率が悪化してします。 トも使用中とみなすため、このようなバケットか増えるに しまいます。探索では、この削余斉みマーク付きのバケッ と、どうしても削余斉みマークの付いたバケットか増えて の印を使いながらレコードの追加や削除を繰り返している

特集・プログラミング入門 一方、スキップリスト自体を表す -skiplist 構造体を割 り当てるための関数は次のようになっています。この関数 では、 -skiplist 構造体のための領域だけでなく、うび頁に 配置するダミー要素の領域も割り当てています。 skiplist skiplistnew(cmpfunc func) skiplist P ; p = (skiplist)malloc(sizeof (skiplistelem) ) ; bzero(), sizeof (skiplistelem)) ; p->head = s1110denew(SKIPLIST-MAXLEVEL , (void * ) 0 ) ; if (c p—>func = func ; return p ; ダミー要素の割当てには、さきほどの slnodenew 関数 を利用します。このとき、レベルとして MAXLEVEL を 指定することで、最大のレベルをもつ要素か現れた場合に も対処できるようにしています。また、登録するデータと して 0 を指定していますが、これは使わない値を適当に指 定しているわけではありません。「データ構造」の項でも 述べたように、ダミー要素のデータ部分は、スキップリス ト全体の最大のレベルをイ尉寺します。この時点では要素は まだ 1 つもありませんが、これを 0 としているのです。 slnodenew 関数では領域を 0 でクリアするため、ダミ ー要素の follow 酉冽の要素がすべて 0 となっている点も 重要です。後ろに要素がないことを follow 配列の要素が 0 となっていることで表すため、これが 0 に初期化されて いないと正しく動かなくなってしまいます。 スキップリストの構築に入る前に、探索を実行する関数 からみていきましよう。これは、意外に簡単です。凾の 整列されたリストでの探索といな処理を最大レベルのリ ンクから開始し、レベル 0 になるまて繰り返すだけです。 void * skiplistmember (skiplist s , VOid *elem) 探索関数 slnodenull ; q = (p = q) → follow[level] ) { s—>func(elem, q->elem) ) if ( (c = > 0 ) return q—>elem; = の continue ; level; int slnode p, q; int p = s->head; for (level for (q 116 skiplistlevel(s) ; —level) 1eve1 > = 0 ; p—>follow[level] ; break ; NULL ; タ M 則のループは最大レベルからレベル 0 までのループ、 return UNIX MAGAZINE 2003.4 こないます。ここでは二重登録をエラーとしているので、 す。まず、追加する位置をみつけるために普通に探索をお ちらも、考え方は整列されたリストにおける探索と同しで それでは、データを追加する関数に進みましよう。こ データ追加関数 数 p 凵尉寺しているのです。 索を続けられるように、 1 つ前に注目していたノードを変 を通りすぎてしまう場合もあります。このようなときも探 側のループを実行していくときに、変数 q が目的のノード ドです。変数 p はこのようなノードを表しています。内 は目的の値よりも小さいデータをイ尉寺している最大のノー 変数か重要になります。殞則のループに移る際、重要なの し、 break によって外側のループに移るときは 2 つ目の だけ注目するのであれは 2 つの変数は不要でしよう。しか 奇異に思えるかもしれません。たしかに、内側のループに このとき、 p と q という 2 つの変数を使っているのが ベルを 1 つ下げ、殞則のループに処理を移行します。 でみすぎてしまったことを表すため、 break を実行してレ のはうが大きくなってしまった、つまり同一レベルで先ま して終了します。これが負の値となった場合は、探索キー 数として指定した値か探索したい値ですから、この値を返 tinue としています。もしこの値が 0 であれば、第 2 引 すので、同じレベルでもうすこし先を探索するために con- 索のためのキーとして指定した値のほうが大きいことを示 は、第 2 引数よりも第 1 引数のほうカ吠きい、すなわち探 比較に利用する s->func 関数が正の値を返した場合 されたリスト構造での探索のコードとそっくりです。 になります。この内側のループは、 1 月号て紹介した整列 内側のループはそのレベルで要素をみつけるためのループ

特集・プログラミング入門 次の PROB は、レベルを上げる確率を決めるための値 です。 1 / 2PR 。 B が実際の確率になります。ですから、確 率として 1 / 2 を使うなら 1 、 1 / 4 を使うなら 2 になりま す。 PROBMASK は PROB ビット 1 か連続した値に なっていて、この値でオ鬮以乱数のマスクをとったものが 0 であればレベルを 1 つ上げるようにしています。 関数では、擬似乱数を何回も生成するのではなく、以 乱数のうちの必要なビット数だけを利用し、残りは次の呼 出しに備えてとっておきます。このため、以下のように 擬似乱数の残りを表す slrandomval 、以乱数に残って いるビット数を表す slrandomleft を青勺変数として旦言 しています。なお、この関数自体も static と旦言されて います。これは、スキップリスト自身を操作する関数は呼 び出されることはあっても、そこから内部的に呼び出され るこの関数が外部から呼び出されるとは考えられないから static int slrandomlevel (void) static 10 Ⅱ g static int int 1eve1 slrandomval ; slrandomleft 通常の変数として level を宣言しています。関数は、 slrandomleft SKIPLIST_RBITS / slrandomval = random() ; if (——slrandomleft く = 0 ) { slrandomval > > = SKIPLIST_PROB ; while (level く SKIPLIST-MAXLEVEL) { は最刻直になっているわけです。 まわります。このループを正常に終了するときは、 レベルの値が MAXLEVEL にいたるまではループを の値を戻り値として使います。 level SKIPLIST_PROB ; UNIX MAGAZINE 2003.4 else break; if (slrandomval & SKIPLIST—PROBMASK) インクリメントしてループを続けます。 以外ならループを強缶了します。 0 の場合には、 level を 乱数があれは、その下位 RBITS ピットをチェックし、 0 ライプラリ関数を呼び出して以乱数を取得します。以 を石忍します。すでに情報カ戯っていなけれは、 random ループの本体では、ます擬似乱数の情報カ戦っているか level + + ・ return 1eve1; この処理により、指定された確率で level を上げていく ことができます。 さきほど例に挙げた関数とこの関数を作成し、それぞれ の夫行時間を上交したところ、 ( システムによって違いは あると思いますか ) 約 1.5 ~ 2 倍の速度向ー E がみられまし 初期化関数 スキップリストは 2 つのデータ構造を組み合わせて利 用しているので、きちんと初期化しておかなければ使えま せん。そのための初期イ凵数は、以下のようになっていま す。ます、スキップリスト内で要素寺するために使う slnode の初期イ tl 数からみてみましよう。引数として渡 されるのはそのノードのレベルと、実際に登録するデータ の 2 つです。 static slnode slnodenew(int 1 , void *e) slnode p ; p = (slnode)malloc(sizeof(slnodeelem) + 1 * sizeof(slnode)); bzero (p , sizeof (slnodeelem) + 1 * sizeof(slnode) ) ; p—>elem = e; return p; malloc 関数で領域を割り当て、本を 0 でクリアし てから値を設定する普通の匆期イ tl 数ですが、領域のサイ ズの計算ガ去がすこし変わっています。構造体本来のサイ 115 きるようにしています。 す ) を呆し、すべてのレベルのためのポインタをイ尉寺で こでさらに 3 つぶん ( ちょうどレベルぶんで ないので、 せん。しかし、構造体の旦言では 1 つぶんしかとってい 合は、 0 ~ 3 の 4 つの配列の要素尉寺しなけれは・なりま ける正しいサイズの引算です。レベルが 3 と指定された場 これが、「データ構造」の項で紹介した初期・化関数にお ます。 定されたレベルを sizeof (slnode) に掛けた値も加えてい ズである sizeof (slnodeelem) だけでなく、引数として指

特集・プログラミング入門 想的です。しかし、現実にはそんなことは不可能なので、 できるだけいろいろな値カ亟るようにします。なお、ハッ シュ関数は、、関数 " ですから、同し引数に対して呼び出さ れた場合は同し値を返さなけれはなりません。呼出しごと に異なる値を返してしまうと、ハッシュ法はまったく機能 しなくなってしまいます。 たとえば、整数のキーを考えると、キーの値を M で剰 余をとるだけでもそれなりの結果カ碍られます。この場合 も、 M が素数のはうがよい結果カ碍られます。これは 10 、 20 、 30 といった規則的な値を思い浮かべれはすぐに分か るでしよう。 文字列をキーとする場合には、次のような点に注意が必 要です。文字列の先頭のほうだけでハッシュ値を計算し てしまうと、大半が同し値になってしまうケースもあり ます。そこで、できるかぎりすべての文字を使ってハッ シュを引算します。たとえば、あるプログラミンク言語で 書かれたプログラムの処理を考えてみましよう。 tmpl 、 ・・といった連番の変数はよく使います tmp2 、 tmp3 、 が、これらを異なるハッシュ値にするには、先頭だけで なく末尾まで利用することが重要です。さらに、使い方に よっては、利用している文字の順番も考慮しないと意味が なくなってしまう場合もあります。たとえば、 a 、 b 、 c 、 d の 4 文字から生成できる単語の一覧を作るとき、それぞれ の文字の順番を考慮に入れないと、すべてか同レ、ツシュ 値になってしまいます。 ハッシュ関数については、重要な点がもう 1 つありま す。ハッシュ関数の引算にあまりにコストがかかるようで は、未がないという点です。今回は、探索を高速化する ためにハッシュ関数を使おうとしています 3 。しかし、ハッ シュを引算するためのコストがあまりに高いと探索自イ柘 ) コストも高くなってしまいます。それなら、わざわざハッ シュ法を使うのではなく、辛鼾豸架索のほうがよかったなど という結果になりかねません。整数れのハッシュ値を求 めるのに、 l( れ十 0.5 ー I れ十 0.5 」 ) * 100 」といった 言 1 算をすれば、 0 ~ 99 刎直は得られます。しかし、はたし 3 もちろん、ハッシュ関数の用途は高速イけごけではありません。たとえば、 電イ署名などに利用されるメッセージ・ダイジェストを引算するために使 うハッシュ関ま 0 は、速度よりも、同レ、ツシュ値をもつオリジナルの データを竹城しにくいという性質のほうか重要になります。このように 同レ、ツシュ関数でも、その用途によって必要とされる生は変わりま す。 UNIX MAG AZINE 2003.4 てこれがハッシュ値を求める計算として有効かどうかは疑 間か残ります。ここまで複雑な計算をしなくても、同程度 にう靖攵している値は得られるのではないでしようか。ハッ シュ関数を言するときは、そのコストもヨ - 分に考慮して ください。 こで、よくできたハッシュ関数を紹介しておきましょ う。これは文字列をハッシュするための関数で、の作 者としても有名な DonaId E. Knuth カ非ったものです。 unsigned 10 Ⅱ g knuth—hash(unsigned char *str , int len) unsigned 10 Ⅱ g hash; for (hash=len; len-—; ) hash = ((hash くく 5) (hash>>27)) + + ; return hash ; 文字列をハッシュに掛けるときには、 1 文字ごとにビッ トシフトが 2 回、そして排他的論理和が 2 回必要になり ます。この程度なら地にはならないでしよう。 もう 1 つ、 P. J. Weinberg の作成したハッシュ関数も みてみましよう。こちらは、コンパイラの古典的な教科書 でも紹介されているものです。 unsigned 10 Ⅱ g hashpjw(unsigned char* str) unsigned long hash=O ; unsigned long g ; for(;*str; 十 + str) hash = (hash くく 4 ) + *Str; if ( ( g = has & 0Xf0000000 ) ) hash = g > > 24 ; hash 121 の処理が必要なわけではありません。 理横寅算が必要になります。とはいっても、それほど多く トシフトが 2 回、幇 Ff 鮖侖理和が 2 回、さらに加算と論 文字列をハッシュに掛けるときには、 1 文字ごとにビッ return hash;

特集・プログラミング入門 す ( 図 15 ) 。なお、このときの手間は、匀していくつの バケットをヾるかを表します。 。 = 0.5 であれば、成功する探索では 1.5 イ呈度のハッ シュバケットを、失敗する探索では 2.5 イ酥呈度のハッシュ バケットを調べる必要があります。また、。 = 0.8 とする と、成功する探索では 3 個程度を、失敗する探索では 12 イ酥呈度を卩ヾなけれはならないことか分かります。 図 15 のグラフからも分かるように、占有率が 0.8 のあ たりから性能は急激に悪化します。卿第架査法は、性能劣 化カ暾しくならない範囲て利用するように注意しなければ なりません。 ニ重ハッシュ法 線形探査法で占有率が - E がってくると性能か急激に悪化 するのは、ハッシュバケットの並びのなかに、使用中ノ ケット " の塊ができるためです。バケットの塊ができ始め ると、探索しようとしているノ、ツシュ値をもつバケット だけでなく、はかのハッシュ値をもつバケットも検査対 象となるため、効率が悪くなるのです。 塊ができてしまうのは、ハッシュの衝突が発生した際、 すぐ次のバケットを調べているためです。ハッシュ値 5 で 衝突が発生したときは、ハッシュ値 6 のバケットに登録し ます。こオび人降は、ハッシュ値が 5 、 6 、 7 のいすれの場合 にもこの塊が成長することになります。このように、 し ) っ たん塊ができ始めると、どんどん成長してしまうのです。 こで、塊がなぜできるのかを考えてみましよう。 入力ェが与えられたとき、最初に探すバケットの位置 をん ( ェ , 1 ) と表すことにします。もし、 ここに異なるデー タが入っているようであれは、次の位置を探さなければな りません。この 2 番目に探す位置をんは , 2 ) と表すことに します。塊ができてしまう原因は、んは , 1 ) = ん朝 , 1 ) の ときにん ( ェ , 2 ) = ん朝 , 2 ) となったり、ん ( ェ , 1 ) = んは 2 ) のときにん ( ェ , 2 ) = んは 3 ) となるからです。つまり、 1 回の衝突を起こすような組合ぜでは、その次以降の探剽立 置でもそオ功ゞずっと連続して続くため、塊ができてしまう わけです。 そこで、塊ができにくい方法が考案されました。これ は、ん ( ェ , 1 ) = ん朝 , 1 ) のときにんは , 2 ) / ん朝 , 2 ) と なったり、ん ( ェ , 1 ) = んは 2 ) のときにんは , 2 ) んは 3 ) UNIX MAGAZINE 2003.4 となるようにするという考え方です。これを寒見する簡便 なガ去が二重ハッシュ法 (double hashing) です。 一重ハッシュ法では、ハッシュの衝突を検出したとき に、、、次の " バケットではなく、、 2 次ハッシュて計算した 値だけ離れた " バケットを調べます。ここで引算する 2 次 ハッシュは、 0 以タ P ) 値でなければ正しく検索できません し、ハッシュバケットのサイズと互いに素であるような値 にしないと、すべてのバケットを検査することかできなく なる可能性もあります。また、 2 次ハッシュの引算に手間 がかかるようだと、一重ハッシュ法の利用によって得られ る性能の矼 E が、 2 次ハッシュを計算する手間で相殺され てしまうかもしれません。 これらの条件を満たすには、まず、ハッシュバケットの サイズを素数にすることが考えられます。ハッシュバケッ トのサイズが素数になっていれば、どんな値を 2 次ハッ シュにとってもハッシュバケットのサイズとは互いに素 になります。 2 次ハッシュの言算去は、 0 にならす、か つ簡単に計算できるものならよいでしよう。たとえば、文 字列を使う場合には、 1 + *s % 8 線幵豸架査法のプログラムと並べて上交すれは分かると思 といった簡略なものでかまいません。、、ハッシュ " という 名前が付いているので、文字列本を使って、 ・・・などと 考えがちですが、 1 次ハッシュの段階で文字列本を使っ た引をしているので、 2 次ハッシュのほうで一翻 ; だけを 使っても大きな問題にはなりません。 こちらも、プログラムとしてリ見してみましよう。 char * search—add(char *s , int flag) int ; int h2 ; h2 = 1 + *s % 8 ; for (h = hashpjw(s) % HASHSIZE; bucket [h] ! = NULL ; h = (h + (2) % HASHSIZE) if (strcmp (s , bucket Ch] ) return bucket [h] ; if (flag ret urn NULL ; bucket [h] return S ; 127