C言語関係掲示板

過去ログ

No８３６　ハッシュ法

[戻る]　[ホームページ]
No.10593
ハッシュ法について
投稿者---まこと(2003/11/17 18:27:01)		 


今ハッシュ法についてプログラムを考えているのですが行き詰まってしまい
ました。下にプログラムを貼りますので良くない所をどんどん指摘&&御教授
下さい。
データは[数字 文字列]がランダムに入っているもので、データセットの総
数は5000個ほどです。
環境はturbo linux、gccを使っています。
宜しく御願い致します。

例:

4364 hffhnxnxi      
1925 axrvwzshybbnd  
1360 thcqjjwrqlogi  
3879 axrsvntpvrq    
1351 vaaojcftn      
3808 gqamyxgzx      
 894 zlwue          
      :
      :


・ソース・

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 5001
#define BUF_SIZE  16

typedef struct cell{
   int         number ;
   char        name[BUF_SIZE] ;
   struct cell *next ;
} data ;

data  *hashtable[HASH_SIZE] ;
FILE  *fp ;


void MakeHashTable(void) ;
void Chaining(data * ,unsigned int) ;
int  Search_C(char *) ;              // Chaining
unsigned int Hash(char *) ;          // Hash Function
void PrintHash(void) ;
void Free() ;

main(){

        char          buf[BUF_SIZE] ;
	int           func  ;

	MakeHashTable() ;

//      PrintHash() ;

	printf("**********  SEARCH (Chaining) **********\n") ;
	printf("Input a word : ") ;
	scanf("%s" , buf) ;

	if((func = Search_C(buf)) != 0)
               printf("Comparison Times : %d\n" , func) ;
	else
               printf("No such a word in Hash Table .\n") ;

	/* release memory teritory */
	Free() ;

	fclose( fp ) ;

}


void MakeHashTable(){

       data   *temp ;    // temporary node for insert data to Hash Table
       int    i ;

       // Initialize Hash Table
       for(i = 0 ; i < HASH_SIZE ; i++)
	       hashtable[i] = NULL ;

       // acquire the file-pointer
       if((fp = fopen("data.txt" , "r")) == NULL){
	     printf("ERROR : Can't open the file .\n") ;
	     exit(1) ;
       }

       for(;;){

             temp = (data *)malloc(sizeof(data)) ;

	     // make temporary node
	     if(fscanf(fp , "%d" , &temp->number) != EOF){

	          fscanf(fp , "%s" , temp->name) ;
		  temp->next = NULL ;

		  Chaining(temp , Hash( temp->name )) ;
		  free( temp );
	     }

	     else{
		   free( temp );
	           break ;
	     }

       }
}


void Chaining (data *temp , unsigned int f ) {

  data  *s ;    //  substitute for Hashtable[f]

  if(hashtable[f] == NULL){

          hashtable[f] = (data *) malloc (sizeof ( data ));

          hashtable[f] = temp ;
  }

  else{

          s = hashtable[f];

          while (hashtable[f]->next)
                     hashtable[f] = hashtable[f]->next;

          hashtable[f]->next = (data *) malloc (sizeof(data));

          hashtable[f]->next = temp ;

          hashtable[f] = s ;
  }
}


unsigned int Hash(char *buf){

       unsigned int  value ;

       for(value = 0 ; *buf != '\0'; buf++)
	 value = *buf + value * 11 ;

       return value % HASH_SIZE ;
}


int  Search_C(char *buf){

     data          *s ;      //  substitute for Hashtable[f]
     int           cmp = 1 ;
     unsigned int  f ;

     f = Hash( buf ) ;

     s = hashtable[f] ;

     while( hashtable[f] ){   // something exit in hashtable[f]

          if(strcmp(hashtable[f]->name , buf) != 0){
		     cmp++ ;
		     hashtable[f] = hashtable[f]->next ;
          }

          else{
	         hashtable[f] = s ;
                 return cmp ;
	  }
     }
     return 0 ;
}


void PrintHash(void){

     data  *s  ;       // substitute for hashtable[i]
     int   i ;

     for(i = 0 ; i < HASH_SIZE ; i++){

       printf("[%d]\t",i) ;

       s = hashtable[i] ;

       while(hashtable[i]){

         printf("%4d %-16s\t -> ", hashtable[i]->number , hashtable[i]->name) ;

         hashtable[i] = hashtable[i]->next ;
       }

       hashtable[i] = s ;

       printf(" ( NULL )\n") ;      
     }
}


void Free(){

  int i ;

  for(i = 0 ; i < HASH_SIZE ; i++){

      if(hashtable[i])
         hashtable[i] = hashtable[i]->next ;

      else  free( hashtable[i] ) ;
  }
}

No.10609
Re:ハッシュ法について
投稿者---たか(2003/11/17 22:23:40)


