学步园

/*
 * DataStructure.c
 *
 *  Created on: 2013年8月2日
 *      Author: huang
 */

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

//-----------------------------------------------------------------------------
// MurmurHash2, by Austin Appleby

// Note - This code makes a few assumptions about how your machine behaves -

// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4

// And it has a few limitations -

// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
//    machines.

// seed不同就代表了不同的Hash

unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
{
	// 'm' and 'r' are mixing constants generated offline.
	// They're not really 'magic', they just happen to work well.

	const unsigned int m = 0x5bd1e995;
	const int r = 24;

	// Initialize the hash to a 'random' value

	unsigned int h = seed ^ len;

	// Mix 4 bytes at a time into the hash

	const unsigned char * data = (const unsigned char *)key;

	while(len >= 4)
	{
		unsigned int k = *(unsigned int *)data;

		k *= m;
		k ^= k >> r;
		k *= m;

		h *= m;
		h ^= k;

		data += 4;
		len -= 4;
	}

	// Handle the last few bytes of the input array

	switch(len)
	{
	case 3: h ^= data[2] << 16;
	case 2: h ^= data[1] << 8;
	case 1: h ^= data[0];
	        h *= m;
	};

	// Do a few final mixes of the hash to ensure the last few
	// bytes are well-incorporated.

	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;

	return h;
}

typedef struct HashNode {
	char *key;
	void *value;
	struct HashNode *next;
} HashNode ;

typedef struct HashTable {
	HashNode **table;
	int size;
	int used;
} HashTable ;


HashTable *create(int);
HashNode *createNode(char * , void *);
void put(HashTable * , char * , void *);
void *get(HashTable * , char *);
void delete(HashTable * , char * , void * , int (*equal)(char * , char *) );
int contain(HashTable * , char * , void * , int (*equal)(char * , char *) );
HashTable *rehash(HashTable *);
void destory(HashTable *);

int equal(char *data , char *data2)
{
	return strcmp(data , data2) == 0;
}

int main()
{
    HashTable *ht = create(1024);
    put(ht , "name" , "hyy");
    printf("%d%d" , contain(ht , "name" , "hyy" , equal) , contain(ht , "name" , "hyy1" , equal));
    printf("%s" , (char *)get(ht , "name"));
	return 0;
}

HashTable *create(int size)
{
	HashTable *ht = malloc(sizeof(HashTable));
	ht->size = size;
	ht->used = 0;
	ht->table = calloc(size , sizeof(HashNode *));
	return ht;
}

HashNode *createNode(char *key , void *value)
{
	HashNode *node = malloc(sizeof(HashNode));
	node->key = key;
	node->value = value;
	node->next = NULL;
	return node;
}

//不检查是否有相同key value对
void put(HashTable *ht , char *key , void *value)
{
	HashNode *node = createNode(key , value);
	int pos = MurmurHash2(key , strlen(key) , 1) % ht->size;

	if(ht->table[pos] == NULL)
		ht->table[pos] = node;
	else
	{
		HashNode *entry = ht->table[pos];
		while(entry->next != NULL)
		{
			entry = entry->next;
		}
		entry->next = node;
	}
	ht->used++;
}

int contain(HashTable *ht , char *key , void *value , int (*equal)(char * , char *))
{
	int pos = MurmurHash2(key , strlen(key) , 1) % ht->size;
	HashNode *entry = ht->table[pos];
	while(entry != NULL)
	{
		if(strcmp(key , entry->key) == 0 && equal(value , entry->value))
			return 1;
		entry = entry->next;
	}
	return 0;
}

void *get(HashTable *ht , char *key)
{
	int pos = MurmurHash2(key , strlen(key) , 1) % ht->size;
	HashNode *entry = ht->table[pos];

	if(entry == NULL)
		return NULL;
	else
	{
		while(entry != NULL)
		{
			if(strcmp(key , entry->key) == 0)
				return entry->value;
			entry = entry->next;
		}
		return NULL;
	}
}

HashTable *rehash(HashTable *ht)
{
	int i = ht->size;
	HashTable *new = create(i * 2);
	while(i >= 0)
	{
		if(ht->table[i] != NULL)
		{
			HashNode *entry = ht->table[i];
			while(entry != NULL)
			{
				put(new , entry->key , entry->value);
				entry = entry->next;
			}
		}
		i--;
	}
	free(ht->table);
	free(ht);
	return new;
}

void destory(HashTable *ht)
{
	free(ht->table);
	free(ht);
}

void delete(HashTable *ht , char *key , void *data , int (*equal)(char * , char *))
{
	int pos = MurmurHash2(key , strlen(key) , 1) % ht->size;
	HashNode *entry = ht->table[pos];

	if(entry == NULL)
		return ;

	if(entry != NULL && entry->next == NULL)
	{
		if(strcmp(key , entry->key) == 0 && equal(data , entry->value))
			entry = NULL;
	}
	else
	{
		HashNode *next = entry->next;
		if(strcmp(key , entry->key) == 0 && equal(data , entry->value))
		{
			HashNode *tmp = entry;
			entry = next;
			free(tmp);
		}
		else
		{
			while(next != NULL)
			{
				if(strcmp(key , next->key) == 0 && equal(data , next->value))
				{
					if(next->next == NULL)
					{
						entry->next = NULL;
						free(next);
					}
					else
					{
						entry->next = next->next;
						free(next);
					}
				}
				entry = next;
				next = next->next;
			}
		}
	}
}