0

Would you consider this as a good hash function and load function? It seems rather slow not sure where is the biggest problem here :( Running time is around 0.8s. I am trying to make hash table consisting of all alphabet characters + '. Multiplying all indexes ( apart from the index of ' ) by 45 according to the value of first letter and inserting them back to front in alphabetical order regarding of their length.

 typedef struct node
 {
   char word[46];
   struct node* next;
 }
 node;
 node* hashTable[1171];
 node* cursor = NULL;
 node* new_node = NULL;

 int hashF(char* word)
 {
    int index = 0;
    if(isalpha(word[0])){
    int a = (word[0] - 97) * 45;
    int b = strlen(word);
    index = (a + b);
   //printf("\n%d\n",index);
 }
 else if(word[0] == 39)
 {
    index = 1170;
 }

 return index % SIZE_H;
 }
      /**
 * Returns true if word is in dictionary else false.
 */
 // Loads dictionary into memory.  Returns true if successful else false.
 bool load(const char* dictionary)
 {
//open the file for reading 
FILE* dict = fopen(dictionary,"r");
//check if the file exist
if(!dict)
{
    printf("Could not open the file");
    return false;
}
//allocate memory for all of the hashtable nodes
for (int i = 0; i < 1171; i++)
{
   hashTable[i] =(node*) malloc(sizeof(node));
  // memset =(hashTable[i],0,sizeof(node));
   hashTable[i]->next = NULL;
}
//setup the word counter to zero
int s = 0;



  //allocate the memory for  cursor and a first word holder
 new_node = malloc(sizeof(node));
 //remember about memsets
 new_node->next = NULL;  
 cursor = malloc(sizeof(node));
 cursor->next = NULL;
    while(fscanf(dict,"%s",new_node->word)!=EOF)
    {
          s++; 
          int b = hashF(new_node->word);


          if(hashTable[hashF(new_node->word)] == NULL)
          {
              printf("Does not exist");
          }
          //define the hashtable to be used
          cursor = hashTable[b];

         //sorting the list
              if(strcmp(new_node->word,cursor->word) < 0)
              {
                new_node = cursor;
                cursor->next = cursor;
                cursor->next = NULL;
              }
              else 
              {
                new_node->next = NULL;
                new_node->next = cursor->next;
                cursor->next = new_node;
              }             

              while(cursor->next != NULL)
              {
                  cursor = cursor->next;

              }

              new_node = malloc(sizeof(node));
              cursor->next = NULL;


    } 
    cursor = hashTable[11];
    while(cursor->next!=NULL)
    {
        cursor = cursor->next;
        printf("\n%s, %d",cursor->word, s);

    }

  //node* root = malloc(sizeof(node));
  //s++;

// printf("%s, %d",cursor->word,s);




 return true;

}
0

Personally, I'd say no, the hash function is little improvement on just using 0 to 27. All the hash function does essentially, is to multiply the ascii value by a constant and add the length of the word. While this is an improvement, the maximum number of hashes would be the number of possible first characters * the maximum length, or 27 * 45 = 1215. As a practical matter, assuming no words start with an apostrophe and 95% of words will be 2 to 14 letters or less, then the realistic number is 26 * 12 = 312 hash buckets will contain 95% of the words. This also means that the average length of each linked list will be around 458 words. (You could get a more accurate accounting by actually counting the linked list lengths directly.)

The shorter the average length of the linked lists, the better the performance. If the average length could be brought down substantially, say to 20 or less, the performance would substantially improve, but that would require at least 143091/20 or about 7150 different hashes. For average length 10, you'd need more like 14,000 hash buckets. In short, you want a very wide, but very shallow hash table.

Further, sorting the linked list is a time consuming process compared to adding each new word to the beginning of a linked list. Sorting would only be helpful if you could execute a search more efficient than a linear search, such as a binary search. Since you can't, without implementing more structure to support the binary search, the time expense of sorting the data is an unnecessary cost.

So, if your goal is to maximize execution time, look hard at a hash function that will produce a large number of hashes, and skip the sort while loading the dictionary.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

3
  • Would you think that doing a hash function that takes all of the character of a given word and sums up their ASCII values and than perturb them over options with 2 - 14 ( last option would be 14+ characters depending on the length of the word) characters long would have better performance? I might give it a go and see for myself :) – Kamil Kug Sep 15 '16 at 17:35
  • This I am afraid is even slower hehe. I am not sure how to use 20 words linked lists and than check a randomly given word in the right bucket. – Kamil Kug Sep 15 '16 at 19:32
  • As the length of the lists become shorter, the type of search used becomes less important. If the lists are really short, a linear search becomes almost as efficient as any other search. – Cliff B Sep 15 '16 at 20:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .