散列的C語(yǔ)言實(shí)現

散列是能一種快速實(shí)現訪(fǎng)問(wèn)的存儲方式。通常作為檢索部分的數據項是整形或者字符串，當是字符串時(shí)，字符串的數量要遠遠大于數組的長(cháng)度，這時(shí)候就會(huì )有多個(gè)字符串映射到一個(gè)存儲位置的情況，這就是所謂的沖突問(wèn)題，而且沖突時(shí)肯定存在的，這時(shí)候如何實(shí)現數據的存儲又是需要解決的。

目前主要的解決方式有兩大類(lèi)，第一種采用鏈表的形式，將所有沖突的數據項采用鏈表的形式鏈接起來(lái)，這樣搜索數據的復雜度就包含了鏈表的遍歷問(wèn)題，特別是當所有的項都鏈接到一個(gè)鏈表下時(shí)，這時(shí)候實(shí)際上就是遍歷鏈表，復雜度并不一定有很大的進(jìn)步，但是這種鏈表鏈接的方式有很高的填充率。第二種就是充分利用沒(méi)有實(shí)現的存儲空間，利用探測法探測空閑的空間，進(jìn)而實(shí)現數據的存儲，目前有三種探測方式：線(xiàn)性探測法、平方探測法，以及雙散列法，三種方式中平方探測法運用比較多，但是都存在各種各樣的優(yōu)缺點(diǎn)，這時(shí)候的散列搜索優(yōu)勢就沒(méi)有理想情況下那么明顯。有時(shí)候甚至比遍歷數組更加的慢。但是確實(shí)不失為一種處理方式。

映射函數可選擇的比較多，其實(shí)完全可以定義自己的映射函數，但是有時(shí)候為了降低沖突的概率設置了一些比較好的映射函數，比如求和取余，或者乘以一定的系數再求和取余等。

本文采用平方探測法解決了沖突問(wèn)題，具體的實(shí)現如下所示：

1、結構體定義

#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;

/*鍵值結構體*/

typedef struct _pair

{

char *key;

char *value;

}Pair_t, *Pair_handle_t;

/*每一個(gè)實(shí)際的存儲對象*/

typedef struct _hashEntry

{

Pair_handle_t pair;

State state;

}HashEntry_t, *HashEntry_handle_t;

/*哈希表結構體，便于創(chuàng )建*/

typedef struct _hashmap

{

HashEntry_t *map;

/*存儲實(shí)際的存儲量*/

int size;

/*容量*/

int capacity;

}Hashmap_t, *Hashmap_handle_t;

/*隱射函數類(lèi)型定義*/

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í)現表的分配和創(chuàng )建，采用了動(dòng)態(tài)分配的方式實(shí)現，這樣可能在性能上比不上靜態(tài)數據，但是為了實(shí)現數組大小的調整，我選擇了動(dòng)態(tài)分配的實(shí)現方式。

/*分配一個(gè)新的對象，可以實(shí)現自動(dòng)分配*/

bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity)

{

HashEntry_handle_t temp = NULL;

Hashmap_t * map = NULL;

if(*hashmap == NULL)

{

/*分配一個(gè)散列對象*/

map = (Hashmap_handle_t)malloc(sizeof(Hashmap_t));

if(map == NULL)

return false;

/*指針指向當前對象*/

*hashmap = map;

map = NULL;

/*分配一個(gè)數組空間，大小可以控制*/

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;

}

/*初始化一個(gè)新的對象，這個(gè)對象已經(jīng)創(chuàng )建，只是沒(méi)有初始化而已*/

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;

}

關(guān)于數組中對象的創(chuàng )建，和釋放操作，如下所示：

/*分配一個(gè)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)] = 国产精品自在自线亚洲|国产精品无圣光一区二区|国产日产欧洲无码视频|久久久一本精品99久久K精品66|欧美人与动牲交片免费播放