ホーム » 2021 » 12月

月別アーカイブ: 12月 2021

2021年12月
 1234
567891011
12131415161718
19202122232425
262728293031  

検索・リンク

共有のあるデータの取扱い

これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数により指定サイズのメモリ空間を借りて、処理が終わったら free() 関数によって返却をしてきた。この返却を忘れたままプログラムを連続して動かそうとすると、返却されなかったメモリが使われない状態(メモリリーク)となり、メモリ領域不足から他のプログラムの動作に悪影響を及ぼす。

メモリリークを防ぐためには、malloc() で借りたら、free() で返すを実践すればいいのだが、複雑なデータ構造になってくると、こういった処理が困難となる。そこで、ヒープメモリの問題点について以下に説明する。

共有のあるデータの取扱の問題

リスト構造で集合計算の和集合を求める処理を考える。

// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{  struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}

void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}

void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ; // c = { 1, 2, 3, 4 }
                                     //          ~~~~~~~ ここは b
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;
   list_del( b ) ;
   list_del( c ) ; // list_del(b)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、c=join(a,b) ; が終わると下の図のようなデータ構造となる。しかし処理が終わってリスト廃棄list_del(a), list_del(b), listdel(c)を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

実体をコピーする方法

こういった共有の問題の一つの解決法としては、共有が発生しないように実体を別にコピーする方法もある。しかし、この方法はメモリがムダになる場合もあるし、List内のデータを修正した時に、実体をコピーした部分でも修正が反映されてほしい場合に問題となる。

// 実体をコピーする(簡潔に書きたいので再帰を使う)
struct List* copy( struct List* p ) {
   if ( p != NULL )
      return cons( p->data , copy( p->next ) ) ;
   else
      return NULL ;
}

// 共有が無い集合和を求める処理
struct List* join( struct List* a , struct List* b )
{
   struct List* ans = copy( b ) ;
   //                 ~~~~~~~~~実体をコピー
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
        ans = cons( a->data , ans ) ;
   return ans ;
}

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

struct List* cons( int x , struct List* p ) {
   struct List* n = (struct List*)malloc( sizeof( struct List* ) ) ;
   if ( n != NULL ) {
      n->refc = 1 ; // 初期状態は参照カウンタ=1
      n->data = x ;
      n->next = p ;
   }
   return n ;
}

struct List* copy( struct List* p ) {
   p->refc++ ;  // 共有が発生したら参照カウンタを増やす。
   return p ;
}
// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{
   struct List* ans = copy( b ) ;
   //                 ~~~~~~~~~共有が発生するのでrefc++
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p != NULL
        && --(p->refc) <= 0 ) {    // 参照カウンタを減らし
      //   ~~~~~~~~~~~
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

int main() { // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ;

   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;  // aの要素は全部refc=1なので普通に消えていく
   list_del( b ) ;  // bは、joinの中のcopy時にrefc=2なので、
                    // この段階では、refc=2 から refc=1 になるだけ
   list_del( c ) ;  // ここで全部消える。
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

unix i-nodeで使われている参照カウンタ

unixのファイルシステムの基本的構造 i-node では、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。

以下に、unix 環境で 参照カウンタがどのように使われているのか、コマンドで説明していく。

$ echo a > a.txt
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
          ~~~ # ここが参照カウンタの値
$ ln a.txt b.txt      # ハードリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが増えているのが分かる
$ rm a.txt            # 元ファイルを消す
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが減っている
$ ln -s b.txt c.txt   # シンボリックリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ rm b.txt            # 元ファイルを消す
$ ls -al *.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ cat c.txt           # c.txt は存在するけどその先の実体 b.txt は存在しない
cat: c.txt: そのようなファイルやディレクトリはありません

文字列のハッシュ関数

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

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 ;
}

データベースの物理設計

データベース後半課題

データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。

情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。

レポートで記載する内容は、以下の通りとする。

  • 卒業研究におけるデータベース化する対象の説明
  • データベースをトップダウン設計する際の
    • 実体と関連を抽出するまでの説明
    • 正規化を行う経過の説明
    • 上記を踏まえたトップダウン設計でのER図
  • データベースをボトムアップ設計する際の
    • 対象とする帳票に相当するデータの一例と説明
    • レベル分けや正規化を行う経過の説明
    • 上記を踏まえたボトムアップ設計でのER図
  • 考察
    • トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
    • 両設計方法から分かったこと

データベースの物理設計

データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。

ディスク容量の見積もり

データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。

実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。

そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。

また、データベースへのデータの削除を行う場合、データが1つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。

このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。

一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い

また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。

補足:残り予定:トランザクション処理, 内部構造, テスト前レポート課題

プログラムの処理時間の測り方

今回の課題レポートでは、テスト素点が良くレポート提出でも加点が少ないと思われる人でも、まじめに取り組んだレポート提出が多かった。この中で、興味深いレポートで、2分探索木の検索が偏っていたらO(N),バランスが良ければO(log N)の検証をしているものがあった。ただ、計測方法がちょっと残念だったので解説。

処理時間の計測方法

速度の検証をするにしてもデータ数も少なく、検索は一瞬で終わってしまうので、以下のような 1000 回ループで時間を測定していた。1000回といったループで計測するのは正しいアプローチ。

for( int i = 0 ; i < 1000 ; i++ ) {
   if ( find( top , key ) )
      printf( "みつかった" ) ;
   else
      printf( "みつからない" ) ;
}

ただ、この方法では、find() の処理時間以上に、printf() の処理時間の方が問題となる。

printf の処理時間

printf は、ただでさえも、第一引数の中にある “%” フォーマットの分析をするという面倒な処理をしているので、かなり複雑な処理をしている関数。メモリ容量の少ない組込み系のシステムを構築する時は、%フォーマットの分析のコードも大きくなるので、使うのを避けることも多い。

また、printf は、%フォーマットの解析に加え、出力バッファリングなどを経て、最終的に文字を標準出力に出力する。標準出力への出力が発生すると、OSのシステムコールを呼び出し、結果を表示するターミナルプログラムは、画面への文字の出力や、画面からはみ出た文字のスクロールアップなどの処理を行う。このため、find() 関数の処理時間以上に手間がかかっている。このため、精度の低い結果となってしまっている。

つまり、自分の関数の処理時間を計測したいなら、余計な時間がかかる printf などの入出力処理は時間計測に含めないこと。

time コマンド

プログラムの処理時間を測る場合には、測定対象のプログラムの処理時間の他にも、最近のOSではマルチタスクだからこそ、他の並列処理にとられている時間、OSでマルチタスクの切替に係る時間なども含まれてしまう。

このため Linux 環境でプロセスの処理時間を測定する場合には、time コマンドを用いる。

((( ちょっと時間のかかりそうな /usr/lib 配下のファイルの一覧出力 )))
$ find /usr/lib -type f -print
(略)
((( time コマンドは、time の後ろに計測したい処理を書く )))
$ time find /usr/lib -type f -print 
(略)
0.00s user 0.33s system 26% cpu 1.242 total
((( 比較のために出力を /dev/null に捨てて実行 )))
$ time find /usr/lib -type f -print > /dev/null
find /usr/lib -type f -print > /dev/null
0.00s user 0.25s system 87% cpu 0.287 total

この例では、find 自体の処理時間 user 時間 0秒、find が 出力命令のようなシステムコールを実行したことによる OS の処理時間 system 時間 0.33 秒、出力なども含めて見かけ上の本当の処理時間が 1.242 秒というのがわかる。

この結果を見ても、如何に出力処理が遅いのかが分かる。

だからこそ、自分のプログラムの処理時間として使う場合は、user 時間の部分を使うこと。

プロファイラによる解析

プログラムの処理が遅い場合の原因を究明する場合には、プロファイラというプログラムを用いることが多い。

例えば gcc などのコンパイラのためのプロファイラの gprof では、プログラムの処理に一定時間で割り込みをかけ、そのタイミング毎にどの関数の処理中だったのかを調べることで、全体の処理時間の何パーセントをその関数の処理をしていた…ということを計測できる。(統計的プロファイラ)

((( 測定対象のプログラムにプロファイラ用の情報を埋め込んでコンパイル )))
$ gcc -pg foobar.c
((( プログラムを実行すると gmon.out という統計情報が出力される )))
$ ./a.out
((( gprof で統計結果の確認 )))
$ gprof ./a.out gmon.out

といっても、割り込みをかけて計測しているので、プロファイラの結果は精度の高いデータとは言えない。

ハッシュ衝突の対策

前回の授業で説明したハッシュ法は、データから簡単な計算(ハッシュ関数)で求まるハッシュ値をデータの記憶場所とする。しかし、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いか?

ハッシュ法を簡単なイメージで説明すると、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 ;
}

