hash.c

hash表算法

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

void hash_init(hash_table *hash, int length)
{
	hash->table = (hash_item **)malloc(sizeof(hash_item *) * length);//array[length],store hash_item*

	memset(hash->table, 0x00, sizeof(hash_item *) * length);

	hash->length = length;
	hash->cur = 0;
}

void hash_clear(hash_table *hash)
{
}

void hash_insert(hash_table *hash, KeyType key, DataType data, HASH_KEY_PROC hash_key, KEY_EQUAL_PROC key_equal)
{
	hash_item *new = NULL;
	hash_item *get = NULL;
	int index;	

	index =  hash_key(key) % hash->length;
	get = hash->table[index];	

	while(get) {// if have item in table[index],enter
		if(key_equal(key,get->key)) {//check if old key(get->key) equal new key(key).= re 0,!= re 1 ,break,
			break;
		}

		get = get->next;
	}//after loop, get will be NULL;

	if (get) {	//have same key
		new = get;
	} else {		//no item or no same key
		new = (hash_item *)malloc(sizeof(hash_item));

		new->next = hash->table[index];	//add new item before all exist item

		if (NULL == new->next)//if no item exist
			hash->cur ++;

		hash->table[index] = new;
	}

	new->key = key;//overwrite item
	new->data = data;
	
	if (hash->cur >= (hash->length))
		hash_expend(hash, hash_key);
}

DataType hash_search(hash_table *hash, KeyType key, HASH_KEY_PROC hash_key, KEY_EQUAL_PROC key_equal, DataType invaild)
{
	DataType ret;
	hash_item *item = NULL;
	int index;	

	ret = invaild;

	index = hash_key(key) % hash->length;		
	item = hash->table[index];
	
	while(item) {
		if (key_equal(key, item->key)) {
			ret = item->data;	
			break;
		}

		item = item->next;
	}
	
	return ret;//if item exisit && key == item->key ,return item->data,else return invaild;
}

void hash_for_each(hash_table *hash, HASH_PROC proc)
{
	int i = 0;
	hash_item *item =NULL;
	
	for (i = 0; i < hash->length; i ++) {
		item = hash->table[i];

		int count = 0;

		while(item) {	//














































































































































































































































































































































































































































































































































































































































































































































































































































`







 
			printf("count:%d\t | ", count);
			proc(item->key, item->data);
			
			item = item->next;
			count ++;
		}
	}
}

void hash_expend(hash_table *tl, HASH_KEY_PROC hash_key)
{
	int i, index;
	int newLength =  tl->length * 2;
	hash_item *item = NULL;
	hash_item *next = NULL;

	printf("expend.\n");
	hash_item **newTable = (hash_item **)malloc(sizeof(hash_item *) * newLength);
	memset(newTable, 0x00, sizeof(hash_item*) * newLength);

	for (i = 0; i < tl->length; i ++) {
		item = tl->table[i];	
		
		while (item) {
			next = item->next;

			index = hash_key(item->key) % newLength;	

			item->next = newTable[index];
			newTable[index] = item;
			item = next;
		}
	}	
	
	free(tl->table);
	tl->table = newTable;
	tl->length = newLength;
}