散列的C語言實現(xiàn)
加入技術(shù)交流群
散列是能一種快速實現(xiàn)訪問的存儲方式。通常作為檢索部分的數(shù)據(jù)項是整形或者字符串，當是字符串時，字符串的數(shù)量要遠遠大于數(shù)組的長度，這時候就會有多個字符串映射到一個存儲位置的情況，這就是所謂的沖突問題，而且沖突時肯定存在的，這時候如何實現(xiàn)數(shù)據(jù)的存儲又是需要解決的。
目前主要的解決方式有兩大類，第一種采用鏈表的形式，將所有沖突的數(shù)據(jù)項采用鏈表的形式鏈接起來，這樣搜索數(shù)據(jù)的復(fù)雜度就包含了鏈表的遍歷問題，特別是當所有的項都鏈接到一個鏈表下時，這時候?qū)嶋H上就是遍歷鏈表，復(fù)雜度并不一定有很大的進步，但是這種鏈表鏈接的方式有很高的填充率。第二種就是充分利用沒有實現(xiàn)的存儲空間，利用探測法探測空閑的空間，進而實現(xiàn)數(shù)據(jù)的存儲，目前有三種探測方式：線性探測法、平方探測法，以及雙散列法，三種方式中平方探測法運用比較多，但是都存在各種各樣的優(yōu)缺點，這時候的散列搜索優(yōu)勢就沒有理想情況下那么明顯。有時候甚至比遍歷數(shù)組更加的慢。但是確實不失為一種處理方式。
映射函數(shù)可選擇的比較多，其實完全可以定義自己的映射函數(shù)，但是有時候為了降低沖突的概率設(shè)置了一些比較好的映射函數(shù)，比如求和取余，或者乘以一定的系數(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;
/*每一個實際的存儲對象*/
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;
/*存儲實際的存儲量*/
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
實現(xiàn)表的分配和創(chuàng)建，采用了動態(tài)分配的方式實現(xiàn)，這樣可能在性能上比不上靜態(tài)數(shù)據(jù)，但是為了實現(xiàn)數(shù)組大小的調(diào)整，我選擇了動態(tài)分配的實現(xiàn)方式。
/*分配一個新的對象，可以實現(xiàn)自動分配*/
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;
/*分配一個數(shù)組空間，大小可以控制*/
temp = (HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp != NULL)
{
/*散列對象的指針指向數(shù)組*/
(*hashmap)->map = temp;
temp = NULL;
/*設(shè)置參數(shù)*/
(*hashmap)->capacity = capacity;
(*hashmap)->size = 0;
/*初始化分配的數(shù)組空間*/
Tabinital((*hashmap)->map,capacity);
return true;
}
}
return false;
}
/*初始化一個新的對象，這個對象已經(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)
{
/*完成對象的填充操作*/
hashmap->map = temp;
temp = NULL;
hashmap->capacity = capacity;
hashmap->size = 0;
/*初始化數(shù)組對象*/
Tabinital(hashmap->map,capacity);
return true;
}
}
return false;
}
關(guān)于數(shù)組中對象的創(chuàng)建，和釋放操作，如下所示：
/*分配一個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)] =