哈希桶 entry_哈希表代码实现
哈希表的主要用處：快速的數據存儲和查找。例如，在我們日常上網過程中搜索某條信息的時候，信息的存儲方式決定了查找該信息的速度，哈希表結合了數組的便捷訪問和鏈表的便捷查找和刪除的特點。
實現方式：通過哈希函數獲取哈希表的地址，遇到沖突的情況下采用拉鏈法解決沖突。
時間復雜度O(1)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*定義哈希表數組的長度*/
#define BUCKETCOUNT 16
/*哈希表結點數據結構定義*/
struct hashEntry
{
char *key;
char *value;
struct hashEntry *next;
};
typedef struct hashEntry entry;
struct hashTable
{
entry bucket[BUCKETCOUNT];/*先默認定義16個桶*/
};
typedef struct hashTable table;
/*初始化哈希表*/
void initHashTable(table *t)
{
int i;
if(!t)
return;
for(i = 0; i < BUCKETCOUNT; ++i)
{
t->bucket[i].key = NULL;
t->bucket[i].next = NULL;
t->bucket[i].value = NULL;
}
}
/*散列函數*/
int keyToIndex(const char *key)
{
int index, len, i;
if(key == NULL)
return -1;
len = strlen(key);
index = (int)key[0];
for(i = 1; i < len; ++i)
{
index *= 1103515245 + (int)key[i];
}
index >>= 27;
index &= (BUCKETCOUNT - 1);
return index;
}
/*在堆上分配足以保存str的內存，并拷貝str的內容到新分配的位置*/
char *strDup(const char *str)
{
int len;
char *ret;
if(!str)
return NULL;
len = strlen(str);
ret = (char *)malloc(sizeof(len + 1));
if(!ret)
return NULL;
memcpy(ret, str, len);
ret[len] = '0';
return ret;
}
/*插入數據到hash表中*/
int insertEntry(table *t, const char *key, const char *value)
{
int index, vlen1, vlen2;
entry *e, *ep;
if(t == NULL || key == NULL || value == NULL)
return -1;
index = keyToIndex(key);
if(!t->bucket[index].key)
{
t->bucket[index].key = strDup(key);
t->bucket[index].value = strDup(value);
}
else
{
e = ep = &(t->bucket[index]);
/*先從已經存在的找*/
while(e)
{
/*找到key所在的位置，替換相應的值*/
if(strcmp(e->key, key) == 0)
{
vlen1 = strlen(value);
vlen2 = strlen(e->value);
if(vlen1 > vlen2)
{
free(e->value);
e->value = (char *)malloc(sizeof(vlen1 + 1));
}
memcpy(e->value, value, vlen1 + 1);
return index;/*插入完成*/
}
ep = e;
e = e->next;
}
/*沒有在當前桶中找到，創建條目加入*/
e = (entry *)malloc(sizeof(entry));
e->key = strDup(key);
e->value = strDup(value);
e->next = NULL;
ep->next = NULL;
}
return index;
}
/*找到哈希表中key對應的entry，找到之后返回對應的entry，并將其刪除*/
/*沒找到返回NULL*/
entry *removeEntry(table *t, char *key)
{
int index;
entry *e, *ep;
if(!t || !key)
return NULL;
index = keyToIndex(key);
e = &(t->bucket[index]);
while(e)
{
if(strcmp(e->key, key) == 0)/*如果是桶的第一個*/
{
if(e == &(t->bucket[index]))
{
ep = e->next;
if(ep)
{
entry *tmp = e;
e = ep;
ep = tmp;
ep->next = NULL;
}
else/*這個桶只有一個元素*/
{
//ep = (entry*)malloc(sizeof(entry));
ep = e;
e->key = e->value = NULL;
e->next = NULL;
}
return ep;
}
}
else/*如果不是木桶第一個元素*/
{
//找到它的前一個
ep = t->bucket[index].next;
while((ep->key != key) && ep)
{
ep = ep->next;
}
if(!ep)
return NULL;
return ep;
}
e = e->next;
}
return NULL;
}
/*打印hash表*/
void printTable(table *t)
{
int i;
entry *e;
if(!t)
return;
for(i = 0; i < BUCKETCOUNT; i++)
{
printf("nbucket[%d]:n", i);
e = &(t->bucket[i]);
while(e)
{
printf("t%st = t%sn",e->key, e->value);
e = e->next;
}
}
}
/*釋放哈希表*/
void freeHashTable(table* t)
{
int i;
entry* e,*ep;
if (t == NULL)return;
for (i = 0; i<BUCKETCOUNT; ++i) {
e = &(t->bucket[i]);
while (e->next != NULL) {
ep = e->next;
e->next = ep->next;
free(ep->key);
free(ep->value);
free(ep);
}
}
}
int main(void)
{
table t;
initHashTable(&t);
insertEntry(&t , "電腦型號" , "華碩 X550JK 筆記本電腦");
insertEntry(&t , "操作系統" , "Windows 8.1 64位 (DirectX 11)");
insertEntry(&t , "處理器" , "英特爾 Core i7 - 4710HQ @ 2.50GHz 四核");
insertEntry(&t , "主板" , "華碩 X550JK(英特爾 Haswell)");
insertEntry(&t , "內存" , "4 GB(Hynix / Hyundai)");
insertEntry(&t , "主硬盤" , "日立 HGST HTS541010A9E680(1 TB / 5400 轉 / 分)");
insertEntry(&t , "顯卡" , "NVIDIA GeForce GTX 850M (2 GB / 華碩)");
insertEntry(&t , "顯示器" , "奇美 CMN15C4(15.3 英寸)");
insertEntry(&t , "光驅" , "松下 DVD - RAM UJ8E2 S DVD刻錄機");
insertEntry(&t , "聲卡" , "Conexant SmartAudio HD @ 英特爾 Lynx Point 高保真音頻");
insertEntry(&t , "網卡" , "瑞昱 RTL8168 / 8111 / 8112 Gigabit Ethernet Controller / 華碩");
insertEntry(&t , "主板型號" , "華碩 X550JK");
insertEntry(&t , "芯片組" , "英特爾 Haswell");
insertEntry(&t , "BIOS" , "X550JK.301");
insertEntry(&t , "制造日期" , "06 / 26 / 2014");
insertEntry(&t , "主人" , "就是我");
insertEntry(&t , "價格" , "六十張紅色毛主席");
insertEntry(&t , "主硬盤" , "換了個120G的固態");
entry *e = removeEntry(&t, "主板型號");
if(!e)
{
printf("不存在相關記錄.n");
}
else
{
puts("釋放記錄結點的內存.");
free(e->key);
free(e->value);
free(e);
e = NULL;
}
printTable(&t);
freeHashTable(&t);
getchar();
return 0;
}
總結
以上是生活随笔為你收集整理的哈希桶 entry_哈希表代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 浦发腾讯动漫联名信用卡申请条件
- 下一篇： SharePoint 2016文档库所在