とりあえずさらっと見ただけなのでまだバグがあるかもしれません。
リスト構造のデータ及びポインタと実体の扱い方が間違っていました。
こういう場合デバッグはHASH_SIZEを1にして正しくリストが構築されて
いるか確かめるのが正攻法です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 5001
#define BUF_SIZE  16

typedef struct cell{
   int         number ;
   char        name[BUF_SIZE] ;
   struct cell *next ;
} data ;

data *hashtable[HASH_SIZE] ;
FILE *fp ;

void MakeHashTable(void) ;
void Chaining(data * ,unsigned int) ;
int  Search_C(char *) ;              // Chaining
unsigned int Hash(char *) ;          // Hash Function
void PrintHash(void) ;
void Free(void) ;

int main(void)
{
  char buf[BUF_SIZE];
  int func;

  MakeHashTable() ;

  PrintHash() ;

  printf("**********  SEARCH (Chaining) **********\n") ;
  printf("Input a word : ") ;
  scanf("%s" , buf) ;

  if((func = Search_C(buf)) != 0)
    printf("Comparison Times : %d\n" , func) ;
  else
    printf("No such a word in Hash Table .\n") ;

  /* release memory teritory */
  Free() ;

  fclose( fp ) ;

  return 0;
}


void MakeHashTable(){

  data   *temp ;    // temporary node for insert data to Hash Table
  int    i ;

  // Initialize Hash Table
  for(i = 0 ; i < HASH_SIZE ; i++)
    hashtable[i] = NULL ;

  // acquire the file-pointer
  if((fp = fopen("data.txt" , "r")) == NULL){
    printf("ERROR : Can't open the file .\n") ;
    exit(1) ;
  }

  for(;;){
    temp = (data *)malloc(sizeof(data)) ;
    // make temporary node
    if(fscanf(fp , "%d" , &temp->number) != EOF){
      fscanf(fp , "%s" , temp->name) ;
      temp->next = NULL ;
      Chaining(temp , Hash( temp->name )) ;
      free( temp );
    } else {
      free( temp );
      break ;
    }
  }
}

void Chaining (data *temp , unsigned int f )
{

  data  *s ;    //  substitute for Hashtable[f]

  if (hashtable[f] == NULL){
     hashtable[f] = (data *) malloc (sizeof ( data ));
     *hashtable[f] = *temp ;
  } else {
    s = hashtable[f];
    while (s->next)
      s = s->next;
    s->next = (data *) malloc (sizeof(data));
    *s->next = *temp ;
    s->next->next = NULL;
  }
}

unsigned int Hash(char *buf){

  unsigned int  value ;

  for(value = 0 ; *buf != '\0'; buf++)
    value = *buf + value * 11 ;

  return value % HASH_SIZE ;
}

int  Search_C(char *buf){

  data          *s ;      //  substitute for Hashtable[f]
  int           cmp = 1 ;
  unsigned int  f ;

  f = Hash( buf ) ;
  s = hashtable[f] ;
  while(s){   // something exit in hashtable[f]
    if(strcmp(s->name , buf) != 0){
      cmp++ ;
      s = s->next ;
    } else return cmp ;
  }
  return 0 ;
}

void PrintHash(void){

  data  *s  ;       // substitute for hashtable[i]
  int   i ;

  for(i = 0 ; i < HASH_SIZE ; i++){
    printf("[%d]\t",i) ;
    s = hashtable[i] ;
    while(s){
      printf("%4d %-16s\t -> ", s->number , s->name) ;
      s = s->next ;
    }
    printf(" ( NULL )\n") ;      
  }
}

void Free(void){

  int i ;
  data *s, *t;
  
  for(i = 0 ; i < HASH_SIZE ; i++){
    s = hashtable[i];
    while (s) {
      t = s->next ;
      free( s ) ;
      s = t;
    }
  }
}

No.10610
Re:ハッシュ法について
投稿者---たか(2003/11/17 22:30:46)


ついでに書くと、こういうハッシュ法はオープン・ハッシュといい、キー
の削除が楽ですね。ただし同じキーが重なると速度が低下します。

リスト構造を作らない方法がクローズド・ハッシュ法で、速度が早い反面
キーの削除が困難で、更に同じキーが重なると衝突処理が必要です。

参考URL:
ここ
No.10636
Re:ハッシュ法について
投稿者---まこと(2003/11/18 13:38:23)


たかさん丁寧なレス有難う御座いました。
正常に動きました。

>リスト構造のデータ及びポインタと実体の扱い方が間違っていました。
>こういう場合デバッグはHASH_SIZEを1にして正しくリストが構築されて
>いるか確かめるのが正攻法です。


リスト構造のプログラムは何個か作ったことがあったのですがまだまだ
勉強が足りないようですね。
こちらのプログラム参考にさせて頂きます。
有難う御座いました。