简单的哈希表数据结构实现 https://github.com/watmough/jwHash

hash.c

// gcc -DHASHDEBUG hash.c -o hash
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

#ifdef HASHDEBUG
# define HASH_DEBUG(fmt,args...) printf(fmt, ## args)
#else
# define HASH_DEBUG(fmt,args...) do {} while (0);
#endif

typedef enum
{
	HASHOK,
	HASHADDED,
	HASHREPLACEDVALUE,
	HASHALREADYADDED,
	HASHDELETED,
	HASHNOTFOUND,
} HASHRESULT;

typedef struct HashEntry HashEntry;
struct HashEntry
{
	char *key;
	void  *value;
	HashEntry *next; //chain
};

typedef struct HashTable HashTable;
struct HashTable
{
	HashEntry **bucket;			// pointer to array of buckets
	size_t buckets;
};

static inline long int hashString(char * str)
{
	unsigned long hash = 5381;
	int c;

	while (c = *str++)
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
	return hash;
}

static inline char * copystring(char * value)
{
	char * copy = (char *)malloc(strlen(value)+1);
	if(!copy) {
		printf("Unable to allocate string value %s\n",value);
		abort();
	}
	strcpy(copy,value);
	return copy;
}

HashTable *create_hash( size_t buckets )
{
	HashTable *table= (HashTable *)malloc(sizeof(HashTable));
	if(!table) {
		return NULL;
	}
	// setup
	table->bucket = (HashEntry **)malloc(buckets*sizeof(void*));
	if( !table->bucket ) {
		free(table);
		return NULL;
	}
	memset(table->bucket,0,buckets*sizeof(void*));
	table->buckets = buckets;
	HASH_DEBUG("table: %x bucket: %x\n",table,table->bucket);
	return table;
}

HASHRESULT delete_hash( HashTable *table )
{
	if (!table) {
		return HASHNOTFOUND;
	}

	free(table->bucket);

	free(table);

	return HASHOK;
}

HASHRESULT add_ptr_by_str( HashTable *table, char *key, void *ptr )
{
	// compute hash on key
	size_t hash = hashString(key) % table->buckets;
	HASH_DEBUG("adding %s -> %x hash: %ld\n",key,ptr,hash);

	// add entry
	HashEntry *entry = table->bucket[hash];

	// already an entry
	HASH_DEBUG("entry: %x\n",entry);
	while(entry!=0) //处理冲突
	{
		HASH_DEBUG("checking entry: %x\n",entry);
		// check for already indexed
		if(0==strcmp(entry->key,key) && ptr==entry->value)
			return HASHALREADYADDED;
		// check for replacing entry
		if(0==strcmp(entry->key,key) && ptr!=entry->value)
		{
			entry->value = ptr;
			return HASHREPLACEDVALUE;
		}
		// move to next entry
		entry = entry->next;
	}

	// create a new entry and add at head of bucket
	HASH_DEBUG("creating new entry\n");
	entry = (HashEntry *)malloc(sizeof(HashEntry));
	HASH_DEBUG("new entry: %x\n",entry);
	entry->key = copystring(key);
	entry->value = ptr;
	entry->next = table->bucket[hash];
	table->bucket[hash] = entry;
	HASH_DEBUG("added entry\n");
	return HASHOK;
}

HASHRESULT del_by_str( HashTable *table, char *key )
{
	// compute hash on key
	size_t hash = hashString(key) % table->buckets;
	HASH_DEBUG("deleting: %s hash: %ld\n",key,hash);

	// add entry
	HashEntry *entry = table->bucket[hash];
	HashEntry *previous = NULL;

	// found an entry
	HASH_DEBUG("entry: %x\n",entry);
	while(entry!=0)
	{
		HASH_DEBUG("checking entry: %x\n",entry);
		// check for already indexed
		if(0==strcmp(entry->key,key))
		{
			// skip first record, or one in the chain
			if(!previous)
				table->bucket[hash] = entry->next;
			else
				previous->next = entry->next;
			// delete string value if needed
			free(entry->value);
			free(entry->key);
			free(entry);
			return HASHDELETED;
		}
		// move to next entry
		previous = entry;
		entry = entry->next;
	}
	return HASHNOTFOUND;
}

void* get_ptr_by_str( HashTable *table, char *key )
{
	// compute hash on key
	size_t hash = hashString(key) % table->buckets;
	HASH_DEBUG("fetching %s -> ?? hash: %d\n",key,hash);

	// get entry
	HashEntry *entry = table->bucket[hash];

	// already an entry
	while(entry)
	{
		// check for key
		HASH_DEBUG("found entry key: %d value: %s\n",entry->key,entry->value);
		if(0==strcmp(entry->key,key)) {
			return entry->value;
		}
		// move to next entry
		entry = entry->next;
	}
	// not found
	return NULL;
}

int main(int argc, char *argv[])
{
	char *get_str;
	char ch[] = "hello,hash!";
	char *p = (char *)malloc(sizeof(ch));
	strncpy(p, ch, sizeof(ch));
	HashTable *phash = create_hash(1); //创建散列表
	if (add_ptr_by_str(phash, "ljp", (void *)p) != HASHOK)
		return -1;
	printf("get from hash: %s\n", (char *)get_ptr_by_str(phash, "ljp"));
	del_by_str(phash, "ljp");
	delete_hash(phash);
	return HASHOK;
}