散列的C語言實(shí)現(xiàn)
加入技術(shù)交流群
散列是能一種快速實(shí)現(xiàn)訪問的存儲(chǔ)方式。通常作為檢索部分的數(shù)據(jù)項(xiàng)是整形或者字符串，當(dāng)是字符串時(shí)，字符串的數(shù)量要遠(yuǎn)遠(yuǎn)大于數(shù)組的長(zhǎng)度，這時(shí)候就會(huì)有多個(gè)字符串映射到一個(gè)存儲(chǔ)位置的情況，這就是所謂的沖突問題，而且沖突時(shí)肯定存在的，這時(shí)候如何實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)又是需要解決的。
目前主要的解決方式有兩大類，第一種采用鏈表的形式，將所有沖突的數(shù)據(jù)項(xiàng)采用鏈表的形式鏈接起來，這樣搜索數(shù)據(jù)的復(fù)雜度就包含了鏈表的遍歷問題，特別是當(dāng)所有的項(xiàng)都鏈接到一個(gè)鏈表下時(shí)，這時(shí)候?qū)嶋H上就是遍歷鏈表，復(fù)雜度并不一定有很大的進(jìn)步，但是這種鏈表鏈接的方式有很高的填充率。第二種就是充分利用沒有實(shí)現(xiàn)的存儲(chǔ)空間，利用探測(cè)法探測(cè)空閑的空間，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)，目前有三種探測(cè)方式：線性探測(cè)法、平方探測(cè)法，以及雙散列法，三種方式中平方探測(cè)法運(yùn)用比較多，但是都存在各種各樣的優(yōu)缺點(diǎn)，這時(shí)候的散列搜索優(yōu)勢(shì)就沒有理想情況下那么明顯。有時(shí)候甚至比遍歷數(shù)組更加的慢。但是確實(shí)不失為一種處理方式。
映射函數(shù)可選擇的比較多，其實(shí)完全可以定義自己的映射函數(shù)，但是有時(shí)候?yàn)榱私档蜎_突的概率設(shè)置了一些比較好的映射函數(shù)，比如求和取余，或者乘以一定的系數(shù)再求和取余等。
本文采用平方探測(cè)法解決了沖突問題，具體的實(shí)現(xiàn)如下所示：
1、結(jié)構(gòu)體定義
#ifndef __HASHMAP_H_H_
#define __HASHMAP_H_H_
#include "list.h"
#define TABSIZE 101
/*狀態(tài)變量*/
typedef enum STATE{EMPTY = 0, ACTIVE = 1, DELETED = 2} State;
/*鍵值結(jié)構(gòu)體*/
typedef struct _pair
{
char *key;
char *value;
}Pair_t, *Pair_handle_t;
/*每一個(gè)實(shí)際的存儲(chǔ)對(duì)象*/
typedef struct _hashEntry
{
Pair_handle_t pair;
State state;
}HashEntry_t, *HashEntry_handle_t;
/*哈希表結(jié)構(gòu)體，便于創(chuàng)建*/
typedef struct _hashmap
{
HashEntry_t *map;
/*存儲(chǔ)實(shí)際的存儲(chǔ)量*/
int size;
/*容量*/
int capacity;
}Hashmap_t, *Hashmap_handle_t;
/*隱射函數(shù)類型定義*/
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
實(shí)現(xiàn)表的分配和創(chuàng)建，采用了動(dòng)態(tài)分配的方式實(shí)現(xiàn)，這樣可能在性能上比不上靜態(tài)數(shù)據(jù)，但是為了實(shí)現(xiàn)數(shù)組大小的調(diào)整，我選擇了動(dòng)態(tài)分配的實(shí)現(xiàn)方式。
/*分配一個(gè)新的對(duì)象，可以實(shí)現(xiàn)自動(dòng)分配*/
bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity)
{
HashEntry_handle_t temp = NULL;
Hashmap_t * map = NULL;
if(*hashmap == NULL)
{
/*分配一個(gè)散列對(duì)象*/
map = (Hashmap_handle_t)malloc(sizeof(Hashmap_t));
if(map == NULL)
return false;
/*指針指向當(dāng)前對(duì)象*/
*hashmap = map;
map = NULL;
/*分配一個(gè)數(shù)組空間，大小可以控制*/
temp = (HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp != NULL)
{
/*散列對(duì)象的指針指向數(shù)組*/
(*hashmap)->map = temp;
temp = NULL;
/*設(shè)置參數(shù)*/
(*hashmap)->capacity = capacity;
(*hashmap)->size = 0;
/*初始化分配的數(shù)組空間*/
Tabinital((*hashmap)->map,capacity);
return true;
}
}
return false;
}
/*初始化一個(gè)新的對(duì)象，這個(gè)對(duì)象已經(jīng)創(chuàng)建，只是沒有初始化而已*/
bool init_hashmap(Hashmap_handle_t hashmap, int capacity)
{
HashEntry_handle_t temp = NULL;
if(hashmap != NULL)
{
/*分配數(shù)組空間*/
temp = (HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp != NULL)
{
/*完成對(duì)象的填充操作*/
hashmap->map = temp;
temp = NULL;
hashmap->capacity = capacity;
hashmap->size = 0;
/*初始化數(shù)組對(duì)象*/
Tabinital(hashmap->map,capacity);
return true;
}
}
return false;
}
關(guān)于數(shù)組中對(duì)象的創(chuàng)建，和釋放操作，如下所示：
/*分配一個(gè)pair對(duì)象*/
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)] =