C语言实现:哈希桶。使用例子加上详细的解析。
时间: 2023-09-15 09:17:55 浏览: 80
哈希桶是一种常见的数据结构,它可以将数据存储在哈希表中,以实现快速查找和插入。在哈希桶中,每个元素都有一个对应的哈希值,这个哈希值可以用来计算元素的存储位置。通过哈希值,我们可以快速地找到元素的位置,从而实现快速的查找和插入。
以下是使用 C 语言实现哈希桶的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 1000
struct Node {
char key[100];
int value;
struct Node* next;
};
struct HashTable {
struct Node* bucket[MAX_SIZE];
};
int hash(char* key) {
int hash = 0;
for (int i = 0; i < strlen(key); i++) {
hash += (int) key[i];
}
return hash % MAX_SIZE;
}
struct HashTable* createHashTable() {
struct HashTable* hashTable = (struct HashTable*) malloc(sizeof(struct HashTable));
for (int i = 0; i < MAX_SIZE; i++) {
hashTable->bucket[i] = NULL;
}
return hashTable;
}
void put(struct HashTable* hashTable, char* key, int value) {
int hashValue = hash(key);
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
strcpy(newNode->key, key);
newNode->value = value;
newNode->next = NULL;
if (hashTable->bucket[hashValue] == NULL) {
hashTable->bucket[hashValue] = newNode;
} else {
struct Node* currentNode = hashTable->bucket[hashValue];
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}
currentNode->next = newNode;
}
}
int get(struct HashTable* hashTable, char* key) {
int hashValue = hash(key);
struct Node* currentNode = hashTable->bucket[hashValue];
while (currentNode != NULL) {
if (strcmp(currentNode->key, key) == 0) {
return currentNode->value;
}
currentNode = currentNode->next;
}
return -1;
}
int main() {
struct HashTable* hashTable = createHashTable();
put(hashTable, "apple", 10);
put(hashTable, "banana", 20);
put(hashTable, "orange", 30);
printf("apple: %d\n", get(hashTable, "apple"));
printf("banana: %d\n", get(hashTable, "banana"));
printf("orange: %d\n", get(hashTable, "orange"));
return 0;
}
```
在上面的代码中,我们定义了两个结构体 `Node` 和 `HashTable`。`Node` 结构体表示哈希桶中的一个元素,包括键、值和指向下一个节点的指针。`HashTable` 结构体表示整个哈希桶,包括一个大小为 `MAX_SIZE` 的桶,每个桶可以存储一个链表。
我们使用 `hash` 函数计算给定键的哈希值。该函数将键中每个字符的 ASCII 码相加,然后对 `MAX_SIZE` 取模,以便将哈希值映射到桶中。
`createHashTable` 函数用于创建哈希桶。我们使用 `malloc` 分配了一个 `HashTable` 结构体,并将所有桶初始化为 `NULL`。
`put` 函数用于插入元素。我们首先使用 `hash` 函数计算键的哈希值,并创建一个新的 `Node` 结构体,将键、值和指向下一个节点的指针设置为 `NULL`。如果该桶为空,则我们将新节点插入该桶。否则,我们遍历链表,找到最后一个节点并将新节点插入链表的末尾。
`get` 函数用于查找元素。我们首先使用 `hash` 函数计算键的哈希值,并遍历链表,查找与给定键匹配的节点。如果找到了匹配的节点,则返回其值。否则,返回 `-1`。
在 `main` 函数中,我们创建了一个新的哈希桶,插入了三个键值对,并打印了每个键的值。运行代码会输出如下结果:
```
apple: 10
banana: 20
orange: 30
```
在哈希桶中,我们可以快速地查找和插入元素,因为插入和查找的时间复杂度都是 $O(1)$。但是,当哈希碰撞发生时,我们需要使用链表来解决冲突,这可能导致查找和插入的时间复杂度变为 $O(n)$,其中 $n$ 是链表的长度。因此,在设计哈希桶时需要特别注意哈希函数的选择和哈希表的大小。