散列的C语言实现

/*散列对象的指针指向数组*/

(*hashmap)->map = temp;

temp = NULL;

/*设置参数*/

(*hashmap)->capacity = capacity;

(*hashmap)->size = 0;

/*初始化分配的数组空间*/

Tabinital((*hashmap)->map,capacity);

return true;

}

}

return false;

}

/*初始化一个新的对象，这个对象已经创建，只是没有初始化而已*/

bool init_hashmap(Hashmap_handle_t hashmap, int capacity)

{

HashEntry_handle_t temp = NULL;

if(hashmap != NULL)

{

/*分配数组空间*/

temp = (HashEntry_handle_t)malloc(

sizeof(HashEntry_t)*capacity);

if(temp != NULL)

{

/*完成对象的填充操作*/

hashmap->map = temp;

temp = NULL;

hashmap->capacity = capacity;

hashmap->size = 0;

/*初始化数组对象*/

Tabinital(hashmap->map,capacity);

return true;

}

}

return false;

}

关于数组中对象的创建，和释放操作，如下所示：

/*分配一个pair对象*/

static bool make_pair(Pair_handle_t *pair, const char *key, const char *value)

{

Pair_handle_t newpair =(Pair_handle_t)malloc(sizeof(Pair_t));

char *newstr = NULL;

if(newpair == NULL)

return false;

newstr = (char *)malloc(strlen(key) + 1);

if(newstr == NULL)

return false;

strcpy(newstr, key);

newstr[strlen(key)] = ;

newpair->key = newstr;

newstr = NULL;

newstr = (char *)malloc(strlen(value) + 1);

if(newstr == NULL)

return false;

strcpy(newstr, value);

newstr[strlen(value)] = ;

newpair->value = newstr;

newstr = NULL;

(*pair) = newpair;

return true;

}

/*释放一个对象pair*/

static void delete_pair(Pair_handle_t *pair)

{

Pair_handle_t temp = NULL;

if(*pair == NULL)

return ;

temp = *pair;

free(temp->key);

temp->key = NULL;

free(temp->value);

temp->value = NULL;

free(temp);

temp = NULL;

*pair = NULL;

}

数组元素的基本操作：

/*完成数组对象的初始化操作*/

static void Tabinital(HashEntry_t *tab, int size)

{

int i = 0;

for(; i < size; ++ i)

{

tab[i].pair = NULL;

tab[i].state = EMPTY;

}

}

static void delete_array(HashEntry_handle_t *array, int size)

{

int i = 0;

if(*array != NULL)

{

for(i = 0; i < size; ++ i)

{

if((*array)[i].state == ACTIVE)

{

delete_pair(&((*array)[i].pair));

(*array)[i].state = DELETED;

}

}

free(*array);

*array = NULL;

}

}

插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。

/*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/

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[s