ホーム » 2019 » 1月 » 08

日別アーカイブ: 2019年1月8日

2019年1月
« 12月    
 12345
6789101112
13141516171819
20212223242526
2728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ハッシュ法(チェイン法)

前回説明のハッシュ法(オープンアドレス法)は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。

チェイン法

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。

#define SIZE 100
int hash_func( int ph ) {
   return ph % SIZE ;
}
struct PhoneNameList {
   int phone ;
   char name[ 20 ] ;
   struct PhoneNameList* next ;
} ;
struct PhoneNameList* table[ 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 ;
}

2次元配列のデータ並び順

2年生のJavaScriptでの実験で、2次元配列のデータ並び順を誤解している人が多かったので、改めて説明。

何気なく、2次元配列を初期化した後、array[y][x] のデータの場所を誤解している。

数学の行列だと、a[x][y] で記述することが多いけど、配列の並び順を考える時は、a[y][x] との違いに慣れていないのが原因。

理解確認

以下のプログラムの実行結果は、何?

答え:23

// C言語
int a[][] = {
  { 11 , 12 , 13 , 14 } ,
  { 21 , 22 , 23 , 24 } ,
  { 31 , 32 , 33 , 34 } ,
} ;
int main() {
  printf( "%d\n" , a[ 1 ][ 2 ] ) ;
  return 0 ;
}

// JavaScript
var a = [
  [ 11 , 12 , 13 , 14 ] ,
  [ 21 , 22 , 23 , 24 ] ,
  [ 31 , 32 , 33 , 34 ] ,
] ;
alert( a[ 1 ][ 2 ] ) ;

このプログラムの実行結果を 32 と答えた人は、以下の説明を読むこと。

2次元配列の行と列

数学の行列表記と2次元配列の添え字の違い

数学の行列と2次元配列の添え字は、列を単位として考えるか、行を単位として考えるかが違うので注意が必要。

答え:21

ちなみに、科学技術計算用のプログラム言語 Fortran は、数学をベースに文法が決められたので、C 言語と添え字の順序が違うので注意が必要。