用C实现哈希算法代码并作注释
时间: 2024-05-11 16:16:11 浏览: 15
好的,下面是C语言实现的哈希算法代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 哈希表大小 */
#define HASH_TABLE_SIZE 100
/* 结点结构体 */
typedef struct node
{
char key[128];
char value[128];
struct node *next;
}Node;
/* 哈希表结构体 */
typedef struct hash_table
{
/* 指向结点的指针数组 */
Node *nodes[HASH_TABLE_SIZE];
}HashTable;
/* 哈希函数,计算字符串的哈希值 */
unsigned int hash(char *str)
{
unsigned int hash_value = 0;
unsigned int seed = 131;
while(*str)
{
hash_value = hash_value * seed + (*str++);
}
return hash_value % HASH_TABLE_SIZE;
}
/* 创建结点 */
Node *create_node(char *key, char *value)
{
Node *node = (Node*)malloc(sizeof(Node));
strcpy(node->key, key);
strcpy(node->value, value);
node->next = NULL;
return node;
}
/* 插入结点 */
void insert_node(HashTable *hash_table, char *key, char *value)
{
unsigned int index = hash(key);
/* 如果该位置还未有结点,则直接插入 */
if(hash_table->nodes[index] == NULL)
{
hash_table->nodes[index] = create_node(key, value);
return;
}
/* 如果该位置已有结点,则在链表尾部插入新结点 */
Node *node = hash_table->nodes[index];
while(node->next != NULL)
{
node = node->next;
}
node->next = create_node(key, value);
}
/* 查找结点 */
Node *find_node(HashTable *hash_table, char *key)
{
unsigned int index = hash(key);
/* 如果该位置没有结点,则返回空指针 */
if(hash_table->nodes[index] == NULL)
{
return NULL;
}
/* 如果该位置有结点,则遍历链表查找 */
Node *node = hash_table->nodes[index];
while(node != NULL && strcmp(node->key, key) != 0)
{
node = node->next;
}
return node;
}
int main()
{
HashTable hash_table = {0};
/* 在哈希表中插入若干个结点 */
insert_node(&hash_table, "apple", "苹果");
insert_node(&hash_table, "banana", "香蕉");
insert_node(&hash_table, "cat", "猫");
insert_node(&hash_table, "dog", "狗");
/* 查找特定结点 */
Node *node = find_node(&hash_table, "apple");
if(node != NULL)
{
printf("%s-%s\n", node->key, node->value);
}
return 0;
}
```
上述代码实现了一个简单的哈希表,使用字符串作为 key 和 value。其中,哈希函数使用了常见的"乘法取整"法,同时使用了随机种子,以尽可能降低冲突的可能性。代码中,insert_node() 函数实现了将结点插入哈希表的操作,而 find_node() 函数实现了在哈希表中查找结点的操作。
相关推荐
![](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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)