hash table implementations in C Language

Applications Programming
1

Hello List,

Iam searching for a solution where i can use hash based searching .

In Detail , I have linked list which will be dynamically increasing .

I need a best searching mechanisim such a way that it can take only one itereation .

Right now iam using linear search which is taking n-1 iteriations if we have n nodes in it.

I cannot use binary search as i cannot arrange them in order because the node contains string variables.

Please advice me

regards
Kanth

2

hashit is a good, generic hash table implimentation in C that supports open addressing, chaining, or blocking. It's under the GPLv2 licence.

3

Why can you not sort string variables?

see:

for libjudy which will create associative arrays - which is what you probably should consider.

4

glib is probably a more "standard" choice for hash table, especially if you are on Linux or BSD as you probably already has it installed.

5

thanks for your suggestions,

iam trying to use glib hashtables.

here my problem is i could not able to compile a program which has glib.h as the include one.

#include <stdio.h>
#include <glib.h>

int main(){

        printf ( "Hello");
        return 0;
}

gcc -I/usr/include/glib-2.0 -g glibtest.c -o glibtest.o

In file included from /usr/include/glib-2.0/glib/galloca.h:30,
from /usr/include/glib-2.0/glib.h:30,
from glibtest.c:2:
/usr/include/glib-2.0/glib/gtypes.h:30:24: glibconfig.h: No such file or directory
In file included from /usr/include/glib-2.0/glib/galloca.h:30,
from /usr/include/glib-2.0/glib.h:30,
from glibtest.c:2:

.
.
.
.
.
.

can any body advise my how to use glib

thanks

6

glibconfig.h is in /usr/lib/glib-2.0/include

gcc -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -g glibtest.c -o glibtest.o
7

thanks vino veritas it indeed worked

8

Hello vino ,

i have the program

# cat glibtest.c

#include <stdio.h>
#include <glib.h>

int main(){

        GHashTable *hash = g_hash_table_new(g_int_hash, g_int_equal);
        g_hash_table_insert(hash,"Virginia","Richmond");

        printf(" %s ",g_hash_table_lookup(hash,"Virginia"));
        gboolean found = g_hash_table_remove(hash,"Virginia");
        printf("The Value 'virginia' was %s found and removed \n",found ? "":"not");
        g_hash_table_destory(hash);

        return 0;
}

the compilation problems are

# gcc -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -g glibtest.c -o glibtest.o
/tmp/ccElT30B.o(.text+0x20): In function `main':
/home/ramakanth/cprogs/hashprogs/glibtest.c:6: undefined reference to `g_int_equal'
/tmp/ccElT30B.o(.text+0x25):/home/ramakanth/cprogs/hashprogs/glibtest.c:6: undefined reference to `g_int_hash'
/tmp/ccElT30B.o(.text+0x2a):/home/ramakanth/cprogs/hashprogs/glibtest.c:6: undefined reference to `g_hash_table_new'
/tmp/ccElT30B.o(.text+0x45):/home/ramakanth/cprogs/hashprogs/glibtest.c:7: undefined reference to `g_hash_table_insert'
/tmp/ccElT30B.o(.text+0x58):/home/ramakanth/cprogs/hashprogs/glibtest.c:9: undefined reference to `g_hash_table_lookup'
/tmp/ccElT30B.o(.text+0x79):/home/ramakanth/cprogs/hashprogs/glibtest.c:10: undefined reference to `g_hash_table_remove'
/tmp/ccElT30B.o(.text+0xb3):/home/ramakanth/cprogs/hashprogs/glibtest.c:12: undefined reference to `g_hash_table_destory'
collect2: ld returned 1 exit status

I think still iam missing some libraires ..

please advise me

thanks

9

Try adding the libglib-2.0 library.

gcc -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -g glibtest.c -o glibtest.o -lglib-2.0
10

The glib-config utility can make this a lot simpler.

$ glib-config --cflags
-I/usr/include/glib-1.2 -I/usr/lib/glib/include
$ glib-config --libs
-L/usr/lib -lglib
$

So your compile line could be simplified to

gcc `glib-config --cflags` -g glibtest.c -o glibtest `glib-config --libs`

...and would continue to work on systems where glib was a different version and/or installed in a different location.

11

freshmeat has this hashtable lib:

12

lists a hashtable library in C with ref counting: