欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

利用C語言實現HashTable

 更新時間：2013年09月14日 09:09:39   作者：  
根據KEY從hashtable中獲取接點，步驟是先根據KEY計算hash值，然后從hashtable中找到指定的接點或者接點鏈表

HashTable是在實際應用中很重要的一個結構，下面討論一個簡單的實現，雖然簡單，但是該有的部分都還是有的。

一，訪問接口
創(chuàng)建一個hashtable.
hashtable hashtable_new（int size） /其中size表示包含的接點個數。

存入key-value至hashtable中。
void hashtable_put（hashtable h,const char* key,void *val）；

根據key從hashtable中取出value值。
void * hashtable_get（hashtable h,const char *key）；

釋放hashtable。
void hashtable_free（hashtable h）；

釋放單個hash 接點
void hashtable_delete_node（hashtable h, const char *key）；

二，數據結構
hash接點的結構：

復制代碼 代碼如下:

typedef struct hashnode_struct{
struct hashnode_struct *next;
const char *key;
void *val;
}*hashnode,_hashnode;

這個結構還是很容易理解的，除了必須的key-value之外，包含一個用于沖突的鏈表結構。
hashtable的數據結構：
復制代碼 代碼如下:

typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
}*hashtable,_hashtable;

對這個結構說明如下：
pool_t：內存池結構管理hashtable使用的內存。結構參考"C語言內存池使用模型"
size：當前hash的接點空間大小。
count：用于表示當前接點空間中可用的hash接點個數
z：用于在接點空間中存儲接點。

三，創(chuàng)建hashtable
代碼如下：

復制代碼 代碼如下:

hashtable hashtable_new（int size）
{
hashtable ht;
pool_t p;
p = _pool_new_heap（sizeof（_hashnode）*size + sizeof（_hashtable））；
ht= pool_malloc（p, sizeof（_hashtable））；
ht->size = size;
ht->p = p;
ht->z = pool_malloc（p, sizeof（_hashnode）*prime）；
return ht;
}

這個函數比較簡單，先定義并初始化一個內存池，大小根據size而定，所以在實際使用時，我們的size應該要分配的相對大點，比較好。

四，存入key-value值
在這個操作之前，先要定義一個根據KEY值計算hashcode的函數。

復制代碼 代碼如下:

static int hashcode（const char *s, int len）
{
const unsigned char *name = （const unsigned char *）s;
unsigned long h = 0, g;
int i;
for（i=0;i
{
h = （h 《 4） + （unsigned long）（name[i]）； //hash左移4位，當前字符ASCII存入hash
if （（g = （h & 0xF0000000UL））！=0）
h ^= （g 》 24）；
h &= ~g; //清空28-31位。
}
return （int）h;
}

這個函數采用精典的ELF hash函數。
代碼如下：
復制代碼 代碼如下:

void hashtable_put（hashtable h, const char *key, void *val）
{
if（h == NULL || key == NULL）
return;
int len = strlen（key）；
int index = hashcode（key,len）；
hashtable node;
h->dirty++;
if（（node = hashtable_node_get（h, key,len, index）） != NULL） //如果已經存在，就替換成現在的值，因為現在的比較新。
{
n->key = key;
n->val = val;
return;
}
node = hashnode_node_new（h, index）； // 新建一個HASH NODE接點。
node->key = key;
node->val = val;
}
hashtable_node_get用于查找該KEY是否在HASH中已經存在，實現很簡單，如下：
static hashnode hashtable_node_get（hashtable h, const char *key, int len, int index）
{
hashnode node;
int i = index % h->size;
for（node = &h->z[i]; node != NULL; node = node->next） // 在index值 [HASH值] 所對應的HASH桶上遍歷尋找
if（node->key != NULL && （strlen（node->key）==len） && （strncmp（key, node->key, len） == 0））
return node;
return NULL;
}

新建一個HASH NODE接點如下：
復制代碼 代碼如下:

