[数据结构与算法]手写hash数据结构

用C语言手写hash数据结构和接口； 提供添加、删除、查询等功能。

/*
  采用链表方式解决冲突问题。
*/

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

#define MaxSize 65535

//hash 节点
typedef struct dnode{
	char *key;
	char *value;
	struct dnode * next;
} DNode;

//hash表
typedef struct dtable{
	Dnode ** table;
	int size; //节点个数
}DTable;

//创建节点
DNode* create_dnode(const char* key, const char* value){
	DNnode * node = (DNode *)malloc(sizeof(DNode));
	node->key = (char *)malloc(strlen(key)+1);
	node->value = (char *)malloc(strlen(value)+1);
	strcpy(node->key, key);
	strcpy(node->value, value);
	node->next = NULL;
	return node;
}
void free_dnode(DNode * node){
	free(node->key);
	free(node->value);
	free(node);
}

//创建hash表
DTable * create_table(void){
	DTable * hash_table = (DTable *)malloc(sizeof(DTable));
	hash_table-> size = 0;
	hash_table->table = (DNode **) calloc(MaxSize, sizeof(DNode*))
	for (int idx=0; idx<MaxSize; idx ++){
		hash_table->table[idx] = NULL;
	}
	return hash_table;
} 

void free_table(DTable *hash_table){
	for (int idx=0; idx<MaxSize; idx++){
		DNode * item = hash_table->table + idx;
		while（item !=NULL）{
			DNode *tmp= item;
			item=item->next;
			free_dnode(tmp);
		}
	}
	free(hash_table->table);
	free(hash_table);
}
//简单的hash 函数
int simple_hash(const char *key)
{   
    unsigned long hash = 0;  
    char *p = key;
    for(hash = 0; *p; p++) {
        hash = 31 * hash + *p;
    }
    return (hash & 0x7FFFFFFF) % MaxSize;
}

void insert(DTable* hash_table, char *key, char*value){
	int idx = simple_hash(key);
	DNode *item = hash_table->table[idx];
	DNode *node = create_dnode(key, value);
	if (item ==NULL){
		hash_table->table[idx]= node;
		hash_table->size ++;
		return;
	}
	while(item->next !=NULL){
		if (strcmp(item->key, key)==0){
			if (strcpm(item->value, value) !=0)
				strcpy(item->value, value);
			return ;
		} 
		item = item->next;
	}
	item->next = node;
	hash_table->size ++;
}

void delete(DTable* hash_table, char *key){
	int idx = simple_hash(key);
	DNode *item = hash_table->table[idx];
	if (item ==NULL){return;}

	if (strcmp(item-> key, key)==0){
		hash_table->table[idx] = item ->next;
		free_dnode(item);
		hash_table->size --;
		return;
	}
	DNode *pre = item;
	item=item->next;
	while (item !=NULL){
		if (strcmp(item-> key, key)==0){
			pre->next = item->next;
			free_dnode(item);
			hash_table->size --;
			return;
		}
		pre=item;
		item =item->next;
	}
}

char * search(DTable* hash_table, char *key){
	int idx = simple_hash(key);
	DNode *item = hash_table->table[idx];
	if (item ==NULL){return NULL;}
	while(item !=NULL){
		if (strcmp(item->key, key)==0){
			return item->value;
		}
		item = item->next;
	}
	return NULL;
}