散列的C语言实现
插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。
/*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/
static bool insert_data(Hashmap_handle_t hashmap,
const char *key, const char *value, hashfunc func)
{
int hashval = func(key,hashmap->capacity);
int index = 0;
char * newstr = NULL;
Pair_handle_t newpair = NULL;
while(hashmap->map[hashval].state != EMPTY)
{
if((hashmap->map[hashval].state == ACTIVE)
&& (strcmp(hashmap->map[hashval].pair->key,key) == 0))
break;
index ++;
hashval += index * index;
hashval %= hashmap->capacity;
if(index == 200)
break;
}
if(hashmap->map[hashval].state == EMPTY)
{
if(make_pair(&newpair,key,value))
{
hashmap->map[hashval].state = ACTIVE;
hashmap->map[hashval].pair = newpair;
newpair = NULL;
hashmap->size ++;
return true;
}
}
else if((hashmap->map[hashval].state == ACTIVE)
&& (strcmp(hashmap->map[hashval].pair->key, key) == 0))
{
newstr = (char *)malloc(strlen(value) + 1);
if(newstr != NULL)
{
strcpy(newstr,value);
newstr[strlen(value)] = ;
free(hashmap->map[hashval].pair->value);
hashmap->map[hashval].pair->value = newstr;
newstr = NULL;
return true;
}
}
return false;
}
static bool insert2map(HashEntry_handle_t map,
const char *key, const char *value,
hashfunc func, int size)
{
int hashval = func(key,size);
int index = 0;
char *newstr = NULL;
Pair_handle_t newpair = NULL;
if(map != NULL)
{
while(map[hashval].state != EMPTY)
{
if((map[hashval].state == ACTIVE)
&& (strcmp(map[hashval].pair->key, key) == 0))
break;
index ++;
hashval += index * index;
hashval %= size;
/*防止死循环*/
if(index == 200)
break;
}
if(map[hashval].state == EMPTY)
{
if(!make_pair(&newpair,key,value))
return false;
map[hashval].pair = newpair;
map[hashval].state = ACTIVE;
newpair = NULL;
return true;
}
else if((map[hashval].state == ACTIVE) &&
(strcmp(map[hashval].pair->key, key) == 0))
{
newstr = (char *)malloc(strlen(value) +1);
if(newstr != NULL)
{
free(map[hashval].pair->value);
map[hashval].pair->value = NULL;
strcpy(newstr, value);
newstr[strlen(value)] = ;
map[hashval].pair->value = newstr;
return true;
}
}
}
return false;
}
调整大小和插入的实际操作。
bool resize(Hashmap_handle_t hashmap)
{
int i = 0;
HashEntry_handle_t newarray = NULL;
int size = next_prime(2*hashmap->capacity);
if(hashmap != NULL)
{
newarray = (HashEntry_handle_t)malloc(sizeof(HashEntry_t)
*size);
if(newarray == NULL)
return false;
/*这一步至关重要*/
Tabinital(newarray, size);
for(; i < hashmap->capacity ; ++ i)
{
if(hashmap->map[i].state == ACTIVE)
{
if(!insert2map(newarray,
hashmap->map[i].pair->key,
hashmap->map[i].pair->value,
HashFunc, size))
return false;
}
}
delete_array(&hashmap->map,hashmap->capacity);
hashmap->map = newarray;
hashmap->capacity = size;
return true;
}
return false;
}
bool insert_hashnode(Hashmap_handle_t hashmap,
const char *key, const char *value)
{
if(hashmap->size < hashmap->capacity)
{
if(insert_data(hashmap,key,value,HashFunc))
{
//hashmap->size ++;
}
return true;
}
else /*增加容量*/
{
if(!resize(hashmap))
return false;
if(insert_data(hashmap,key,value,HashFunc))
{
//hashmap->size ++;
}
return true;
}
return false;
}
搜索操作
static Pair_handle_t search_data(Hashmap_handle_t hashmap, const char *key, hashfunc func)
{
int hashval = func(key, hashmap->capacity);
int index = 0;
while(hashmap->map[hashval].state != EMPTY)
{
if((hashmap->map[hashval].state == ACTIVE)
&& (strcmp(hashmap->map[hashval].pair->key,key) == 0))
break;
index ++;
hashval += index * index;
hashval %= hashmap->capacity;
if(index == 200)
break;
}
if((hashmap->map[hashval].state == ACTIVE)
&& (strcmp(hashmap->map[hashval].pair->key, key) == 0))
{
return hashmap->map[hashval].pair;
}
return NULL;
}
Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char * key)
{
return search_data(hashmap,key,HashFunc);
}
删除操作
static bool delete_node(Hashmap_handle_t hashmap,const char *key,hashfunc func)
{
int hashval = func(key, hashmap->capacity);
int index = 0;
/**********************************************
*退出循环的条件是找到空闲的单元，或者关键字匹配
*********************************************/
while(hashmap->map[hashval].state != EMPTY)
{
if((hashmap->map[hashval].state == ACTIVE)
&& strcmp(hashmap->map[hashval].pair->key,key) == 0)
break;
index ++;
hashval += index * index;
hashval %= hashmap->capacity;
if(index == 200)
break;
}
/*判断删除条件*/
if((hashmap->map[hashval].state == ACTIVE) &&
(strcmp(hashmap->map[hashval].pair->key, key) == 0))
{
hashmap->map[hashval].state = DELETED;
delete_pair(&(hashmap->map[hashval].pair));
hashmap->map[hashval].pair = NULL;
return true;
}
return false;
}
bool delete_hashnode(Hashmap_handle_t hashmap, const char *key)
{
if(delete_node(hashmap, key, HashFunc))
{
hashmap->size --;
return true;
}
return false;
}
参数获取函数；
int Length(Hashmap_t *map)
{
return map->size;
}
int Capacity(Hashmap_t *map)
{
return map->capacity;
}
void delete_hashmap(Hashmap_handle_t hashmap)
{
int i = 0;
int size = hashmap->capacity;
if(hashmap != NULL)
{
for(; i < size; ++ i)
{
if(hashmap->map[i].state == ACTIVE)
{
delete_pair(&(hashmap->map[i].pair));
hashmap->map[i].state = DELETED;
hashmap->map[i].pair = NULL;