評論(0

散列存儲方法

標籤: 暫無標籤

1百科名片

散列存儲,又稱hash存儲,是一種力圖將數據元素的存儲位置與關鍵碼之間建立確定對應關係的查找技術。散列法存儲的基本思想是:由節點的關鍵碼值決定節點的存儲地址。散列技術除了可以用於查找外,還可以用於存儲。
hash

  hash

散列技術是一種力圖將數據元素的存儲位置與關鍵碼之間建立確定對應關係的查找技術。散列法存儲的基本思想是:由節點的關鍵碼值決定節點的存儲地址。散列技術除了可以用於查找外,還可以用於存儲。

2散列存儲的特點

散列是數組存儲方式的一種發展,相比數組,散列的數據訪問速度要高於數組,因為可以依據存儲數據的部分內容找到數據在數組中的存儲位置,進而能夠快速實現數據的訪問,理想的散列訪問速度是非常迅速的,而不像在數組中的遍歷過程,採用存儲數組中內容的部分元素作為映射函數的輸入,映射函數的輸出就是存儲數據的位置,這樣的訪問速度就省去了遍曆數組的實現,因此時間複雜度可以認為為O(1),而數組遍歷的時間複雜度為O(n)。
散列是能一種快速實現訪問的存儲方式。通常作為檢索部分的數據項是整形或者字元串,當是字元串時,字元串的數量要遠遠大於數組的長度,這時候就會有多個字元串映射到一個存儲位置的情況,這就是所謂的衝突問題,而且衝突時肯定存在的,這時候如何實現數據的存儲又是需要解決的。

3散列存儲的分類

探測法探測空閑的空間
第二種就是充分利用沒有實現的存儲空間,利用探測法探測空閑的空間,進而實現數據的存儲,目前有三種探測方式:線性探測法、平方探測法,以及雙散列法,三種方式中平方探測法運用比較多,但是都存在各種各樣的優缺點,這時候的散列搜索優勢就沒有理想情況下那麼明顯。有時候甚至比遍曆數組更加的慢。但是確實不失為一種處理方式。

4散列存儲中的衝突解決

映射函數可選擇的比較多,其實完全可以定義自己的映射函數,但是有時候為了降低衝突的概率設置了一些比較好的映射函數,比如求和取余,或者乘以一定的係數再求和取余等。
本文採用平方探測法解決了衝突問題,具體的實現如下所示:
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
#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;
}
關於數組中對象的創建,和釋放操作,如下所示:
"
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;
}
"
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;
}
數據在計算機中存儲的物理結構有四種:順序、鏈表、散列與索引。散列是由單詞Hash翻譯過來的,有時也直接音譯為「哈希」,就是把任意長度的輸入(又叫做預映射, pre-image),通過散列演算法,變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小於輸入的空間,不同的輸入可能會散列成相同的輸出,而不可能從散列值來唯一的確定輸入值。
上一篇[數據運算]    下一篇 [鏈式存儲結構]

相關評論

同義詞:暫無同義詞