半通用哈希表

Question

经过大量的阅读和测试，我创建了一个“半通用”哈希表。

我所说的半泛型的意思是，我使用的结构有一个名称变量，它是char *，是我的键，它包含的第二个变量是一个指向void的指针，所以它可以是任何结构。

hashTable.c

#include "hashTable.h"


/*createHnode*/
  hnode* createHnode(hnode* next, char* name, void* value)
  {
      hnode* newhnode;
      char*  copiedname;
      if((NULL == name)||(NULL == value)){
        return NULL;
      }
    /*Allocate hnode*/
      if (NULL == (newhnode = (hnode*)malloc(sizeof(hnode)))) {
        return NULL;
      }
    /*set next*/
      newhnode->next = next;
    /*set name*/
      if (NULL == (copiedname = (char*)malloc(sizeof(char)*(strlen(name)+1)))) {
        return NULL;
      }
      strcpy(copiedname,name);
      newhnode->name = copiedname;   /*point at the input name string*/
    /*set value*/
      newhnode->value = value; /*points at the input value*/
    /*return a pointer to the allocated hnode*/
      return newhnode;
  }


/*createHashTable*/
/*Allocate an array of pointers to item.*/
  hnode** createHashTable(int hashsize)
  {
    int i;
    hnode** hashtable;
  /*If allocation failed, return NULL */
    if(NULL == (hashtable = (hnode**)malloc(sizeof(hnode*)*hashsize)) ){
       return NULL;
    }
  /*set all pointers in hashtable to NULL */
    for(i=0; i<hashsize; i++){
        hashtable[i]=NULL;
    }
    return hashtable;
  }


/*hashfunction*/
/*gets a string as argument, returns the index inside
  the hash-array:  0 - 51.
  A string is match to the index of its first character: a-z or A-Z.
  If several words start with the same character, a linked-list joins each new key.*/
  int hashfunction(char* name)
  {
     if(NULL == name){
        return -1; /*name = NULL*/
     }
   /*A-Z:  ASCII: 65-90*/
     if( name[0] - 97 <0 ){
         return (name[0]-65); /*index  0 - 25 in the hash-array*/
     }
   /*a-z: ASCII: 97-122*/
          return (26+ name[0]-97); /*index 26 - 51 in the hash-array*/
  }


/*insertNameValue*/
/*Input arguments:
   The hash-array and the new item to be added (if not inside hash-table already).
   The item will be added to the array-cell according to its key.
   If several items have the same hashindex, they will form a linked-list, in which the last
   item is added last in line.
   If the item is first in the hash-index, it will be the first
  Will enter the object to the hash-array according to the key.
  If object is already inside (has the same key string), than putValueForKey returns an
  error code*/
  int insertNameValue (hnode** hashArray, char* name, void* value)
  {
     int hashIndex;
     hnode* curr = NULL;             /*A pointer to the current item in the Hash(not the new item).*/
     if( (NULL == name)||(NULL == value) ){
          return -1;
     }
     hashIndex = hashfunction(name); /*get index for new name*/
   /*parse the linked-list, if exist, and compare input name to existing name-value pairs.*/
     curr = hashArray[hashIndex];
   /*if hashArray is empty at this cell, insert the new name-value pair*/
     if( NULL == curr){
         /*create a new hnode with name and value*/
           hashArray[hashIndex] = createHnode(NULL, name, value);
           return 1;
     }
   /*if hashArray points at a single hnode in this cell*/
     else if( NULL == curr->next){
              /*compare names(keys) of new pair and existing one*/
                if( 0 == strcmp(name, curr->name)){
                    return(-1); /*item is already in hash*/
                }
     }
   /*hashArray has a linked-list --> compare and add name-value at the end of
     the list. New hnode points at the end, need to point at NULL*/
     while( NULL != curr->next ){
            /*compare new key with each existing keys*/
              printf("curr->name = %s, name = %s\n",curr->name, name);
              if( 0 == strcmp(name, curr->name)){
                  return(-1); /*item is already in hash*/
              }
              curr = curr->next;
     }
   /*Reached end of list*/
   /*Create a new hnode with name and value*/
     curr->next = createHnode(NULL, name, value);
     return 1;
  }


/*getValueByName*/
/*returns a pointer to the value-object if the given name exists in the hash-Table*/
  void *getValueByName (hnode** hashArray, char* name)
  {
      hnode* curr; /*curr cell in the hashTable*/
    /*Get the hash index*/
      int hashIndex = hashfunction(name);
      curr = hashArray[hashIndex];
    /*Move in array until an empty */
      while(curr != NULL) {
            if(0 == (strcmp(hashArray[hashIndex]->name,name))){
               return hashArray[hashIndex]; /*key has value in hash*/
            }
            curr = curr->next;
      }
      return NULL;
  }/*End getValueByKey*/



  void deleteHashTable(hnode** hashArray, void (*deleteValue)(void*))
  {
     int i;
     hnode* curr;             /*points at hashArray[]                               */
     hnode* next;             /*another temporary hnode                             */
     if (hashArray == NULL){
         return;
     }
   /*parse the hashTable and delete hnodes, also in list*/
     for(i=0; i< HASHSIZE; i++){
         curr = hashArray[i];
         while(NULL != curr){
               next = curr->next; /*mark next hnode */
             /*Delete current hnode*/
             /*Delete the value*/
               deleteValue(curr->value);
             /*Delete the name*/
               free(curr->name);
             /*Delete current hnode*/
               free(curr);
             /*continue to next hnode*/
               curr = next;
         }
     }
   /*Delete the hash-Array: */
     free(hashArray);
  }/*End deleteHashTable*/


/*For testing...*/
  void displayHashTable (hnode** hashArray, void (*printValue)(void* )){
       int i;
       hnode *curr, *next;
       printf("%-20s%-20s\n", "hashTable-Key,", "hashTable-Value");
       for (i = 0; i < HASHSIZE; i++){
            curr = hashArray[i];
            while(NULL != curr){
                  next = curr->next;
                  printf("%-20s,",curr->name);
                  printValue(curr->value);
                  printf("\n");
                  curr = next;
             }
       }
  }

hashTable.h

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

#ifndef HASHTABLE_H_INCLUDED
#define HASHTABLE_H_INCLUDED
#define HASHSIZE 52  /* 26 for a-z and 26 for A-Z*/

/*struct hnode*/
  struct hnode{
       struct hnode *next;       /*next entry in chain                         */
       char*  name;             /*the key is a string(label or name)          */
       void*  value;            /*value can be any type or struct --> Generic */
  }typedef hnode;

/*createHnode*/
  hnode* createHnode(hnode* next, char* name, void* value);


/*hashfunction*/
  int hashfunction(char* name);


/*createHashTable*/
/*Allocate an array of pointers to item.*/
  hnode** createHashTable(int hashsize);


/*putValueForKey*/
  int insertNameValue(hnode** hashArray, char* name, void* value);


/*getValueByKey*/
  void* getValueByName(hnode** hashArray, char* key);


/*deleteHashTable*/
/*get the hashTable to be deleted
  and a pointer to a function to delete the value object
  void (*deleteValue)(void *)  --> a pointer to function to delete the value struct */
  void deleteHashTable(hnode** hashArray, void (*deleteValue)(void*));


/*For testing...*/
  void displayHashTable (hnode** hashArray, void (*printValue)(void* ob));


#endif /* HASHTABLE_H_INCLUDED */

我相信这段代码有很好的评论，我想看看你对它的看法。

Answer 1

• 注释不应重复代码。例如，/*Allocate hnode*/ if中的注释(NULL == =(hnode*)malloc(sizeof(Hnode){返回NULL；}没有增加任何清晰度，而是创建了噪声。
• 不要抛出malloc的返回值。充其量它是多余的，在最坏的情况下可能会导致难以找到的错误。
• 避免神奇的数字。65, 26, 97更好地表示为'a', 'z' - 'a' + 1, 'A'。也就是说，更喜欢标准库调用isalpha和islower。说到标准库，malloc/strcpy可以说是一个很长的strdup。
• 在碰撞中返回-1看上去不对。调用方很可能对阻止插入的元素感兴趣。考虑返回一个指针。
• getValueByName有一个漏洞:循环中的hashArray[hashIndex]必须是curr。我希望这是一个复制粘贴错误。
• 干的。insertNameValue中的查找循环重复了getValueByName的(预期)功能。
• 缺少功能。没有办法删除单个条目。
• 挑剔。sizeof(type)可能导致双重维护。更喜欢sizeof(expression)，例如newhnode = malloc(sizeof(*newnode))酌情使用calloc。根据定义，sizeof(char)是1。