散列的C言语完成

散列是能一种快速完结拜访的存储方法。一般作为检索部分的数据项是整形或许字符串，当是字符串时，字符串的数量要远远大于数组的长度，这时候就会有多个字符串映射到一个存储方位的状况，这便是所谓的抵触问题，并且抵触时必定存在的，这时候怎么完结数据的存储又是需求处理的。

现在首要的处理方法有两大类，第一种选用链表的方法，将一切抵触的数据项选用链表的方法链接起来，这样查找数据的复杂度就包含了链表的遍历问题，特别是当一切的项都链接到一个链表下时，这时候实践上便是遍历链表，复杂度并不必定有很大的前进，可是这种链表链接的方法有很高的填充率。第二种便是充分使用没有完结的存储空间，使用勘探法勘探闲暇的空间，从而完结数据的存储，现在有三种勘探方法：线性勘探法、平方勘探法，以及双散列法，三种方法中平方勘探法运用比较多，可是都存在各式各样的优缺点，这时候的散列查找优势就没有抱负状况下那么显着。有时候乃至比遍历数组愈加的慢。可是的确不失为一种处理方法。

映射函数可挑选的比较多，其实完全能够界说自己的映射函数，可是有时候为了下降抵触的概率设置了一些比较好的映射函数，比方求和取余，或许乘以必定的系数再求和取余等。

本文选用平方勘探法处理了抵触问题，详细的完结如下所示：

1、结构体界说

#ifndef __HASHMAP_H_H_

#define __HASHMAP_H_H_

#include “list.h”

#define TABSIZE 101

/*状态变量*/

typedef enum STATE{EMPTY = 0, ACTIVE = 1, DELETED = 2} State;

/*键值结构体*/

typedef struct _pair

{

char *key;

char *value;

}Pair_t, *Pair_handle_t;

/*每一个实践的存储目标*/

typedef struct _hashEntry

{

Pair_handle_t pair;

State state;

}HashEntry_t, *HashEntry_handle_t;

/*哈希表结构体，便于创立*/

typedef struct _hashmap

{

HashEntry_t *map;

/*存储实践的存储量*/

int size;

/*容量*/

int capacity;

}Hashmap_t, *Hashmap_handle_t;

/*影射函数类型界说*/

typedef int(*hashfunc)(const char *, int);

#ifdef __cplusplus

extern “C”

{

#endif

bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity);

bool init_hashmap(Hashmap_handle_t hashmap, int capacity);

bool insert_hashnode(Hashmap_handle_t hashmap, const char *key, const char *value);

Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char *key);

char *GetValue(Hashmap_handle_t hashmap, const char *key);

bool delete_hashnode(Hashmap_handle_t hashmap, const char *key);

int Length(Hashmap_handle_t hashmap);

int Capacity(Hashmap_handle_t hashmap);

void delete_hashmap(Hashmap_handle_t hashmap);

void free_hashmap(Hashmap_handle_t *hashmap);

char *key_pair(Pair_handle_t pair);

char *value_pair(Pair_handle_t pair);

Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap);

bool resize(Hashmap_handle_t hashmap);

#ifdef __cplusplus

}

#endif

#endif

完结表的分配和创立，选用了动态分配的方法完结，这样可能在性能上比不上静态数据，可是为了完结数组巨细的调整，我挑选了动态分配的完结方法。

/*分配一个新的目标，能够完结主动分配*/

bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity)

{

HashEntry_handle_t temp = NULL;

Hashmap_t * map = NULL;

if(*hashmap == NULL)

{

/*分配一个散列目标*/

map = (Hashmap_handle_t)malloc(sizeof(Hashmap_t));

if(map == NULL)

return false;

/*指针指向当时目标*/

*hashmap = map;

map = 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;

}

/*初始化一个新的目标，这个目标现已创立，仅仅没有初始化罢了*/

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;

}

}