ハッシュ衝突対策と文字列のハッシュ関数
前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか?
ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか?
オープンアドレス法
先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。
これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。
// オープンアドレス法 // table[] は大域変数で0で初期化されているものとする。 // 配列に電話番号と名前を保存 void entry( int phone , name ) { int idx = hash_func( phone ) ; while( table[ idx ].phone != 0 ) idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席 } // idx++ でないのは何故? table[ idx ].phone = phone ; strcpy( table[ idx ].name , name ) ; } // 電話番号から名前を調べる char* search( int phone ) { int idx = hash_func( phone ) ; while( table[ idx ].phone != 0 ) { if ( table[ idx ].phone == phone ) return table[ idx ].name ; idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席 } // idx++ でないのは何故? return NULL ; // 見つからなかった }
注意:このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。
この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。
チェイン法
前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。
チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。
この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。
#define SIZE 100 int hash_func( int ph ) { return ph % SIZE ; } struct PhoneNameList { int phone ; char name[ 20 ] ; struct PhoneNameList* next ; } ; struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化 struct PhoneNameList* cons( int ph , char* nm , struct PhoneNameList* nx ) { struct PhoneNameList* ans ; ans = (struct PhoneNameList*)malloc( sizeof( struct PhoneNameList ) ) ; if ( ans != NULL ) { ans->phone = ph ; strcpy( ans->name , nm ) ; ans->next = nx ; } return ans ; } void entry( int phone , char* name ) { int idx = hash_func( phone ) ; hash[ idx ] = cons( phone , name , hash[ idx ] ) ; } char* search( int phone ) { int idx = hash_func( phone ) ; struct PhoneNameList* p ; for( p = hash[ idx ] ; p != NULL ; p = p->next ) { if ( p->phone == phone ) return p->name ; } return NULL ; }
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = sum + s[i] ; } return sum % SIZE ; }
文字列順で異なる値となるように
前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。
int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = sum*2 + s[i] ; // sum = (sum * 小さい素数 + s[i]) % 大きい素数 ; } return sum % SIZE ; }
上記のプログラムの、sum = sum*2 + s[i] では、2倍していった数を最後に SIZE で割っているだけなので、文字が長い場合文字コードの値の違いが sum の中に残らない場合も考えられる。こういった場合には、以下のような方法も考えられる。大きな素数で割ることで、余りの中に、元の数の値の違いの影響が残る。これは、疑似乱数生成での剰余法(or 線形合同法)の考え方を取り入れた方法ともいえる。
#define PRIME_B 大きな素数 #define PRIME_A 小さな素数 int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = (sum * PRIME_A + s[i]) % PRIME_B ; } return sum % SIZE ; }
ポート番号とメールが届くまで
ポート番号
サーバとなるコンピュータでは、1台のコンピュータで様々なサービスを提供することから、サービスを区別する必要がある。このためにポート番号が使われる。1台毎のコンピュータに割り当てられたIPアドレスを電話番号に例えるなら、ポート番号は内線電話番号に例えることができる。
サーバと通信する場合、サービスを提供するプログラムに応じて標準的なポート番号が決められている。サーバに届いたパケットは、ポート番号に応じてサービスプログラムを起動する。以下の表によく使われるポート番号の一例をあげる。
ポート番号 | プロトコル | 概要 |
20 | ftp | ファイル転送(データ) |
21 | ftp | ファイル転送(命令) |
22 | ssh | リモート接続(暗号対策あり) |
23 | telnet | リモート接続(暗号化なし) |
25 | smtp | 電子メール送信 |
465 | smtps | 電子メール送信(暗号化) |
53 | DNS | ドメインネームサービス |
80 | http | Web |
443 | https | Web(暗号化) |
110 | pop3 | メールダウンロード |
995 | pop3s | メールダウンロード(暗号化) |
143 | imap | メール閲覧 |
993 | imaps | メール閲覧(暗号化) |
137,138,139 | netbios | Windows のファイル共有 |
通信パケットには、送信元IPアドレス、送信元ポート番号、送信先IPアドレス、送信先ポート番号の情報がある。
パソコンがサーバと通信する場合は、(1)自分のIPアドレスを送信元IPアドレス、(2)その時に使われていないポート番号をランダムに選び、送信元ポート番号とする。(3)通信相手のIPアドレスと、(4)通信先のサービスのポート番号をセットして、パケットを送付する。サーバは、サービスを要求してきたクライアントの送信先ポート番号をみて、対応するサーバのプログラムを起動する。プログラムの結果を送り返す時は、送信元と送信先のIPアドレス、ポート番号を入替えてパケットを送信する。
1024未満のポート番号(ウェルノウンポート番号)は、サービスを受けとるために用途が決められているので、通常の通信プログラムでは使われない。これ以外のポート番号は、通信の送信元のポート番号として使われ、エフェメラルポート番号と呼ばれる。
ファイアウォール
ネットワークのサービスの中には、組織外に見せたくないものも多い。また、インターネットでは、悪意のあるプログラマが通信して攻撃を加えてくるかもしれない。こういった場合には、ルータなどで、パケットの送信相手のポート番号や、送信元のIPアドレスをみて、パケットを廃棄する場合がある。こういう、ネットワークからの攻撃を防ぐ装置は、ファイアウォール(防火壁)と呼ばれる。
メールが届くまで
電子メールは、非常に迅速にメッセージを相手に届けることができ、そのメッセージを蓄積・加工・編集・転送できる。また、音声や画像といった情報も、複雑な文字情報に置き換えることで、転送できるようになっている。
メールは、利用者のコンピュータに直接届けられるわけではなく、多くの場合はメールを蓄積するメールサーバに送られる。利用者がメールを読む場合、メールサーバから自分の端末に蓄積されたメッセージを読み込み、メッセージを確認する。このメールのやり取りにおいて、メールを送る時、あるいはメールサーバ間でメールを中継するときには、SMTP(Simple Mail Transfer Protocol) が用いられる。一方、メールサーバからメール
を読み出すときには、POP(Post Office Protocol) やIMAP(Internet Message Access Protocol) と呼ばれるプロトコルが用いられる。最近では、IMAPを使ったメールの読み書きをブラウザの中で実行できる WebMail が使われることが増えている。
メールが届くまでの流れは、aさんが”foo@bar.jp”に送る場合、
- aさんは、自分の組織のメールサーバに、SMTPでメールを送る。
- メールサーバは、メールアドレスのコンピュータ名部分”bar.jp”をDNSに問合せ、そのIPアドレスを調べ、そのコンピュータにSMTPでメールを送る。
- “bar.jp”のメールサーバは、メールアドレスのユーザ名部分を取り出し、各ユーザ毎にメールを保存する。
- “foo”さんは、自分宛のメールを確認するために、POPまたはIMAPで自分のメールサーバ”bar.jp”に接続し、ユーザ名,パスワードで認証して自分宛のメールを受け取る。
上記の手順2で、相手のメールサーバに直接送れない場合は、コンピュータ名のMXレコードをDNSに問合せを行い、そこで得られたメールサーバに中継を依頼する。
$ nslookup -query=MX fukui-nct.ac.jp. Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com.
POPは、一般的に、メールサーバから自分のメールをダウンロードして削除してしまうため、メールはダウンロードしたコンピュータにしか残らない。このため、様々なコンピュータでメールを読む人には不便となってきた。IMAPでは、メールを読んでも、サーバに残しておく方式であり、別のコンピュータを使う時にもサーバに残っているメールを読むことができる。
通常、SMTPでメールを送る際には、ユーザ認証が行われない。このため、ウィルスに感染したプログラムから迷惑メールを出すことに利用されることが多い。そこで、SMTP送信の前にPOP/IMAP接続しユーザ認証を行った時だけメールを送れる、POP before SMTP(or IMAP before SMTP)といった方式をとる場合もある。
理解度確認
- メールの送信から受信までの処理を、それに使われるプロトコルを交えて説明せよ。