データベースの設計と正規形

データベースの設計において、重要な正規形についての説明

正規形

データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。

第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。


キーの説明超キー(スーパーキー)とは、データベースで1つのデータを 選び出すために必要なデータ項目であり、複数の項目で1データを指定 できる場合もある。

候補キーとは、必要最小限の項目となっているものを指す。 1項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。

データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。

第1正規化 第2正規化

第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。

  • 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
  • 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。

この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か?

  • 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。

第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。

第3正規化

上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。

おまけ:BC正規形,第4,5正規形

この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。

トップダウン設計・ボトムアップ設計

データベースの設計にあたって、実際の設計手順の説明を行う。

トップダウン設計では、対象業務を記述し、その中から名詞となっている実体を抽出する。 さらに動詞や形容詞のように記載されている関連を抽出する。 抽出した実体・関連では、あいまいであったり冗長であったりするので、整理したうえで、 その実体・関連をER図に表す。

ボトムアップ設計では、対象業務で実際に使われている入力帳票や結果の出力などを 見ながら、第1正規形を満たすように表を作っていく作業からおこなう。

トップダウン設計やボトムアップ設計で、 ER図や第一正規形を満たすような表が出来上がったら、 その属性の中で従属性を確認しながら、第2正規形・第3正規形へと整理していく。

ハッシュ法(導入)

前半は中間試験の返却と解説を行う。後半は次のテーマのハッシュ法の導入話。

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)2分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか?

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

// メモリ無駄遣いな超高速方法
struct PhoneName {
   int  phone ;
   char name[ 20 ] ;
} ;

// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?

// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
   table[ phone ].phone = phone ;
   strcpy( table[ phone ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   return table[ phone ].name ;
}

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

// ハッシュ衝突を考えないハッシュ法

#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;

// ハッシュ関数
int hash_func( int phone ) {
   return phone % HASH_SIZE ;
}

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   return table[ idx ].name ;
}

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

たとえ話で言うなら、100個の椅子が連番付きで並んでいて、自分の電話番号末尾2桁の場所に座ろうとしたら、先に座っている人がいるような状態である。このような状態で、あなたなら何処に座るだろうか?

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムでなくなってしまう。このことから、ハッシュ関数には以下のような特徴が必要となる。

  • 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
  • 簡単な計算で求まること。
  • 同じデータに対し常に、同じハッシュ値が求まること。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー