C语言实现的简单HashTable - jwHash

xpkdi 4年前

你可创建一个HashTable,然后往其添加字符串,long ints, doubles 和指针,keyed是strings或long ints。
然后通过get函数取得strings, long ints, doubles 和 pointers。

Data Structures

Hash Table

typedef struct jwHashTable jwHashTable;  struct jwHashTable  {      jwHashEntry **bucket;           // pointer to array of buckets      size_t buckets;      size_t bucketsinitial;          // if we resize, may need to hash multiple times      HASHRESULT lastError;  #ifdef HASHTHREADED      volatile int *locks;            // array of locks      volatile int lock;              // lock for entire table  #endif  };

Hash Entry

typedef struct jwHashEntry jwHashEntry;  struct jwHashEntry  {      union      {          char  *strValue;          double dblValue;          int    intValue;      } key;      HASHVALTAG valtag;      union      {          char  *strValue;          double dblValue;          int    intValue;          void  *ptrValue;      } value;      jwHashEntry *next;  };


Creating a Hash Table

jwHashTable *create_hash( size_t buckets );  void *delete_hash( jwHashTable *table );        // clean up all memory

Storing by String Key

HASHRESULT add_str_by_str( jwHashTable*, char *key, char *value );  HASHRESULT add_int_by_str( jwHashTable*, char *key, long int value );  HASHRESULT add_dbl_by_str( jwHashTable*, char *key, double value );  HASHRESULT add_ptr_by_str( jwHashTable*, char *key, void *value );

Deleting by String

HASHRESULT del_by_str( jwHashTable*, char *key );

Retrieving by String

HASHRESULT get_str_by_str( jwHashTable *table, char *key, char **value );  HASHRESULT get_int_by_str( jwHashTable *table, char *key, int *i );  HASHRESULT get_dbl_by_str( jwHashTable *table, char *key, double *val );  HASHRESULT get_ptr_by_str( jwHashTable *table, char *key, void **val );

[Similar for long int keys]


  1. Support multi-threading, -- this started, and implemented for the test
  2. Implement clean-up,
  3. Implement re-hashing to a larger hash table,
  4. Implement a callback to allow iterating through keys, values


Example 1 - Save and Retrieve Some Values

// Test hashing by string  char * strv1 = "Jonathan";  char * strv2 = "Zevi";  char * strv3 = "Jude";  char * strv4 = "Voldemort";    add_str_by_str(table,"oldest",strv1);  add_str_by_str(table,"2ndoldest",strv2);  add_str_by_str(table,"3rdoldest",strv3);  add_str_by_str(table,"4tholdest",strv4);    char * sstrv1; get_str_by_str(table,"oldest",&sstrv1);  char * sstrv2; get_str_by_str(table,"2ndoldest",&sstrv2);  char * sstrv3; get_str_by_str(table,"3rdoldest",&sstrv3);  char * sstrv4; get_str_by_str(table,"4tholdest",&sstrv4);  printf("got strings:\noldest->%s \n2ndoldest->%s \n3rdoldest->%s \n4tholdest->%s\n",      sstrv1,sstrv2,sstrv3,sstrv4);

Example 2 - Write and Read Key Value Pairs on Multiple Threads

#define NUMTHREADS 8  #define HASHCOUNT 1000000    typedef struct threadinfo {jwHashTable *table; int start;} threadinfo;  void * thread_func(void *arg)  {      threadinfo *info = arg;      char buffer[512];      int i = info->start;      jwHashTable *table = info->table;      free(info);      for(;i<HASHCOUNT;i+=NUMTHREADS) {          sprintf(buffer,"%d",i);          add_int_by_str(table,buffer,i);      }  }      int thread_test()  {      // create      jwHashTable * table = create_hash(HASHCOUNT>>2);        // hash a million strings into various sizes of table      struct timeval tval_before, tval_done1, tval_done2, tval_writehash, tval_readhash;      gettimeofday(&tval_before, NULL);      int t;      pthread_t * threads[NUMTHREADS];      for(t=0;t<NUMTHREADS;++t) {          pthread_t * pth = malloc(sizeof(pthread_t));          threads[t] = pth;          threadinfo *info = (threadinfo*)malloc(sizeof(threadinfo));          info->table = table; info->start = t;          pthread_create(pth,NULL,thread_func,info);      }      for(t=0;t<NUMTHREADS;++t) {          pthread_join(*threads[t], NULL);      }      gettimeofday(&tval_done1, NULL);      int i,j;      int error = 0;      char buffer[512];      for(i=0;i<HASHCOUNT;++i) {          sprintf(buffer,"%d",i);          get_int_by_str(table,buffer,&j);          if(i!=j) {              printf("Error: %d != %d\n",i,j);              error = 1;          }      }      if(!error) {          printf("No errors.\n");       }      gettimeofday(&tval_done2, NULL);      timersub(&tval_done1, &tval_before, &tval_writehash);      timersub(&tval_done2, &tval_done1, &tval_readhash);      printf("\n%d threads.\n",NUMTHREADS);      printf("Store %d ints by string: %ld.%06ld sec, read %d ints: %ld.%06ld sec\n",HASHCOUNT,          (long int)tval_writehash.tv_sec, (long int)tval_writehash.tv_usec,HASHCOUNT,          (long int)tval_readhash.tv_sec, (long int)tval_readhash.tv_usec);        return 0;  }