icoding数据结构——哈希表添加（详细注释）

题目：

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：

typedef enum{     HASH_OK,     HASH_ERROR,     HASH_ADDED,     HASH_REPLACED_VALUE,     HASH_ALREADY_ADDED,     HASH_DELETED,     HASH_NOT_FOUND, } HASH_RESULT;  typedef struct __HashEntry HashEntry; struct __HashEntry{     union{         char  *str_value;         double dbl_value;         int       int_value;     } key;     union{         char  *str_value;         double dbl_value;         int       int_value;         long   long_value;         void  *ptr_value;     } value;     HashEntry *next; };  struct __HashTable{     HashEntry **bucket;             int size;     HASH_RESULT last_error; }; typedef struct __HashTable HashTable;  // 向哈希表中添加元素，其中键类型为char*， 元素类型为int。 HASH_RESULT hash_add_int(HashTable * table, const char * key, int value); 

哈希表相关说明：

• HASH_RESULT 类型为相关函数的返回类型
• HashEntry 为哈希表所保存元素（即键值对 《key, value》）类型
• HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
• 哈希表采用链地址法处理冲突

请实现 hash_add_int 函数，向哈希表中添加元素，其中键类型为char*， 元素类型为int。在添加过程中，如果要添加的键值key已在哈希表中，且对应的值value也已存在，则函数返回 HASH_ALREADY_ADDED；如果要添加的键值key已在哈希表中，但对应的值value不同，则函数将value值更新到哈希表中，之后返回 HASH_REPLACED_VALUE；如果要添加的键值key不在哈希表中，则函数创建 HashEntry 类型，并将其加入到哈希表中，且函数返回 HASH_ADDED。本题所用的哈希函数如下：

long hash_string(const char *str) {     long hash = 5381;     int c;      while (c = *str++)         hash = ((hash << 5) + hash) + c; /* hash * 33 + c */     if(hash < 0)         hash *= -1;     return hash; } 

代码：

#include <stdio.h> #include "stdlib.h" #include "hash.h" #include <string.h>  HASH_RESULT hash_add_int(HashTable* table, const char* key, int value) {     long hash_value = hash_string(key);  // 计算键的哈希值     int index = hash_value % table->size;  // 根据哈希值计算链表头指针数组索引      // 在对应链表中查找是否已存在相同的键     HashEntry* entry = table->bucket[index];     while (entry != NULL) {         if (strcmp(entry->key.str_value, key) == 0) {             // 键已存在             if (entry->value.int_value != value) {                 // 值不同，更新值                 entry->value.int_value = value;                 return HASH_REPLACED_VALUE;             } else {                 // 值相同，不做修改                 return HASH_ALREADY_ADDED;             }         }         entry = entry->next;     }      // 创建新的哈希表元素     HashEntry* new_entry = (HashEntry*)malloc(sizeof(HashEntry));     if (new_entry == NULL) {         return HASH_ERROR;     }      // 复制键字符串到新的内存中      // 注意在分配new_entry->key.str_value的内存时，为了容纳字符串结尾的空字符\0，我们将分配的大小设置为strlen(key)+1     new_entry->key.str_value = (char*)malloc(sizeof(char) * (strlen(key) + 1));     if (new_entry->key.str_value == NULL) {         free(new_entry);         return HASH_ERROR;     }     strcpy(new_entry->key.str_value, key);      // 设置值     new_entry->value.int_value = value;      // 头插法     new_entry->next = table->bucket[index];     table->bucket[index] = new_entry;      return HASH_ADDED; }