C ведро струн

Question

У меня есть задание для завершения. Он говорит, что я должен прочитать файл, который содержит 3 миллиона строк.
Я должен прочитать файл и построить структуру для хранения строк. Эта система должна быть в состоянии ответить на вопрос "присутствует ли эта новая строка?"

Я также ожидал, что список будет разбит на «сегменты» строк, чтобы «строка для сопоставления» могла выбрать правильный сегмент для поиска (быстро), и этот блок должен содержать не более общего Строки / hashMask или около того (то есть 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 может также быть структурой in-bucket, это редкая хеш-таблица, которая нуждается в ссылках next и prev внутри сегментов. Именно поэтому я предположил, что эта структура данныхвместо этого предназначен для самой таблицы.)

Вам также нужно выбрать хорошую хеш-функцию .Существует множество исследований хороших хэш-функций, но вы действительно ищете что-то лучшее, чем ужасное, для домашнего задания.Входными данными для хэш-функции являются ваши строки, а выходные данные должны быть целыми числами.Вам понадобится % вывод с размером вашего массива (выберите простое число около 5000), чтобы выяснить, какой сегмент использовать.

Вот хеш-функция из библиотеки stb.hудобных функций :

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

Примечание. Этот ответ зависит от того, насколько строгим является текст вашего задания с использованием "сегментов", поскольку я интерпретирую ваш вопрос несколько более либерально, чем ваш пример кода.

Несомненно лучшийСтруктура данных для этой задачи: Trie или ее обобщение.Вы можете построить дерево, где каждый узел содержит «крошечные» хеш-таблицы, в которых хранится один атом строк.Например, атомы вашей строки могут быть одиночными символами.Вы можете параметризовать свою структуру данных, чтобы изменить размер атома (т. Е. Каждый узел имеет фиксированный массив из 16 подузлов, так что ваши атомы имеют длину 4 бита) - этот подход к массиву допускает постоянное время спуска, но требует сравнительнобольшое о памяти.Но, как я уже сказал, вместо быстрых массивов поиска вы можете использовать крошечные хеш-таблицы (которые будут более совместимы с вашим назначением).