散列的C语言实现

散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)。

散列是能一种快速实现访问的存储方式。通常作为检索部分的数据项是整形或者字符串，当是字符串时，字符串的数量要远远大于数组的长度，这时候就会有多个字符串映射到一个存储位置的情况，这就是所谓的冲突问题，而且冲突时肯定存在的，这时候如何实现数据的存储又是需要解决的。

目前主要的解决方式有两大类，第一种采用链表的形式，将所有冲突的数据项采用链表的形式链接起来，这样搜索数据的复杂度就包含了链表的遍历问题，特别是当所有的项都链接到一个链表下时，这时候实际上就是遍历链表，复杂度并不一定有很大的进步，但是这种链表链接的方式有很高的填充率。第二种就是充分利用没有实现的存储空间，利用探测法探测空闲的空间，进而实现数据的存储，目前有三种探测方式：线性探测法、平方探测法，以及双散列法，三种方式中平方探测法运用比较多，但是都存在各种各样的优缺点，这时候的散列搜索优势就没有理想情况下那么明显。有时候甚至比遍历数组更加的慢。但是确实不失为一种处理方式。

映射函数可选择的比较多，其实完全可以定义自己的映射函数，但是有时候为了降低冲突的概率设置了一些比较好的映射函数，比如求和取余，或者乘以一定的系数再求和取余等。

本文采用平方探测法解决了冲突问题，具体的实现如下所示：

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)

{