hash table implementation 哈希列表的代码实现

My implementation of Hash Table 

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized^[2]) constant average cost per operation.^[3][4]

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

我的代码实现:

hash_table.h

#ifndef _HASH_TABLE_H
#define _HASH_TABLE_H 1

	#define NODE_NAME_SIZE 20
	struct node
	{
		int used;
		int index;
		char name[NODE_NAME_SIZE];//store the string what we interesting
	};

	#define ARRAY_SIZE 10
	#define TABLE_SIZE 40

	#define OPEN_SUCCESS   0
	#define OPEN_FAILED    1
	#define FREAD_FAILED   2
	#define FREAD_SUCCESS  3
	#define FWRITE_FAILED  4
	#define FWRITE_SUCCESS 5

	#define USED   1
	#define UNUSED 0

	#include "hash_function.h"
	#include "hash_insert_data.h"
	#include "init_table.h"
	#include "print_hash_table.h"

#endif

/************************************************************
code writer: EOF
code date: 2014.03.06
e-mai: jasonleaster@gmail.com
code purpose:
	Just a test source file for hash table. I would be
happy, if my code will help you to know what is hash table.

If something wrong with my code, please touche me by e-mail

************************************************************/

#include <stdio.h>
#include "hash_table.h"
 
int main()
{
	int temp  = 0;
	int foo   = 0;
	int index = 0;

	char* people[ARRAY_SIZE] = {"jason",
			 	   "liuzijian",
			 	   "yunyun",
			 	   "foo",
			 	   "hello",
				   "world",
			           "dedo",
				   "an",
			 	   "god",
			 	   "tomato"};
	
	init_table("test.txt",TABLE_SIZE);
	
	for(temp = 0;temp < ARRAY_SIZE; temp++)
	{
		index = hash_function(people[temp]);

		foo  = hash_insert_data("test.txt",people[temp],index);
		if(foo != OPEN_SUCCESS)
		{
			printf("something wrong!\n");
			return 0;
		}
	}

	print_hash_table("test.txt",TABLE_SIZE);		

	return 0;
}

/************************************************************
code writer: EOF
code date: 2014.03.06
e-mai: jasonleaster@gmail.com
code purpose:
	Just a test source file for hash table. I would be
happy, if my code will help you to know what is hash table.

If something wrong with my code, please touche me by e-mail

************************************************************/

#include <stdio.h>
#include "hash_table.h"

int init_table(char* filename,int table_size)
{
	struct node temp_data;
	int temp = 0;

	FILE* p_file;
	
	p_file = fopen(filename,"a");
	//For special attention, access premission "a" is very improtant. I kill 5 hours with this fucking bug!!
	
	if(p_file == NULL)
	{
		printf("fopen error\n");
		return 0;
	}
	else
	{
		temp_data.used = UNUSED;
		temp_data.index = 0;
	}
	
	fseek(p_file,0,SEEK_SET);
	
	for(temp = 0;temp < TABLE_SIZE; temp++)
	{
	 	fseek(p_file,(temp)*sizeof(struct node),SEEK_SET);

		if(fwrite(&temp_data,sizeof(struct node),1,p_file) < 0)
		{
			printf("fwrite process\n");
			fclose(p_file);
			return 0;
		}
	}	

	fclose(p_file);

	return 0;
}

/************************************************************
code writer: EOF
code date: 2014.03.06
e-mai: jasonleaster@gmail.com
code purpose:
	Just a implementation for hash_function.I would be
happy, if my code will help you to know what is hash table.

If something wrong with my code, please touche me by e-mail
************************************************************/
#include "hash_table.h"

int hash_function(char * string)
{
	int temp = 0;
	int key = 0;
	
	for(temp = 0; string[temp] != ‘\0‘;temp++)
	{
		key += string[temp];
	}
	
	key %= TABLE_SIZE;
	
	return key;//index value
}

print_hash_table.c

/************************************************************
code writer: EOF
code date: 2014.03.06
e-mai: jasonleaster@gmail.com
code purpose:
	Just a implementation for print_hash_table function .
I would be happy, if my code will help you to know 
what is hash table.

If something wrong with my code, please touche me by e-mail

***********************************************************/
#include "stdio.h"
#include "hash_table.h"

int print_hash_table(char* filename,int table_size)
{
	FILE* p_file = NULL;
	
	int temp = 0;
	struct node temp_node;

	p_file = fopen(filename,"r");
	
	if(p_file == NULL)
	{
		printf("fopen failed\n");
		return OPEN_FAILED;
	}

	for(temp = 0;temp < TABLE_SIZE; temp++)
	{
		fseek(p_file,temp*sizeof(struct node),SEEK_SET);

		if(fread(&temp_node,sizeof(struct node),1,p_file) <= 0)
		{
			printf("fread wrong!\n");
		}	

		if(temp_node.used == USED)
		{
			printf("index: %d name:%s\n",temp_node.index,temp_node.name);
		}
	}

	fclose(p_file);

	return OPEN_SUCCESS;
}

老规矩，简单到shi的header file就不全部贴出来了，一个example搞定：

#ifndef _INIT_TABLE_H
#define _INIT_TABLE_H 1

	extern int init_table(char* filename,int table_size);

#endif

我始终坚持开源精神，希望看过代码的人能挑出我代码中的瑕疵，也希望我的代码能帮助不懂hash table的初学者理解what is hash table.

EOF
2014.03.07

于XTU 晚

hash table implementation 哈希列表的代码实现,布布扣,bubuko.com

hash table implementation 哈希列表的代码实现

原文：http://blog.csdn.net/cinmyheart/article/details/20740975