C实现Hash表，开放定址法

typedef int KeyType; 
typedef int ValueType; 

//用枚举来表示当前节点的状态
typedef enum Status 
{ 
	EMPTY, //空
	EXITS, //存在
	DELET, //删除
}Status; 

typedef struct HashNode 
{ 
	KeyType _key; 
	ValueType _value; 
	Status _status; 
}HashNode; 

typedef struct HashTable 
{ 
	HashNode* _tables; 
	size_t _size; 
	size_t _N;
}HashTable; 

size_t GetNextPrimeSize(size_t cur);
size_t HashFunc(KeyType key,size_t size);
HashTable* HashTableInit();
int HashTableInsert(HashTable** ht, KeyType key, ValueType value);
HashNode* HashTableFind(HashTable* ht, KeyType key); 
int HashTableRemove(HashTable** ht, KeyType key); 
void HashTableDestory(HashTable** ht); 

//实现代码

void HashTablePrint(HashTable* ht){
	int i;
	assert(ht);
	for(i=0;i<ht->_size;i++){
		printf("[%d]%d  ",i,ht->_tables[i]._key);
		if(i>0&&i%10==0)
			printf("
");
	}
	printf("

");
}

HashTable* HashTableInit(){
    HashTable* ht;
    size_t i;
    ht=(HashTable*)malloc(sizeof(HashTable));
    ht->_N=0;ht->_size=GetNextPrimeSize(0);
    ht->_tables=(HashNode*)malloc(sizeof(HashNode)*(ht->_size));
    for(i=0;i<ht->_size;i++){
        ht->_tables[i]._key=0;
        ht->_tables[i]._status=EMPTY;
    }
    return ht;
}

size_t HashFunc(KeyType key,size_t size){
    return key%size;
}


//插入注意扩容问题
int HashTableInsert(HashTable** ht, KeyType key, ValueType value){
	HashNode* newTable,*curTable;
	int index,cur,i;
	assert(*ht);
	if((*ht)->_N*10/(*ht)->_size>7){
		//扩容后重新放入数据
		cur=(*ht)->_size;
		(*ht)->_size=GetNextPrimeSize((*ht)->_size);
		newTable=(HashNode*)malloc(sizeof(HashNode)*((*ht)->_size));
		memset(newTable,NULL,sizeof(HashNode)*(*ht)->_size);
		curTable=(*ht)->_tables;
		(*ht)->_tables=newTable;
		for(i=0;i<cur;i++){
			if(curTable[i]._status==EXITS){
				(*ht)->_tables[i]._status==DELET;
				HashTableInsert(&(*ht),curTable[i]._key,curTable[i]._value);
			}
		}
	}
	index=HashFunc(key,(*ht)->_size);

	while((*ht)->_tables[index]._status==EXITS){
		index++;
		if(index==(*ht)->_size)
			index=0;
	}
	(*ht)->_tables[index]._key=key;
	(*ht)->_tables[index]._value=value;
	(*ht)->_tables[index]._status=EXITS;
	(*ht)->_N++;
	return 0;
}

HashNode* HashTableFind(HashTable* ht, KeyType key){
	int index;
	assert(ht);
	if(ht->_size==1)
		return NULL;
	index=HashFunc(key,ht->_size);
	while(ht->_tables[index]._status!=EMPTY){
		if(ht->_tables[index]._key==key&&ht->_tables[index]._status==EXITS)
			return &(ht->_tables[index]);

		index++;
		if(index==ht->_size)
			index=0;
	}
	return NULL;
}

int HashTableRemove(HashTable** ht, KeyType key){
	HashNode* cur;
	assert(*ht);
	if(HashTableFind((*ht),key)){
		cur=HashTableFind(*ht,key);
		cur->_status=DELET;
		(*ht)->_N--;
		return 1;
	}
	return 0;
}

void HashTableDestory(HashTable** ht){
	free((*ht)->_tables);
	(*ht)->_N=0;
	(*ht)->_size=1;
}

size_t GetNextPrimeSize(size_t cur){
	int i;
	static const unsigned long _PrimeList [28] ={
		53ul,         97ul,        193ul,       389ul,       769ul,
		1543ul,       3079ul,      6151ul,      12289ul,     24593ul,
		49157ul,      98317ul,     196613ul,    393241ul,    786433ul,
		1572869ul,    3145739ul,   6291469ul,   12582917ul,  25165843ul,
		50331653ul,   100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};
	for(i=0;i<28;i++){
		if(cur<_PrimeList[i])
			return _PrimeList[i];
	}
	return 0;
}

void TestHashTable(){
	int i;
	HashTable* ht;
	ht=HashTableInit();

	HashTableInsert(&ht, 4 , 104);
	HashTableInsert(&ht, 5 , 105);
	HashTableInsert(&ht, 7 , 107);
	HashTableInsert(&ht, 6 , 106);
	HashTableInsert(&ht, 32 , 106);
	HashTableInsert(&ht, 58 , 106);

	printf("%d 
",HashTableFind(ht,4)->_value);
	printf("%d 
",HashTableFind(ht,5)->_value);
	printf("%d 
",HashTableFind(ht,6)->_value);
	printf("%d 
",HashTableFind(ht,7)->_value);

	HashTablePrint(ht);

	printf("4 : %p 
",HashTableFind(ht,4));
	printf("3 : %p 
",HashTableFind(ht,3));
	printf("5 : %p 
",HashTableFind(ht,5));
	HashTableRemove(&ht,5);
	printf("5 : %p 
",HashTableFind(ht,5));
//	HashTableDestory(&ht);
	printf("***********************************
");
	printf("4 : %p 
",HashTableFind(ht,4));
	printf("6 : %p 
",HashTableFind(ht,6));
	printf("5 : %p 
",HashTableFind(ht,5));
	printf("7 : %p 
",HashTableFind(ht,7));
	printf("===================================
");
	for(i=0;i<100;i++){
		HashTableInsert(&ht, i , 0);
	}
	HashTablePrint(ht);
}