哈希实现

叁歲伎倆 2022-08-09 11:55 192阅读 0赞

/*
    *一、哈希函数	
    1. 将节点保存在FILE_NODE中，以链地址法，加入全局Hash表
    2. 使用FILE_NODE作为结点，实现一个全局Hash表
    3. 采用除留余数法，表长为P，取P=5
        散列函数为  H (key)=key % P；
    4. 使用size作为key
    5. 实现查找某个文件的操作
    6. 实现对Hash表的遍历函数
    *
    *data:  2015-10-22 *
    *by: lcf
    *
    */
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define  MAX_HASH_KEY   5  
    
    typedef struct _FILE_NODE {
    
    	struct _FILE_NODE  *prev;
    	struct _FILE_NODE  *next;
    
    	void   *wzFileName;
    	int         size;
    
    } FILE_NODE, *LPFILENODE;
    
    
    typedef struct _HASH
    {
    	FILE_NODE** bucket;
    	int (*hash)(int );
    	
    	
    }Hash;
    
    int my_hash(int  key)
    {
    	return  key%MAX_HASH_KEY;
    }
    
    
    static inline void my_add(FILE_NODE* new, FILE_NODE* prev, FILE_NODE* next)
    {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
    }
    
    static inline void my_del_init(FILE_NODE* prev, FILE_NODE* next)
    {
        next->prev = prev;
        prev->next = next;
    }
    
    
    int my_add_hash(Hash* ht, char* data, int data_len)
    {
    	if(NULL == ht)
    		return -1;
    	int val = ht->hash(data_len);
    	FILE_NODE* tmp = (FILE_NODE* )calloc(1, sizeof(FILE_NODE));
    	tmp->wzFileName = data;
    
    	tmp->size = data_len;
    
    	if(ht->bucket[val] ==  NULL)
    	{	
    		tmp->prev = tmp->next = tmp;
    		ht->bucket[val] = tmp;	
    	}
    	else
    	{
    		my_add(tmp, ht->bucket[val], ht->bucket[val]->next);
    	}
    	return 0;
    }
    
    void  travel(Hash* ht)
    {
    	int i = 0;
    	for(i; i<MAX_HASH_KEY; i++)
    	{
    		FILE_NODE* node = ht->bucket[i];
    		if(NULL == node)
    			continue;
    		FILE_NODE* pos = ht->bucket[i]->next;
    		FILE_NODE* tmp = pos->next;
    	
    		while(pos != node)
    		{
    				
    			printf("filename: %s, size: %d\n", (char*)pos->wzFileName, pos->size);
    			tmp = pos->next;
    			pos = tmp;
    				
    		}
    		if(node == pos)
    		{
    			printf("filename: %s, size: %d\n", (char*)node->wzFileName, node->size);
    		}
    	}
    }
    
    
    void look(Hash* ht, char* dst)
    {
    	int val = ht->hash(strlen(dst));
    
    	if(NULL == ht->bucket[val])
    	{	
    		printf("can't  find data\n");
    		return ;
    	}
    	FILE_NODE* head = ht->bucket[val];
    	if(!memcmp(head->wzFileName, dst, strlen(dst)))
    	{
    		printf("find it : ");
    		printf("filename: %s, size: %d\n", (char*)head->wzFileName, head->size);
    		return;
    	}
    	FILE_NODE* pos, *n;
    	pos = NULL ; n = NULL;
    	for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
    	{
    		if(!memcmp(pos->wzFileName, dst, strlen(dst)))
    		{
    			printf("find it : ");
    			printf("filename: %s, size: %d\n", (char*)pos->wzFileName, pos->size);
    			break;
    		}
    	}
    	return;
    }
    
    void del(Hash* ht, char* dst)
    {
    	int val = ht->hash(strlen(dst));
    	if(NULL == ht->bucket[val])
    	{
    		printf("can't find data\n");
    		return ;
    	}
    	FILE_NODE* head = ht->bucket[val]; //需考虑删除头结点情况
    	FILE_NODE* pos, *n;pos = NULL ; n = NULL;
    	for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
    	{
    		if(!memcmp(pos->wzFileName, dst, strlen(dst)))
    		{	
    			printf("remove it : ");
    			printf("filename: %s, size: %d\n", (char*)pos->wzFileName, pos->size);
    			my_del_init(pos->prev, pos->next);
    			free(pos);pos = NULL;
    			break;
    		}
    	}
    	return;
    }
    
    #define KERNEL_LIST_POISON1 ((void *) 0x00100100)
    #define KERNEL_LIST_POISON2 ((void *) 0x00200200)
    
    void my_free(Hash* ht)
    {
    	int i =0;
    	for(i; i<MAX_HASH_KEY; i++)
    	{
    		FILE_NODE* head = ht->bucket[i];
    		if(NULL == head)
    			continue;
    		FILE_NODE* pos, *n;
    		pos = NULL ; n = NULL;
    		for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
    		{
    			my_del_init(pos->prev, pos->next);
    			pos->prev  = (FILE_NODE  *)KERNEL_LIST_POISON1;
    			pos->next = (FILE_NODE  *)KERNEL_LIST_POISON2;
    		}
    		if(NULL != head)
    		{
    			free(head);
    			head = NULL;
    		}
    	}
    	free(ht);
    	ht = NULL;
    	return;
    }
    
    
    int main()
    {
    	Hash* ht = (Hash*)calloc(1, sizeof(Hash));
    
    	ht->bucket = (FILE_NODE*)calloc(1, sizeof(FILE_NODE)*1024);
    	ht->hash = my_hash;
    
    	char * lcf = "lcf";
        my_add_hash(ht, lcf, strlen(lcf));
    
    	char * lcf3 = "l2f";
    	my_add_hash(ht, lcf3, strlen(lcf3));
    
    	char * lcf5 = "l5f";
    	my_add_hash(ht, lcf5, strlen(lcf5));
    
    	char * lcf2 = "lcf222";
    	my_add_hash(ht, lcf2, strlen(lcf2));
    
    	char * lcf4 = "lcf888";
    	my_add_hash(ht, lcf4, strlen(lcf4));
    
    	travel(ht);
    
    	look(ht, "l2f");
    	look(ht, "lcf2222");
    	look(ht, "l5f");printf("====del===========");
    
    	del(ht, "l2f");
    
    	travel(ht);
    
    	my_free(ht);
    	ht = NULL;
    }
    
    
    附： 常用的hash函数
    int my_hash(char* data)
    {
    	unsigned n=0;    
        char* p;    
        for(p=data;*p;p++)    
            n=31*n+(*p);    
    	return  n%MAX_HASH_KEY;
    }