static hashnode hashnode_node_new（hashtable h, int index）
{
hashnode node;
int i = index % h->size;
h->count++;
for（node = &h->z[i]; node != NULL; node = node->next）
if（node->key == NULL） //這里的處理是：如果在HASH桶中存在某個值，KEY是空的，表明這個值已經沒有用了，就用它來替換為現在準備寫入的新接點。
return node;
node = pool_malloc（h->p, sizeof（_hashnode））； // 新建一個接點
node->next = h->z[i].next; // 加入到桶中，就是加到鏈表的第一個接點。
h->z[i].next = node;
return node;
}

五，從HASHTABLE中獲取接點
根據KEY從hashtable中獲取接點，步驟是先根據KEY計算hash值，然后從hashtable中找到指定的接點或者接點鏈表。如下：
復制代碼 代碼如下:

void *hashtable_get（hashtable h, const char *key）
{
if（h == NULL || key == NULL）
return NULL;
hashnode node;
int len = strlen（key）；
if（h == NULL || key == NULL || len <= 0 || （node = hashtable_node_get（h, key, len, hashcode（key,len））） == NULL）
{
return NULL;
}
return node->val;
}

這個函數就很容易理解了。

六，釋放HASHTABLE
hashtable的釋放就比較簡單了，因為我們所有的內存申請都在內存池上完成的，就只需要釋放內存池，如下：

復制代碼 代碼如下:

void hashtable_free（hashtable h）
{
if（h != NULL）
pool_free（h->p）；
}

七，釋放單個hash接點
代碼如下：
復制代碼 代碼如下:

void hashtable_delete_node（hashtable h, const char *key）
{
if（h == NULL || key == NULL）
return;
hashnode node;
int len = strlen（key）；
if（h == NULL || key == NULL || （node = hashtable_node_get（h, key, len, hashcode（key,len））） == NULL） //沒有這個接點
return;
node->key = NULL;
node->val = NULL;
h->count--;
}

這個就實現了一個簡單的HASHTABLE結構，當然后還是有不足的，比如遍歷HASHTABLE，如果用數組的方式來遍歷，效率肯定很低，下面討論一種實現方案，用于遍歷hashtable.

八，hashtable的遍歷討論
直接用數組，就是hashtable中的struct hashnode_struct數組是可以遍歷，但如果只包含一個接點，也要遍歷所有的數組，如下遍歷：

復制代碼 代碼如下:

void hashtable_traverse（hashtable h）
{
int i;
hashnode node;
if（h == NULL）
return;
for（i = 0; i < h->prime; i++）
for（node = &h->z[i]; node != NULL; node = node->next）
if（node->key != NULL && node->val != NULL）
XXXXXXXXXXXXXXXXX // 這里是一些操作。
}

這樣效率很低，其實在接點中包含了next域，可以用這個來實現遍歷。
需要對前面hashtable數據結構做簡單的改動，增加兩個域：
復制代碼 代碼如下:

typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
int bucket;
hashnode node;
}*hashtable,_hashtable;

就是增加了bucket和node兩個域，加這兩個域的思路是這樣的：
node表示當前遍歷的游標，在遍歷過程中，不斷的移動這個接點所指向的接點。
bucket是和node相關聯的，用于記錄當前的node在哪個桶上。
首先建立連接，就是將所有的接點都連接起來，按照慣例，也采用XXX_iter_first函數，先初始化，如下：
復制代碼 代碼如下:

int hashtable_iter_first（hashtable h） {
if（h == NULL）
return 0;
h->bucket = -1;
h->node = NULL;
return hashtable_iter_next（h）；
}
hashtable_iter_next用于獲取下一個接點，如果這時游標已經確定，那下一個接點就會被很快的被確定，定義如下：
int xhash_iter_next（xht h） {
if（h == NULL） return 0;
while（h->node != NULL） {
h->node = h->node->next; // 移向下一個接點，如果接點合法，返回成功
if（h->node != NULL && h->node->key != NULL && h->node->val != NULL）
return 1;
}
for（h->bucket++; h->bucket < h->prime; h->bucket++） {
h->node = &h->z[h->bucket];
while（h->node != NULL） {
if（h->node->key != NULL && h->node->val != NULL）
return 1;
h->node = h->node->next;
}
}
h->bucket = -1; // 不存在下一個接點。
h->node = NULL;
return 0;
}

