散列的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);