基本介紹
- 中文名：散列存儲方法
- 又稱：hash存儲
- 特點：散列的數據訪問速度要高於數組
- 分類：採用鍊表的形式
基本思想,特點,分類,衝突解決,
基本思想
特點
散列是數組存儲方式的一種發展，相比數組，散列的數據訪問速度要高於數組，因為可以依據存儲數據的部分內容找到數據在數組中的存儲位置，進而能夠快速實現數據的訪問，理想的散列訪問速度是非常迅速的，而不像在數組中的遍歷過程，採用存儲數組中內容的部分元素作為映射函式的輸入，映射函式的輸出就是存儲數據的位置，這樣的訪問速度就省去了遍歷數組的實現，因此時間複雜度可以認為為O(1)，而數組遍歷的時間複雜度為O(n)。
散列是能一種快速實現訪問的存儲方式。通常作為檢索部分的數據項是整形或者字元串，當是字元串時，字元串的數量要遠遠大於數組的長度，這時候就會有多個字元串映射到一個存儲位置的情況，這就是所謂的衝突問題，而且衝突時肯定存在的，這時候如何實現數據的存儲又是需要解決的。
分類
主要的解決方式有兩大類，第一種採用鍊表的形式，將所有衝突的數據項採用鍊表的形式連結起來，這樣搜尋數據的複雜度就包含了鍊表的遍歷問題，特別是當所有的項都連結到一個鍊表下時，這時候實際上就是遍歷鍊表，複雜度並不一定有很大的進步，但是這種鍊表連結的方式有很高的填充率。
探測法探測空閒的空間
第二種就是充分利用沒有實現的存儲空間，利用探測法探測空閒的空間，進而實現數據的存儲，有三種探測方式：線性探測法、平方探測法，以及雙散列法，三種方式中平方探測法運用比較多，但是都存在各種各樣的優缺點，這時候的散列搜尋優勢就沒有理想情況下那么明顯。有時候甚至比遍歷數組更加的慢。但是確實不失為一種處理方式。
衝突解決
映射函式可選擇的比較多，其實完全可以定義自己的映射函式，但是有時候為了降低衝突的機率設定了一些比較好的映射函式，比如求和取余，或者乘以一定的係數再求和取余等。
本文採用平方探測法解決了衝突問題，具體的實現如下所示：
1、結構體定義
#ifndef__HASHMAP_H_H_
#define__HASHMAP_H_H_
#include"list.h"
#defineTABSIZE101
/*狀態變數*/
typedefenumSTATE{EMPTY=0,ACTIVE=1,DELETED=2}State;
/*鍵值結構體*/
typedefstruct_pair
{
char*key;
char*value;
}Pair_t,*Pair_handle_t;
/*每一個實際的存儲對象*/
typedefstruct_hashEntry
{
Pair_handle_tpair;
Statestate;
}HashEntry_t,*HashEntry_handle_t;
/*哈希表結構體，便於創建*/
typedefstruct_hashmap
{
HashEntry_t*map;
/*存儲實際的存儲量*/
intsize;
/*容量*/
intcapacity;
}Hashmap_t,*Hashmap_handle_t;
/*隱射函式類型定義*/
typedefint(*hashfunc)(constchar*,int);
#ifdef__cplusplus
extern"C"
{
#endif
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity);
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity);
boolinsert_hashnode(Hashmap_handle_thashmap,constchar*key,constchar*value);
Pair_handle_tsearch_hashnode(Hashmap_handle_thashmap,constchar*key);
char*GetValue(Hashmap_handle_thashmap,constchar*key);
booldelete_hashnode(Hashmap_handle_thashmap,constchar*key);
intLength(Hashmap_handle_thashmap);
intCapacity(Hashmap_handle_thashmap);
voiddelete_hashmap(Hashmap_handle_thashmap);
voidfree_hashmap(Hashmap_handle_t*hashmap);
char*key_pair(Pair_handle_tpair);
char*value_pair(Pair_handle_tpair);
Hashmap_handle_tcopy_hashmap(Hashmap_handle_thashmap);
boolresize(Hashmap_handle_thashmap);
#ifdef__cplusplus
}
#endif
實現表的分配和創建，採用了動態分配的方式實現，這樣可能在性能上比不上靜態數據，但是為了實現數組大小的調整，我選擇了動態分配的實現方式。
/*分配一個新的對象，可以實現自動分配*/
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity)
{
HashEntry_handle_ttemp=NULL;
Hashmap_t*map=NULL;
if(*hashmap==NULL)
{
/*分配一個散列對象*/
map=(Hashmap_handle_t)malloc(sizeof(Hashmap_t));
if(map==NULL)
returnfalse;
/*指針指向當前對象*/
*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);
returntrue;
}
}
returnfalse;
}
/*初始化一個新的對象，這個對象已經創建，只是沒有初始化而已*/
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity)
{
HashEntry_handle_ttemp=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);
returntrue;
}
}
returnfalse;
}
關於數組中對象的創建，和釋放操作，如下所示：
/*分配一個pair對象*/
staticboolmake_pair(Pair_handle_t*pair,constchar*key,constchar*value)
{
Pair_handle_tnewpair=(Pair_handle_t)malloc(sizeof(Pair_t));
char*newstr=NULL;
if(newpair==NULL)
returnfalse;
newstr=(char*)malloc(strlen(key)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,key);
newstr[strlen(key)]='\0';
newpair->key=newstr;
newstr=NULL;
newstr=(char*)malloc(strlen(value)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,value);
newstr[strlen(value)]='\0';
newpair->value=newstr;
newstr=NULL;
(*pair)=newpair;
returntrue;
}
/*釋放一個對象pair*/
staticvoiddelete_pair(Pair_handle_t*pair)
{
Pair_handle_ttemp=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;
}
數組元素的基本操作：
/*完成數組對象的初始化操作*/
staticvoidTabinital(HashEntry_t*tab,intsize)
{
inti=0;
for(;i
{
tab[i].pair=NULL;
tab[i].state=EMPTY;
}
}
staticvoiddelete_array(HashEntry_handle_t*array,intsize)
{
inti=0;
if(*array!=NULL)
{
for(i=0;i
{
if((*array)[i].state==ACTIVE)
{
delete_pair(&((*array)[i].pair));
(*array)[i].state=DELETED;
}
}
free(*array);
*array=NULL;
}
}
插入元素的操作、有兩個函式的創建，其中一個為了便於後期大小的調整操作。
/*插入數據到散列中，採用了二次探測的實現方式，並設定了退出條件*/
staticboolinsert_data(Hashmap_handle_thashmap,
constchar*key,constchar*value,hashfuncfunc)
{
inthashval=func(key,hashmap->capacity);
intindex=0;
char*newstr=NULL;
Pair_handle_tnewpair=NULL;
while(hashmap->map[hashval].state!=EMPTY)
{
if((hashmap->map[hashval].state==ACTIVE)
&&(strcmp(hashmap->map[hashval].pair->key,key)==0))
break;
index++;
hashval+=index*index;
hashval%=hashmap->capacity;
if(index==200)
break;
}
if(hashmap->map[hashval].state==EMPTY)
{
if(make_pair(&newpair,key,value))
{
hashmap->map[hashval].state=ACTIVE;
hashmap->map[hashval].pair=newpair;
newpair=NULL;
hashmap->size++;
returntrue;
}