有了上面兩個方法之后，遍歷操作如下：
復制代碼 代碼如下:

hashtable ht
if（hashtable_iter_first（ht）） //取第一個接點。
do{
// 此時可以處理ht->node，表示當前的接點。
}while（hashtable_iter_next（ht））； //取下一個接點

這樣處理的話， 是不是高效多了。當然在第一遍的時候，還是需要遍歷整個數組和數組下的桶中接點。不過這樣操作之后，在刪除一個結點的時候，就需要做一些操作。刪除一個接點時，需要考慮當前的h->node是不是當前被刪除的接點，如果是，就把h->node稱至下一個接點。就是刪除之后，要作如下處理，假如刪除了。

假如被刪除的接點為node,需要如下處理：
if（h->node == n）
hashtable_iter_next（h）；
將h->node移動到下一個接點。

相關文章

  • C++中 map的基本操作

    C++中 map的基本操作

    map是一類關聯式容器。接下來通過本文給大家分享c++中的map基本操作，需要的朋友參考下
    2017-05-05
  • VC中SDK與MFC的區(qū)別淺析

    VC中SDK與MFC的區(qū)別淺析

    這篇文章主要介紹了VC中SDK與MFC的區(qū)別淺析,需要的朋友可以參考下
    2014-07-07
  • C語言用遞歸函數實現漢諾塔

    C語言用遞歸函數實現漢諾塔

    大家好，本篇文章主要講的是C語言用遞歸函數實現漢諾塔，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下
    2022-01-01
  • 怎么通過C語言自動生成MAC地址

    怎么通過C語言自動生成MAC地址

    以下是對使用C語言自動生成MAC地址的實現代碼進行了詳細的分析介紹，需要的朋友可以過來參考下
    2013-09-09
  • 一起來學習C++的函數指針和函數對象

    一起來學習C++的函數指針和函數對象

    這篇文章主要為大家詳細介紹了C++函數指針和函數對象，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-03-03
  • 利用Matlab實現陰影柱狀圖的繪制

    利用Matlab實現陰影柱狀圖的繪制

    陰影柱狀圖繪制的代碼MATHWORKS上也有，不過是生成圖片后，識別圖像上不同顏色塊并直接修改像素生成陰影線。這樣的生成方式不可逆且自由度較低，所以本文為大家?guī)淼氖且粋€直接畫線條填充的硬畫版本，希望有所幫助
    2022-09-09
  • C++ 漢諾塔問題知識點總結

    C++ 漢諾塔問題知識點總結

    在本篇文章里小編給大家整理的是關于C++ 漢諾塔問題知識點內容，有需要的朋友們可以參考下。
    2020-02-02
  • C語言實現掃雷小游戲完整算法詳解(附完整代碼)

    C語言實現掃雷小游戲完整算法詳解(附完整代碼)

    掃雷游戲想必我們都有玩過，那么今天就用C語言來簡單實現“掃雷”小游戲,這篇文章主要給大家介紹了關于C語言實現掃雷小游戲完整算法的相關資料,文中給出了完整的實例代碼,需要的朋友可以參考下
    2022-06-06
  • C++ Qt開發(fā)之使用QHostInfo查詢主機地址

    C++ Qt開發(fā)之使用QHostInfo查詢主機地址

    Qt 是一個跨平臺C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺窗體應用程序,本文將重點介紹如何運用QHostInfo組件實現對主機地址查詢功能,希望對大家有所幫助
    2024-03-03
  • C++構造函數詳解

    C++構造函數詳解

    這篇文章主要介紹了C++構造函數詳解，上一篇文章我們介紹了定義了類，在使用之前，往往還需要對類進行初始化。這篇介紹的就是對類進行初始化的方法,需要的朋友可以參考一下
    2022-01-01

最新評論