字符串HASH

￡神魔★判官ぃ 2021-10-23 11:58 307阅读 0赞

字符串哈希方法很多。

当字符串很多，但是不同得却很小时候，利用字符串HASH很方便。而不用大费内存去用MAP。有时侯

还可能使MLE。

详细字符串HASH讲解。

[http://www.cnblogs.com/atlantis13579/archive/2010/02/06/1664792.html][http_www.cnblogs.com_atlantis13579_archive_2010_02_06_1664792.html]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<time.h>
    
    #define HASH 1000003
    int head[HASH];
    char str[1000][40];
    
    int hash( char *str)
    {
      int h = 0, seed = 131;
      while( *str )
      {
         h = h * seed + *(str++);
      }
      return ( h & 0x7fffffff) % HASH;
    }
    
    int main( )
    {
      int N;
      char sample[100] = "hello,world! welcome you --";
      int len = strlen(sample);
      srand(time(NULL));
      while( scanf("%d",&N) != EOF )
      {
         int n = 1;
         memset(head, -1,sizeof(head));
         for( int i = 0; i < N; i++)
         {
            char ch = rand() % 26 + 'A'; 
            char st = rand() % 26 + 'A';
            sample[len] = ch;
            sample[len+1] =st;
            sample[len+2] = '\0';
            printf("input:%s\n", sample);
            int x = hash( sample );
            if( head[x] != -1 )
            printf("成功找到已存字符串:%s\n", str[head[x]]);
            else
            {
               head[x] = n;
               strcpy(str[n], sample);
               n++;
            }     
         }
    
      }
      return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/14/2591645.html

[http_www.cnblogs.com_atlantis13579_archive_2010_02_06_1664792.html]: http://www.cnblogs.com/atlantis13579/archive/2010/02/06/1664792.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/028b61574adc44adaab3a4378ef1ebcc.png