散列的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;
}
评论