hash算法采用最简单的求余。
/hash算法/
int hash(char key, int size){
int rect = 0;
while (key != ‘\0’)
{
rect += key;
key++;
}
return rect%size;
}
解决冲突使用的是 链表
###头文件
Hashtable.h###typedef struct HashNode{
char key;
char value;
HashNode next; //相同hash取下一个节点
} HashNode;
typedef struct Hashtable{
int size;
int item_size;
HashNode head;
} Hashtable;
/初始化/
Hashtable hashtable_init(int size);
/添加一个/
void hashtable_put(Hashtable hashtable, char key, char value);
/获取一个/
char hashtable_get(Hashtable hashtable, char key);
/删除一个/
void hashtable_remove(Hashtable hashtable, char key);
/销毁/
void hashtable_destroy(Hashtable hashtable);
/打印/
void hashtable_print(Hashtable hashtable);
/hash算法/
int hash(char* key, int size);
###实现 Hashtable.c###
// HashTable.c: 主项目文件。
#include <stdio.h>
#include <stdlib.h>
#include "Hashtable.h"
/*hash算法*/
int hash(char* key, int size){
int rect = 0;
while (*key != '\0')
{
rect += *key;
key++;
}
return rect%size;
}
/*初始化hashtable*/
Hashtable* hashtable_init(int size){
Hashtable* hashtable = (Hashtable*)calloc(1, sizeof(Hashtable));
hashtable->size = size;
hashtable->item_size = 0;
HashNode* head = (HashNode *)calloc(size, sizeof(HashNode));
hashtable->head = head;
return hashtable;
}
/*添加一个*/
void hashtable_put(Hashtable *hashtable, char* key, char* value){
int index = hash(key, hashtable->size);
HashNode *hashNode = hashtable->head + index;
while (true)
{
if (hashNode->key == NULL || *key == *(hashNode->key))
{
if (hashNode->key == NULL)
{
hashtable->item_size = hashtable->item_size + 1;
}
hashNode->key = key;
hashNode->value = value;
return;
}
if (hashNode->next != NULL){
hashNode = hashNode->next;
}
else{
HashNode *newNode = (HashNode*)calloc(1, sizeof(HashNode));
newNode->key = key;
newNode->value = value;
hashNode->next = newNode;
hashtable->item_size = hashtable->item_size + 1;
return;
}
}
}
/*获取一个*/
char* hashtable_get(Hashtable *hashtable, char* key){
int index = hash(key, hashtable->size);
HashNode *hashNode = hashtable->head + index;
while (hashNode != NULL)
{
if (hashNode->key != NULL&&*key == *(hashNode->key))
{
return hashNode->value;
}
hashNode = hashNode->next;
}
return NULL;
}
/*删除一个*/
void hashtable_remove(Hashtable *hashtable, char* key){
int index = hash(key, hashtable->size);
HashNode *hashNode = hashtable->head + index;
HashNode *temp = hashNode;
while (hashNode != NULL)
{
if (*key == *(hashNode->key))
{
if ((hashtable->head + index) == hashNode)
{
hashNode->key = NULL;
hashNode->value = NULL;
}
else
{
temp->next = hashNode->next;
free(hashNode);
}
hashtable->item_size = hashtable->item_size - 1;
return;
}
temp = hashNode;
hashNode = hashNode->next;
}
return;
}
/*销毁*/
void hashtable_destroy(Hashtable *hashtable){
HashNode *head = hashtable->head;
for (int index = 0; index < hashtable->size; index++)
{
HashNode *next = head->next;
while (next != NULL)
{
HashNode *temp = next;
next = next->next;
free(temp);
}
head++;
}
free(hashtable->head);
free(hashtable);
}
/*打印*/
void hashtable_print(Hashtable *hashtable){
HashNode *head = hashtable->head;
for (int index = 0; index < hashtable->size; index++)
{
printf("index:%d\t", index);
if (head->key!=NULL)
{
printf("%s:%s\t", head->key, head->value);
}
HashNode *next = head->next;
while (next != NULL)
{
if (next->key != NULL)
{
printf("%s:%s\t", next->key, next->value);
}
next = next->next;
}
printf("\n");
head++;
}
}
int main()
{
Hashtable * hashtable = hashtable_init(10);
hashtable_put(hashtable, "a", "1");
hashtable_put(hashtable, "b", "2");
hashtable_put(hashtable, "c", "3");
hashtable_put(hashtable, "d", "4");
hashtable_put(hashtable, "e", "5");
hashtable_put(hashtable, "f", "6");
hashtable_put(hashtable, "g", "7");
hashtable_put(hashtable, "h", "8");
hashtable_put(hashtable, "i", "9");
hashtable_put(hashtable, "j", "10");
hashtable_put(hashtable, "k", "11");
hashtable_put(hashtable, "l", "12");
hashtable_put(hashtable, "f", "8");
hashtable_remove(hashtable, "f");
hashtable_print(hashtable);
char * s = hashtable_get(hashtable, "M");
hashtable_destroy(hashtable);
getchar();
return 0;
}