利用C语言实现HashTable

利用C语言实现HashTable的完整攻略

HashTable是一种常见的数据结构，用于存储键值对。在C语言中，我们可以通过指针和结构体来实现HashTable。以下是一些步骤来实现HashTable：

步骤一：定义结构体

我们需要首先定义一个结构体来存储键值对，如下所示：

typedef struct hashnode{
    char *key;
    int data;
    struct hashnode *next;
} hashnode;

这个结构体包含了键（char*类型）、值（int类型）和下一个节点的指针（用于解决散列冲突）。

步骤二：定义HashTable

接下来，我们需要定义一个HashTable结构体来存储所有的hashnode。HashTable由一个指针数组和一个大小组成，数组中存储的指针指向hashnode。

typedef struct hashtable{
    int size;
    struct hashnode **table;
} hashtable;

指针数组可以使用malloc函数动态分配内存，大小为空间的大小。初始化表格数组时，应该使用calloc函数分配内存，以使所有指针初始值均为NULL。

步骤三：实现散列函数

每个HashTable都需要一种散列函数，用于将键映射为数字索引。散列函数应该返回一个整数，该整数应该落在HashTable大小范围内。

一个简单的散列函数可以使用字符串的ASCII码值之和模HashTable大小，如下所示：

int hash(char *key, int size){
    int sum = 0;
    for (int i = 0; key[i] != '\0'; i++){
        sum += key[i];
    }
    return sum % size;
}

任何具有相同ASCII总和的两个字符串都将散列到同一个单元格中，但在实际使用中，随机产生的散列函数效果更好。

步骤四：实现插入功能

现在，我们有了HashNode和HashTable结构体，并且有了散列函数来映射键到指针。现在，我们需要实现插入键值对的方法，可以将一个新的hashnode添加到HashTable中。

对于散列的密集使用，包括插入和查找，开链法可能比线性探测法更好。因此，在这个示例中我们使用开链法来解决冲突。

我们的插入函数首先使用散列函数将键m映射到桶t上。如果t为空，我们将m值插入到桶t上。如果t不为空，则迭代桶，将扫描找到的每个节点的键与m进行比较。如果存在一个键匹配，则更新该桶中的键值对。否则，在桶末尾添加新节点。

void insert(hashtable *ht, char *key, int value){
    int index = hash(key, ht->size);
    hashnode *new_node = calloc(1, sizeof(hashnode));
    hashnode *current_node = ht->table[index];
    // 查找表中是否已有该键，有则更新值
    while (current_node != NULL){
        if (strcmp(current_node->key, key) == 0){
            current_node->data = value;
            return;
        }
        current_node = current_node->next;
    }
    // 没有该键，则创建新节点并添加到表中
    new_node->key = key;
    new_node->data = value;
    new_node->next = ht->table[index];
    ht->table[index] = new_node;
}

步骤五：实现查找功能

最后，我们需要实现一个查找的方法，以便从HashTable中检索特定键的值。

hashnode *search(hashtable *ht, char *key){
    int index = hash(key, ht->size);
    hashnode *current_node = ht->table[index];
    while (current_node != NULL){
        if (strcmp(current_node->key, key) == 0){
            return current_node;
        }
        current_node = current_node->next;
    }
    return NULL;
}

这将在HashTable中搜索一个键，并返回相应的hashnode，如果找不到，则返回NULL。

示例

假设我们创建了一个HashTable，它具有以下参数：

hashtable *ht = (hashtable*)malloc(sizeof(hashtable));
ht->size = 5;
ht->table = (hashnode**)calloc(ht->size, sizeof(hashnode*));

现在，我们可以使用insert函数添加新成员并使用search查找单个成员。以下是一个简单的示例：

insert(ht, "Alice", 1);
insert(ht, "Bob", 2);
hashnode *result = search(ht, "Bob");
if (result != NULL){
    printf("%d\n", result->data);
}

这将打印出“2”，因为我们已经将“Bob”的值存储在HashTable中，并使用search方法搜索到它。