ハッシュ・テーブル(ハッシュを開く)
8553 ワード
HashOpen.h
#pragma once
#include
size_t HashMaxSize=1000;
typedef int KeyType;
typedef int ValType;
typedef size_t (*HashFunc)(KeyType key);
typedef struct HashElem
{
KeyType key;
ValType value;
struct HashElem* next;
} HashElem;
//
// , NULL
typedef struct HashTable
{
HashElem** data;
size_t size;
HashFunc hash_func;
} HashTable;
void HashInit(HashTable* ht, HashFunc hash_func);
// key .
int HashInsert(HashTable* ht, KeyType key, ValType value);
int HashFind(HashTable* ht, KeyType key, ValType* value);
void HashRemove(HashTable* ht, KeyType key);
size_t HashSize(HashTable* ht);
int HashEmpty(HashTable* ht);
void HashDestroy(HashTable* ht); #include
#include
#include"HashOpen.h"
#define TEST_HEADER printf("
==================%s==================
",__FUNCTION__)
size_t Hashfunc(KeyType Key)
{
return Key / 10;
}
HashElem* CreateNode(KeyType key, ValType value)
{
HashElem* tmp= (HashElem*)malloc(sizeof(HashElem));
tmp->key=key;
tmp->value=value;
tmp->next=NULL;
return tmp;
}
void DestroyNode(HashElem** elem)
{
free(*elem);
*elem=NULL;
}
void HashInit(HashTable* ht, HashFunc hash_func)
{
if(ht==NULL)
{
return;
}
ht->data=(HashElem**)malloc(sizeof(HashElem*) * HashMaxSize);
size_t i;
for(i=0;idata[i]=NULL;
}
ht->size=0;
ht->hash_func=hash_func;
}
void HashExpansion(HashTable *ht)
{
int i;
size_t tmp= HashMaxSize;
HashMaxSize = HashMaxSize* 2 +1;
HashElem** old_data=ht->data;
ht->data=(HashElem**)malloc(sizeof(HashElem*)* HashMaxSize);
ht->size=0;
for(i=0;i< (int)HashMaxSize;i++)
{
ht->data[i]=NULL;
}
for(i=0;ikey, cur->value);
cur=cur->next;
}
}
else
{
continue;
}
}
}
// key .
int HashInsert(HashTable* ht, KeyType key, ValType value)
{
if(ht==NULL)
{
return -1;
}
if( (ht->size) >=(10*HashMaxSize))
{
HashExpansion(ht);
}
size_t ret = ht->hash_func(key);
if(ht->data[ret]!=NULL)
{
HashElem* to_insert= ht->data[ret];
while(to_insert->next!=NULL)
{
to_insert=to_insert->next;
}
to_insert->next=CreateNode(key,value);
}
else
{
ht->data[ret]=CreateNode(key, value);
}
++ht->size;
return 0;
}
int HashFind(HashTable* ht, KeyType key, ValType* value)
{
if(ht==NULL)
{
return -1;
}
size_t ret=ht->hash_func(key);
if(ht->data[ret]==NULL)
{
//
return 1;
}
else
{
HashElem* cur = ht->data[ret];
while(cur!=NULL)
{
if(cur->key==key)
{
*value=cur->value;
return 0;
}
cur=cur->next;
}
return 1;
}
}
void HashRemove(HashTable* ht, KeyType key)
{
if(ht==NULL)
{
return;
}
size_t ret = ht->hash_func(key);
if(ht->data[ret]==NULL)
{
return;
}
else
{
if(ht->data[ret]->key==key)
{
HashElem* to_delete=ht->data[ret];
ht->data[ret]=to_delete->next;
DestroyNode(&to_delete);
--ht->size;
return;
}
HashElem* pre=ht->data[ret];
HashElem* cur = pre->next;
while(cur!=NULL)
{
if(cur->key==key)
{
pre->next=cur->next;
DestroyNode(&cur);
--ht->size;
return;
}
pre=cur;
cur=cur->next;
}
}
}
size_t HashSize(HashTable* ht)
{
return ht->size;
}
int HashEmpty(HashTable* ht)
{
if(ht==NULL)
{
return -1;
}
if(ht->size==0)
{
return 0;
}
else
{
return 1;
}
}
void HashDestroy(HashTable* ht)
{
if(ht==NULL)
{
return;
}
size_t i;
for(i=0;idata[i]!=NULL)
{
HashElem* to_delete=ht->data[i];
ht->data[i]=NULL;
HashElem* after = to_delete->next;
while(to_delete!=NULL)
{
free(to_delete);
--ht->size;
to_delete=after;
if(after!=NULL)
{
after=after->next;
}
}
}
}
}
void ShowLinkedList(HashElem* elem)
{
while(elem!=NULL)
{
printf("key-value:%5d-%5d
",elem->key,elem->value);
elem=elem->next;
}
}
void ShowHashTable(HashTable* ht, char* str)
{
printf("
------------%s------------
",str);
printf(" HashTable
");
printf("data: %10p
",ht->data);
printf("size: %10lu
", ht->size);
printf("func: %10p
", ht->hash_func);
}
void TestInit()
{
TEST_HEADER;
HashTable ht;
HashInit(&ht,Hashfunc);
ShowHashTable(&ht, (char*)"init");
}
void TestInsert()
{
TEST_HEADER;
HashTable ht;
HashInit(&ht,Hashfunc);
ShowHashTable(&ht,(char*)"before insert 15000 elemt");
size_t i;
for(i=0; i<15000;i++)
{
HashInsert(&ht,i,i*4);
}
ShowHashTable(&ht,(char*)"after insert 15000 elemt");
ShowLinkedList(ht.data[3]);
}
void TestFind()
{
TEST_HEADER;
HashTable ht;
HashInit(&ht,Hashfunc);
size_t i;
for(i=0; i<15000;i++)
{
HashInsert(&ht,i,i*4);
}
ValType value;
int ret= HashFind(&ht,10034,&value);
printf("ret:%d key-value:%5d-%5d
",ret, 10034, value);
}
void TestRemove()
{
TEST_HEADER;
HashTable ht;
HashInit(&ht,Hashfunc);
size_t i;
for(i=0; i<15000;i++)
{
HashInsert(&ht,i,i*4);
}
for(i=0;i<15000;i++)
{
HashRemove(&ht,i);
}
ShowHashTable(&ht, (char*)"After remove");
}
void TestDestroy()
{
TEST_HEADER;
HashTable ht;
HashInit(&ht,Hashfunc);
size_t i;
for(i=0; i<15000;i++)
{
HashInsert(&ht,i,i*4);
}
HashDestroy(&ht);
ShowHashTable(&ht, (char*)"After destroy");
}
int main()
{
TestInit();
TestInsert();
TestFind();
TestRemove();
TestDestroy();
return 0;
} HashOpen:HashOpen.c
gcc -o $@ $^[abc123@localhost hash_open]$ ./HashOpen
==================TestInit==================
------------init------------
HashTable
data: 0x183c010
size: 0
func: 0x400610
==================TestInsert==================
------------before insert 15000 elemt------------
HashTable
data: 0x183df60
size: 0
func: 0x400610
------------after insert 15000 elemt------------
HashTable
data: 0x188e0b0
size: 15000
func: 0x400610
key-value: 30- 120
key-value: 31- 124
key-value: 32- 128
key-value: 33- 132
key-value: 34- 136
key-value: 35- 140
key-value: 36- 144
key-value: 37- 148
key-value: 38- 152
key-value: 39- 156
==================TestFind==================
ret:0 key-value:10034-40136
==================TestRemove==================
------------After remove------------
HashTable
data: 0x19803d0
size: 0
func: 0x400610
==================TestDestroy==================
------------After destroy------------
HashTable
data: 0x1984260
size: 0
func: 0x400610