用C语言做出哈希查找

好的,我很乐意为您介绍如何使用C语言实现哈希查找。哈希查找是一种高效的查找算法,它在平均情况下可以达到O(1)的时间复杂度。下面是一个简单的C语言实现:

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

#define TABLE_SIZE 100

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

Node *hashTable[TABLE_SIZE];

unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + hash + *key++;
    }
    return hash % TABLE_SIZE;
}

Node *createNode(const char *key, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void insert(const char *key, int value) {
    unsigned int index = hash(key);
    Node *newNode = createNode(key, value);
    
    if (hashTable[index] == NULL) {
        hashTable[index] = newNode;
    } else {
        Node *temp = hashTable[index];
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

int search(const char *key) {
    unsigned int index = hash(key);
    Node *temp = hashTable[index];
    
    while (temp != NULL) {
        if (strcmp(temp->key, key) == 0) {
            return temp->value;
        }
        temp = temp->next;
    }
    
    return -1; // Not found
}

int main() {
    insert("apple", 100);
    insert("banana", 200);
    insert("orange", 300);
    
    printf("apple: %d\n", search("apple"));
    printf("banana: %d\n", search("banana"));
    printf("orange: %d\n", search("orange"));
    printf("grape: %d\n", search("grape")); // Not found
    
    return 0;
}

这段代码实现了一个简单的哈希表,其中:

1. 定义了一个哈希表`hashTable`,大小为`TABLE_SIZE`。

2. `hash`函数用于计算键的哈希值。

3. `createNode`函数用于创建新节点。

4. `insert`函数用于插入键值对。

5. `search`函数用于查找值。

6. `main`函数演示了如何使用这些函数。

这个实现使用了链地址法来处理哈希冲突。每个哈希桶都是一个链表,当有多个键映射到同一个桶时,它们会被链接在这个桶的链表上。