Hashmap eli hajautustaulu on tietorakenne, jossa voi säilöä avain-arvo pareja. Tietojen käsittely (insert,delete,search) tapahtuu keskimäärin vakioajassa. Hashmap on monelle tuttu muista kielistä (esim. java) jossa se on valmiina. Seuraava toteutus ei ole mikään parhaimmasta päästä. Hashmapille ei ole toteutettu uudelleenhajautusta ja taulun koon kasvattamista/pienentämistä, mutta nämä ovat helppo toteuttaa tarpeenvaatiessa. Oheinen rakenne koostuu taulukosta, jonka alkioina on yhteen suuntaan linkitettyjä järjestettyjä listoja. Kun rakenne määritellään, sille tulee kertoa hajautusfunktio sekä vertailufunktio. Myös tulostusfunktion voi ilmoittaa jos haluaa tulostaa koko hajautustaulun (ei järkevää isoissa datamäärissä).
// hashmap.h ------------------------------
/* Tyyppi ja tietuemäärittelyt sekä funktioiden esittelyt */
#ifndef hashmap_ordered_single_linked_list
#define hashmap_ordered_single_linked_list
//tyyppimäärittelyt hajautus-, vertailu- ja tulostusfunktioille
typedef int(*hashfunction)(void*);
typedef int(*comparefunction)(void*,void*);
typedef void(*printfunction)(void*,void*);
//linkitetyn listan alkio
typedef struct llnode_{
void *key;
void *value;
struct llnode_ *next;
}llnode;
//linkitetty (tunnussolmullinen) lista
typedef struct{
llnode *first;
}llist;
//hajautustaulu. sisältää hajautus-, vertailu- ja tulostusfunktiot (niiden ositteet)
typedef struct{
llist **table; //taulukko, jonka alkioina linkitettyjä lisjota
int size; //taulukon koko. ei voida muuttaa jälkeenpäin!
hashfunction func;
comparefunction comparator;
printfunction printer;
}hashmap;
//funktioiden esittelyt
hashmap *NewHashmap(int size,comparefunction comparator,hashfunction func,printfunction printer);
llnode *HashmapPut(hashmap *map, void *key,void *value);
llnode *HashmapDeleteKey(hashmap *map,void *key);
void *HashmapSearchKey(hashmap *map,void *key);
llist *NewLlist(void);
llnode *NewLlNode(void *key,void *value);
void *SearchLlistKey(llist *list,void *key,comparefunction comparator);
llnode *InsertLlistKey(llist *list,void *key,void *value,comparefunction comparator);
llnode *DeleteLlistKey(llist *list,void *key,comparefunction comparator);
llnode *DeleteLlistNode(llist *list,llnode *node);
int Hash1(void *key);
void PrintHashmap(hashmap *map);
void PrintLlist(printfunction printer,llist *list);
void PrintString(void *key,void *value);
#endif// hashmap.c ---------------------------------------------
/* Sisältää funktiot hashmapin käsittelyyn */
#include <stdlib.h>
#include <stdio.h>
#include "hashmap.h"
//luo uuden hajautustaulun annettujen parametrien mukaan
hashmap *NewHashmap(int size,comparefunction comparator,hashfunction func,printfunction printer){
hashmap *hm=(hashmap*)malloc(sizeof(hashmap));
hm->size=size;
hm->comparator=comparator;
hm->func=func;
hm->printer=printer;
hm->table=(llist**)malloc(sizeof(llist*)*size);
for(int i=0;i<size;i++)
hm->table[i]=NewLlist();
return hm;
}
//lisää annetun avain-arvo parin tauluun
llnode *HashmapPut(hashmap *map,void *key,void *value){
return InsertLlistKey(map->table[map->func(key)%map->size],key,value,map->comparator);
}
//poistaa taulusta annetun avaimen
llnode *HashmapDeleteKey(hashmap *map,void *key){
return DeleteLlistKey(map->table[map->func(key)%map->size],key,map->comparator);
}
//palauttaa haettua avainta vastaavan arvon
void *HashmapSearchKey(hashmap *map,void *key){
return SearchLlistKey(map->table[map->func(key)%map->size],key,map->comparator);
}
void PrintHashmap(hashmap *map){
for(int i=0;i< map->size;i++){
printf("%d:\n",i);
PrintLlist(map->printer,map->table[i]);
}
}// llist.c ----------------------------------------------
/* Sisältää linkitettyihin listoihin liittyvät funktiot */
#include <stdlib.h>
#include <stdio.h>
#include "hashmap.h"
//palauttaa uuden (tyhjän, tunnussolmullisen) listan
llist *NewLlist(void){
llist *list=(llist*)malloc(sizeof(llist));
list->first=NULL;
return list;
}
//palauttaa uuden key-value sisältöisen linkitetyn listan solmun
llnode *NewLlNode(void *key,void *value){
llnode *node=(llnode*)malloc(sizeof(llist));
node->key=key;
node->value=value;
node->next=NULL;
return node;
}
//palauttaa avainta vastaavan arvon kyseisestä listasta
void *SearchLlistKey(llist *list,void *key,comparefunction comparator){
llnode *node;
for(node=list->first;node!=NULL&&comparator(node->key,key);node=node->next);
if(node!=NULL)
return node->value;
return NULL;
}
/* lisää avain-arvo parin (järjestettyyn) listaan. Tämän funktion olisi varmaankin voinut toteuttaa paremmin!*/
llnode *InsertLlistKey(llist *list,void *key,void *value,comparefunction comparator){
llnode *node=NewLlNode(key,value);
llnode *pre=list->first;
llnode *post;
int result;
if(pre==NULL){
list->first=node;
return node;
}
if(comparator(node->key,pre->key)<0){
node->next=pre;
list->first=node;
return node;
}
if(comparator(node->key,pre->key)==0){
DeleteLlistNode(list,pre);
node->next=list->first;
list->first=node;
return node;
}
post=pre->next;
while(post!=NULL&&(result=comparator(node->key,post->key))>0){
pre=pre->next;
post=pre->next;
}
if(result==0)
DeleteLlistNode(list,post);
node->next=pre->next;
pre->next=node;
return node;
}
//Poistaa listasta annettua avainta vastaavan solmun
llnode *DeleteLlistKey(llist *list,void *key,comparefunction comparator){
llnode *node;
for(node=list->first;node!=NULL&&comparator(node->key,key);node=node->next);
if(node!=NULL)
DeleteLlistNode(list,node);
return node;
}
//poistaa listasta annetun solmun
llnode *DeleteLlistNode(llist *list,llnode *node){
llnode *pre;
if(list->first==node){
list->first=node->next;
return node;
}
for(pre=list->first;pre->next!=NULL&&pre->next!=node;pre=pre->next);
if(pre->next!=NULL){
pre->next=pre->next->next;
return node;
}
return NULL;
}
//tulostaa listan
void PrintLlist(printfunction printer,llist *list){
llnode *node;
for(node=list->first;node!=NULL;node=node->next)
printer(node->key,node->value);
}//------------------------------------------------------
/* Esimerkki käytöstä */
// main.c ----------------------------------------------
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "hashmap.h"
/* "wrapper" funktio standardikirjaston strcmp funktiosta. ideana vain se,
että comparefunktio on hashmap.h tiedostossa määritelty ottavan vastaan
void* tyyppisiä parametrejä mutta strcmp ottaa const char* tyyppiä.
ohjelmaa voisi käyttää suoraan strcmp:llä, mutta tämä aiheuttaa kääntäjältä varoituksen.*/
int CompareStrings(void *a,void *b);
//ei kovin hyvä hajautusfunktio merkkijonoille, mutta kelpaa esimerkiksi.
int Hash1(void *key);
//tulostaa parametrinsa (käsittelee niitä char* muodossa)
void PrintString(void *key,void *value);
int main(int argc,char *argv[]){
hashmap *map=NewHashmap(5,CompareStrings,Hash1,PrintString);
HashmapPut(map,"Mikko Musta","Afrikka");
HashmapPut(map,"Mikki Hiiri","Ankkalinna");
HashmapPut(map,"Barak Obama","Washington");
HashmapPut(map,"Pummi","Slummi");
HashmapDeleteKey(map,"Pummi");
HashmapDeleteKey(map,"asd");
HashmapPut(map,"Kori Anteri","Maustekaappi");
printf("%s\n",(char*)HashmapSearchKey(map,"Mikko Musta"));
PrintHashmap(map);
return 0;
}
int Hash1(void *key){
char *data=(char*)key;
int value=0;
for(int i=0;data[i]!='\0';i++)
value+=i*11*(int)data[i];
return value;
}
int CompareStrings(void *a,void *b){
return strcmp((char*)a,(char*)b);
}
void PrintString(void *key,void *value){
printf("%s:\t%s\n",(char*)key,(char*)value);
}käännös esim. komennolla: gcc hashmap.c llist.c main.c -std=c99 -o hmt
Ohjelma tulostaa seuraavaa:
[aba@random hashmap]$ ./hmt
Afrikka
0:
1:
Barak Obama: Washington
2:
3:
Kori Anteri: Maustekaappi
Mikki Hiiri: Ankkalinna
4:
Mikko Musta: Afrikka
Koodiin tarvitaan lisää selitystä siitä, mitä tapahtuu ja miksi. Hyviä hajautustauluja on netissä jo monta, joten vinkin julkaisussa ei ole järkeä, jos siinä ei edes opeteta asioita perusteellisesti suomeksi.
Koodissasi ei missään vapauteta muistia. Tämä on ehdottomasti korjattava.
Linkitetty lista on epäselvästi toteutettu. Ylipäänsä llist-rakenne on turha; voisi vain suoraan olla ensimmäinen llnode. Listan pitäminen järjestyksessä ei ole kovin olennaista, mutta jos haluat pitää, toteuta se sitten edes selvästi ja hyvin. Lisäksi kahden saman esto olisi parempi toteuttaa hajautustaulun puolella eikä linkitetyssä listassa, tai sitten listan nimeä pitää muuttaa.
Lisäksi voisit siistiä koodia, esim. nimetä loogisesti (nyt on välillä Ll ja välillä Llist), käyttää järkevästi välejä (erityisesti näkyy pitkissä rimpsuissa kuten ”for(pre=list->first;pre->next!=NULL&&pre->next!=node;pre=pre->next)”) ja käyttää sisennykseen yhtenäisesti joko välejä tai tabulaattoria.
Ehkä näistä pääset alkuun korjauksissa.
Aihe on jo aika vanha, joten et voi enää vastata siihen.