用c语言实现hashmap
时间: 2023-10-25 15:07:03 浏览: 50
好的,我可以回答这个问题。HashMap是一种数据结构,可以在O(1)时间内进行插入,删除和查找操作。在C语言中,可以使用结构体和指针来实现HashMap。具体实现可以使用链表或者红黑树作为HashMap的桶结构。在添加元素时,先计算元素的哈希值,再将元素添加到相应的桶中。当遇到哈希冲突时,可以使用链表或者红黑树等方式解决冲突。在查找元素时,先计算元素的哈希值,然后在相应的桶中查找。如果桶中有多个元素,可以遍历链表或者树进行查找。在删除元素时,也需要先计算哈希值,并在相应的桶中查找元素,然后从链表或者树中删除元素。
相关问题
用c语言实现hashmap代码
很高兴能为您解答问题。以下是一个简单的C语言实现hashmap的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASHSIZE 101
typedef struct Node Node;
struct Node {
char *key;
char *value;
Node *next;
};
Node *hashTable[HASHSIZE];
int hash(char *key) {
int hashval;
for (hashval = 0; *key != '\0'; key++) {
hashval = *key + 31 * hashval;
}
return hashval % HASHSIZE;
}
Node *lookup(char *key) {
int hashval = hash(key);
Node *np;
for (np = hashTable[hashval]; np != NULL; np = np->next) {
if (strcmp(key, np->key) == 0) {
return np;
}
}
return NULL;
}
char *get(char *key) {
Node *np = lookup(key);
return np == NULL ? NULL : np->value;
}
void put(char *key, char *value) {
Node *np;
int hashval;
if ((np = lookup(key)) == NULL) {
np = (Node *) malloc(sizeof(*np));
if (np == NULL || (np->key = strdup(key)) == NULL) {
return;
}
hashval = hash(key);
np->next = hashTable[hashval];
hashTable[hashval] = np;
} else {
free(np->value);
}
if ((np->value = strdup(value)) == NULL) {
return;
}
}
void del(char *key) {
int hashval = hash(key);
Node *prev = NULL;
Node *np;
for (np = hashTable[hashval]; np != NULL; prev = np, np = np->next) {
if (strcmp(key, np->key) == 0) {
if (prev == NULL) {
hashTable[hashval] = np->next;
} else {
prev->next = np->next;
}
free(np->key);
free(np->value);
free(np);
return;
}
}
}
int main() {
put("apple", "red");
put("banana", "yellow");
put("orange", "orange");
printf("%s\n", get("apple"));
printf("%s\n", get("banana"));
printf("%s\n", get("orange"));
del("banana");
printf("%s\n", get("apple"));
printf("%s\n", get("banana"));
printf("%s\n", get("orange"));
return 0;
}
```
这个示例中,我们使用一个固定大小的哈希表数组来保存键值对。在哈希表中,我们使用hash函数将每个键映射为一个在0到100之间的值,以便可以将其保存在相应的哈希表槽中。如果两个不同的键被映射到相同的位置上,它们将被链表链接起来。在查询和删除操作中,我们需要遍历该链表来查找相应的键。
c语言实现hashmap
实现哈希表(Hashmap)的基本思路是将键值对存储在一个数组中,通过哈希函数将键转换为数组的索引,然后将值存储在该索引处。
下面是一个简单的C语言实现哈希表的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct {
char* key;
int value;
} hash_node;
hash_node* hash_table[TABLE_SIZE];
int hash_function(char* key) {
int hash = 0;
for (int i = 0; i < strlen(key); i++) {
hash += key[i];
}
return hash % TABLE_SIZE;
}
void insert(char* key, int value) {
int index = hash_function(key);
if (hash_table[index] == NULL) {
hash_table[index] = malloc(sizeof(hash_node));
hash_table[index]->key = strdup(key);
hash_table[index]->value = value;
} else {
hash_node* node = hash_table[index];
while (node->next != NULL) {
node = node->next;
}
node->next = malloc(sizeof(hash_node));
node->next->key = strdup(key);
node->next->value = value;
}
}
int search(char* key) {
int index = hash_function(key);
hash_node* node = hash_table[index];
while (node != NULL) {
if (strcmp(node->key, key) == 0) {
return node->value;
}
node = node->next;
}
return -1;
}
int main() {
insert("apple", 1);
insert("banana", 2);
insert("orange", 3);
printf("apple = %d\n", search("apple"));
printf("banana = %d\n", search("banana"));
printf("orange = %d\n", search("orange"));
return 0;
}
```
这个例子中,我们使用一个简单的哈希函数,将字符串中所有字符的ASCII码之和作为哈希值。我们将哈希表的大小设为100,即数组的长度为100。如果两个不同的键具有相同的哈希值,我们采用链表的方式来处理冲突。
在主函数中,我们插入了三个键值对,然后通过搜索函数查找对应的值。运行程序,可以得到以下输出:
```
apple = 1
banana = 2
orange = 3
```
这表明我们的哈希表实现是正确的。当然,这只是一个简单的实现,实际应用中需要考虑更多的因素,例如哈希函数的设计、冲突处理的效率等。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)