TOPK算法的Hash实现

该代码为TOPK算法的Hash实现，简要说明请见博客http://blog.csdn.net/yankai0219/article/details/8185872

/*
 * yk_hash.c
 *
 *  Created on: Nov 13 2012
 *      Author: root
 */


#include“yk_hash.h“

/*for loop :hash = 31* hash + *p  */
unsigned int yk_simple_hash_string（char * strint str_len）
{
	unsigned int hash;
	unsigned char * p;
	int i;
	for（i = 0 hash = 0p = （unsigned char *）str; i < str_len && p; i++p++）
		hash = 31 * hash + *p;

	return （hash & 0x7FFFFFFF）;
}
HASH_TABLE* yk_hash_table_init（）
{
	HASH_TABLE* hashTB = NULL;
	hashTB = （HASH_TABLE *）malloc（sizeof（HASH_TABLE）*BUCKET_LEN）;
	if（NULL == hashTB）{
		printf（“create HASH TABLE error\n“）;
		return NULL;
	}
	memset（hashTB0sizeof（HASH_TABLE）*BUCKET_LEN）;
	return hashTB;
}


NODE * yk_find_data_from_hash_table（HASH_TABLE * hashTbtype keyint key_len）
{
	unsigned int hash_value;
	NODE * pNode;
	hash_value = yk_simple_hash_string（keykey_len）%BUCKET_LEN;
	if（NULL == hashTb ）{
		printf（“NO CHAIN when find data\n“）;
		return NULL;
	}

	pNode = hashTb[hash_value].keys_chain;
	for（;pNode;）{
		if（yk_strcmp（keypNode->keykey_lenpNode->key_len）  == 0）{
			pNode->occur_count++;
			return pNode;
		}

		pNode = pNode->next;
	}
	return NULL;
}


STATUS yk_insert_data_into_hash_table（HASH_TABLE * hashTbtype keyint key_len）
{
	if（NULL == hashTb ）{
		printf（“NO CHAIN when find data\n“）;
		return FALSE;
	}
	unsigned int hash_value;
	NODE * pNode*pNewNode;
	hash_value = yk_simple_hash_string（keykey_len） % BUCKET_LEN;
	printf（“hash value is %d\t key is “hash_value）;
	yk_print_str（keykey_len）;


	hashTb[hash_value].hit_count++;
	pNode = hashTb[hash_value].keys_chain;
	/*no chainso insert data into this chain*/
	if（NULL == pNode）{

		if（ NULL == （pNewNode = （NODE*）malloc（sizeof（NODE））） ）{
			printf（“allocate NODE error“）;
			return FALSE;
		}

		if（NULL == （pNewNode->key = （char*）malloc（key_len * sizeof（char））））{
			printf（“allocate key“）;
			return FALSE;
		}
		/*pNewNode->key = yk_strdup（key）;*/
		yk_cpy_str（pNewNode->keykeykey_len）;
		pNewNode->key_len = key_len;
		pNewNode->next = NULL;
		pNewNode->occur_count = 1;
		hashTb[hash_value].keys_chain = pNewNode;

	    return TRUE;
	}
	/*data has exited in hash table */
	if（ NULL != （yk_find_data_from_hash_table（hashTb keykey_len）） ）
		return FALSE;
	/*insert data into end of chain */
	for（;pNode->next;）
		pNode = pNode->next;

	if（ NULL == （pNewNode = （NODE*）malloc（sizeof（NODE））） ）{
				printf（“allocate NODE error“）;
				return FALSE;
	}
	if（NULL == （pNewNode->key = （char*）malloc（key_len * sizeof（char））））{
			printf（“allocate key“）;
			return FALSE;
	}
	yk_cpy_str（pNewNode->keykeykey_len）;
	pNewNode->key_len = key_len;
	pNewNode->next = NULL;
	pNewNode->occur_count = 1;
	pNode->next = pNewNode;
	return TRUE;

}

void yk_cpy_str（char *dstchar *srcint str_len）
{
	int i;
	for（i = 0; i < str_len; i++）{
		*（dst + i） = *（ src + i）;
	}
}

void   yk_output_result（HASH_TABLE * hashTb）
{
	int i;
	NODE * pNode;
	for（i = 0; i < BUCKET_LEN;i++）{
		printf（“\nBUCKET:@@@ %d @@@ \nhit_count is %d\n“ihashTb[i].hit_count）;
		for（pNode = hashTb[i].keys_c

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      10822  2012-11-15 10:12  study-hash3\.cproject

     文件        763  2012-11-15 10:12  study-hash3\.project

     文件        974  2012-11-15 10:12  study-hash3\Debug\makefile

     文件        231  2012-11-15 10:12  study-hash3\Debug\objects.mk

     文件        390  2012-11-15 10:12  study-hash3\Debug\sources.mk

     文件      66805  2012-11-15 10:12  study-hash3\Debug\study-hash3

     文件        711  2012-11-15 10:12  study-hash3\Debug\subdir.mk

     文件         62  2012-11-15 10:12  study-hash3\Debug\yk_hash.d

     文件      26632  2012-11-15 10:12  study-hash3\Debug\yk_hash.o

     文件         77  2012-11-15 10:12  study-hash3\Debug\yk_hash_main.d

     文件      39480  2012-11-15 10:12  study-hash3\Debug\yk_hash_main.o

     文件        350  2012-11-15 10:12  study-hash3\readme.txt

     文件        205  2012-11-15 10:12  study-hash3\testForTop10.txt

     文件       3720  2012-11-15 10:12  study-hash3\yk_hash.c

     文件       1026  2012-11-15 10:12  study-hash3\yk_hash.h

     文件        693  2012-11-15 10:12  study-hash3\yk_hash_main.c

     目录          0  2012-11-15 10:12  study-hash3\Debug

     目录          0  2012-11-15 10:12  study-hash3

----------- ---------  ---------- -----  ----

               152941                    18