C桶串

Question

我有一项任务要完成。它说我必须读取一个包含300万字符串的文件。

我必须读取文件并构建一个结构来保存字符串。这个系统必须能够回答以下问题：“这个新字符串是否存在？”

我还需要将列表分解为字符串的“桶”，这样‘要匹配的字符串’就能够(快速)选择要搜索的正确桶，并且该桶不应该包含总计/散列字符串(即每个桶包含3,000,000 / 0xFFF == 732个对象)。

现在我已经创建了一个哈希表、列表和函数的结构来读取文件、添加和删除函数。但我对用黑体字输入的文字一无所知。我是否需要在哈希函数中添加某些内容(请求以粗体表示)？

下面是我的示例代码

 #define MAX_NAME 100 
    /* Linked list structure */
    typedef struct list
    {
        char *string;
        int index;
        struct list *next
    } list_t ;

     /* hash table structure*/

     typedef struct hashTable
    {
        int size; // size of the table
        list_t **table; // the table element
    } hash_table_t;

    HashListType *createHashTable( size_t size)
   {        
     // allocate hash table ..I know how to do it    
   }    
    unsigned int hash(HashListType *hashTable, void *str )     
     {        
        uint64_t hashVal;    
        hashVal = 0;    
       while( *str != '\0')   
       {
         hashVal = *str + (hashVal << 5 ) - hashVal;    
         str++;    
       }     
      return (hashVal % hashTable->size);     
     }      

    void addToHashList( HashListType *list, void *obj, uint64_t hash)    
   {    

      // add item of new list to table  --> have an idea how to do it       
   }       

  void removeFromHashList(HashListType *list, void *criterion, uint64_t hash )      
   {
      // got an idea how to do it       
   }      
   /*        
      this  function will read the file (assume one string per line)     
      and create the list of lists (list of buckets), adding one object per string.    
   */     
     HashList *loadDataSet(char *filename, int hashMask)     
     {     
        // to read a file
       char readString[ MAX_NAME];
       File *fp ;

        if( (fp = fopen(filename, "r") )== NULL)
        {
          printf(" failed to open the file\n");
          exit(0);
        }
        while( fgets ( readString,MAX_NAME -1, fp ) != NULL)
        {
         //need to break the list down into "buckets" of strings so the 'string to match'
         // is able to chose the correct bucket to search in (quickly)
         //and that bucket should contain no more than total/hashMask strings
         or so (ie 3,000,000   / 0xFFF == 732 objects per bucket). 
        }
      fclose(fp);
     }

Answer 1

我相信您为您的哈希表选择了错误的数据结构：

typedef struct hashTable
{   
  char key[MAX_NAME];
  int index;
  struct hashTable *next;
  struct hashTable *prev;
};

哈希表的主要优点之一是能够直接跳转到包含正在搜索的元素的桶中。这是哈希桶链接列表的一部分--这意味着您必须在每次查找或插入时平均遍历4098/2个桶。这不会给你提供你所需要的表现。

您的哈希表应该是一个structs数组；每个struct都应该有一个指向字符串的指针(或短字符串的直接存储)和一个指向桶中下一个struct的指针。(虽然这个struct hashTable也可以是桶中的结构，但它是一个罕见的哈希表，需要桶内的next和prev链接。这就是为什么我猜测这个数据结构是为表本身设计的。)

您还需要选择一个好的散列函数。对好的散列函数进行了大量的研究，但是对于家庭作业来说，你确实是在寻找比可怕更好的东西。哈希函数的输入是您的字符串，输出应该是一个整数。您将需要使用数组大小的%输出(选择近5000的质数)来确定要使用哪个桶。

下面是来自方便函数库的哈希函数

unsigned int stb_hash(char *str)
{
   unsigned int hash = 0;
   while (*str)
      hash = (hash << 7) + (hash >> 25) + *str++;
   return hash + (hash >> 16);
}

一个简短的提示是，虽然stb.h代码在公共领域，但是在项目中引用源代码是非常明智的--教授、律师，以及将来的同事，会感谢您包含了您自己没有做过的事情的来源。

Answer 2

不仅可以为整数定义散列函数，还可以为字符或字符串定义散列函数(提示:字符编码)。为字符串创建哈希函数。提交时，必须与输出文件一起提交或运行。

Answer 3

注意:这个答案取决于你的作业文本对使用“桶”有多严格，因为我对你的问题的解释比你的示例代码要宽松一些。

毫无疑问，这一任务的最佳数据结构是一个特瑞或它的概括。您可以构建一个树，其中每个节点包含存储一个字符串原子的“微小”哈希表。例如，字符串中的原子可以是单个字符。你可以用参数化你的数据结构来改变一个原子的大小(也就是说，每个节点都有一个固定的16次数组，这样你的原子就有4位长) --这种数组方法允许恒定的时间下降，但需要相当大的内存。但是，正如我所说的，与快速查找数组不同，您可以使用微小的哈希表(这将使您的分配更加兼容)。